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.
Della Penna, G., Intrigila, B., Magazzeni, D., & Mercorio, F. (2015). Synthesis of cost-optimal strong plans in non-deterministic domains. INTERNATIONAL JOURNAL ON ARTIFICIAL INTELLIGENCE TOOLS, 24(6), 1-45 [10.1142/S0218213015500256].
|Citazione:||Della Penna, G., Intrigila, B., Magazzeni, D., & Mercorio, F. (2015). Synthesis of cost-optimal strong plans in non-deterministic domains. INTERNATIONAL JOURNAL ON ARTIFICIAL INTELLIGENCE TOOLS, 24(6), 1-45 [10.1142/S0218213015500256].|
|Tipo:||Articolo in rivista - Articolo scientifico|
|Carattere della pubblicazione:||Scientifica|
|Presenza di un coautore afferente ad Istituzioni straniere:||Si|
|Titolo:||Synthesis of cost-optimal strong plans in non-deterministic domains|
|Autori:||Della Penna, G; Intrigila, B; Magazzeni, D; Mercorio, F|
|Data di pubblicazione:||2015|
|Rivista:||INTERNATIONAL JOURNAL ON ARTIFICIAL INTELLIGENCE TOOLS|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1142/S0218213015500256|
|Appare nelle tipologie:||01 - Articolo su rivista|