Timeline-based planning over dense temporal domains. (English) Zbl 1433.68406
Summary: Planning is one of the most studied problems in computer science. In this paper, we focus on the timeline-based approach, where the domain is modeled by a set of independent, but interacting, components, each one represented by a number of state variables, whose behavior over time (timelines) is governed by a set of temporal constraints (transition functions and synchronization rules). Whereas the time domain is usually assumed to be discrete, here we address decidability and complexity issues for timeline-based planning (TP) over dense time.
We first prove that dense TP is undecidable in the general case; then, we show that decidability can be recovered by restricting to synchronization rules with a suitable future semantics. More “tractable” settings can be obtained by additionally constraining the form of intervals used in rules: EXPSPACE-completeness is obtained by avoiding singular intervals, and PSPACE-completeness by admitting only intervals of the forms \([0, a]\) and \([b, + \infty [\). Finally, NP-completeness can be proved for dense TP with purely existential rules only.
We first prove that dense TP is undecidable in the general case; then, we show that decidability can be recovered by restricting to synchronization rules with a suitable future semantics. More “tractable” settings can be obtained by additionally constraining the form of intervals used in rules: EXPSPACE-completeness is obtained by avoiding singular intervals, and PSPACE-completeness by admitting only intervals of the forms \([0, a]\) and \([b, + \infty [\). Finally, NP-completeness can be proved for dense TP with purely existential rules only.
MSC:
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
| 03B44 | Temporal logic |
| 68Q25 | Analysis of algorithms and problem complexity |
| 68Q45 | Formal languages and automata |
References:
| [1] | Alur, R.; Dill, D. L., A theory of timed automata, Theor. Comput. Sci., 126, 2, 183-235 (1994) · Zbl 0803.68071 |
| [2] | Alur, R.; Feder, T.; Henzinger, T. A., The benefits of relaxing punctuality, J. ACM, 43, 1, 116-146 (1996) · Zbl 0882.68021 |
| [3] | Alur, R.; Henzinger, T. A., Real-time logics: complexity and expressiveness, Inf. Comput., 104, 1, 35-77 (1993) · Zbl 0791.68103 |
| [4] | Barreiro, J.; Boyce, M.; Do, M.; Frank, J.; Iatauro, M.; Kichkaylo, T.; Morris, P.; Ong, J.; Remolina, E.; Smith, T.; Smith, D., EUROPA: a platform for AI planning, scheduling, constraint programming, and optimization, (Proc. of ICKEPS (2012)) |
| [5] | Bozzelli, L.; Molinari, A.; Montanari, A.; Peron, A., Complexity of timeline-based planning over dense temporal domains: exploring the middle ground, (Proc. of GandALF (2018), EPTCS), 191-205 · Zbl 1528.68358 |
| [6] | Bozzelli, L.; Molinari, A.; Montanari, A.; Peron, A., Decidability and complexity of timeline-based planning over dense temporal domains, (Proc. of KR 2018 (2018), AAAI Press), 627-628 |
| [7] | Bozzelli, L.; Molinari, A.; Montanari, A.; Peron, A.; Woeginger, G., Timeline-based planning over dense temporal domains with trigger-less rules is NP-complete, (Proc. of ICTCS. CEUR WP (2018)), 116-127 |
| [8] | Cesta, A.; Cortellessa, G.; Fratini, S.; Oddi, A.; Policella, N., An innovative product for space mission planning: an a posteriori evaluation, (Proc. of ICAPS (2007), AAAI), 57-64 |
| [9] | Chien, S.; Tran, D.; Rabideau, G.; Schaffer, S.; Mandl, D.; Frye, S., Timeline-based space operations scheduling with external constraints, (Proc. of ICAPS (2010), AAAI), 34-41 |
| [10] | Cialdea Mayer, M.; Orlandini, A.; Umbrico, A., Planning and execution with flexible timelines: a formal account, Acta Inform., 53, 6-8, 649-680 (2016) · Zbl 1351.90092 |
| [11] | Demri, S.; Lazic, R., LTL with the freeze quantifier and register automata, ACM Trans. Comput. Log., 10, 3, 16:1-16:30 (2009) · Zbl 1351.68158 |
| [12] | Frank, J.; Jónsson, A., Constraint-based attribute and interval planning, Constraints, 8, 4, 339-364 (2003) · Zbl 1074.68609 |
| [13] | Gigante, N.; Montanari, A.; Cialdea Mayer, M.; Orlandini, A., Timelines are expressive enough to capture action-based temporal planning, (Proc. of TIME (2016), IEEE Computer Society), 100-109 |
| [14] | Gigante, N.; Montanari, A.; Cialdea Mayer, M.; Orlandini, A., Complexity of timeline-based planning, (Proc. of ICAPS (2017), AAAI), 116-124 |
| [15] | Harel, D., Algorithmics: The Spirit of Computing (2012), Springer · Zbl 1243.68007 |
| [16] | Jónsson, A. K.; Morris, P. H.; Muscettola, N.; Rajan, K.; Smith, B. D., Planning in interplanetary space: theory and practice, (Proc. of ICAPS (2000), AAAI), 177-186 |
| [17] | Jungnickel, D., Graphs, Networks and Algorithms, Algorithms and Computation in Mathematics (2013), Springer · Zbl 1255.68001 |
| [18] | Koymans, R., Specifying real-time properties with metric temporal logic, Real-Time Syst., 2, 4, 255-299 (1990) |
| [19] | Minsky, M. L., Computation: Finite and Infinite Machines. Automatic Computation (1967), Prentice-Hall, Inc. · Zbl 0195.02402 |
| [20] | Muscettola, N., HSTS: integrating planning and scheduling, (Intelligent Scheduling (1994), Morgan Kaufmann), 169-212 |
| [21] | Ouaknine, J.; Worrell, J., On the decidability and complexity of metric temporal logic over finite words, Log. Methods Comput. Sci., 3, 1 (2007) · Zbl 1128.03008 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
