Planejamento

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 - 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

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

a₁

^a4

g₄

g₂

g₀

a₂

a₃

s₀

^a5

g₅

g₃

Planejamento Regresivo

a₁

a₂

a₃

^a1

a₂

a₃

… a₅₀

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 (Manu al)

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)

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

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:{S₁: Build(Foundation),S₂:Build(Frame),

S₃: Build(Roof), S₄:Build(Walls),

S₅: Build(Interior)}

Orderings:{S₁<S₂<S₃<S₅, S₂<S₄<S₅},

Bindings:{},

Links:{S₁^F^o^uⁿ^d^a^tⁱ^oⁿ S , S₂^F^r^a^m^e S₃, S₂^F^r^a^m^e S₄,

2

Walls

Roof

S₃

S₅, S₄

S₅}))

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.

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