Skip to main content
SpringerLink
Log in

CTP: A New Constraint-Based Formalism for Conditional, Temporal Planning

  • Published:
Constraints Aims and scope Submit manuscript

Abstract

Temporal constraints pose a challenge for conditional planning, because it is necessary for a conditional planner to determine whether a candidate plan will satisfy the specified temporal constraints. This can be difficult, because temporal assignments that satisfy the constraints associated with one conditional branch may fail to satisfy the constraints along a different branch. In this paper we address this challenge by developing the Conditional Temporal Problem (CTP) formalism, an extension of standard temporal constraint-satisfaction processing models used in non-conditional temporal planning. Specifically, we augment temporal CSP frameworks by (1) adding observation nodes, and (2) attaching labels to all nodes to indicate the situation(s) in which each will be executed. Our extended framework allows for the construction of conditional plans that are guaranteed to satisfy complex temporal constraints. Importantly, this can be achieved even while allowing for decisions about the precise timing of actions to be postponed until execution time, thereby adding flexibility and making it possible to dynamically adapt the plan in response to the observations made during execution. We also show that, even for plans without explicit quantitative temporal constraints, our approach fixes a problem in the earlier approaches to conditional planning, which resulted in their being incomplete.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Armando, A., Castellini, C., & Giunchiglia, E. (1999). SAT-based procedures for temporal reasoning. In 5th European Conference on Planning (ECP-99).

  2. Barber, F. (2000). Reasoning on interval and point-based disjunctive metric constraints in temporal contexts. Journal of Artificial Intelligence Research, 12: 35–86.

    Google Scholar 

  3. Bessiere, C. (1999). Non-binary constraints. In Principles and Practice of Constraint Programming (CP'99). Springer, Alexandria, Virginia, USA.

    Google Scholar 

  4. Chleq, N. (1995). Efficient algorithms for networks of quantitative temporal constraints. In Proceedings of the Workshop CONSTRAINTS'95, pages 40–45.

  5. Dechter, R., Meiri, I., & Pearl, J. (1991). Temporal constraint networks. Artificial Intelligence, 49: 61–95.

    Google Scholar 

  6. Georgakopoulos, D., Hornick, M., & Sheth, A. (1995). An overview of workflow management: from process modeling to workflow autonomation infastructure. Distributed and Parallel Databases, 3: 119–153.

    Google Scholar 

  7. Goldman, R. P., & Boddy, M. S. (1996). Expressive planning and explicit knowledge. In Proceedings of the 3rd International Conference on Artificial Intelligence Planning Systems, pages 110–117.

  8. Laborie, P., & Ghallab, M. (1995). Planning with sharable constraints. In Proceedings of the 14th International Joint Conference on A.I. (IJCAI-95), pages 1643–1649.

  9. Mackworth, A., & Freuder, E. (1985). The complexity of some polynomial network consistency algorithms for constraint satisfaction problems. Artificial Intelligence, 25(1): 65–74.

    Google Scholar 

  10. Morris, P., Muscettola, N., & Vidal, T. (2001). Dynamic control of plans with temporal uncertainty. In Proceedings of the 17th International Joint Conference on A.I. (IJCAI-01), pages 494–499.

  11. Muscettola, N., Nayak, P. P., Pell, B., & Williams, B. C. (1998). Remote agent: to boldly go where no AI system has gone before. Artificial Intellience, 103: 5–47.

    Google Scholar 

  12. Myers, K. L. (1997). Procedural reasoning system: user's guide. Technical report, SRI International.

  13. Oddi, A., & Cesta, A. (2000). Incremental forward checking for the disjunctive temporal problem. In European Conference on Artificial Intelligence (ECAI-2002).

  14. Onder, N., & Pollack, M. E. (1999). Conditional, probabilistic planning: a unifying algorithm and effective search control mechanisms. In Proceedings of the 16th National Conference on Artificial Intelligence, pages 577–584.

  15. Peot, M., & Smith, D. E. (1992). Conditional nonlinear planning. In Proceedings of the First International Conference on AI Planning Systems (AIPS-92), pages 189–197. College Park, MD.

  16. Pollack, M. E., McCarthy, C., Ramakrishnan, S., Tsamardinos, I., Brown, L., Carrion, S., Colbry, D., Orosz, C., & Peintner, B. (2002). Autominder: a planning, monitoring, and reminding assistive agent. In 7th International Conference on Intelligent Autonomous Systems, pages 265–272.

  17. Pryor, L., & Collins, G. (1996). Planning for contingencies: a decision-based approach. Journal of Artificial Intelligence Research, 4: 287–339.

    Google Scholar 

  18. Schwalb, E., & Dechter, R. (1997). Processing disjunctions in temporal constraint networks. Artificial Intelligence, 93: 29–61.

    Google Scholar 

  19. Schwalb, E., Kask, K., & Dechter, R. (1994). Temporal reasoning with constraints on fluents and events. In Proceedings of the 12th National Conference on Artificial Intelligence (AAAI-94), Vol. 2, pages 1067–1072. AAAI Press/MIT Press, Seattle, Washington, USA.

    Google Scholar 

  20. Smith, D., Frank, J., & Jónsson, A. (2000). Bridging the gap between planning and scheduling. Knowledge Engineering Review, 15: 61–94.

    Google Scholar 

  21. Stergiou, K., & Koubarakis, M. (2000). Backtracking algorithms for disjunctions of temporal constraints. Artificial Intelligence, 120: 81–117.

    Google Scholar 

  22. Tsamardinos, I., (2001). Constrained-Based Temporal Reasoning Algorithms with Applications to Planning. Ph.D. thesis, University of Pittsburgh, PA.

  23. Tsamardinos, I., Morris, P., & Muscettola, N. (1998). Fast transformation of temporal plans for efficient execution. In Proceedings of the 15th National Conference on Artificial Intelligence, pages 254–261.

  24. Tsamardinos, I., Pollack, M. E., & Ganchev, P. (2001). Flexible dispatch of disjunctive plans. In 6th European Conference in Planning, pages 417–422.

  25. Tsamardinos, I., Pollack, M. E., & Horty, J. F. (2000). Merging plans with quantitative temporal constraints, temporally extended actions, and conditional branches. In Proceedings of the 5th International Conference on Artificial Intelligence Planning and Scheduling, pages 264–272.

  26. Vidal, T., & Fargier, H. (1999). Handling contingency in temporal constraint networks: from consistency to controllabilities. Journal of Experimental & Theoretical Artificial Intelligence, 11: 23–45.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Biomedical Informatics, Vanderbilt University, USA

    Ioannis Tsamardinos

  2. Production Engineering Laboratory (LGP) - ENIT, France

    Thierry Vidal

  3. Computer Science and Engineering, University of Michigan, USA

    Martha E. Pollack

Authors
  1. Ioannis Tsamardinos
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Thierry Vidal
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Martha E. Pollack
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Tsamardinos, I., Vidal, T. & Pollack, M.E. CTP: A New Constraint-Based Formalism for Conditional, Temporal Planning. Constraints 8, 365–388 (2003). https://doi.org/10.1023/A:1025894003623

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1025894003623

Search

Navigation