[figure]

Representações para Planos

Soluções:

• uma solução é um plano que um agente possa executar, e que garanta chegar ao objetivo.

• para garantir que um plano é uma solução, basta garantir que o plano é totalmente ordenado e instanciado.

• na prática, não razoável usar esta abordagem.

– 1) mais natural gerar um plano de ordem parcial (mais geral).

– 2) alguns agentes podem executar em paralelo.

– 3) mais flexível para combinar com outros planos.

Representações para Planos

• Solução deve ser consistente e completa.

• Um plano é completo se toda pré-condição de cada passo for satisfeita por algum outro passo.

• mais formalmente: um passo S_{i} atinge uma pré-condição c do passo S_{j} se:

– 1) S_{i} ≺ S_{j} e c ∈ EF EIT OS(S_{i})

– 2) não há nenhum passo S_{k} tal que (¬c) ∈ EF EIT OS(S_{k}), onde S_{i} ≺ S_{k} ≺ S_{j} em alguma linearização do plano.

Representações para Planos

• Um plano é consistente se não tiver contradições na ordem ou valores das restrições.

• Contradição ocorre quando S_{i} ≺ S_{j} aparece ao mesmo tempo que S_{j} ≺ S_{i} no plano gerado ou quando v = A e v = B.

• Como ≺ e = são operadores relacionais com propriedade transitiva, teremos contradição se S_{1} ≺ S_{2}, S_{2} ≺ S_{3}, e S_{3} ≺ S_{1}.

[figure]

Exemplo de Planning com Ordem Parcial • Planner regressivo usando ordenação parcial, e buscando

soluções no espaço de planos.

• Começa com um plano inicial representado pelos passos inicial e final.

• Adiciona passos a cada iteração.

• Se o passo for inconsistente, retrocede (backtracks) e tenta outro ramo no espaço de busca.

• Para manter a busca guiada, o planner somente considera adicionar passos cuja pré-condição ainda não tenha sido alcançada (links causais são utilizados neste caso).

Exemplo de Planning com Ordem Parcial

• Ex: Op(ACAO : Inicia, EF EIT O :

Em(Casa) ∧ V ende(HW S, Lanterna) ∧ V ende(SM, Leite), V ende(SM, Macas))

• Op(ACAO : T ermina, P RECOND :

T em(Lanterna) ∧ T em(Leite) ∧ T em(Macas) ∧ Em(Casa))

• Op(ACAO : V a(la), P RECOND : Em(aqui), EF EIT O : Em(la) ∧ ¬Em(aqui))

• Op(ACAO : Comprar(x), P RECOND :

Em(loja) ∧ V ende(loja, x), EF EIT O : T em(x)

Exemplo de Planning com Ordem Parcial • Várias maneiras de gerar planos para este problema.

• Algumas levam a caminhos que não são soluções.

• Planner escolhe comprar somente aquelas coisas que interessam, dos lugares que interessam, sem gastar muito tempo.

• Links protegidos, um link causal é protegido garantindo que ’ameaças’, isto é, passos que poderiam ’deletar’ uma condição protegida, são ordenadas de forma a aparecer antes ou depois do link protegido: demotion ou promotion.

Exemplo de Planning com Ordem Parcial Exemplo de Planning com Ordem Parcial