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)
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 só 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