Robustness envelopes for temporal plans

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

Abstract

To achieve practical execution, planners must produce temporal plans with some degree of run-time adaptability. Such plans can be expressed as Simple Temporal Networks (STN), that constrain the timing of action activations, and implicitly represent the space of choices for the plan executor. A first problem is to verify that all the executor choices allowed by the STN plan will be successful, i.e. the plan is valid. An even more important problem is to assess the effect of discrepancies between the model used for planning and the execution environment. We propose an approach to compute the 'robustness envelope' (i.e., alternative action durations or resource consumption rates) of a given STN plan, for which the plan remains valid. Plans can have boolean and numeric variables as well as discrete and continuous change. We leverage Satisfiability Modulo Theories (SMT) to make the approach formal and practical.
Original languageEnglish
Title of host publicationProceedings of the Thirty-Third AAAI Conference on Artificial Intelligence
Subtitle of host publicationAAAI Technical Track: Planning, Routing, and Scheduling
Place of PublicationMenlo Park, US-CA.
Number of pages8
Volume33
DOIs
Publication statusPublished - 1 Feb 2019
EventThirty-Third AAAI Conference on Artificial Intelligence (AAAI-19) - Honolulu, United States
Duration: 27 Jan 20191 Feb 2019

Conference

ConferenceThirty-Third AAAI Conference on Artificial Intelligence (AAAI-19)
Abbreviated titleAAAI-19
CountryUnited States
CityHonolulu
Period27/01/191/02/19

Fingerprint

Chemical activation
Planning

Keywords

  • simple temporal networks (STN)
  • temporal plans

Cite this

Cashmore, M., Cimatti, A., Magazzeni, D., Micheli, A., & Zehtabi, P. (2019). Robustness envelopes for temporal plans. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence : AAAI Technical Track: Planning, Routing, and Scheduling (Vol. 33). [6285] Menlo Park, US-CA.. https://doi.org/10.1609/aaai.v33i01.33017538
Cashmore, Michael ; Cimatti, Alessandro ; Magazzeni, Daniele ; Micheli, Andrea ; Zehtabi, Parisa. / Robustness envelopes for temporal plans. Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence : AAAI Technical Track: Planning, Routing, and Scheduling . Vol. 33 Menlo Park, US-CA., 2019.
@inproceedings{2b88c61b0dd54b58bd48e37321ee9e41,
title = "Robustness envelopes for temporal plans",
abstract = "To achieve practical execution, planners must produce temporal plans with some degree of run-time adaptability. Such plans can be expressed as Simple Temporal Networks (STN), that constrain the timing of action activations, and implicitly represent the space of choices for the plan executor. A first problem is to verify that all the executor choices allowed by the STN plan will be successful, i.e. the plan is valid. An even more important problem is to assess the effect of discrepancies between the model used for planning and the execution environment. We propose an approach to compute the 'robustness envelope' (i.e., alternative action durations or resource consumption rates) of a given STN plan, for which the plan remains valid. Plans can have boolean and numeric variables as well as discrete and continuous change. We leverage Satisfiability Modulo Theories (SMT) to make the approach formal and practical.",
keywords = "simple temporal networks (STN), temporal plans",
author = "Michael Cashmore and Alessandro Cimatti and Daniele Magazzeni and Andrea Micheli and Parisa Zehtabi",
year = "2019",
month = "2",
day = "1",
doi = "10.1609/aaai.v33i01.33017538",
language = "English",
volume = "33",
booktitle = "Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence",

}

Cashmore, M, Cimatti, A, Magazzeni, D, Micheli, A & Zehtabi, P 2019, Robustness envelopes for temporal plans. in Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence : AAAI Technical Track: Planning, Routing, and Scheduling . vol. 33, 6285, Menlo Park, US-CA., Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19) , Honolulu, United States, 27/01/19. https://doi.org/10.1609/aaai.v33i01.33017538

Robustness envelopes for temporal plans. / Cashmore, Michael; Cimatti, Alessandro; Magazzeni, Daniele; Micheli, Andrea; Zehtabi, Parisa.

Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence : AAAI Technical Track: Planning, Routing, and Scheduling . Vol. 33 Menlo Park, US-CA., 2019. 6285.

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

TY - GEN

T1 - Robustness envelopes for temporal plans

AU - Cashmore, Michael

AU - Cimatti, Alessandro

AU - Magazzeni, Daniele

AU - Micheli, Andrea

AU - Zehtabi, Parisa

PY - 2019/2/1

Y1 - 2019/2/1

N2 - To achieve practical execution, planners must produce temporal plans with some degree of run-time adaptability. Such plans can be expressed as Simple Temporal Networks (STN), that constrain the timing of action activations, and implicitly represent the space of choices for the plan executor. A first problem is to verify that all the executor choices allowed by the STN plan will be successful, i.e. the plan is valid. An even more important problem is to assess the effect of discrepancies between the model used for planning and the execution environment. We propose an approach to compute the 'robustness envelope' (i.e., alternative action durations or resource consumption rates) of a given STN plan, for which the plan remains valid. Plans can have boolean and numeric variables as well as discrete and continuous change. We leverage Satisfiability Modulo Theories (SMT) to make the approach formal and practical.

AB - To achieve practical execution, planners must produce temporal plans with some degree of run-time adaptability. Such plans can be expressed as Simple Temporal Networks (STN), that constrain the timing of action activations, and implicitly represent the space of choices for the plan executor. A first problem is to verify that all the executor choices allowed by the STN plan will be successful, i.e. the plan is valid. An even more important problem is to assess the effect of discrepancies between the model used for planning and the execution environment. We propose an approach to compute the 'robustness envelope' (i.e., alternative action durations or resource consumption rates) of a given STN plan, for which the plan remains valid. Plans can have boolean and numeric variables as well as discrete and continuous change. We leverage Satisfiability Modulo Theories (SMT) to make the approach formal and practical.

KW - simple temporal networks (STN)

KW - temporal plans

U2 - 10.1609/aaai.v33i01.33017538

DO - 10.1609/aaai.v33i01.33017538

M3 - Conference contribution book

VL - 33

BT - Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence

CY - Menlo Park, US-CA.

ER -

Cashmore M, Cimatti A, Magazzeni D, Micheli A, Zehtabi P. Robustness envelopes for temporal plans. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence : AAAI Technical Track: Planning, Routing, and Scheduling . Vol. 33. Menlo Park, US-CA. 2019. 6285 https://doi.org/10.1609/aaai.v33i01.33017538