Usando Redes de Petri e Resolvedores ISCAS para Tratar Planejamento como Satisfatibilidade

• Razer Montaño UFPR
• Marcos Castilho UFPR
• Fabiano Silva UFPR
• Luis Künzle UFPR

Resumo

Este trabalho apresenta uma abordagem para resolver o problema de planejamento clássico em IA como um problema de satisfatibilidade não clausal. Uma instância SAT em formato ISCAS é gerada pela conversão do problema de planejamento tendo como base uma rede de Petri na qual o problema de alcançabilidade de sub-marcação deve ser resolvido. A instância ISCAS é então resolvida usando-se resolvedores SAT não-clausais conhecidos.

Referências

Blum, A. and Furst, M. (1995). Fast planning through planning graph analysis. In Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI 95), pages 1636–1642.

Bonet, B. and Geffner, H. (2001). Heuristic search planner 2.0. AI Magazine, 22(3):77–80.

D’Agostino, M. and Mondadori, M. (1994). The taming of the cut: Classical refutations with analytic cut. Journal of Logic and Computation, 4(3):285–319.

Darwiche, A. and Marquis, P. (2002). A Knowledge Compilation Map. Journal of Artificial Intelligence Research, 17:229–264.

Drummond, M. E. (1985). Refining and extending the procedural net. In Proceedings of the 9th international joint conference on Artificial intelligence - Volume 2, pages 1010–1011, San Francisco, CA, USA. Morgan Kaufmann Publishers Inc.

Esparza, J. (1996). Decidability and complexity of petri net problems - an introduction. In Petri Nets, pages 374–428.

Fikes, R. and Nilsson, N. (1971). Strips: A new approach to the application of theorem proving to problem solving. Technical Report 43r, AI Center, SRI International, 333 Ravenswood Ave, Menlo Park, CA 94025. SRI Project 8259.

3SATPLAN venceu a competição de planejadores na quarta edição do IPC (4th International Planning Competition) e empatou em primeiro lugar em sua quinta edição

Gerevini, A., Saetti, A., and Serina, I. (2003). Planning through stochastic local search and temporal action graphs in lpg. J. Artif. Int. Res., 20:239–290.

Hickmott, S., Rintanen, J., Thiébaux, S., and White, L. (2007). Planning via petri net unfolding. In Proceedings of the 20th international joint conference on Artifical intelligence, pages 1904–1911, San Francisco, CA, USA. Morgan Kaufmann Publishers Inc.

Hoffmann, J. and Nebel, B. (2001). The FF planning system: Fast plan generation through heuristic search. Journal of Artificial Intelligence Research, 14:253–302.

Jain, H. and Clarke, E. M. (2009). Efficient SAT solving for Non-Clausal formulas using DPLL, graphs, and watched cuts. In 46th Design Automation Conference (DAC).

Kautz, H. and Selman, B. (1999). Unifying SAT-based and graph-based planning. In Minker, J., editor, Workshop on Logic-Based Artificial Intelligence, Washington, DC, June 14–16, 1999, College Park, Maryland. Computer Science Department, University of Maryland.

Kautz, H. A. and Selman, B. (1992). Planning as satisfiability. In Proceedings of the Tenth European Conference on Artificial Intelligence (ECAI’92), pages 359–363.

Massacci, F. (1998). Simplification: A general constraint propagation technique for propositional and modal tableaux. Lecture Notes in Computer Science, 1397:217–231.

Mcdermott, D., Ghallab, M., Howe, A., Knoblock, C., Ram, A., Veloso, M., Weld, D., and Wilkins, D. (1998). PDDL - the planning domain definition language. Technical report, CVC TR-98-003/DCS TR-1165, Yale Center for Computational Vision and Control.

Montaño, R., Silva, F., Castilho, M., and Kunzle, L. (2007). Planejamento como satisfatibilidade: uma abordagem não-clausal. In Proceedings of the VI Encontro Nacional de Inteligência Artificial (ENIA).

Murata, T. (1989). Petri nets: Properties, analysis and applications. Proceedings of the IEEE, 77(4):541–580.

Palacios, H., Bonet, B., Darwiche, A., and Geffner, H. (2005). Pruning conformant plans by counting models on compiled d-DNNF representations. In ICAPS, pages 141–150.

R. Hähnle and N. Murray and E. Rosenthal (2005). Normal forms for knowledge compilation. Lecture Notes in Computer Science, 3488:304–313.

Silva, F. (2005). Rede de Planos: Uma Proposta para a Solução de Problemas de Planejamento em Inteligência Artificial usando Redes de Petri. PhD thesis, CEFET, Curitiba PR, Brasil.

Silva, F., Castilho, M., and Künzle, L. (2000). Petriplan: a new algorithm for plan generation (preliminary report). In Lecture Notes in Artificial Intelligence, volume 1952, pages 86–95. International Joint Conference IBERAMIA’2000 - SBIA’2000.

Thiffault, C., Bacchus, F., and Walsh, T. (2004). Solving non-clausal formulas with dpll search. In In SAT, pages 663–678. Springer.

Tseitin, G. (1968). On the complexity of derivation in propositional calculus. Studies in constructive mathematics and mathematical logic, 2(115-125):10–13.