|
Abstract : |
Many real world planning problems require goals with deadlines and durative actions that consume resources. In this paper, we present Sapa, a domain-independent heuristic forward chaining planner that can handle durative actions, metric resource constraints, and deadline goals. The main innovation of Sapa is the set of distance based heuristics it employs to control its search. We consider both optimizing and satisficing search. For the former, we identify admissible heuristics for objective functions based on makespan and slack. For satisficing search, our heuristics are aimed at scalability with reasonable plan quality. Our heuristics are derived from the ?relaxed temporal planning graph ? structure, which is a generalization of planning graphs to temporal domains. We also provide techniques for adjusting the heuristic values to account for resource constraints. Our experimental results indicate that Sapa returns good quality solutions for complex planning problems in reasonable time. 1, |
