Cost-Optimal Strong Planning in Non-Deterministic Domains

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.