Document Open Access Logo

Efficient Anytime Computation and Execution of Decoupled Robustness Envelopes for Temporal Plans

Authors Michael Cashmore , Alessandro Cimatti , Daniele Magazzeni , Andrea Micheli , Parisa Zehtabi

PDF

File

Thumbnail PDF
PDF
LIPIcs.TIME.2021.13.pdf
  • Filesize: 0.86 MB
  • 14 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Computing methodologies → Robotic planning
Keywords
  • Temporal Planning
  • Robustness Envelopes

Metrics

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

Abstract

One of the major limitations for the employment of model-based planning and scheduling in practical applications is the need of costly re-planning when an incongruence between the observed reality and the formal model is encountered during execution. Robustness Envelopes characterize the set of possible contingencies that a plan is able to address without re-planning, but their exact computation is expensive; furthermore, general robustness envelopes are not amenable for efficient execution.
In this paper, we present a novel, anytime algorithm to approximate Robustness Envelopes, making them scalable and executable. This is proven by an experimental analysis showing the efficiency of the algorithm, and by a concrete case study where the execution of robustness envelopes significantly reduces the number of re-plannings.

Cite As Get BibTex

Michael Cashmore, Alessandro Cimatti, Daniele Magazzeni, Andrea Micheli, and Parisa Zehtabi. Efficient Anytime Computation and Execution of Decoupled Robustness Envelopes for Temporal Plans. In 28th International Symposium on Temporal Representation and Reasoning (TIME 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 206, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.TIME.2021.13

Author Details

Michael Cashmore
  • Strathclyde University, Glasgow, UK
Alessandro Cimatti
  • Fondazione Bruno Kessler, Trento, Italy
Daniele Magazzeni
  • Kings College London, UK
Andrea Micheli
  • Fondazione Bruno Kessler, Trento, Italy
Parisa Zehtabi
  • Kings College London, UK

Acknowledgements

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

References

  1. C. Barrett, R. Sebastiani, S. Seshia, and C. Tinelli. Satisfiability modulo theories. In Handbook of Satisfiability, pages 825-885. IOS Press, 2009. Google Scholar
  2. M. Cashmore, A. Cimatti, D. Magazzeni, A. Micheli, and P.a Zehtabi. Robustness envelopes for temporal plans. In AAAI, 2019. Google Scholar
  3. M. Cashmore, M. Fox, D.Long, D. Magazzeni, B. Ridder, A. Carrera, N. Palomeras, N. Hurtós, and M. Carreras. Rosplan: Planning in the robot operating system. In Proceedings of the Twenty-Fifth International Conference on Automated Planning and Scheduling, ICAPS 2015, Jerusalem, Israel, June 7-11, 2015., pages 333-341, 2015. Google Scholar
  4. 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
  5. A. Cimatti, M. Do, A. Micheli, M. Roveri, and D. Smith. Strong temporal planning with uncontrollable durations. Artif. Intell., 256:1-34, 2018. URL: https://doi.org/10.1016/j.artint.2017.11.006.
  6. R. Dechter, I. Meiri, and J. Pearl. Temporal constraint networks. Artificial Intelligence, 49(1-3):61-95, 1991. URL: https://doi.org/10.1016/0004-3702(91)90006-6.
  7. M. Do and S. Kambhampati. Improving temporal flexibility of position constrained metric temporal plans. In ICAPS, pages 42-51, 2003. Google Scholar
  8. 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. URL: https://doi.org/10.1613/jair.1129.
  9. J. Frank and A. Jónsson. Constraint-based Attribute and Interval Planning. Constraints, 8(4):339-364, 2003. Google Scholar
  10. J. Frank and P. Morris. Bounding the resource availability of activities with linear resource impact. In ICAPS, pages 136-143, 2007. Google Scholar
  11. M. Ghallab and H. Laruelle. Representation and control in IxTeT, a temporal planner. In AIPS, pages 61-67, 1994. Google Scholar
  12. M. Ghallab, D. Nau, and P. Traverso. Automated planning - theory and practice. Elsevier, 2004. Google Scholar
  13. Félix Ingrand and Malik Ghallab. Deliberation for autonomous robots: A survey. Artificial Intelligence, 247:10-44, 2017. Google Scholar
  14. Mausam and A. Kolobov. Planning with markov decision processes: An ai perspective. Synthesis Lectures on Artificial Intelligence and Machine Learning, 6(1):1-210, 2012. URL: https://doi.org/10.2200/S00426ED1V01Y201206AIM017.
  15. N. Muscettola. Computing the envelope for stepwise-constant resource allocations. In CP, pages 139-154, 2002. Google Scholar
  16. T. Niemueller, G. Lakemeyer, and A. Ferrein. The robocup logistics league as a benchmark for planning in robotics. Planning and Robotics (PlanRob-15), page 63, 2015. Google Scholar
  17. N. Policella, S. Smith, A. Cesta, and A. Oddi. Generating robust schedules through temporal flexibility. In ICAPS, pages 209-218, 2004. Google Scholar
  18. A. Schrijver. Theory of Linear and Integer Programming. J. Wiley & Sons, 1998. Google Scholar
  19. A. Umbrico, A. Cesta, M. Cialdea Mayer, and A. Orlandini. Integrating resource management and timeline-based planning. In ICAPS, pages 264-272, 2018. Google Scholar
  20. B. Williams and V. Gupta. Unifying model-based and reactive programming within a model-based executive. In Workshop on Principles of Diagnosis, 1999. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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