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].

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

MERCORIO, FABIO
2015

Abstract

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.
Articolo in rivista - Articolo scientifico
Cost-optimal strong planning; explicit model checking; non-deterministic systems;
Cost-optimal strong planning; explicit model checking; non-deterministic systems
English
dic-2015
2015
24
6
1
45
1550025
none
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].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/99062
Citazioni
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
Social impact