Planning via petri net unfolding
Date
2007
Authors
Hickmott, S.
Rintanen, J.
Thiebaux, S.
White, L.
Editors
Mantaras, R.
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
Proceedings of the 20th IJCAI-07, 2007 / pp.1-8
Statement of Responsibility
Sarah Hickmott, Jussi Rintanen, Sylvie Thiébaux, Lang White
Conference Name
International Joint Conference on Artificial Intelligence (20th : 2007 : Hyderabad, India)
Abstract
The factored state representation and concurrency semantics of Petri nets are closely related to those of concurrent planning domains, yet planning and Petri net analysis have developed independently, with minimal and usually unconvincing attempts at cross-fertilisation. In this paper, we investigate and exploit the relationship between the two areas, focusing on Petri net unfolding, which is an attractive reachability analysis method as it naturally enables the recognition and separate resolution of independent subproblems. On the one hand, based on unfolding, we develop a new forward search method for cost-optimal partial-order planning which can be exponentially more efficient than state space search. On the other hand, inspired by well-known planning heuristics, we investigate the automatic generation of heuristics to guide unfolding, resulting in a more efficient, directed reachability analysis tool for Petri nets.