Domain-independent temporal planning in a planning-graph-based approach

Article type: Research Article

Authors: Garrido, Antonio | Onaindía, Eva

Affiliations: Dpto. de Sistemas Informáticos y Computación, Universidad Politécnica de Valencia, Camino de Vera s/n, 46071, Valencia, Spain E-mail: {agarridot,onaindia}@dsic.upv.es

Abstract: Many planning domains have to deal with temporal features that can be expressed using durations that are associated to actions. This paper presents a temporal planning approach that combines the principles of Graphplan and TGP, and uses the information calculated in the planning graph to deal with a model of actions that include local conditions and effects. In this approach, we propose two strategies for search. The first one is based on the Graphplan backward search. The second one is a new strategy for search based on a least-commitment and heuristic search, which attempts to overcome the main limitations of a chronological backtracking search when dealing with large temporal problems. This search has proved to be beneficial in the scalability of the planner and the experiments show that a planner using this new search is competitive with other state-of-the-art planners w.r.t. the plan quality.

Keywords: Planning, temporal planning, heuristic planning, least-commitment, planning graphs

Journal: AI Communications, vol. 19, no. 4, pp. 341-367, 2006