Planejamento Clássico e STRIPS

O planejamento clássico aborda o problema de encontrar uma sequência de ações para atingir um objetivo em um ambiente determinístico, totalmente observável e estático, usando a representação fatorada de ações no estilo STRIPS por pré-condições e efeitos.

Definition

O planejamento clássico busca uma sequência de ações determinísticas que transforma um estado inicial totalmente conhecido em um estado que satisfaz o objetivo, onde cada ação é descrita pelas condições que devem ser válidas para que ela se aplique e pelas mudanças que ela provoca.

Scope

Este tópico abrange o modelo de planejamento clássico e suas suposições (ações determinísticas, observabilidade total, um único agente, tempo atômico), as representações STRIPS e ADL/PDDL de estados e ações, os métodos básicos de solução de busca no espaço de estados progressiva (forward) e regressiva (backward) e planejamento de ordem parcial, e a complexidade computacional do planejamento proposicional. A orientação heurística e os grafos de planejamento são tratados no tópico relacionado, e as variantes não determinísticas ou probabilísticas estão fora do escopo.

Core questions

• Quais suposições definem o modelo de planejamento clássico e quando elas são apropriadas?
• Como a representação STRIPS decompõe um estado em proposições e uma ação em pré-condições e efeitos de adição/exclusão?
• Como a busca progressiva e regressiva diferem como estratégias de planejamento?
• Qual a dificuldade computacional do planejamento clássico em geral?

Key concepts

• modelo determinístico e totalmente observável
• pré-condições e efeitos STRIPS
• listas de adição e exclusão
• PDDL e ADL
• busca progressiva (forward)
• busca regressiva (backward)
• planejamento de ordem parcial
• complexidade da existência de planos

Key theories

Representação STRIPS

O STRIPS descreve o mundo como um conjunto de proposições verdadeiras e cada ação por uma lista de pré-condições mais listas de adição e exclusão, de modo que aplicar uma ação simplesmente adiciona e remove proposições; este modelo fatorado é a base de quase todos os planejadores clássicos.

Busca progressiva e regressiva

Planos clássicos podem ser encontrados buscando-se para frente a partir do estado inicial aplicando ações aplicáveis (progressão) ou para trás a partir do objetivo calculando subobjetivos regressivos (regressão), com o planejamento de ordem parcial relaxando o compromisso com uma ordenação total das ações.

Complexidade do planejamento

Decidir se um plano proposicional STRIPS existe é PSPACE-completo em geral, explicando formalmente por que o planejamento é difícil e motivando métodos heurísticos e estruturais para torná-lo prático.

Clinical relevance

As representações de planejamento clássico são a interface comum para o planejamento de tarefas de robôs, montagem e logística automatizadas, e qualquer aplicação onde ações determinísticas devem ser sequenciadas para atingir um objetivo; os planejadores clássicos baseados em PDDL são os principais instrumentos do campo e das Competições Internacionais de Planejamento.

History

O STRIPS foi desenvolvido no SRI por volta de 1971 para controlar o robô Shakey, introduzindo o modelo de ação de pré-condição/efeito que define o planejamento clássico. O planejamento de ordem parcial amadureceu nas décadas de 1970-80, Bylander estabeleceu a PSPACE-completude do planejamento proposicional em 1994, e o padrão PDDL posteriormente unificou os benchmarks do campo.

Key figures

• Richard E. Fikes
• Nils J. Nilsson
• Tom Bylander
• Earl D. Sacerdoti

Seminal works

• fikes1971
• bylander1994

Frequently asked questions

Quais são as suposições do planejamento clássico?

O planejamento clássico assume um único agente atuando em um ambiente determinístico, totalmente observável e estático, com ações que levam tempo unitário e um estado inicial totalmente conhecido. Relaxar qualquer uma dessas suposições, por exemplo, permitindo incerteza ou concorrência, leva a problemas de planejamento mais ricos além do modelo clássico.

O que significam as listas de adição e exclusão do STRIPS?

Quando uma ação STRIPS é aplicada, as proposições em sua lista de adição tornam-se verdadeiras e as em sua lista de exclusão tornam-se falsas; todas as outras proposições permanecem inalteradas. Esta regra de atualização simples é o que torna o STRIPS uma representação compacta e computacionalmente conveniente de como as ações mudam o mundo.