Synthesis of cost-optimal strong plans in non-deterministic domains

Automatic planning tools can be a valuable aid to build control systems for a wide range of everyday appliances. Many systems which interact with the real world present a non-deterministic behaviour, often made more complex by nonlinear continuous dynamics. In this context, strong planning, which requires finding a plan that is guaranteed to achieve the goal regardless of non-determinism, plays an important role. With the increasing need for optimising the use of resources, finding strong solutions while minimising a cost function appears a significant research challenge, which has not previously been addressed. In this paper we provide a formal description of the cost-optimal strong planning problem and present an algorithm to solve it with good complexity bounds. The algorithm correctness and completeness are formally proved, and its implementation in the disk-based SUPMurphi tool is described. Finally, two meaningful case studies are presented to show the effectiveness of the proposed approach compared with a state-of-the-art strong planning tool.