COST-OPTIMAL STRONG PLANNING IN NON-DETERMINISTIC DOMAINS

Giuseppe Della Penna, Fabio Mercorio, Benedetto Intrigila, Daniele Magazzeni, Enrico Tronci

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.

Paper Citation

in Harvard Style

Della Penna G., Mercorio F., Intrigila B., Magazzeni D. and 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 - Volume 1: ICINCO, ISBN 978-989-8425-74-4, pages 56-66. DOI: 10.5220/0003448200560066

in Bibtex Style

@conference{icinco11,
author={Giuseppe Della Penna and Fabio Mercorio and Benedetto Intrigila and Daniele Magazzeni and Enrico Tronci},
title={COST-OPTIMAL STRONG PLANNING IN NON-DETERMINISTIC DOMAINS},
booktitle={Proceedings of the 8th International Conference on Informatics in Control, Automation and Robotics - Volume 1: ICINCO,},
year={2011},
pages={56-66},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0003448200560066},
isbn={978-989-8425-74-4},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 8th International Conference on Informatics in Control, Automation and Robotics - Volume 1: ICINCO,
TI - COST-OPTIMAL STRONG PLANNING IN NON-DETERMINISTIC DOMAINS
SN - 978-989-8425-74-4
AU - Della Penna G.
AU - Mercorio F.
AU - Intrigila B.
AU - Magazzeni D.
AU - Tronci E.
PY - 2011
SP - 56
EP - 66
DO - 10.5220/0003448200560066