Document Open Access Logo

Olisipo: A Probabilistic Approach to the Adaptable Execution of Deterministic Temporal Plans

Authors Tomás Ribeiro, Oscar Lima, Michael Cashmore, Andrea Micheli , Rodrigo Ventura

PDF
Thumbnail PDF

File

LIPIcs.TIME.2021.15.pdf
  • Filesize: 1.39 MB
  • 15 pages

Document Identifiers

Author Details

Tomás Ribeiro
  • Institute for Systems and Robotics, Instituto Superior Tecnico, Lisbon, Portugal
Oscar Lima
  • DFKI German Research Center for Artificial Intelligence, Saabrücken, Germany
Michael Cashmore
  • University of Strathclyde, Glasgow, UK
Andrea Micheli
  • Fondazione Bruno Kessler, Trento, Italy
Rodrigo Ventura
  • Institute for Systems and Robotics, Instituto Superior Tecnico, Lisbon, Portugal

Acknowledgements

The open access publication of this article was supported by the Alpen-Adria-Universität Klagenfurt, Austria.

Cite AsGet BibTex

Tomás Ribeiro, Oscar Lima, Michael Cashmore, Andrea Micheli, and Rodrigo Ventura. Olisipo: A Probabilistic Approach to the Adaptable Execution of Deterministic Temporal Plans. In 28th International Symposium on Temporal Representation and Reasoning (TIME 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 206, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.TIME.2021.15

Abstract

The robust execution of a temporal plan in a perturbed environment is a problem that remains to be solved. Perturbed environments, such as the real world, are non-deterministic and filled with uncertainty. Hence, the execution of a temporal plan presents several challenges and the employed solution often consists of replanning when the execution fails. In this paper, we propose a novel algorithm, named Olisipo, which aims to maximise the probability of a successful execution of a temporal plan in perturbed environments. To achieve this, a probabilistic model is used in the execution of the plan, instead of in the building of the plan. This approach enables Olisipo to dynamically adapt the plan to changes in the environment. In addition to this, the execution of the plan is also adapted to the probability of successfully executing each action. Olisipo was compared to a simple dispatcher and it was shown that it consistently had a higher probability of successfully reaching a goal state in uncertain environments, performed fewer replans and also executed fewer actions. Hence, Olisipo offers a substantial improvement in performance for disturbed environments.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Robotic planning
Keywords
  • Temporal Planning
  • Temporal Plan Execution
  • Robotics

Metrics

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

Supplementary Materials

References

  1. Christer Bäckström. Computational aspects of reordering plans. Journal of Artificial Intelligence Research, 9:99-137, 1998. Google Scholar
  2. Craig Boutilier, Thomas Dean, and Steve Hanks. Decision-theoretic planning: Structural assumptions and computational leverage. Journal of Artificial Intelligence Research, 11:1-94, 1999. Google Scholar
  3. Michael Cashmore, Alessandro Cimatti, Daniele Magazzeni, , Andrea Micheli, and Parisa Zehtabi. Robustness envelopes for temporal plans. In AAAI, 2019. Google Scholar
  4. Michael Cashmore, Andrew Coles, Bence Cserna, Erez Karpas, Daniele Magazzeni, and Wheeler Ruml. Replanning for situated robots. In J. Benton, Nir Lipovetzky, Eva Onaindia, David E. Smith, and Siddharth Srivastava, editors, Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling, ICAPS 2018, Berkeley, CA, USA, July 11-15, 2019, pages 665-673. AAAI Press, 2019. URL: https://aaai.org/ojs/index.php/ICAPS/article/view/3534.
  5. Michael Cashmore, Maria Fox, Derek Long, Daniele Magazzeni, Bram Ridder, Arnau Carrera, Narcis Palomeras, Natalia Hurtos, and Marc Carreras. Rosplan: Planning in the robot operating system. In ICAPS, 2015. Google Scholar
  6. A. Cesta, G. Cortellessa, S. Fratini, A. Oddi, and R. Rasconi. The APSI Framework: a Planning and Scheduling Software Development Environment. In ICAPS (Application Showcase), 2009. Google Scholar
  7. Alessandro Cimatti, Minh Do, Andrea Micheli, Marco Roveri, and David E. Smith. Strong temporal planning with uncontrollable durations. Artif. Intell., 256:1-34, 2018. URL: https://doi.org/10.1016/j.artint.2017.11.006.
  8. Amanda Coles, Andrew Coles, Maria Fox, and Derek Long. Forward-chaining partial-order planning. ICAPS 2010 - Proceedings of the 20th International Conference on Automated Planning and Scheduling, pages 42-49, January 2010. Google Scholar
  9. Patrick R. Conrad and Brian Charles Williams. Drake: An efficient executive for temporal plans with choice. J. Artif. Intell. Res., 42:607-659, 2011. URL: https://doi.org/10.1613/jair.3478.
  10. Paul Dagum, Adam Galper, and Eric Horvitz. Dynamic network models for forecasting. In Uncertainty in Artificial Intelligence, pages 41-48. Morgan Kaufmann, 1992. URL: https://doi.org/10.1016/B978-1-4832-8287-9.50010-4.
  11. Rina Dechter, Itay Meiri, and Judea Pearl. Temporal constraint networks. Artificial intelligence, 1991. Google Scholar
  12. M. Do and S. Kambhampati. Improving temporal flexibility of position constrained metric temporal plans. In ICAPS, pages 42-51, 2003. Google Scholar
  13. Maria Fox, Alfonso Gerevini, Derek Long, and Ivan Serina. Plan stability: Replanning versus plan repair. In Derek Long, Stephen F. Smith, Daniel Borrajo, and Lee McCluskey, editors, Proceedings of the Sixteenth International Conference on Automated Planning and Scheduling, ICAPS 2006, Cumbria, UK, June 6-10, 2006, pages 212-221. AAAI, 2006. Google Scholar
  14. Maria Fox and Derek Long. PDDL2.1: An extension to PDDL for expressing temporal planning domains. Journal of artificial intelligence research, 2003. Google Scholar
  15. J. Frank and A. Jónsson. Constraint-based Attribute and Interval Planning. Constraints, 8(4):339-364, 2003. Google Scholar
  16. J. Frank and P. Morris. Bounding the resource availability of activities with linear resource impact. In ICAPS, pages 136-143, 2007. Google Scholar
  17. M. Ghallab, D. Nau, and P. Traverso. Automated Planning: Theory and Practice. Elsevier, 2004. Google Scholar
  18. Félix Ingrand and Malik Ghallab. Deliberation for autonomous robots: A survey. Artif. Intell., 247:10-44, 2017. Google Scholar
  19. Ailsa H. Land and Alison G. Doig. An automatic method for solving discrete programming problems. In Michael Jünger, Thomas M. Liebling, Denis Naddef, George L. Nemhauser, William R. Pulleyblank, Gerhard Reinelt, Giovanni Rinaldi, and Laurence A. Wolsey, editors, 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art, pages 105-132. Springer Berlin Heidelberg, Berlin, Heidelberg, 2010. URL: https://doi.org/10.1007/978-3-540-68279-0_5.
  20. Steven Levine and Brian Williams. Watching and acting together: Concurrent plan recognition and adaptation for human-robot teams. Journal of Artificial Intelligence Research, 63, 2018. Google Scholar
  21. Oscar Lima, Michael Cashmore, Daniele Magazzeni, Andrea Micheli, and Rodrigo Ventura. Robust plan execution with unexpected observations. CoRR, abs/2003.09401, 2020. URL: http://arxiv.org/abs/2003.09401.
  22. Paul Morris. Dynamic controllability and dispatchability relationships. In Helmut Simonis, editor, Integration of AI and OR Techniques in Constraint Programming, pages 464-479, Cham, 2014. Springer International Publishing. Google Scholar
  23. Paul H. Morris and Nicola Muscettola. Execution of temporal plans with uncertainty. In Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on on Innovative Applications of Artificial Intelligence, July 30 - August 3, 2000, Austin, Texas, USA., pages 491-496, 2000. Google Scholar
  24. Nicola Muscettola, Paul H. Morris, and Ioannis Tsamardinos. Reformulating temporal plans for efficient execution. In Proceedings of the Sixth International Conference on Principles of Knowledge Representation and Reasoning (KR'98), Trento, Italy, June 2-5, 1998., pages 444-452, 1998. Google Scholar
  25. Morgan Quigley, Brian Gerkey, Ken Conley, Josh Faust, Tully Foote, Jeremy Leibs, Eric Berger, Rob Wheeler, and Andrew Ng. Ros: an open-source robot operating system. In Proc. of the IEEE Intl. Conf. on Robotics and Automation (ICRA) Workshop on Open Source Robotics, Kobe, Japan, 2009. Google Scholar
  26. Masood Feyzbakhsh Rankooh and Gholamreza Ghassem-Sani. Itsat: An efficient sat-based temporal planner. Journal of Artificial Intelligence Research, 53(1):541–632, 2015. Google Scholar
  27. T. Ribeiro, O. Lima, M. Cashmore, A.Micheli, and R. Ventura. Experimental material for "A Probabilistic Approach to the Adaptable Execution of Deterministic Temporal Plans". URL: https://github.com/TomasRibeiro96/Olisipo-planner.
  28. Ioannis Tsamardinos and Martha E. Pollack. Efficient solution techniques for disjunctive temporal reasoning problems. Artif. Intell., 151(1-2):43-89, 2003. URL: https://doi.org/10.1016/S0004-3702(03)00113-9.
  29. Edwin B. Wilson. Probable inference, the law of succession, and statistical inference. Journal of the American Statistical Association, 22(158):209-212, 1927. URL: https://doi.org/10.1080/01621459.1927.10502953.
  30. Sung Yoon, Alan Fern, and Robert Givan. Ff-replan: A baseline for probabilistic planning. ICAPS 2007, pages 352-, 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 Imprint Privacy Contact