Document Open Access Logo

Complexity of Qualitative Timeline-Based Planning

Authors Dario Della Monica , Nicola Gigante , Salvatore La Torre , Angelo Montanari

PDF
Thumbnail PDF

File

LIPIcs.TIME.2020.16.pdf
  • Filesize: 0.49 MB
  • 13 pages

Document Identifiers

Author Details

Dario Della Monica
  • University of Udine, Italy
Nicola Gigante
  • University of Udine, Italy
Salvatore La Torre
  • University of Salerno, Italy
Angelo Montanari
  • University of Udine, Italy

Funding

The authors acknowledge the partial support by the Italian INdAM-GNCS project Ragionamento Strategico e Sintesi Automatica di Sistemi Multi-Agente. Nicola Gigante and Angelo Montanari are partially supported by the PRID project ENCASE - Efforts in the uNderstanding of Complex interActing SystEms.

Cite AsGet BibTex

Dario Della Monica, Nicola Gigante, Salvatore La Torre, and Angelo Montanari. Complexity of Qualitative Timeline-Based Planning. In 27th International Symposium on Temporal Representation and Reasoning (TIME 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 178, pp. 16:1-16:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.TIME.2020.16

Abstract

The timeline-based approach to automated planning was originally developed in the context of space missions. In this approach, problem domains are expressed as systems consisting of independent but interacting components whose behaviors over time, the timelines, are governed by a set of temporal constraints, called synchronization rules. Although timeline-based system descriptions have been successfully used in practice for decades, the research on the theoretical aspects only started recently. In the last few years, some interesting results have been shown concerning both its expressive power and the computational complexity of the related planning problem. In particular, the general problem has been proved to be EXPSPACE-complete. Given the applicability of the approach in many practical scenarios, it is thus natural to ask whether computationally simpler but still expressive fragments can be identified. In this paper, we study the timeline-based planning problem with the restriction that only qualitative synchronization rules, i.e., rules without explicit time bounds in the constraints, are allowed. We show that the problem becomes PSPACE-complete.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Temporal reasoning
Keywords
  • Timeline-based planning
  • qualitative temporal constraints
  • complexity

Metrics

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

References

  1. James F. Allen. Maintaining knowledge about temporal intervals. Communications of the ACM, 26(11):832-843, 1983. URL: https://doi.org/10.1145/182.358434.
  2. Javier Barreiro, Matthew Boyce, Minh Do, Jeremy Frank, Michael Iatauro, Tatiana Kichkaylo, Paul Morris, James Ong, Emilio Remolina, Tristan Smith, and David Smith. EUROPA: A Platform for AI Planning, Scheduling, Constraint Programming, and Optimization. In Proceedings of the 4th International Competition on Knowledge Engineering for Planning and Scheduling, 2012. Google Scholar
  3. S. Chien, G. Rabideau, R. Knight, R. Sherwood, B. Engelhardt, D. Mutz, T. Estlin, B. Smith, F. Fisher, T. Barrett, G. Stebbins, and D. Tran. Aspen - automating space mission operations using automated planning and scheduling. In Proceedings of the International Conference on Space Operations, 2000. Google Scholar
  4. Steve A. Chien, Gregg Rabideau, Daniel Tran, Martina Troesch, Joshua Doubleday, Federico Nespoli, Miguel Perez Ayucar, Marc Costa Sitja, Claire Vallat, Bernhard Geiger, Nico Altobelli, Manuel Fernandez, Fran Vallejo, Rafael Andres, and Michael Kueppers. Activity-based scheduling of science campaigns for the rosetta orbiter. In Proceedings of the 24th International Joint Conference on Artificial Intelligence, pages 4416-4422. AAAI Press, 2015. Google Scholar
  5. Dario Della Monica, Nicola Gigante, Angelo Montanari, and Pietro Sala. A novel automata-theoretic approach to timeline-based planning. In Michael Thielscher, Francesca Toni, and Frank Wolter, editors, Proceedings of the 16th International Conference on Principles of Knowledge Representation and Reasoning, pages 541-550. AAAI Press, 2018. Google Scholar
  6. Alessandro Donati, Nicola Policella, Erhard Rabenau, Giovanni Righini, and Emanuele Tresoldi. An automatic planning and scheduling system for the mars express uplink scheduling problem. IEEE Transactions on Systems, Man, and Cybernetics, Part C, 41(6):942-954, 2011. URL: https://doi.org/10.1109/TSMCC.2011.2114880.
  7. Richard Fikes and Nils J. Nilsson. STRIPS: A new approach to the application of theorem proving to problem solving. Artificial Intelligence, 2(3/4):189-208, 1971. URL: https://doi.org/10.1016/0004-3702(71)90010-5.
  8. Simone Fratini, Amedeo Cesta, Andrea Orlandini, Riccardo Rasconi, and Riccardo De Benedictis. Apsi-based deliberation in goal oriented autonomous controllers. In ASTRA 2011, volume 11. ESA, 2011. Google Scholar
  9. Simone Fratini and L. Donati. Apsi timeline representation framework v. 3.0. Technical report, European Space Agency - ESOC, 2011. Google Scholar
  10. Malik Ghallab, Dana S. Nau, and Paolo Traverso. Automated Planning and Acting. Cambridge University Press, 2016. URL: http://www.cambridge.org/de/academic/subjects/computer-science/artificial-intelligence-and-natural-language-processing/automated-planning-and-acting?format=HB.
  11. Nicola Gigante, Angelo Montanari, Marta Cialdea Mayer, and Andrea Orlandini. Timelines are expressive enough to capture action-based temporal planning. In Curtis E. Dyreson, Michael R. Hansen, and Luke Hunsberger, editors, Proceedings of the 23rd International Symposium on Temporal Representation and Reasoning, pages 100-109. IEEE Computer Society, 2016. URL: https://doi.org/10.1109/TIME.2016.18.
  12. Nicola Gigante, Angelo Montanari, Marta Cialdea Mayer, and Andrea Orlandini. Complexity of timeline-based planning. In Laura Barbulescu, Jeremy Frank, Mausam, and Stephen F. Smith, editors, Proceedings of the 27th International Conference on Automated Planning and Scheduling, pages 116-124. AAAI Press, 2017. Google Scholar
  13. Nicola Gigante, Angelo Montanari, Andrea Orlandini, Marta Cialdea Mayer, and Mark Reynolds. On timeline-based games and their complexity. Theor. Comput. Sci., 815:247-269, 2020. URL: https://doi.org/10.1016/j.tcs.2020.02.011.
  14. John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to automata theory, languages, and computation, 3rd Edition. Pearson international edition. Addison-Wesley, 2007. Google Scholar
  15. Drew McDermott, Malik Ghallab, Adele Howe, Craig Knoblock, Ashwin Ram, Manuela Veloso, Daniel Weld, and David Wilkins. PDDL - The Planning Domain Definition Language. Technical Report Technical Report TR98003, Yale Center for Computational Vision and Control, 1997. Google Scholar
  16. Nicola Muscettola. HSTS: Integrating Planning and Scheduling. In Monte Zweben and Mark S. Fox, editors, Intelligent Scheduling, chapter 6, pages 169-212. Morgan Kaufmann, 1994. 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 Imprint Privacy Contact