Planejamento Automatizado
O planejamento automatizado é o ramo da inteligência artificial que se ocupa de calcular sequências de ações que transformam um estado inicial do mundo em um estado objetivo desejado, dada uma descrição formal das ações disponíveis.
Definition
Planejamento automatizado é o cálculo de um plano — um conjunto ordenado (ou parcialmente ordenado) de ações — que comprovadamente atinge um objetivo a partir de um estado inicial, dado um modelo de como cada ação altera o estado do mundo.
Scope
Esta área abrange a representação de problemas de planejamento (estados, ações com pré-condições e efeitos, objetivos) e os algoritmos que os resolvem: planejamento clássico em domínios determinísticos e totalmente observáveis, métodos de grafo de planejamento e busca heurística, planejamento de rede de tarefas hierárquicas, e a extensão para tempo, recursos e agendamento. Trata formalismos padrão como STRIPS e PDDL e a complexidade do planejamento. O planejamento sob incerteza probabilística conecta-se ao raciocínio sob incerteza, e a aprendizagem de modelos de ação ou políticas a partir de dados pertence ao subcampo de aprendizado de máquina.
Sub-topics
Core questions
- Como as ações, estados e objetivos são representados de forma compacta o suficiente para descrever grandes domínios?
- Como o problema de planejamento é pesquisado eficientemente, apesar de um espaço de estados exponencialmente grande?
- Como heurísticas admissíveis e informativas são derivadas automaticamente de uma descrição de domínio?
- Como os planos podem ser estruturados hierarquicamente e como as restrições de tempo e recursos são incorporadas?
Key concepts
- estados, ações, objetivos
- pré-condições e efeitos
- STRIPS e PDDL
- busca de espaço de estados para frente e para trás
- grafos de planejamento
- heurísticas independentes de domínio
- redes de tarefas hierárquicas
- planejamento temporal e agendamento
Key theories
- Representação de ação STRIPS
- O formalismo STRIPS descreve ações por pré-condições e efeitos de adição/exclusão sobre um conjunto de proposições, fornecendo uma representação compacta e fatorada que torna o planejamento uma busca através de estados simbólicos em vez de uma enumeração de estados explícitos do mundo.
- Busca heurística independente de domínio para planejamento
- Planejadores modernos encaram o planejamento como busca heurística e derivam heurísticas automaticamente da descrição do problema, por exemplo, ignorando efeitos de exclusão ou explorando a estrutura causal, permitindo um forte desempenho de propósito geral.
- Planejamento como uma hierarquia de classes de problemas
- O planejamento abrange um espectro desde o planejamento determinístico clássico até variantes hierárquicas, temporais e com restrição de recursos, cada uma com representações e complexidade características, organizadas na teoria padrão do planejamento automatizado.
Clinical relevance
O planejamento automatizado é aplicado em robótica e sistemas autônomos, operações de naves espaciais e missões, logística e cadeias de suprimentos, manufatura, e geração de jogos e narrativas; planejadores derivados dessas técnicas controlaram naves espaciais autônomas reais e coordenam fluxos de trabalho complexos.
History
O planejamento automatizado começou com STRIPS para o robô Shakey no SRI por volta de 1971, enquadrando o planejamento como prova de teorema sobre descrições de ações. O campo progrediu através do planejamento de ordem parcial, o avanço do Graphplan (1995), e o surgimento de planejadores de busca heurística rápidos e independentes de domínio e o padrão PDDL do final dos anos 1990 em diante, acompanhados através das Competições Internacionais de Planejamento.
Key figures
- Richard E. Fikes
- Nils J. Nilsson
- Malik Ghallab
- Dana Nau
- Paolo Traverso
- Malte Helmert
Related topics
Seminal works
- fikes1971
- ghallab2004
- helmert2006
Frequently asked questions
- Como o planejamento automatizado difere da busca geral?
- O planejamento automatizado é uma forma de busca, mas funciona a partir de uma descrição declarativa e fatorada de ações (pré-condições e efeitos) em vez de uma função sucessora opaca. Essa estrutura permite que os planejadores derivem heurísticas automaticamente e raciocinem sobre quais ações são relevantes, o que a busca genérica não pode fazer.
- O que é PDDL?
- PDDL, a Planning Domain Definition Language (Linguagem de Definição de Domínio de Planejamento), é uma linguagem padrão para descrever domínios e problemas de planejamento — objetos, predicados, ações, o estado inicial e o objetivo. Ela permite que planejadores independentes de domínio sejam comparados em um benchmark comum, como nas Competições Internacionais de Planejamento.