Satplan - Satplan

Satplan (mais conhecido como Planejamento como satisfabilidade) é um método de planejamento automatizado . Ele converte a instância problema de planejamento em uma instância do problema de satisfatibilidade booleana , que é então resolvido usando um método para estabelecer satisfiability como o algoritmo dpll ou WalkSAT .

Dado um exemplo problema de planeamento, com um determinado estado inicial, um determinado conjunto de acções, um meta, e um comprimento horizontal, uma fórmula é gerado de modo que a fórmula pode ser satisfeita se e apenas se existe um plano com o determinado comprimento horizonte . Isso é semelhante a simulação de máquinas de Turing com o problema satisfiability na prova do teorema de Cook . Uma planta pode ser encontrado por meio de testes do satisfazibilidade das fórmulas para diferentes comprimentos de horizonte. A maneira mais simples de fazer isso é ir através horizonte comprimentos sequencialmente, 0, 1, 2, e assim por diante.

Veja também

Referências

  • HA Kautz e B. Selman (1992). Planejamento como satisfiability. Em Proceedings da Conferência Europeia Décimo em Inteligência Artificial (ECAI'92) , páginas 359-363.
  • HA Kautz e B. Selman (1996). Empurrando o envelope: planejamento, lógica proposicional, e busca estocástica. Em Proceedings da Conferência Nacional Thirteenth em Inteligência Artificial (AAAI'96) , páginas 1194-1201.
  • J. Rintanen (2009). Planejamento e sáb. Em A. Biere, H. van Maaren, M. Heule e Toby Walsh, Eds., Handbook of satisfabilidade , páginas 483-504, IOS Press.