Abstract
In this paper we describe Constraint-based Attribute and Interval Planning (CAIP), a paradigm for representing and reasoning about plans. The paradigm enables the description of planning domains with time, resources, concurrent activities, mutual exclusions among sets of activities, disjunctive preconditions and conditional effects. We provide a theoretical foundation for the paradigm, based on temporal intervals and attributes. We show how the plans are naturally expressed by networks of constraints, and show that the process of planning maps directly to dynamic constraint reasoning. We describe compatibilities, a compact mechanism for describing planning domains. We also demonstrate how this framework incorporates the use of constraint representation and reasoning technology to improve planning. Finally, we describe EUROPA, an implementation of the CAIP framework.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Allen, J. (1991). Planning as temporal reasoning. In Proceedings of the Second Conference on Knowledge Representation.
Allen, J. & Koomen, J. (1983). Planning using a temporal world model. In Proceedings of the Eighth International Joint Conference on Artificial Intelligence.
Dechter, R., Meiri, I., & Pearl, J. (1991). Temporal constraint networks. Artificial Intelligence, 49: 61–94.
Do, M. B., & Khambhampati, S. (2000). Solving planning-graph by compiling it into CSP. In Proceedings of the Fifth International Conference on Artificial Intelligence Planning and Scheduling, pages 82–91.
Fikes, R. E., & Nilsson, N. J. (1971). STRIPS: a new approach to the application of theorem proving to problem solving. Artificial Intelligence, 2(3-4).
Fox, M., & Long, D. (2002). PDDL 2.1: an extension to PDDL for expressing temporal planning domains. Technical Report 2/02, University of Durham Computer Science Department.
Frank, J., Jónsson, A. K., & Morris, P. H. (2000). On reformulating planning as dynamic constraint satisfaction. In Choueiry, B., & Walsh, T., eds., 4th International Symposium on Abstraction, Reformulation and Approximation.
Ghallab, M., & Laruelle, H. (1994). Representation and control in IxTeT, a temporal planner. In Proceedings of the 2d Conference on Artificial Intelligence Planning And Scheduling, pages 61–67.
Haslum, P., & Geffner, H. (2000). Admissible heuristics for optimal planning. In Proceedings of the Fifth International Conference on Artificial Intelligence Planning and Scheduling, pages 140–149.
Jónsson, A. (1997). Procedural reasoning in constraint satisfaction. Ph.D. thesis, Stanford University Computer Science Department.
Jónsson, A., & Frank, J. (2000). A framework for dynamic constraint reasoning using procedural constraints. In European Conference on Artificial Intelligence.
Jónsson, A. K., Morris, P. H., Muscettola, N., Rajan, K., & Smith, B. (2000). Planning in interplanetary space: theory and practice. In Proceedings of the Fifth International Conference on Artificial Intelligence Planning and Scheduling.
Joslin, D. (1996). Passive and active decision postponement in plan generation. Ph.D. thesis, Carnegie Mellon University Computer Science Department.
Kautz, H., & Selman, B. (1996). Pushing the envelope: planning, propositional logic, and stochastic search. In Proceedings of the 13th National Conference on Artificial Intelligence, pages 1194–1200.
Laborie, P. (2001). Algorithms for propagating resource constraints in AI planning and scheduling: existing approaches and new results. In Proceedings of the 6th European Conference on Planning.
Laborie, P., & Ghallab, M. (1995). Planning with sharable resource constraints. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 1643–1649.
McAllester, D., & Rosenblitt, D. (1991). Systematic non-linear planning. In Proceedings of the Ninth National Conference on Artificial Intelligence.
McDermott, D. (2000). The 1998 AI planning systems competition. AI Magazine, 21(2).
Muscettola, N. (1994). HSTS: integrated planning and scheduling. In Zweben, M., & Fox, M., eds., Intelligent Scheduling, pages 169–212. Morgan Kaufman.
Nuijten, W. (1994). Time and resource constrained project scheduling: a constraint satisfaction approach. Ph.D. thesis, Eindhoven University of Technology Department of Mathematics and Computer Science Department.
Penberthy, S. (1993). Planning with continuous change. Ph.D. thesis, University of Washington Department of Computer Science and Engineering.
Smith, D. E., & Weld, D. S. (1999). Temporal planning with mutual exclusion reasoning. In Proceedings of the 16th International Joint Conference on Artificial Intelligence, pages 326–337.
Vere, S. (1983). Planning in time: windows and durations for activities and goals. Pattern Matching and Machine Intelligence, 5: 246–267.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Frank, J., Jónsson, A. Constraint-Based Attribute and Interval Planning. Constraints 8, 339–364 (2003). https://doi.org/10.1023/A:1025842019552
Issue Date:
DOI: https://doi.org/10.1023/A:1025842019552