Document Open Access Logo

Taming the Complexity of Timeline-Based Planning over Dense Temporal Domains

Authors Laura Bozzelli, Angelo Montanari, Adriano Peron

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2019.34.pdf
  • Filesize: 0.56 MB
  • 14 pages

Document Identifiers

Author Details

Laura Bozzelli
  • University of Napoli "Federico II", Napoli, Italy
Angelo Montanari
  • University of Udine, Udine, Italy
Adriano Peron
  • University of Napoli "Federico II", Napoli, Italy

Cite As Get BibTex

Laura Bozzelli, Angelo Montanari, and Adriano Peron. Taming the Complexity of Timeline-Based Planning over Dense Temporal Domains. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 34:1-34:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.FSTTCS.2019.34

Abstract

The problem of timeline-based planning (TP) over dense temporal domains is known to be undecidable. In this paper, we introduce two semantic variants of TP, called strong minimal and weak minimal semantics, which allow to express meaningful properties. Both semantics are based on the minimality in the time distances of the existentially-quantified time events from the universally-quantified reference event, but the weak minimal variant distinguishes minimality in the past from minimality in the future. Surprisingly, we show that, despite the (apparently) small difference in the two semantics, for the strong minimal one, the TP problem is still undecidable, while for the weak minimal one, the TP problem is just PSPACE-complete. Membership in PSPACE is determined by exploiting a strictly more expressive extension (ECA^+) of the well-known robust class of Event-Clock Automata (ECA) that allows to encode the weak minimal TP problem and to reduce it to non-emptiness of Timed Automata (TA). Finally, an extension of ECA^+ (ECA^{++}) is considered, proving that its non-emptiness problem is undecidable. We believe that the two extensions of ECA (ECA^+ and ECA^{++}), introduced for technical reasons, are actually valuable per sé in the field of TA.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Planning under uncertainty
  • Theory of computation → Quantitative automata
Keywords
  • Timeline-based planning
  • timed automata
  • event-clock automata

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. R. Alur and T. A. Henzinger. A Really Temporal Logic. Journal of the ACM, 41(1):181-204, 1994. Google Scholar
  2. Rajeev Alur and David L. Dill. A Theory of Timed Automata. Theoretical Computer Science, 126(2):183-235, 1994. Google Scholar
  3. Rajeev Alur, Limor Fix, and Thomas A. Henzinger. Event-Clock Automata: A Determinizable Class of Timed Automata. Theoretical Computer Science, 211(1-2):253-273, 1999. Google Scholar
  4. J. Barreiro, M. Boyce, M. Do, J. Frank, M. Iatauro, T. Kichkaylo, P. Morris, J. Ong, E. Remolina, T. Smith, and D. Smith. EUROPA: A Platform for AI Planning, Scheduling, Constraint Programming, and Optimization. In Proc. of the 4th ICKEPS, 2012. Google Scholar
  5. L. Bozzelli, A. Molinari, A. Montanari, and A. Peron. Complexity of Timeline-Based Planning over Dense Temporal Domains: Exploring the Middle Ground. In Proc. of the 9th GandALF 2018, EPTCS 277, pages 191-205, 2018. Google Scholar
  6. L. Bozzelli, A. Molinari, A. Montanari, and A. Peron. Decidability and Complexity of Timeline-Based Planning over Dense Temporal Domains. In Proc. of the 16th KR, pages 627-628. AAAI Press, 2018. Google Scholar
  7. L. Bozzelli, A. Molinari, A. Montanari, and A. Peron. Undecidability of future timeline-based planning over dense temporal domains. arxiv.org/abs/1904.09184, 2019. URL: http://arxiv.org/abs/1904.09184.
  8. L. Bozzelli, A. Molinari, A. Montanari, A. Peron, and G. J. Woeginger. Timeline-Based Planning over Dense Temporal Domains with Trigger-less Rules is NP-Complete. In Proc. of the 19th ICTCS, volume 2243 of CEUR Workshop Proceedings, pages 116-127, 2018. Google Scholar
  9. A. Cesta, G. Cortellessa, S. Fratini, A. Oddi, and N. Policella. An Innovative Product for Space Mission Planning: An A Posteriori Evaluation. In Proc. of the 17th ICAPS, pages 57-64, 2007. Google Scholar
  10. A. Cesta, A. Finzi, S. Fratini, A. Orlandini, and E. Tronci. Flexible Timeline-Based Plan Verification. In Proc. of the 32nd KI, LNCS 5803, pages 49-56. Springer, 2009. Google Scholar
  11. A. Cesta, A. Finzi, S. Fratini, A. Orlandini, and E. Tronci. Analyzing Flexible Timeline-Based Plans. In Proc. of the 19th ECAI, volume 215 of Frontiers in Artificial Intelligence and Applications, pages 471-476. IOS Press, 2010. Google Scholar
  12. S. Chien, D. Tran, G. Rabideau, S.R. Schaffer, D. Mandl, and S. Frye. Timeline-Based Space Operations Scheduling with External Constraints. In Proc. of the 20th ICAPS, pages 34-41. AAAI, 2010. Google Scholar
  13. M. Cialdea Mayer and A. Orlandini. An Executable Semantics of Flexible Plans in Terms of Timed Game Automata. In Proc. of the 22nd TIME, pages 160-169. IEEE Computer Society, 2015. Google Scholar
  14. M. Cialdea Mayer, A. Orlandini, and A. Ubrico. A Formal Account of Planning with Flexible Timelines. In Proc. of the 21st TIME, pages 37-46. IEEE Computer Society, 2014. Google Scholar
  15. M. Cialdea Mayer, A. Orlandini, and A. Umbrico. Planning and Execution with Flexible Timelines: a Formal Account. Acta Informatica, 53(6-8):649-680, 2016. Google Scholar
  16. A. Cimatti, A. Micheli, and M. Roveri. Timelines with Temporal Uncertainty. In Proc. of the 27th AAAI, 2013. Google Scholar
  17. M. Fox and D. Long. PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains. Journal of Artificial Intelligence Research, 20:61-124, 2003. Google Scholar
  18. J. Frank and A. Jónsson. Constraint-based Attribute and Interval Planning. Constraints, 8(4):339-364, 2003. Google Scholar
  19. G. Geeraerts, J.F. Raskin, and N. Sznajder. Event Clock Automata: From Theory to Practice. In Proc. of the 9th FORMATS, LNCS 6919, pages 209-224. Springer, 2011. Google Scholar
  20. N. Gigante, A. Montanari, M. Cialdea Mayer, and A. Orlandini. Timelines are Expressive Enough to Capture Action-based Temporal Planning. In Proc. of the 23rd TIME, pages 100-109. IEEE Computer Society, 2016. Google Scholar
  21. N. Gigante, A. Montanari, M. Cialdea Mayer, and A. Orlandini. Complexity of Timeline-Based Planning. In Proc. of the 27th ICAPS, pages 116-124. AAAI Press, 2017. Google Scholar
  22. D. Harel. Algorithmics: The spirit of computing. Wesley, 2nd edition, 1992. Google Scholar
  23. A. K. Jónsson, P. H. Morris, N. Muscettola, K. Rajan, and B. D. Smith. Planning in Interplanetary Space: Theory and Practice. In Proc. of the 5th AIPS, pages 177-186. AAAI, 2000. Google Scholar
  24. M. L. Minsky. Computation: Finite and Infinite Machines. Prentice-Hall, Inc., 1967. Google Scholar
  25. N. Muscettola. HSTS: Integrating Planning and Scheduling. In Intelligent Scheduling, pages 169-212. Morgan Kaufmann, 1994. Google Scholar
  26. J. Ouaknine and J. Worrell. On Metric Temporal Logic and Faulty Turing Machines. In Proc. of the 9th FOSSACS, LNCS 3921, pages 217-230. Springer, 2006. Google Scholar
  27. J. Ouaknine and J. Worrell. On the decidability and complexity of Metric Temporal Logic over finite words. Logical Methods in Computer Science, 3(1), 2007. Google Scholar
  28. J. Rintanen. Complexity of Concurrent Temporal Planning. In Proc. of the 17th ICAPS, pages 280-287. AAAI, 2007. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact