×

zbMATH — the first resource for mathematics

Strong temporal planning with uncontrollable durations. (English) Zbl 1443.68163
Summary: Planning in real world domains often involves modeling and reasoning about the duration of actions. Temporal planning allows such modeling and reasoning by looking for plans that specify start and end time points for each action. In many practical cases, however, the duration of actions may be uncertain and not under the full control of the executor. For example, a navigation task may take more or less time, depending on external conditions such as terrain or weather. In this paper, we tackle the problem of strong temporal planning with uncontrollable action durations (STPUD). For actions with uncontrollable durations, the planner is only allowed to choose the start of the actions, while the end is chosen, within known bounds, by the environment. A solution plan must be robust with respect to all uncontrollable action durations, and must achieve the goal on all executions, despite the choices of the environment. We propose two complementary techniques. First, we discuss a dedicated planning method, that generalizes the state-space temporal planning framework, leveraging SMT-based techniques for temporal networks under uncertainty. Second, we present a compilation-based method, that reduces any STPUD problem to an ordinary temporal planning problem. Moreover, we investigate a set of sufficient conditions to simplify domains by removing some of the uncontrollability. We implemented both our approaches, and we experimentally evaluated our techniques on a large number of instances. Our results demonstrate the practical applicability of the two techniques, which show complementary behavior.

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Software:
ANML; COLIN; MathSAT5; PDDL
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Cimatti, A.; Micheli, A.; Roveri, M., Strong temporal planning with uncontrollable durations: a state-space approach, (AAAI, (2015)), 3254-3260
[2] Micheli, A.; Do, M.; Smith, D. E., Compiling away uncertainty in strong temporal planning with uncontrollable durations, (IJCAI, (2015)), 1631-1637
[3] Fox, M.; Long, D., PDDL2.1: an extension to PDDL for expressing temporal planning domains, J. Artif. Intell. Res., 20, 61-124, (2003) · Zbl 1036.68093
[4] Vidal, T.; Fargier, H., Handling contingency in temporal constraint networks: from consistency to controllabilities, J. Exp. Theor. Artif. Intell., 11, 1, 23-45, (1999) · Zbl 1054.68664
[5] Peintner, B.; Venable, K.; Yorke-Smith, N., Strong controllability of disjunctive temporal problems with uncertainty, (CP, (2007)), 856-863 · Zbl 1145.68528
[6] Bäckström, C., Computational aspects of reordering plans, J. Artif. Intell. Res., 9, 99-137, (1998) · Zbl 0903.68174
[7] Coles, A.; Fox, M.; Halsey, K.; Long, D.; Smith, A., Managing concurrency in temporal planning using planner-scheduler interaction, Artif. Intell., 173, 1, 1-44, (2009) · Zbl 1180.68245
[8] Coles, A.; Coles, A.; Fox, M.; Long, D., Forward-chaining partial-order planning, (ICAPS, (2010)), 42-49
[9] Coles, A.; Coles, A.; Fox, M.; Long, D., COLIN: planning with continuous linear numeric change, J. Artif. Intell. Res., 44, 1-96, (2012) · Zbl 1280.68236
[10] Dechter, R.; Meiri, I.; Pearl, J., Temporal constraint networks, Artif. Intell., 49, 1-3, 61-95, (1991) · Zbl 0737.68070
[11] Cimatti, A.; Micheli, A.; Roveri, M., Solving strong controllability of temporal problems with uncertainty using SMT, Constraints, 20, 1, 1-29, (2015) · Zbl 1314.90043
[12] Barrett, C. W.; Sebastiani, R.; Seshia, S. A.; Tinelli, C., Satisfiability modulo theories, (Handbook of Satisfiability, (2009), IOS Press), 825-885
[13] Morris, P., A structural characterization of temporal dynamic controllability, (CP, (2006)), 375-389
[14] Santana, P.; Williams, B., A bucket elimination approach for determining strong controllability of temporal plans with uncontrollable choices, (AAAI, (2012)), 2453-2454
[15] Muise, C.; Beck, C.; McIlraith, S., Flexible execution of partial order plans with temporal constraints, (IJCAI, (2013)), 2328-2335
[16] Bresina, J.; Dearden, R.; Meuleau, N.; Ramakrishnan, S.; Smith, D.; Washington, R., Planning under continuous time and resource uncertainty: a challenge for AI, (UAI, (2002)), 77-84
[17] Frank, J.; Jónsson, A., Constraint-based attribute and interval planning, Constraints, 8, 4, 339-364, (2003) · Zbl 1074.68609
[18] Cesta, A.; Cortellessa, G.; Fratini, S.; Oddi, A.; Rasconi, R., The APSI framework: a planning and scheduling software development environment, (ICAPS Application Showcase, (2009))
[19] Ghallab, M.; Laruelle, H., Representation and control in ixtet, a temporal planner, (AIPS, (1994)), 61-67
[20] Dearden, R.; Meuleau, N.; Ramakrishnan, S.; Smith, D. E.; Washington, R. Rich, Incremental contingency planning, (ICAPS’03 Workshop on Planning Under Uncertainty and Incomplete Information, (2003))
[21] Younes, H. L.S.; Simmons, R., Policy generation for continuous-time stochastic domains with concurrency, (ICAPS, (2004)), 325-333
[22] Younes, H. L.S.; Simmons, R., Solving generalized semi-Markov decision processes using continuous phase-type distributions, (AAAI, (2004)), 742-748
[23] Little, I.; Aberdeen, D.; Thiébaux, S., Prottle: a probabilistic temporal planner, (AAAI, (2005)), 1181-1186
[24] Coles, A.; Coles, A.; Clark, A.; Gilmore, S., Cost-sensitive concurrent planning under duration uncertainty for service-level agreements, (ICAPS, (2006)), 34-41
[25] Mausam; Weld, D., Planning with durative actions in stochastic domains, J. Artif. Intell. Res., 31, 33-82, (2008) · Zbl 1183.68581
[26] Beaudry, E.; Kabanza, F.; Michaud, F., Planning for concurrent action executions under action duration uncertainty using dynamically generated Bayesian networks, (ICAPS, (2010)), 10-17
[27] Beaudry, E.; Kabanza, F.; Michaud, F., Planning with concurrency under resources and time uncertainty, (ECAI, (2010)), 217-222 · Zbl 1211.68434
[28] Ghallab, M.; Nau, D.; Traverso, P., Automated planning - theory and practice, (2004), Morgan Kaufmann · Zbl 1074.68613
[29] Palacios, H.; Geffner, H., Compiling uncertainty away in conformant planning problems with bounded width, J. Artif. Intell. Res., 35, 623-675, (2009) · Zbl 1183.68584
[30] Cimatti, A.; Micheli, A.; Roveri, M., Timelines with temporal uncertainty, (AAAI, (2013)), 195-201
[31] Smith, D.; Frank, J.; Cushing, W., The ANML language, (The ICAPS-08 Workshop on Knowledge Engineering for Planning and Scheduling (KEPS), (2008))
[32] Rintanen, J., Impact of modeling languages on the theory and practice in planning research, (AAAI, (2015)), 4052-4056
[33] Dvorak, F.; Bit-Monnot, A.; Ingrand, F.; Ghallab, M., A flexible ANML actor and planner in robotics, (ICAPS Planning and Robotics Workshop, (2014)), 12-19
[34] Fox, M.; Long, D.; Halsey, K., An investigation into the expressive power of PDDL2.1, (ECAI, (2004)), 328-342
[35] Gazen, B.; Knoblock, C., Combining the expressiveness of UCPOP with the efficiency of graphplan, (ECP, (1997), Springer-Verlag New York), 221-233
[36] Rintanen, J., Complexity of concurrent temporal planning, (Proceedings of the Seventeenth International Conference on Automated Planning and Scheduling, ICAPS 2007, Providence, Rhode Island, USA, September 22-26, 2007, (2007)), 280-287
[37] Tsamardinos, I.; Pollack, M. E., Efficient solution techniques for disjunctive temporal reasoning problems, Artif. Intell., 151, 1-2, 43-89, (2003) · Zbl 1082.68825
[38] Veloso, M.; Perez, A.; Carbonell, J., Nonlinear planning with parallel resource allocation, (Proceedings of the DARPA Workshop on Innovative Approaches to Planning, Scheduling, and Control, (1990), Morgan Kaufmann), 207-212
[39] Coles, A. J.; Coles, A.; Olaya, A. G.; Celorrio, S. J.; López, C. L.; Sanner, S.; Yoon, S., A survey of the seventh international planning competition, AI Mag., 33, 1, 83-88, (2012)
[40] Howe, A. E.; Dahlman, E., A critical assessment of benchmark comparison in planning, J. Artif. Intell. Res., 17, 1-3, (2002) · Zbl 1056.68133
[41] Cimatti, A.; Griggio, A.; Schaafsma, B. J.; Sebastiani, R., The mathsat5 SMT solver, (TACAS, (2013)), 93-107 · Zbl 1381.68153
[42] Smith, D. E., The case for durative actions: a commentary on PDDL2.1, J. Artif. Intell. Res., 20, 149-154, (2003) · Zbl 1036.68102
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.