AAAI Publications, Sixth European Conference on Planning

Font Size: 
Sapa: A Domain-Independent Heuristic Metric Temporal Planner
Minh Do, Subbarao Kambhampati

Last modified: 2014-05-21

Abstract


Many real world planning problems require goals with deadlines anddurative actions that consume resources. In this paper, we present Sapa, a domain-independent heuristic forward chaining planner thatcan handle durative actions, metric resource constraints, and deadlinegoals. The main innovation of Sapa is the set of distance basedheuristics it employs to control its search. We consider bothoptimizing and satisficing search. For the former, we identifyadmissible heuristics for objective functions based on makespan andslack. For satisficing search, our heuristics are aimed at scalabilitywith reasonable plan quality. Our heuristics are derived from the``relaxed temporal planning graph'' structure, which is ageneralization of planning graphs to temporal domains. We also providetechniques for adjusting the heuristic values to account for resourceconstraints. Our experimental results indicate that Sapa returnsgood quality solutions for complex planning problems in reasonabletime.

Full Text: PDF