GAPNet: a new genetic approach to the planning problem in artificial intelligence

• Cássio S. Carvalho UFPR
• Marcos A. Castilho UFPR
• Luis A. Künzle UFPR
• Fabiano Silva UFPR

Abstract

The proposed approach aims at solving a planning problem in Artificial Inteligence using genetic algorithms. The planning problem is translated into a Petri net, which permits identifying all the mutex over actions in an automatic manner. An action classification is adopted considering the involved conflicts, from which is possible to generate a chromossomic codification where each gene position is determinated according to a measure of it’s influence across the net.

References

Blum, A. L. and Furst, M. L. (1995). Fast planning through planning graph analysis. In Proc. of the 14th IJCAI, pages 1636–1642, Montreal, Canada.

Bonet, B. and Geffner, H. (1998). HSP: Planning as heuristic search. In Entry at the AIPS-98 Planning Competition, Pittsburgh.

Castilho, M. A., Künzle, L. A., Lecheta, E., Palodeto, V., and Silva, F. (2004). An investigation on genetic algorithms for generic strips planning. In IBERAMIA, pages 185–194.

Ghallab, M., Howe, A., Knoblock, C., McDermott, D., Ram, A., Veloso, M., Weld, D., and Wilkins, D. (1998). PDDL—the planning domain definition language.

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

Kautz, H. and Selman, B. (1992). Planning as satisfiability. In ECAI ’92: Proceedings of the 10th European conference on Artificial intelligence, pages 359–363, New York, NY, USA. John Wiley & Sons, Inc.

Lardeux, F., Saubion, F., and Hao, J.-K. (2006). Gasat: a genetic local search algorithm for the satisfiability problem. Evol. Comput., 14(2):223–253.

Marynowski, J. E. (2004). Ambiente de planejamento ipê. Master’s thesis, Universidade Federal do Paraná, Curitiba PR, Brasil.

Mitchell, M. (1998). An Introduction to Genetic Algorithms. MIT Press, Cambridge, MA, USA.

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

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.

Weld, D. S. (1999). Recent advances in ai planning. AI Magazine, 20(2):93–123.