Many real world domains present a non-deterministic behaviour, mostly due to unpredictable environmental conditions. In this context, strong planning, i.e., finding a plan which is guaranteed to achieve the goal regardless of non-determinism, is a significant research challenge for both the planning and the control communities. In particular, the problem of cost-optimal strong planning has not been addressed so far. In this paper we provide a formal description of the cost-optimal strong planning problem in non-deterministic finite state systems, present an algorithm to solve it with good complexity bounds and formally prove the correctness and completeness of the proposed algorithm. Furthermore, we present experimental results showing the effectiveness of the proposed approach on a meaningful case study.

Della Penna, G., Intrigila, B., Magazzeni, D., Mercorio, F., Tronci, E. (2011). Cost-Optimal Strong Planning in Non-Deterministic Domains. In Proceedings of the 8th International Conference on Informatics in Control, Automation and Robotics (ICINCO) (pp.56-66). SciTePress [10.5220/0003448200560066].

Cost-Optimal Strong Planning in Non-Deterministic Domains

MERCORIO, FABIO;
2011

Abstract

Many real world domains present a non-deterministic behaviour, mostly due to unpredictable environmental conditions. In this context, strong planning, i.e., finding a plan which is guaranteed to achieve the goal regardless of non-determinism, is a significant research challenge for both the planning and the control communities. In particular, the problem of cost-optimal strong planning has not been addressed so far. In this paper we provide a formal description of the cost-optimal strong planning problem in non-deterministic finite state systems, present an algorithm to solve it with good complexity bounds and formally prove the correctness and completeness of the proposed algorithm. Furthermore, we present experimental results showing the effectiveness of the proposed approach on a meaningful case study.
No
paper
Non-Deterministic Systems; Strong Planning; Optimal Planning
English
The International Conference on Informatics in Control, Automation and Robotics (ICINCO) - 28/31 July
978-989-8425-74-4
Della Penna, G., Intrigila, B., Magazzeni, D., Mercorio, F., Tronci, E. (2011). Cost-Optimal Strong Planning in Non-Deterministic Domains. In Proceedings of the 8th International Conference on Informatics in Control, Automation and Robotics (ICINCO) (pp.56-66). SciTePress [10.5220/0003448200560066].
Della Penna, G; Intrigila, B; Magazzeni, D; Mercorio, F; Tronci, E
File in questo prodotto:
File Dimensione Formato  
ICINCO_2011_62_CR.pdf

accesso aperto

Dimensione 123.58 kB
Formato Adobe PDF
123.58 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/30384
Citazioni
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 3
Social impact