INF 1771 Inteligência Artificial  
Aula 10 Planejamento  
Edirlei Soares de Lima  
<elima@inf.puc-rio.br>  
Agentes Vistos Anteriormente  
Agentes Baseados em Busca.  
Busca cega;  
Busca heurística;  
Busca local;  
Agentes Lógicos.  
Lógica proposicional;  
Lógica de primeira ordem;  
Prolog;  
Planejamento  
Planejamento consiste na tarefa de apresentar uma  
sequência de ações para alcançar um determinado objetivo.  
Ir(Mercado), Comprar(Biscoito), Ir(Farmácia), Comprar(Remédio), Ir(Casa)  
Dado um objetivo, um agente planejador deve ser capaz de  
construir um plano de ação para chegar ao seu objetivo.  
Após planejar, o agente deve executar as ações do plano uma  
a uma.  
Funcionamento de um Agente Planejador  
Inicialmente um agente planejador gera um objetivo a  
alcançar.  
Constrói um plano para atingir o objetivo a partir do estado  
atual do ambiente.  
Executa o plano do começo ao fim.  
Gera um novo objetivo com base no novo estado do  
ambiente.  
Planejamento  
Em planejamento clássico o ambiente do problema  
possui as seguintes características:  
Observável  
Determinístico  
Finito  
Estático  
Resolução de Problemas X Planejamento  
Algoritmos de busca tendem a tomar ações  
irrelevantes.  
Grande fator de ramificação.  
Pouco conhecimento para guiar a busca.  
Planejador não considera ações irrelevantes.  
Faz conexões diretas entre estados (sentenças) e ações  
pré-condições + efeitos)  
Objetivo: Ter(Leite).  
(
Ação: Comprar(Leite) => Ter(Leite)  
Resolução de Problemas X Planejamento  
Em problemas do mundo real é difícil definir uma  
boa heurística para algoritmos de busca heurística.  
Um planejador tem acesso a representação explícita  
do objetivo.  
Objetivo: conjunção de sub-objetivos que levam ao  
objetivo final.  
Heurística única: número de elementos da conjunção não-  
satisfeitos.  
Resolução de Problemas X Planejamento  
Algoritmos de busca não tiram proveito da  
decomposição do problema.  
Planejadores aproveitam a estrutura do problema. É  
possível decompor com facilidade sub-objetivos.  
Exemplo: Ter(A) Λ Ter(B) Λ Ter(C) Λ Ter(D)  
Linguagem STRIPS  
Linguagem formal para a especificação de problemas de  
planejamento.  
Representação de estados: conjunção de literais positivos  
sem variáveis.  
Inicial: Em(Casa)  
Final: Em(Casa) ^ Ter(Leite) ^ Ter(Bananas) ^ Ter(Furadeira)  
Hipótese do mundo fechado: qualquer condição não mencionada em  
um estado é considerada negativa.  
Exemplo: ¬Ter(Leite) ^ ¬Ter(Bananas) ^ ¬Ter(Furadeira)  
Linguagem STRIPS  
Objetivos: conjunção de literais e possivelmente variáveis:  
Em(Casa) ^ Ter(Leite) ^ Ter(Bananas) ^ Ter(Furadeira)  
Em(x) ^ Vende(x, Leite)  
Ações são especificadas em termos de pré-condições e  
efeitos:  
Descritor da ação: predicado lógico  
Pré-condição: conjunção de literais positivos  
Efeito: conjunção de literais (positivos ou negativos)  
Linguagem STRIPS  
Operador para ir de um lugar para outro:  
Ação(Ir(Destino),  
Pré-condição Em(Partida) ^ Caminho(Partida, Destino),  
Efeito Em(Destino) ^ ¬ Em(Partida))  
Exemplo Transporte Aéreo de Carga  
Início(Em(C1, SFO) ^ Em(C2,JFK) ^ Em(A1,SFO) ^ Em(A2,JFK) ^ Carga(C1)  
^
Carga(C2) ^ Avião(A1) ^ Avião(A2) ^ Aeroporto(JFK) ^ Aeroporto(SFO))  
Objetivo(Em(C1,JFK) ^ Em(C2,SFO))  
Ação(Carregar(c,a,l)  
PRÉ-CONDIÇÃO: Em(c,l) ^ Em(a,l) ^ Carga(c) ^ Avião(a) ^ Aeroporto(l)  
EFEITO: ¬Em(c,l) ^ Dentro(c,a))  
Ação(Descarregar(c,a,l)  
PRÉ-CONDIÇÃO: Dentro(c,a) ^ Em(a,l) ^ Carga(c) ^ Avião(a) ^ Aeroporto(l)  
EFEITO: Em(c,l) ^ ¬Dentro(c,a))  
Ação(Voar(a,de,para)  
PRÉ-CONDIÇÃO: Em(a,de) ^ Avião(a) ^ Aeroporto(de) ^ Aeroporto(para)  
EFEITO: ¬ Em(a,de) ^ Em(a,para))  
Exemplo Doca Automatizada  
Exemplo de Estado:  
Exemplo Doca Automatizada  
Exemplo Doca Automatizada  
Exemplo - Mundo dos Blocos  
Mesa infinitamente larga, número finito de blocos;  
Ignora a posição em que um bloco está sobre a mesa;  
Um bloco pode estar sobre a mesa ou sobre um outro bloco;  
Os blocos devem ser movidos de uma configuração para outra;  
a
d
b
c
c
e
a b  
Estado Inicial  
Estado Objetivo  
Exemplo - Mundo dos Blocos  
Símbolos constantes:  
d
Os blocos: a, b, c, d, e  
c
e
a b  
Predicados:  
ontable(x)  
on(x,y)  
- bloco x está sobre a mesa  
- bloco x está sobre o bloco y  
clear(x)  
- bloco x não tem nada sobre ele  
holding(x)  
handempty  
- a garra do robô está segurando o bloco x  
- a garra do robô não está segurando nada  
Exemplo - Mundo dos Blocos  
Operadores:  
unstack(x,y)  
c
a b  
Precond: on(x,y), clear(x), handempty  
Effects: ~on(x,y), ~clear(x), ~handempty,  
holding(x), clear(y)  
c
a b  
stack(x,y)  
Precond: holding(x), clear(y)  
Effects: ~holding(x), ~clear(y),  
on(x,y), clear(x), handempty  
c
a b  
pickup(x)  
Precond: ontable(x), clear(x), handempty  
Effects: ~ontable(x), ~clear(x),  
~handempty, holding(x)  
c
b
a
putdown(x)  
Precond: holding(x)  
Effects: ~holding(x), ontable(x),  
clear(x), handempty  
c
a b  
Tipos de Planejadores  
Formas de Buscas de Planos:  
Progressivo: estado inicial -> objetivo.  
Regressivo: objetivo -> estado inicial.  
mais eficiente (há menos caminhos partindo do objetivo do que do estado  
inicial)  
Espaços de busca:  
Espaço de situações: Funciona da mesma forma que na resolução de  
problemas por meio de busca.  
Espaço de planos: planos parciais.  
mais flexível.  
Planejamento Progressivo  
take c3  
take c2  
move r1  
Planejamento Progressivo  
Algoritmos de busca clássicos:  
Busca em profundidade;  
Busca em largura;  
Busca de custo uniforme;  
Pode ter um fator de ramificação muito grande.  
Planejamento Regresivo  
g1  
a1  
a4  
g4  
g2  
g0  
a2  
a3  
s0  
a5  
g5  
g3  
Planejamento Regresivo  
a1  
a2  
a3  
a1  
a2  
a3  
a50  
Estado Objetivo  
Estado inicial  
O fator de ramificação da busca para trás é menor, mas  
existem casos onde pode ainda ser muito grande.  
Muitas instâncias de operadores são avaliadas.  
Planning Domain Definition Language (PDDL)  
Linguagem formal para a codificação de problemas  
de planejamento clássicos.  
Baseada no modelo STRIPS  
Possui varias versões com a incorporação de novas  
características.  
1.2 - Versão básica (Manual)  
2.1 - Funções e métricas (Manual)  
3.1 - Versão atual (Manual)  
Planning Domain Definition Language (PDDL)  
Componentes da linguagem PDDL:  
Objetos: objetos que compõem o problema de  
planejamento.  
Predicados: propriedades dos objetos podem ser  
verdadeiros ou falsos.  
Estado Inicial: estado do mundo onde o processo de  
planejamento se inicia.  
Objetivos: predicados que devem ser verdade para  
concluir o processo de planejamento.  
Ações/Operadores: ações que podem ser executadas e  
modificam o estado do mundo.  
PDDL - Exemplo  
“Existe um robô que pode se mover entre duas salas,  
pegar e soltar caixas com ambas as suas mãos.  
Inicialmente, o robô e 4 caixas estão na sala 1. O  
objetivo é que o robô leve as caixas para a sala 2.”  
PDDL Domain & Problem  
Tarefas de planejamento especificadas em PDDL são  
separadas em dois arquivos:  
Domain File: tipos, predicados e ações.  
Problem File: objetos, estado inicial e objetivos.  
PDDL - Domain File  
Sintaxe:  
(
define (domain <domain name>)  
(
(
(
<
<
[
<
:requirements :strips :equality :typing)  
:types <list of types>)  
:constants <list of constants>)  
PDDL code for predicates>  
PDDL code for first action>  
...]  
PDDL code for last action>  
)
PDDL Types & Constants  
Tipos: sala, caixa, braço  
PDDL:  
(
:types room box arm)  
Constantes objetos que podem ser usados no  
arquivos de domínio.  
PDDL:  
(
:constants left right - arm)  
PDDL - Predicates  
Predicados:  
robot-at(x) verdadeiro se o robô estiver na sala x  
box-at(x, y) verdadeiro se a caixa x estiver na sala y  
free(x) verdadeiro se o braço x não estiver segundando uma caixa  
carry(x, y) verdadeiro se o braço y estiver segurando a caixa x  
PDDL:  
(
:predicates  
(
(
(
(
robot-at ?x - room)  
box-at ?x - box ?y - room)  
free ?x - arm)  
carry ?x box ?y - arm)  
)
PDDL - Actions  
Descrição: O robô se move da sala x para a sala y.  
Precondição: robot-at(x) ser verdade.  
Efeito: robot-at(y) se torna verdade. robot-at(x) se torna  
falso.  
PDDL:  
(
:action move  
:
:
:
parameters (?x ?y - room)  
precondition (robot-at ?x)  
effect (and (robot-at ?y) (not (robot-at ?x)))  
)
PDDL - Domain File  
(define (domain robot)  
(
(
(
(
:requirements :strips :equality :typing)  
:types room box arm)  
:constants left right - arm)  
:predicates  
(
(
(
(
robot-at ?x - room)  
box-at ?x - box ?y - room)  
free ?x - arm)  
carry ?x - box ?y - arm)  
)
(
:action move  
:
:
:
parameters (?x ?y - room)  
precondition (robot-at ?x)  
effect (and (robot-at ?y) (not (robot-at ?x)))  
)
(
:action pickup  
:
:
:
parameters (?x - box ?y - arm ?w - room)  
precondition (and (free ?y) (robot-at ?w) (box-at ?x ?w))  
effect (and (carry ?x ?y) (not (box-at ?x ?w)) (not(free ?y)))  
)
(
:action putdown  
:
:
:
parameters (?x - box ?y -arm ?w - room)  
precondition (and (carry ?x ?y) (robot-at ?w))  
effect (and (not(carry ?x ?y)) (box-at ?x ?w) (free ?y))  
)
)
PDDL Problem File  
Sintaxe:  
(
define (problem <problem name>)  
(
<
<
<
:domain <domain name>)  
PDDL code for objects>  
PDDL code for initial state>  
PDDL code for goal specification>  
)
PDDL - Objects  
Objetos:  
Salas: room1, room2  
Caixas: box1, box2, box3, box4  
Braços: left, right  
PDDL:  
(
:objects  
room1 room2 - room  
box1 box2 box3 box4 - box  
left right - arm  
)
PDDL - Estado Inicial  
Estado Inicial: todas as caixas e robô estão na primeira  
sala.  
PDDL:  
(
:init  
(
(
(
(
(
(
(
robot-at room1)  
box-at box1 room1)  
box-at box2 room1)  
box-at box3 room1)  
box-at box4 room1)  
free left)  
free right)  
)
PDDL - Objetivo  
Objetivo: todas as caixas estão na segunda sala.  
PDDL:  
(
:goal  
(
and (box-at box1 room2)  
(
(
(
box-at box2 room2)  
box-at box3 room2)  
box-at box4 room2)  
)
)
PDDL Problem File  
(
(
define (problem robot1)  
:domain robot)  
(
:objects  
room1 room2 - room  
box1 box2 box3 box4 - box  
left right - arm  
)
(
:init  
(
(
(
(
(
(
(
robot-at room1)  
box-at box1 room1)  
box-at box2 room1)  
box-at box3 room1)  
box-at box4 room1)  
free left)  
free right)  
)
(
:goal  
(and  
(
(
(
(
box-at box1 room2)  
box-at box2 room2)  
box-at box3 room2)  
box-at box4 room2)  
)
)
)
Utilizando o Planejador  
Executar planejador:  
hsp.exe robot-problem.pddl robot-domain.pddl  
Parâmetros:  
Direção da busca: -d backward ou forward  
Algoritmo: -a bfs ou gbfs  
Busca em Espaço de Estados  
A busca em espaço de estados é ineficiente devido a ela não  
considerar o problema das ações irrelevantes. Todas as  
opções de ações são testadas em cada estado.  
Isso faz com que a complexidade do problema cresça muito  
rapidamente.  
Solução?  
Busca no espaço de planos parciais (planejamento de ordem parcial).  
Planejamento de Ordem Parcial  
Subdivisão do problema.  
Ordem de elaboração do plano flexível.  
Compromisso mínimo.  
Adiar decisões durante a procura.  
O planejador de ordem parcial pode inserir duas ações em um  
plano sem especificar qual delas deve ser executada primeiro.  
Exemplo dos Sapatos  
Inicio()  
Objetivo(SapatoDireitoCalçado^SapatoEsquerdoCalçado)  
Ação(SapatoDireito,  
PRECOND: MeiaDireitaCalçada,  
EFFECT: SapatoDireitoCalçado)  
Ação(MeiaDireita,  
EFFECT: MeiaDireitaCalçada)  
Ação(SapatoEsquerdo,  
PRECOND: MeiaEsquerdaCalçada,  
EFFECT: SapatoEsquerdoCalçado)  
Ação(MeiaEsquerda,  
EFFECT: MeiaEsquerdaCalçada)  
Exemplo dos Sapatos  
Um planejador de ordem parcial deve ser capaz de  
chegar a duas sequências de ações:  
MeiaDireita seguido por SapatoDireito;  
MeiaEsqueda seguido por SapatoEsquerdo.  
As duas sequências podem ser combinadas para  
produzir o plano final.  
Exemplo dos Sapatos  
Plano de Ordem Parcial  
Exemplo dos Sapatos  
Plano de Ordem Total  
Planejamento de Ordem Parcial  
O planejamento de ordem parcial pode ser implementado  
como uma busca no espaço de ordem parcial de planos.  
Ideia:  
Busca-se um plano desejado em vez de uma situação desejada (meta-  
busca).  
Parte-se de um plano inicial (parcial) e aplica-se as ações até chegar a  
um plano final (completo)  
Plano Final:  
Completo: todas as pré-condições de todas as ações são alcançada por  
meio de alguma outra ação.  
Consistente: não há contradições.  
Planejamento de Ordem Parcial  
Na estratégia de compromisso mínimo a ordem e  
instanciações totais são decididas quando  
necessário.  
Exemplo:  
Para objetivo Ter(Leite), a ação Comprar(Produto, Loja), instancia-se  
somente item: Comprar(Leite, Loja)  
Para o problema de colocar meias e sapatos: colocar cada meia antes  
do sapato, sem dizer por onde começar (esquerda ou direita)  
Planejamento de Ordem Parcial  
Algoritmo de planejamento de ordem parcial:  
Identifica-se um passo com a pré-condição (sub-goal) não  
satisfeita.  
Introduz-se um passo cujo efeito satisfaz a pré-condição.  
Instancia-se variáveis e atualiza-se as ligações causais.  
Verifica-se se há conflitos e corrige-se o plano se for o  
caso.  
Exemplo  
Plano Inicial:  
Ações:  
Op(ACTION: Go(there),  
PRECOND: At(here),  
EFFECT: At(there) ¬ At(here))  
Op(ACTION: Buy(x),  
PRECOND: At(store) Sells(store, x),  
EFFECT: Have(x))  
Exemplo  
Start  
Conflito At(Home)  
At(Home)  
At(Home)  
Go(HWS)  
Go(SM)  
At(HWS),  
Sells(HWS,Drill)  
At(SM), Sells(SM, Milk)  
At(SM), Sells(SM, Bananas)  
Buy(Drill)  
Buy(Milk)  
Buy(Bananas)  
Have(Drill),  
Have(Milk),  
Have(Bananas),  
At(Home)  
Finish  
Conflito em Planejamento de Ordem Parcial  
Um conflito ocorre quando os efeitos de uma ação põem em  
risco as pré-condições de outra ação.  
No caso anterior, os operadores Go(HWS) e Go(SM) apagam  
At(Home).  
Demotion e Promotion:  
Exemplo  
Start  
At(Home)  
Go(HWS)  
At(HWS)  
Resolve o conflito  
Go(SM)  
At(HWS), Sells(HWS,Drill)  
Buy(Drill)  
At(SM) Sells(SM,Milk)  
At(SM) Sells(SM,Ban.)  
At(SM)  
Buy(Milk)  
Buy(Ban.)  
Go(Home)  
Have(Drill)  
Have(Milk)  
Have(Ban.)  
At(Home)  
Finish  
Exemplo  
Plano de Ordem Parcial  
Planejamento Hierárquico  
Hierarchical Task Network (HTN) Planning  
Planejamento que busca refinar um plano com a decomposição hierárquica  
de operadores abstratos.  
Em planejamento HTN, o plano inicial que descreve o problema, é visto  
como uma descrição de alto nível do que deve ser feito.  
Faz uma busca no espaço de redes de tarefas através das diferentes  
decomposições de ações compostas.  
Ações compostas representam sub-metas de alto nível.  
Ações primitivas representam ações.  
Exemplo  
BuildHouse  
Decomposes to  
Get Permit  
Hire Builder  
land  
Start  
house  
Pay Builder  
Finish  
Construction  
money  
Decomposes to  
Build  
Roof  
Build Foundation  
Build  
Build  
Interior  
Frame  
Build  
Walls  
Planejamento Hierárquico  
Plan library:  
Contém várias decomposições de ações abstratas em  
menos abstratas ou mesmo planos inteiros pré-  
concebidos.  
Cada ação abstrata tem pré-condições e efeitos que são  
comuns a todas as instanciações dela.  
As decomposições podem ser expressadas da seguinte  
maneira Decompose(a, d) - uma ação a um pode ser  
decomposta em plano d.  
Planejamento Hierárquico  
Planejamento hierárquico híbrido  
Na prática, se mistura operadores de decomposição HTN com outros  
operadores do planejamento de ordem parcial.  
Decompose(Contruction,  
Plan(STEPS:{S1: Build(Foundation),S2:Build(Frame),  
S3: Build(Roof), S4:Build(Walls),  
S5: Build(Interior)}  
Orderings:{S1<S2<S3<S5, S2<S4<S5},  
Bindings:{},  
Links:{S1 Foundation S , S2 Frame S3, S2 Frame S4,  
2
Walls  
Roof  
S3  
S5, S4  
S5}))  
Planejamento Hierárquico  
Algoritmo:  
Constrói-se um plano de ordem parcial inicial no maior nível de  
abstração.  
Recursivamente decompõem-se ações abstratas até o plano de ordem  
parcial final conter apenas operadores primitivos (que podem ser  
executados pelo agente).  
Resolve-se ameaças e verifica-se a consistência global do plano de  
ordem parcial final.  
Planejamento Clássico  
Em planejamento clássico, o ambiente do problema precisa  
possuir as seguintes características:  
Observável.  
Estático.  
Determinístico.  
Supõe-se que as descrições das ações são sempre corretas e  
completas. Nestas circunstâncias, um agente poderia planejar  
e depois executar o plano de olhos fechados.  
Planejamento em Ambientes Incertos  
Em ambientes incertos, um agente deve:  
Usar seus sensores para descobrir o que está acontecendo  
no ambiente enquanto o plano está sendo executado.  
Modificar ou substituir o plano se algo inesperado  
acontecer.  
Os agentes precisam lidar com informações incompletas e  
incorretas.  
Planejamento em Ambientes  
Não-Determinísticos  
Existem 4 métodos de planejamento mais comuns  
usados para lidar com o ambientes não-  
determinísticos:  
(1) Planejamento sem sensores: Constrói-se planos sequenciais  
normais (sem percepção), mas considera-se todas as circunstâncias  
independentemente do estado inicial.  
(2) Planejamento condicional: Constrói-se um plano fixo com  
diferentes ramificações para diferentes contingentes. Percebe-se o  
ambiente para saber que ramo seguir.  
Planejamento em Ambientes  
Não-Determinísticos  
Métodos de planejamento para ambientes não-  
determinísticos:  
(3) Monitoramento da execução com replanejamento: Usa qualquer  
uma das técnicas precedentes para construir o plano, mas monitora a  
execução para ver se o plano pode ter sucesso no atual estado ou  
precisa ser revisto. Replaneja no caso de algo estar errado.  
(4) Planejamento contínuo: Planeja-se continuamente as ações, sendo  
capaz de tratar eventos inesperados, mesmo durante a construção do  
plano.  
Planejamento Condicional  
Aplicação em ambientes completamente  
observáveis:  
O agente sabe seu estado atual, mas se o ambiente for não  
determinístico, ele não saberá o efeito de suas ações.  
Exemplo Aspirador de Pó:  
às vezes suja o destino quando se move para lá.  
às vezes suja se sugar em um local limpo.  
Planejamento Condicional - Aspirador de Pó  
Estados:  
Inicial: AtRight CleanLeft CleanRight  
Final: AtLeft CleanLeft CleanRight  
A representação do espaço de busca é feita em uma árvore  
and-or.  
A solução é uma sub-árvore onde todos os nós folha levam  
em algum ponto a solução do problema.  
Árvore And-Or  
Planejamento Condicional  
Ambientes parcialmente observáveis e não determinísticos:  
Os testes condicionais nem sempre funcionam...  
Exemplo: aspirador sabe se tem sujeira na sala em que ele está.  
Belief state (estado de crença):  
Ao invés de estado único, deve-se lidar explicitamente com a ignorância  
para sempre estar consciente do que se sabe (ou do que não se sabe).  
Representado como um conjunto de estados possíveis.  
Solução:  
Grafos And-Or em estados de crença.  
Grafo And-Or em Estados de Crença  
Estado  
de crença  
Acreditava que  
esquerda estava limpa  
Acreditava que  
esquerda estava suja  
Monitoramento da Execução com  
Replanejamento  
Monitoramento da execução checa as percepções para ver se tudo está  
indo de acordo com o plano.  
Existem dois tipos de monitoramento:  
Monitoramento da ação: para ver se a próxima ação é aplicável.  
Exemplo: a porta está fechada.  
Monitoramento do plano: ver se o plano ainda é viável  
Exemplo: não tem mais dinheiro suficiente.  
Replanejamento: Se algo inesperado acontece, pede-se ao planejador um  
novo plano ou tentar reparar o plano antigo.  
Monitoramento da Execução com  
Replanejamento  
A estratégia monitoramento e replanejamento pode ser  
aplicada em todos os tipos problemas.  
Ambiente total ou parcialmente acessível.  
Espaço de estados ou de planos.  
Planos condicionais ou não.  
Monitoramento da Execução com  
Replanejamento  
Monitoramento da ação (exemplo):  
Whole plan = plano inteiro (inicial), S= start, G = goal.  
Plan = plano que resta.  
O agente deveria chegar em E mas foi para O.  
Então tenta encontrar um plano que leve de O a qualquer ponto de WholePlan.  
Monitoramento da Execução com  
Replanejamento  
Monitorando plano:  
Verifica, a cada passo, as pré-condições para o sucesso do  
plano inteiro.  
Problemático em ambientes parcialmente acessíveis.  
Pode-se perder mais tempo verificando todas as condições  
do futuro plano do que agindo.  
Deve ser sempre mantido o monitoramento das ações.  
Planejamento Contínuo  
Diferenças:  
Cria planos incrementalmente (dentro de limites de tempo)  
Pode começar a executar um plano mesmo que ele ainda esteja  
incompleto.  
Continua planejando durante a execução do plano.  
Pode mudar de objetivo durante a execução do plano.  
É capaz de intercalar continuamente entre:  
Execução de passos (de percepção e efetivação).  
Monitoramento.  
Replanejamento.  
Planejamento Contínuo  
Exemplo dos blocos:  
Plano de ordem parcial condicional.  
Mundo observável (mas funcionaria igual em um mundo não observável)  
Action(Mover (x, y),  
PRECOND: Limpo(x) Limpo(y) EmCima(x,z)  
EFFECT: EmCima (x,y) Limpo(z)  EmCima(x,z)  Limpo(y)).  
C
D
Estado Inicial  
Objetivo  
B
A E F G  
B C D  
A E F G  
Planejamento Contínuo  
Supondo que nada acontece enquanto se planeja, o plano é rapidamente  
encontrado com planejamento de ordem parcial  
C
D
B
B C D  
A E F G  
A E F G  
EmCima (C,F)  
Limpo (C)  
Limpo (D)  
Mover (C,D)  
NaMesa (A)  
EmCima (B,E)  
EmCima (C,F)  
EmCima (D,G)  
Limpo (A)  
EmCima (C,D)  
EmCima (D,B)  
Início  
Fim  
Limpo (C)  
Limpo (D)  
Limpo (B)  
EmCima (D,G)  
Limpo (D)  
Limpo (B)  
Mover (D,B)  
Planejamento Contínuo  
Antes da execução das ações, algo faz com que o ambiente mude.  
D
B
E
C
F G  
B C D  
A E F G  
A
EmCima (C,F)  
Limpo (C)  
Limpo (D)  
Mover (C,D)  
NaMesa (A)  
EmCima (B,E)  
EmCima (C,F)  
EmCima (D,B)  
Limpo (A)  
EmCima (C,D)  
EmCima (D,B)  
Início  
Fim  
Limpo (C)  
Limpo (D)  
Limpo (G)  
EmCima (D, y)  
Limpo (D)  
Limpo (B)  
Plano Incompleto!  
Mover (D,B)  
Planejamento Contínuo  
O plano é refeito estendendo-se um link casual.  
C
D
B
B C D  
A E F G  
A E F G  
EmCima (C,F)  
Limpo (C)  
Limpo (D)  
Mover (C,D)  
NaMesa (A)  
EmCima (B,E)  
EmCima (C,F)  
EmCima (D,B)  
Limpo (A)  
EmCima (C,D)  
EmCima (D,B)  
Início  
Fim  
Limpo (C)  
Limpo (D)  
Limpo (G)  
EmCima (D, y)  
Limpo (D)  
Limpo (B)  
Plano completo! porem  
redundante...  
Mover (D,B)  
Planejamento Contínuo  
Elemina-se os passos redundantes.  
C
D
B
B C D  
A E F G  
A E F G  
EmCima (C,F)  
Limpo (C)  
Limpo (D)  
Mover (C,D)  
NaMesa (A)  
EmCima (B,E)  
EmCima (C,F)  
EmCima (D,B)  
Limpo (A)  
EmCima (C,D)  
EmCima (D,B)  
Início  
Fim  
Limpo (C)  
Limpo (D)  
Limpo (G)  
Plano completo!  
Planejamento Contínuo  
O agente é desastrado... Acaba colocando C em cima de A ao invés  
de D.  
D
B
E
D
C B  
A E  
C
F G  
A
F
G
NaMesa (A)  
EmCima (B,E)  
EmCima (C,F)  
EmCima (D,B)  
Limpo (F)  
EmCima (C,D)  
EmCima (D,B)  
Início  
Fim  
Limpo (C)  
Limpo (D)  
Limpo (G)  
Planejamento Contínuo  
Adiciona-se um novo passo ao plano.  
C
D
C B  
A E  
D
B
E
F
G
A
F
G
EmCima (C,A)  
Limpo (C)  
Limpo (D)  
Mover (C,D)  
NaMesa (A)  
EmCima (B,E)  
EmCima (C,A)  
EmCima (D,B)  
Limpo (F)  
EmCima (C,D)  
EmCima (D,B)  
Início  
Fim  
Limpo (C)  
Limpo (D)  
Limpo (G)  
Planejamento Contínuo  
Finalmente o agente consegue realizar o movimento com sucesso  
e chegar no estado final. Agora ele pode buscar um novo objetivo.  
C
D
B
A E F G  
NaMesa (A)  
EmCima (B,E)  
EmCima (C,D)  
EmCima (D,B)  
Limpo (F)  
EmCima (C,D)  
EmCima (D,B)  
Início  
Fim  
Limpo (C)  
Limpo (D)  
Limpo (G)  
Aplicações de Planejamento  
Qualquer problema que necessite de passos/ações para  
chegar a um determinado objetivo.  
Exemplos:  
Robôs que realizam tarefas.  
Personagens de jogos direcionados a objetivos.  
Geração de histórias para storytelling interativo.  
Leitura Complementar  
Russell, S. and Norvig, P. Artificial Intelligence: a  
Modern Approach, 2nd Edition, Prentice-Hall,  
2003.  
Capítulo 11: Planning  
Capítulo 12: Planning and Acting in the Real  
World