SAPA

SAPA: A multi-objective metric temporal planner. SAPA is a domain-independent heuristic forward chaining planner that can handle durative actions, metric resource constraints, and deadline goals. It is designed to be capable of handling the multi-objective nature of metric temporal planning. Our technical contributions include (i) planning-graph based methods for deriving heuristics that are sensitive to both cost and makespan (ii) techniques for adjusting the heuristic estimates to take action interactions and metric resource limitations into account and (iii) a linear time greedy post-processing technique to improve execution flexibility of the solution plans. An implementation of SAPA using many of the techniques presented in this paper was one of the best domain independent planners for domains with metric and temporal constraints in the third International Planning Competition, held at AIPS-02. We describe the technical details of extracting the heuristics and present an empirical evaluation of the current implementation of SAPA.


References in zbMATH (referenced in 16 articles , 1 standard article )

Showing results 1 to 16 of 16.
Sorted by year (citations)

  1. Domshlak, Carmel; Hoffmann, Jörg; Katz, Michael: Red-black planning: a new systematic approach to partial delete relaxation (2015)
  2. Nguyen, Tuan Anh; Do, Minh; Gerevini, Alfonso Emilio; Serina, Ivan; Srivastava, Biplav; Kambhampati, Subbarao: Generating diverse plans to handle unknown and partially known user preferences (2012) ioport
  3. Baioletti, Marco; Milani, Alfredo; Poggioni, Valentina; Rossi, Fabio: Experimental evaluation of pheromone models in ACOPlan (2011)
  4. Do, Minh Binh; Kambhampati, Subbarao: SAPA: A multi-objective metric temporal planner (2011) ioport
  5. Benton, J.; Do, Minh; Kambhampati, Subbarao: Anytime heuristic search for partial satisfaction planning (2009)
  6. Coles, Andrew; Fox, Maria; Halsey, Keith; Long, Derek; Smith, Amanda: Managing concurrency in temporal planning using planner-scheduler interaction (2009)
  7. Garrido, Antonio; Arangu, Marlene; Onaindia, Eva: A constraint programming formulation for planning: From plan scheduling to plan generation (2009)
  8. Roberts, Mark; Howe, Adele: Learning from planner performance (2009)
  9. Gerevini, Alfonso E.; Saetti, Alessandro; Serina, Ivan: An approach to efficient planning with numerical fluents and multi-criteria plan quality (2008)
  10. Sapena, O.; Onaindía, E.: Planning in highly dynamic environments: an anytime approach for planning under time constraints (2008) ioport
  11. de la Asunción, Marc; Castillo, Luis; Fernández-Olivares, Juan; García-Pérez, Oscar; González, Antonio; Palao, Francisco: Handling fuzzy temporal constraints in a planning environment (2007)
  12. Wah, Benjamin W.; Chen, Yixin: Constraint partitioning in penalty formulations for solving temporal planning problems (2006)
  13. Shin, Ji-Ae; Davis, Ernest: Processes and continuous change in a SAT-based planner (2005)
  14. Do, M.; Kambhampati, S.: SAPA: A multi-objective metric temporal planner (2003)
  15. Sanchez, R.; Kambhampati, S.: AltAltp: Online parallelization of plans with heuristic state search (2003)
  16. Nguyen, XuanLong; Kambhampati, Subbarao; Nigenda, Romeo S.: Planning graph as the basis for deriving heuristics for plan synthesis by state space and CSP search (2002)