Planning with Resources
September 16-22, 2002
Philippe Laborie , ILOG ,
A resource can be defined as any substance or (set of)
object(s) whose cost or available quantity induce some constraint
on the operations that use it. A resource can for instance
represent a machine which can only perform one operation
at a time, the fuel contained in the tank of a plane or
the workforce or the money available to perform a
given project. In the context of planning with resources, a
solution plan is defined as a plan that achieves the goals while
allocating resources to operations in such a way that all
resource constraints are satisfied. As in the real life resources
often have a limited availability, it's not surprising that
resource constraints play a key role in practical planning.
The first part of the course will provide a definition of
resources in the context of planning and review the state of the
art of planning with resources. The second part will focus on one
of the most promising approach for dealing with resources in
planning which relies on the application of
constraint-based techniques in Partial-Order or
Hierarchical Task Network planning.
About the lecturer:
Dr. Philippe Laborie graduated from Ecole Nationale
Supérieure des Télécommunications (Paris) in
1992, and received a Ph.D. in Artificial Intelligence from
LAAS/CNRS (Toulouse) on the integration of A.I. Planning and
Scheduling in 1995. He is one of the developers of the IXTET Planning system. He
then worked for two years as post-doctoral fellow at
Electricité de France (Paris) and INRIA/IRISA (Rennes) on
the Supervision and Diagnosis of complex systems
(telecommunication and power distribution networks). His main
scientific interests include planning, scheduling, supervision
and diagnosis of complex systems and more generally, all decision
problems dealing with time. Since 1998 he has been at ILOG S.A.
in Gentilly, France, where he currently holds the position of
Here is a preliminary overview of the course. Note that this
is subject to minor changes.
- Why are Resources important in many practical applications of
- Part I: State of the Art Overview
- Definition of a Resource
- Problem Modeling
- Limits of STRIPS model
- Standalone languages
- Planning Systems (language)
- Problem Solving
- Basic Tools
- Linear Programming (LP)
- Integer Linear Programming (ILP) 
- Satisfiability (SAT) 
- Constraint Satisfaction Problems (CSP) [42,64]
- Planning Techniques
- Planning graphs [9,39,49,69,20]:
- SAT Planners [25,37],
LPSAT  and other encodings [61,38]
- Heuristic Planners [10,11,58,34]: GRT-R
, Metric-FF , Sapa
, TP4 
- Part II: Focus on Constraint-Based Approaches
- Problem Solving (cont'd)
- Planning Techniques
- Partial-Order Causal-Link Planners [50,57]
- Hierarchical Task Networks [70,18,26,53]
- Constraint Programming [62,54,30,67,66,41,60]
- Problem Modeling [1,3]
- Temporal Constraints 
- Resource Usage
- Objective Functions
- Problem Solving 
- Constraint Propagation
- Global constraints
- Algorithms based on activity time windows [47,28,13,56,4,5,27,46,55,2,65]
- Algorithms based on relative positions of activities [44,15,45]
- Branching Schemes [43,14]
- Search heuristics [63,6]
- Beyond the Basic Search Scheme [68,24,7]
Some Planning Systems on the Web:
- K. Baker. Introduction to Sequencing and Scheduling. Wiley,
- P. Baptiste, C. Le Pape and W. Nuijten. Satisfiability Tests
and Time-Bound Adjustments for Cumulative Scheduling Problems.
Annals of Operations Research, 92(1999)305-333.
- P. Baptiste, C. LePape, and W. Nuijten. Constraint-Based
Scheduling. Kluwer Academics Publishers, 2001.
- P. Baptiste and C. Le Pape. A Theoretical and Experimental
Comparison of Constraint Propagation Techniques for Disjunctive
Scheduling. IJCAI 1995. pp600-606.
- P. Baptiste and C. Le Pape. Adjustments of Release and Due
Dates for Cumulative Scheduling Problems. Proc. Third
International Conference on Industrial Engineering and Production
- C. Beck, A. Davenport, E. Sitarski and M. Fox. Texture-Based
Heuristics for Scheduling Revisited. In the Proceedings of the
National Conference on Artificial Intelligence (AAAI-97), 1997.
- C. Beck and P. Refalo. A Hybrid Approach to Scheduling with
Earliness and Tardiness Costs. Third International Workshop on
Integration of AI and OR Techniques (CP-AI-OR'01), Wye College,
Ashford, UK, 2001.
- R. Bixby, M. Fenelon, Z. Gu, E. Rothberg and R. Wunderling.
MIP: Theory and Practice Closing the Gap. System Modelling and
Optimization: Methods, Theory and Applications, Kluwer, The
Netherlands, M. J. D. Powell and S. Scholtes, editors, pp. 19-49,
- A. Blum and M. Furst. Fast Planning Through Planning Graph
Analysis. Proceedings of the 14th International Joint Conference
on Artificial Intelligence (IJCAI 95).
- B. Bonet and H. Geffner. Planning as Heuristic Search: New
Results Proc. European Conference on Planning (ECP-99), Durham,
- B. Bonet and H. Geffner. Planning as Heuristic Search (Long
Version) Artificial Intelligence, Special issue on Heuristic
Search. Vol 129 (1-2) 2001.
- M. Brenner. A Formal Model for Planning with Time and
Resources in Concurrent Domains, Workshop on Planning with
Resources, IJCAI'01, Seattle, Washington, USA, August 2001
- J. Carlier and E. Pinson. A Practical Use of Jackson's
Preemptive Schedule for Solving the Job-Shop Problem, Annals of
Operations Research 26:269-287
- A. Cesta, A. Oddi and S. Smith (2002). A Constrained-Based
Method for Project Scheduling with Time Windows. Journal of
Heuristics, Vol.8, N.1, 2002.
- A. Cesta and C. Stella. A time and resource problem for
planning architectures. In ECP-97, 1997.
- D. Chapman. Planning for Conjunctive Goals. Artificial
Intelligence 32 (3): 333-377 (1987)
- S. Chien, G. Rabideau, R. Knight, R. Sherwood, B. Engelhardt,
D. Mutz, T. Estlin, B. Smith, F. Fisher, T. Barrett, G. Stebbins
and D. Tran. ASPEN Automated Planning and Scheduling for Space
- K. Currie and A. Tate. O-plan: The open planning
architecture. Artificial Intelligence, 52(1):49-86. 1991.
- R. Dechter, I. Meiri and J. Pearl. Temporal constraint
networks. Artificial Intelligence, 49, 61-95. 1991.
- M. Do and S. Kamhampati. Planning as Constraint Satisfaction:
Solving the planning-graph by compiling it into CSP. In Proc. of
Fifth International Conference on Artificial Intelligence
Planning and Scheduling (AIPS), 2000.
- M. Do and S. Kambhampati. Sapa: A Domain-Independent
Heuristic Metric Temporal Planner. Proceedings ECP 2001.
- B. Drabble and A. Tate. The Use of Optimistic and Pessimistic
Resource Profiles to Inform Search in an Activity Based Planner.
Proceedings of the Second International Conference on Planning
Systems (AIPS-94), Chicago, June 1994, AAAI Press.
- A. El-Kholy and B. Richards. Temporal and Resource Reasoning
in Planning: The parcPLAN Approach, in Proceedings of the 12th
European Conference on Artificial Intelligence, pp614-618,
ECAI96, Budapest, John Wiley and Sons Ltd, 1996.
- H. El-Sakkout and M. Wallace. Probe Backtrack Search for
Minimal Perturbation in Dynamic Scheduling, Constraints, Special
Issue on Industrial Constraint-Directed Scheduling, Vol 5 No 4,
- M. Ernst, T. Millstein and D. Weld. Automatic SAT compilation
of planning problems. Proceedings of the International Joint
Conference on Artificial Intelligence (IJCAI), 1997.
- K. Erol, D. Nau and J. Hendler. "UMCP: A Sound and Complete
Planning Procedure for Hierarchical Task-Network Planning." In
AIPS-94, Chicago, June, 1994.
- J. Erschler, P. Lopez and C. Thuriot. Raisonnement temporel
sous contraintes de ressources et problèmes
d'ordonnancement. Revue d'Intelligence Artificielle, 5(3):7--32,
- J. Erschler. Analyse sous contraintes et aide à la
décision pour certains problèmes d'ordonnancement.
PhD thesis, Université Paul Sabatier, 1976.
- M. Fox and D. Long. PDDL2.1: An Extension to PDDL for
Expressing Temporal Planning Domains. Unpublished document. 2002.
- H. Geffner. Planning as Branch and Bound and its Relation to
Constraint-based Approaches. Unpublished document.
- I. Gent and T. Walsh. The Search for Satisfaction.
- M. Ghallab and H. Laruelle. Representation and Control in
IxTeT, a Temporal Planner. In Proceedings AIPS-94, pp61-67,
- P. Haslum and H. Geffner. Heuristic planning with time and
resources. In Proceedings ECP-01.
- J. Hoffmann and B. Nebel. The FF Planning System: Fast Plan
Generation Through Heuristic Search, in: Journal of Artificial
Intelligence Research, Volume 14, 2001, Pages 253 - 302.
- J. Hoffmann. Extending FF to Numerical State Variables.
Proceedings of the 15th European Conference on Artificial
Intelligence, Lyon, France, July 2002.
- A. Jonsson, P. Morris, N. Muscettola, K. Rajan and B. Smith.
Planning in Interplanetary Space: Theory and Practice. In
Proceedings of the Fifth International Conference on Artificial
Intelligence Planning and Scheduling, 2000.
- H. Kautz and B. Selman. Unifying SAT-based and Graph-based
Planning. In Proceedings IJCAI-99, Stockholm, 1999.
- H. Kautz and J. Walser. State-space Planning by Integer
Optimization. Proceedings Fifteenth National Conference on
Artificial Intelligence (AAAI-99), 1999.
- J. Koehler, B. Nebel, J. Hoffmann and Y. Dimopoulos.
Extending Planning Graphs to an ADL Subset, ECP-97, pages
273-285, Springer LNAI 1348. 1997.
- J. Koehler. Planning under Resource Constraints. In
Proceedings of the Thirteenth European Conference on Artificial
Intelligence (ECAI-98), 489-493.
- R. Kowalski. Algorithm = Logic + Control. CACM 22 (7):
- V. Kumar. Algorithms for Constraint-Satisfaction Problems: A
Survey. AI Magazine, Vol 13(1), Spring 1992.
- P. Laborie and M. Ghallab. Planning with Sharable Resource
Constraints. In Proceedings IJCAI-95, pp1643-1649, Montreal,
- P. Laborie. Algorithms for Propagating Resource Constraints
in AI Planning and Scheduling: Existing Approaches and New
Results. European Conference on Planning. Sept. 2001, Toledo,
- P. Laborie. Algorithms for Propagating Resource Constraints
in AI Planning and Scheduling: Existing Approaches and New
Results. European Conference on Planning. Extended version. To
appear in Artificial Intelligence.
- C. Le Pape and P. Baptiste. Resource Constraints for
Preemptive Job-shop Scheduling. Constraints, Volume 3, Number 4,
October 1998. pp263-287.
- C. Le Pape. Implementation of Resource Constraints in ILOG
Schedule: A Library for the Development of Constraint-Based
Scheduling systems. Intelligent Systems Engineering, 3(2):55--66,
- M. Lever and B. Richards. parcPLAN: A Planning Architecture
with Parallel Actions, Resources and Constraints, in Proceedings
of 9th International Symposium on Methodologies for Intelligent
Systems 94, pp213-223, Springer-Verlag, 1994.
- D. Long and M. Fox. Efficient Implementation of the Plan
Graph in STAN (1999). Journal of Artificial Intelligence Research
10 (1999) 87-115.
- D. McAllester and D. Rosenblitt. Systematic Nonlinear
Planning Proceedings AAAI-91 Anaheim, CA (1991).
- C. McCarthy and M. Pollack. A Plan-Based Personalized
Cognitive Orthotic. In Proceedings AIPS-2002 (2002).
- D. McDermott, M. Ghallab, A. Howe, C. Knoblock, A. Ram, M.
Veloso, D. Weld and D. Wilkins. PDDL: The Planning Domain
Definition Language. Unpublished document. 1998.
- D. Nau, Y. Cao, A. Lotem, and H. Munoz-Avila. SHOP: Simple
Hierarchical Ordered Planner. In Proceedings of the 16th
International Joint Conference on Artificial Intelligence, pages
968--973, Stockholm, Sweden, July/August 1999.
- X. Nguyen and S. Kambhampati. Reviving Partial Order
Planning. In Proceedings IJCAI 2001. (2001)
- W. Nuijten and C. Le Pape. Constraint-Based Job Shop
Scheduling with ILOG-Scheduler. Journal of Heuristics, 3:271-286,
- W. Nuijten. Time and resource constrained scheduling. Ph.D.
thesis, Technical University Eindhoven, 1994.
- J. Penberthy and D. Weld. UCPOP: A sound, complete, partial
order planner for ADL. In Proceedings of the Third International
Conference on Knowledge Representation and Reasoning, (KR'92),
108--114. Boston, MA.
- I. Refanidis and I. Vlahavas. GRT: A Domain Independent
Heuristic for STRIPS Worlds based on Greedy Regression Tables.
Proc. 5th European Conference on Planning (ECP-99), Durham, UK,
Springer-Verlag, September 8-10, 1999, pp. 346-358
- I. Refanidis and I. Vlahavas. Heuristic Planning with
Resources. 14th European Conference on Artificial Intelligence,
Berlin, August 2000.
- J-C. Regin. A filtering algorithm for constraints of
difference in CSPs. In Proceedings of the Twelfth National
Conference on Artificial Intelligence, pages 362--367, Seattle,
- J. Rintanen and H. Jungholt. Numeric state variables in
constraint-based planning. In Recent Advances in AI Planning
(ECP'99), S. Biundo and M. Fox, eds., Lecture Notes in Artificial
Intelligence 1809, pages 109-121, 2000. Springer-Verlag, Berlin,
- D. Smith, J. Frank and A. Jónsson. Bridging the Gap
Between Planning and Scheduling. In Knowledge Engineering Review
- S. Smith and C. Cheng. Slack-Based Heuristics for Constraint
Satisfaction Scheduling. Proceedings 11th National Conference on
Artificial Intelligence, July, 1993.
- B. Smith. A tutorial on constraint programming. School of
Computing. Research Report 95.14, University of Leeds, April
- F. Sourd and W. Nuijten. Multiple-machine lower bounds for
shop scheduling problems. INFORMS Journal of Computing,
- R. Stallman and G. Sussman. Forward Reasoning and
Dependency-Directed Backtracking in a System for Computer-Aided
Circuit Analysis. Artificial Intelligence 9 (2): 135-196 (1977)
- G. Steele. The definition and implementation of a computer
programming language based on constraints. Technical Report
AI-TR-595, Massachusetts Institute of Technology Artificial
Intelligence Laboratory, 1980
- P. Torres and P. Lopez. Overview and possible extensions of
shaving techniques for Job-Shop problems. 2nd International
Workshop on Integration of AI and OR techniques in Constraint
Programming for Combinatorial Optimization Problems
(CP-AI-OR'2000), Paderborn (Germany), 8-10 Mars 2000, pp.181-186.
- P. van Beek and X. Chen. CPlan: A constraint programming
approach to planning. Proceedings of the 16th National Conference
on Artificial Intelligence, Orlando, Florida, 585-590, July,
- D. Wilkins. Practical Planning: Extending the classical AI
planning paradigm. Eds Morgan Kaufmann, 1988.
- S. Wolfman and D. Weld. The LPSAT Engine and its Application
to Resource Planning. The LPSAT Engine and its Application to
Resource Planning. In Proceedings of IJCAI-99.