ECAI 2004 Conference Paper

[PDF] [full paper] [prev] [tofc] [next]

Interleaving Execution and Planning for Nondeterministic, Partially Observable Domains

Piergiorgio Bertoli, Alessandro Cimatti, Paolo Traverso

Methods that interleave planning and execution are a practical solution to deal with complex planning problems in nondeterministic domains under partial observability. However, most of the existing approaches do not tackle in a principled way the important issue of termination of the planning-execution loop, or only do so considering specific assumptions over the domains. In this paper, we tackle the problem of interleaving planning and execution relying on a general framework, which is able to deal with nondeterministic, partially observable planning domains. We propose a new, general planning algorithm that guarantees the termination of the interleaving of planning and execution: either the goal is achieved, or the system detects that there is no longer a guarantee to progress toward it. Our experimental analysis shows that our algorithm can efficiently solve planning problems that cannot be tackled with a state of the art off-line planner for nondeterministic domains under partial observability, MBP. Moreover, we show that our algorithm can efficiently detect situations where progress toward the goal can be no longer guaranteed.

Keywords: Planning

Citation: Piergiorgio Bertoli, Alessandro Cimatti, Paolo Traverso: Interleaving Execution and Planning for Nondeterministic, Partially Observable Domains. In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.657-661.


[prev] [tofc] [next]


ECAI-2004 is organised by the European Coordinating Committee for Artificial Intelligence (ECCAI) and hosted by the Universitat Politècnica de València on behalf of Asociación Española de Inteligencia Artificial (AEPIA) and Associació Catalana d'Intel-ligència Artificial (ACIA).