Planejamento Automático: Breve Histórico, Strips, GraphPlan e SATPlan

Planejamento AutomáticoBreve Histórico, Strips, GraphPlan e SATPlan

Jhonatan AlvesUniversidade Federal de Santa Catarina

Sequência da Apresentação

● Histórico● O problema do planejamento● Busca no espaço de estados● Representação do conhecimento● GraphPlan● SatPlan● Conclusão● Perguntas?

Histórico

● Nos anos 60 as principais pesquisas em IA estavam focadas no desenvoltimento de solucionadores gerais: GPS e QA3.

● Nos anos 70, Filkes e Nilson apresentaram o sistema STRIPS que deu origem Éra

Classica do Planejamento Automático.

Histórico

● Novos sistemas de planejamento como ABSTRIPS, NOAH e NONLIN foram apresentados para contornar as restrições de STRIPS.

● Durante os anos 80 a área de planejamento automático progrediu pouco.

Histórico

● A década de 90 foi marcada por grandes avanços na área de planejamento automático com o surgimento dos planejadores GRAPHPLAN e SATPLAN.

● Em 1998 foi criada a linguagem de definição de domínios de problemas - PDDL.

Histórico

● A partir de 1998 várias competições internacionais surgiram com o intuito de premiar os melhores sistema de planejamento automático, tais como:○ Competição Internacional de Planejamento (IPC)○ Conferência Européia de Planejamento (ECP)○ Conferência Internacional de Planejamento e

Escalonamento (ICAPS)

Histórico

● A última edição da IPC ocorreu este ano em Atibaia, São Paulo.

● Atualmente as pesquisas em planejamento automático estão voltadas sobre o conceito de escalonamento automático.

Histórico

● Planejamento automático tem sido estudado em diversos centros de ensino e pesquisa:○ Nasa: desenvolveu um ambiente de planejamento

automático voltado para missões espaciais - ASPEN○ INPE: junto com institutos europeus vem estudando

planejamento automático para testes espaciais - SPAAS

○ UFC: Planejamento automático voltada a administração de recursos hídricos no Estado do Ceará

○ Petrobras: em parceria com a USP está estudando como usar planejamento automático para otimizar problemas que exijam tempo e recursos.

O problema do Planejamento

● Planejamento é o processo de escolher um conjunto de ações que quando executadas em uma determinada sequência satisfazem um conjunto de objetivos.

● Planejamento automático é a área da IA responsável por estudar este processo através do uso do computador.


● Planejamento Automático agrega conhecimento de outras áreas da IA e Computação:○ Engenharia do conhecimento○ Lógica○ Busca


● A modelagem do domínio abstrai um conjunto de fatores, tais como: tempo, custo, recursos e pessoas envolvidas.

● Problemas de Planejamento Automático pertencem a classe NP-Completo.


● Formalmente, um problema de planejamento clássico é a tripla:

P = <T,s0,G>

onde:○ T = sistema de transição de estados○ s0 = estado inicial○ G = conjunto de metas


● T, por sua vez é a seguinte tripla:T = <S,A,y>

onde:○ S = {s0,s1,...,sn} é o conjunto de estados○ A = {a0,a1,...,am} é o conjunto de ações○ y = S x A -> S é a função de transição de estados

Um plano P é formado por uma sequência linear de ações que satisfaz G, tal que:○ s1 = y(s0,ai), s2 = y(s1,aj), ..., sn = y(sn-1,ak)○ P = {ai,aj,...,ak} e sn pertence a G


● Instância do mundo de blocos:


● Possível solução:

Busca no Espaço de Estados

● Busca para frente inicia-se pelo estado inicial do problema e traça por uma sequência de ações que alcance o objetivo do problema.



● Busca para trás inicia-se pelo conjunto G e traça uma sequência de ações que alcance o estado inicial do problema.

Representação do Conhecimento

● Quesito de grande importância no desenvolvimento de um plano.

● Técnicas de representação do conhecimento são empregadas na modelagem do domínio de problemas.

Representação do Conhecimento

● A modelagem do domínio pode ser realizada através da Teoria de conjuntos, Variáveis de Estado e pela Representação clássica.

● As principais linguagens de descrição de domínios da Representação clássica são:○ Cálculo Situacional○ STRIPS○ PDDL

STRIPS● STRIPS é uma linguagem formal derivada

da lógica de primeira ordem usada para decompor problemas de planejamento automático em condições lógicas.

● Em STRIPS um problema é a tripla: <s0,L,O,G>

Onde:○ L é o conjunto de literais○ O é o conjunto de operadores○ G conjunto de objetivos

STRIPS● Um operador O possui a seguinte estrutura:

O: nome((a0,a1,...an),PRE,ADD,DEL)

● Um estado si é representado por uma conjunção de n literais verdadeiros:

STRIPS● Como exemplo, considere a seguinte

instância do mundo de blocos:

Literais:○ Sobre(x,y): x está sobre y○ Livre(x): não há outro bloco sobre x○ Segurando(x): o robô está segurando x○ Mão-livre: o robô não está segurando algum bloco○ Sobre-a-mesa(x): o bloco x está sobre a mesa

STRIPSOperadores:○ Empilhar((x,y),

PRE: livre(y) ^ Segurando(x)ADD: Mão-vazia ^ Sobre(x,y) DEL: Livre(y) ^ Segurando(x)

○ Desempilhar((x,y),PRE: Sobre(x,y) ^ livre(x) ^ Mão-vaziaADD: Segurando(x) ^ Livre(y) DEL: Sobre(x,y) ^ Mão-vazia

STRIPSOperadores:○ Pegar((x),

PRE: livre(x) ^ Sobre-a-mesa(x) ^ Mão-vaziaADD: Segurando(x) DEL: Sobre-a-mesa(x) ^ Mão-vazia

○ Largar((x),PRE: Segurando(x)ADD: Sobre-a-mesa(x) ^ Mão-vazia DEL: Segurando(x)

Representação do ConhecimentoEstado inicial:○ Sobre(A,B) ^ Sobre-a-mesa(B) ^ Mão-vazia ^ Livre

(A)

Objetivo:○ Sobre(B,A) ^ Sobre-a-mesa(A) ^ Mão-vazia ^ Livre

(B)

STRIPS: Busca pelo Plano

○ s_0: Sobre(A,B) ^ Sobre-a-mesa(B) ^ Mão-vazia ^ Livre(A)

○ Empilhar((A,B),PRE: livre(B) ^ Segurando(A), ....)

○ Desempilhar((A,B), PRE: Sobre(A,B) ^ livre(A) ^ Mão-vazia, ...)

○ Pegar((A),PRE: livre(A) ^ Sobre-a-mesa(A) ^ Mão-vazia, ...)

○ Largar((A),PRE: Segurando(A), ...)


● A aplicação do operador:○ Desempilhar((A,B),

PRE: Sobre(A,B) ^ livre(A) ^ Mão-vaziaADD: Segurando(A) ^ Livre(B) DEL: Sobre(A,B) ^ Mão-vazia

sobre o estado:s0: Sobre(A,B) ^ Sobre-a-mesa(B) ^ Mão-vazia ^ Livre(A)gera o novo estado:○ s1: Segurando(A) ^ Livre(B) ^ Sobre-a-mesa(B) ^

Livre(A)


● Sobre o estado s1 aplica-se o operador Largar(A) que gera o estado s3:s3: Sobre-a-mesa(A) ^ Livre(A) ^ Mão-vazia ^ Livre(B) ^ Sobre-a-mesa(B)

● Sobre o estado s3 aplica o operador Pegar

(B) que gera o estado s4:○ S4: Sobre-a-mesa(A) ^ Livre(A) ^ Segurando(B) ^

Livre(B)


● Sobre o estado s4 aplica-se o operador Empilhar(B,A) que gera o estado s4:

○ s4: Sobre(B,A) ^ Livre(B) ^ Mão-vazia ^ Sobre-a-mesa(A)


● O Plano gerado é a seguinte sequência de operadores:

○ Desempilhar(A,B) -> Largar(A) -> Pegar(B) -> Empilhar(B,A)

GRAPHPLAN

● É uma técnica que busca por um plano através de uma estrutura de grafo chamada de grafo de planejamento.

● O grafo de planejamento consiste em uma sequência de camadas onde cada camada corresponde a um passo na busca do plano.

GRAPHPLAN

● Uma camada de literais é formada por todos os literais que poderiam ser verdadeiros nesse passo.

● Uma camada de ações é formada por todas as ações que poderiam ter suas precondições satisfeitas nesse passo.

GRAPHPLAN

GRAPHPLAN

○ Empilhar((A,B),PRE: livre(B) ^ Segurando(A)ADD: Mão-vazia ^ Sobre(A,B) DEL: Livre(B) ^ Segurando(A)

GRAPHPLAN

● As linhas em vermelho indicam vínculos de exclusão mútua.

GRAPHPLAN

● Duas ações são mutuamente exclusivas se uma ou mais condições forem satisfeitas:○ Uma ação nega o efeito da outra.○ Um dos efeitos de uma ação é a negação de uma

precondição de uma outra ação.

GRAPHPLAN

● Dois literais são mutuamente exclusivas se uma ou mais condições forem satisfeitas:○ Um litral é a negação do outro.○ Ações que alcaçam um par de literais são

mutuamente exclusivas.

GRAPHPLAN

● Busca pelo plano:O algoritmo do GRAPH PLAN funciona em duas fases:

■ 1ª: expandir o grafo de planejamento.■ 2ª: tentar extrair um plano do grafo de

planejamento expandido.

GRAPHPLAN

● A fase de extração é realizada somente quando todos os literais do objetivo estão presente na atual camada e se não existem vínculos de exclusão mútua entre qualquer par de literais.

● O processo de expansão pára somente se uma solução seja encontrada ou que se verifique que não é possível extraír um plano do grafo.

GRAPHPLAN

● A prova de que um plano não poderá ser extraído é verificado quando:○ Literais aumentam monotonicamente.○ Ações aumentam monotonicamente.○ Número de exclusões mútuas diminuem

monotonicamente.

GRAPHPLAN

● Extração do plano:○ Busca inicia a partir da camada final.○ A cada camada k selecionar um conjunto de ações

que não possuem relação de exclusão mútua.○ As precondições das ações selecionadas na

camada k se tornam o objetivos a serem alcançados pelas ações da camada k-1.

○ Se a camada inicial é alcançada então existe um plano.

GRAPHPLAN

● Extração do plano:G:{¬garb, dinner, present}

GRAPHPLAN

● Extração do plano:

GRAPH PLAN

● Extração do plano:

Solução: cook -> wrap

SATPLAN

● É uma técnica de planejamento que consiste em reduzir uma instância de planejamento automático ao problema da satisfazitilidade booleana (SAT).

SATPLAN

● O problema da satisfazibilidade booleana consiste em testar se uma senteça lógica F em sua forma normal conjuntiva (CNF) é satisfazível, por exemplo:○ F = (p v q v r) ^ (¬p v ¬ r)○ p = 0, q = 1 e r = 0 então F = 1.

● Ou seja, consiste em encontrar um conjunto C de valores verdade que satisfaça F:○ C = {p=0, q=1, r=0}

SATPLAN

● A redução segue os seguintes passos:○ para i=0 até Tmax○ F = reduzir a instância de planejamento a SAT○ Se F é satisfazível ○ Então extraír um plano P do conjunto de ○ valores verdade que satisfaz F○ Retorne P○ Fim Se

Onde Tmax é um valor que delimita o comprimento do plano.

SATPLAN

● Caso a fórmula lógica F correspondente a instância de planejamento seja satisfazível então um plano poderá ser extraído desta fórmula.

● O plano é formado pelas proposições, correspondentes as ações, assinadas como verdadeiras.

SATPLAN

● Estrutura de um planejador SAT:

SATPLAN

● A redução de uma instância de planejamento consiste no seguinte conjunto de axiomas:

Onde: AES é o conjunto de axiomas de estados sucessores. AP é o conjunto de axiomas de precondições. AE e o conjunto de axiomas de exclusão.

SATPLAN

● Considere o seguinte problema:Um robô precisa se movimentar da célula A para a célula B.Literais:○ EM(x): o robô está na célula x.

Ações:○ Mover((x,y), PRE: EM(x), ADD: EM(y), DEL: EM(x))

SATPLAN

● A codificação do estado inicial:

Esta(A,0) ^ ¬Esta(B,0)

● Codificação de G:

Esta(B,n) ^ ¬Esta(A,n)

SATPLAN

● Axiomas de Estados Sucessores:

Esta(A,1) <--> Mover(B,A,0) v ( Esta(A,0) ¬Mover(A,B,0))

Esta(B,1) <--> Mover(A,B,0) v ( Esta(B,0) ¬Mover(B,A,0))

SATPLAN

● Axiomas de precondições:

Mover(A,B,0)-> Esta(A,0)Mover(B,A,0) -> Esta(B,0)

SATPLAN

● Axiomas de exclusão:

(¬Mover(A,B,0) V ¬Mover(B,A,0))

SATPLAN

● Extraindo a solução: Tmax = 1ESTA(A,0) ^ ¬ESTA(B,0) ^

Esta(A,1) <-> Mover(B,A,0) v ( Esta(A,0) ^ ¬Mover(A,B,0)) ^Esta(B,1) <-> Mover(A,B,0) v ( Esta(B,0) ^ ¬Mover(B,A,0)) ^

Mover(A,B,0) -> Esta(A,0) ^Mover(B,A,0) -> Esta(B,0) ^(¬Mover(A,B,0) V ¬Mover(B,A,0)) ^

Esta(B,1) ^ ¬Esta(A,1)

Conclusões

● Problemas de planejamento são complexos.

● A complexidade está tanto na representação do conhecimento quando no desenvolvimento de algoritmos.

● A complexidade aumenta conforme o número de literais e ações.

Conclusões

● SATPLAN e GRAPHPLAN foram os grandes responsáveis pelo sucesso nas pesquisas em planejamento automático.

● Anos depois outros planejadores foram propostos tendo como base as técnicas do SATPLAN e GRAPHPLAN○ MEDIC○ BLACKBOX

Conclusões

● GRAPHPLAN vs SATPLAN○ Não existe nenhuma prova formal de que um seja

melhor do que o outro.○ Ambos são velozes.○ Resolvem problemas complexos.

Contato

[email protected]

Perguntas?Obrigado!

Science

Planejamento Automático: Breve Histórico, Strips, GraphPlan e SATPlan