Planning with Resources

Introduction

For an application of action planning systems to real-world problems, the incorporation of resources such as time, money and machines is a fundamental feature. This webpage gives an overview of planning systems that are able to handle such resources.
If you want to get included in the listing below, please send an e-mail to Alexander Nareyek <alex@ai-center.com> with information on the system's name, its classification, a list of maximally five keywords, a reference to an overview paper and a URL to the system's homepage (if available). Do not report on features that could potentially be realized but only on existing ones. Multiple systems/versions that are based on each other will not be included; please send only information on the most advanced one.

Classification Categories

Goal Function:
  • Optimization - Complex Functions
      (e.g., maximizing monetary outcome)
  • Optimization - Monotonic Functions
      (e.g., minimizing power use)
  • Satisfaction
      (e.g., that the resources are not overloaded)
Temporal Ontology:
  • Temporal Planning
      (e.g., involving scheduling)
  • No Temporal Planning
      (e.g., STRIPS planning)
Plan Structures:
  • Dynamic Construction
      (e.g., like in partial-order planning or A*)
  • Maximal/Disjunctive Graphs
      (e.g., Graphplan representations or CSPs)
Search Paradigm:
  • Local Search
      (e.g., GSAT or simulated annealing)
  • Refinement Search
      (e.g., partial-order planning or A*)
Integration:
  • Integrated System
      (e.g., respecting resource bottlenecks within planning)
  • Separate Solvers
      (e.g., successive planning and scheduling phases)

Systems

Name ASPEN planner/scheduler
Classification
  • Optimization - Complex Functions
  • Temporal Planning
  • Dynamic Construction
  • Local Search
  • Integrated System
Keywords Iterative Repair; Heuristic Search
Overview Paper Chien, S.; Rabideau, G.; Knight, R.; Sherwood, R.; Engelhardt, B.; Mutz, D.; Estlin, T.; Smith, B.; Fisher, F.; Barrett, T.; Stebbins, G.; and Tran, D. 2000.
ASPEN - Automating Space Mission Operations using Automated Planning and Scheduling.  [PDF]
In Proceedings of the Sixth International Symposium on Technical Interchange for Space Mission Operations and Ground Data Systems (SpaceOps 2000).
Homepage http://www-aig.jpl.nasa.gov/public/planning/aspen/aspen_index.html
 
Name Cooperative Intelligent Real-time Control Architecture (CIRCA)
Classification
  • Satisfaction
  • Temporal Planning
  • Dynamic Construction
  • Refinement Search
  • Separate Solvers
Keywords Real-Time Planning; Temporal Planning; Probabilities; Scheduling; Resource Constraints
Overview Paper Atkins, E. M. 1999.
Plan Generation and Real-Time Execution with Application to Safe, Autonomous Flight.   [PDF]
Ph.D. Thesis, University of Michigan, EECS Department, Computer Science and Engineering Division.
Homepage http://borg.umd.edu/~ella/
 
Name EUROPA - Extensible Universal Remote Operations Planning Architecture
Classification
  • Satisfaction
  • Temporal Planning
  • Dynamic Construction
  • Refinement Search
  • Integrated System
Keywords Temporally Flexible Plans; Modular Architecture; Domain-Independent Heuristics; Constraint-Based Planning
Overview Paper Jonsson, A. K.; and Morris P. H.; Muscettola, N.; Rajan, K.; and Smith, B. 2000.
Planning in Interplanetary Space: Theory and Practice.   [PostScript]
In Proceedings of the Fifth International Conference on Artificial Intelligence Planning and Scheduling (AIPS-2000), 177-186.
 
Name The EXCALIBUR agent's planning system
Classification
  • Optimization - Complex Functions
  • Temporal Planning
  • Dynamic Construction
  • Local Search
  • Integrated System
Keywords Constraint Programming; Heuristic Guidance; Open World; Dynamics; Anytime Computation
Overview Paper Nareyek, A. 2001.
Constraint-Based Agents - An Architecture for Constraint-Based Modeling and Local-Search-Based Reasoning for Planning and Scheduling in Open and Dynamic Worlds.   [HTML]
Reading, Springer LNAI 2062.
Homepage http://www.ai-center.com/projects/excalibur/
 
Name The LPSAT engine's application to resource planning
Classification
  • Satisfaction
  • No Temporal Planning
  • Maximal/Disjunctive Graphs
  • Refinement Search
  • Separate Solvers
Keywords SAT; Incremental Simplex
Overview Paper Wolfman, S. A., and Weld, D. S. 1999.
The LPSAT Engine & its Application to Resource Planning.   [PostScript]
In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence (IJCAI-99), 310-316.
Homepage http://www.cs.washington.edu/ai/lpsat.html
 
Name MO-GRT
Classification
  • Optimization - Monotonic Functions
  • No Temporal Planning
  • Dynamic Construction
  • Refinement Search
  • Integrated System
Keywords Multiple Criteria; Domain-Independent Heuristic Search; Multi-Objective A*
Overview Paper Refanidis, I., and Vlahavas, I. 2001.
Multiobjective Heuristic State-Space Planning.   [PDF]
Technical Report, Aristotle University, Department of Informatics, Thessaloniki, Greece.
Homepage http://www.csd.auth.gr/~lpis/GRT/main.html
 
Name O-Plan
Classification
  • Satisfaction
  • Temporal Planning
  • Dynamic Construction
  • Refinement Search
  • Integrated System
Keywords Integrated tasking, planning, scheduling, execution monitoring and plan repair; Open Planning Architecture; Issue handling; Constraint handling; <I-N-OVA> constraint ontology for plans
Overview Paper Tate, A.; Drabble, B.; and Dalton, J. 1996.
O-Plan: a Knowledge-Based Planner and its Application to Logistics.   [PostScript]
In Tate, A. (ed.), Advanced Planning Technology, Morgan Kaufmann.
Homepage http://www.aiai.ed.ac.uk/project/oplan
 
Name PYRRHUS
Classification
  • Optimization - Monotonic Functions
  • No Temporal Planning
  • Dynamic Construction
  • Refinement Search
  • Integrated System
Keywords UCPOP; Bound Computation; Branch-and-Bound
Overview Paper Williamson, M., and Hanks, S. 1994.
Optimal Planning with a Goal-Directed Utility Model.   [Compressed PostScript]
In Proceedings of the Second International Conference on AI Planning Systems (AIPS-94), 176-181.
 
Name RealPlan
Classification
  • Satisfaction
  • No Temporal Planning
  • Maximal/Disjunctive Graphs
  • Refinement Search
  • Integrated System or Separate Solvers
Keywords Planning; Scheduling; Dynamic CSP; Dependency Directed Backtracking
Overview Paper Srivastava, B.; Kambhampati, S.; and Do, B. M. 2001.
Planning the Project Management Way: Efficient Planning by Effective Integration of Causal and Resource Reasoning in RealPlan.   [PDF]
Artificial Intelligence, to appear.
Homepage http://rakaposhi.eas.asu.edu/realplan.html
 
Name RIPP
Classification
  • Satisfaction
  • No Temporal Planning
  • Maximal/Disjunctive Graphs
  • Refinement Search
  • Integrated System
Keywords IPP Extension to Resource-Constrained Plans
Overview Paper Koehler, J. 1998.
Planning under Resource Constraints.   [Gzipped PostScript]
In Proceedings of the Thirteenth European Conference on Artificial Intelligence (ECAI-98), 489-493.
Homepage http://www.informatik.uni-freiburg.de/~koehler/ipp.html
 
Name TP4
Classification
  • Optimization - Monotonic Functions
  • Temporal Planning
  • Dynamic Construction
  • Refinement Search
  • Integrated System
Keywords Domain-Independent Heuristic Search
Overview Paper Haslum, P., and Geffner, H. 2001.
Heuristic Planning with Time and Resources.   [Gzipped PostScript]
In Workshop Notes of the IJCAI-01 Workshop on Planning with Resources, to appear.
Homepage http://www.ida.liu.se/~pahas/hsps/

Links

IJCAI-01 Workshop on Planning with Resources
http://www.ai-center.com/events/ijcai-2001-ws/

AI Center's Planning Links
http://www.ai-center.com/links/applications/planning.html

AI Center's Scheduling Links
http://www.ai-center.com/links/applications/scheduling.html

Last update:
October 21, 2002 by Alexander Nareyek