Synthesis of Cost-Optimal Strong Plans in Non-Deterministic Domains

Giuseppe Della Penna; Bedenetto Intrigila; Daniele Magazzeni; Fabio Mercorio

doi:10.1142/S0218213015500256

Synthesis of Cost-Optimal Strong Plans in Non-Deterministic Domains

Giuseppe Della Penna, Bedenetto Intrigila, Daniele Magazzeni, Fabio Mercorio

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Article number	1550025
Journal	INTERNATIONAL JOURNAL ON ARTIFICIAL INTELLIGENCE TOOLS
Volume	24
Issue number	6
DOIs	https://doi.org/10.1142/S0218213015500256
Publication status	Published - 21 Dec 2015

Keywords

Cost-optimal strong planning
explicit model checking
non-deterministic systems

Access to Document

10.1142/S0218213015500256

Cite this

@article{94a72d080dda405ab74a95c71bfdabcf,

title = "Synthesis of Cost-Optimal Strong Plans in Non-Deterministic Domains",

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.",

keywords = "Cost-optimal strong planning, explicit model checking, non-deterministic systems",

author = "Penna, {Giuseppe Della} and Bedenetto Intrigila and Daniele Magazzeni and Fabio Mercorio",

year = "2015",

month = dec,

day = "21",

doi = "10.1142/S0218213015500256",

language = "English",

volume = "24",

journal = "INTERNATIONAL JOURNAL ON ARTIFICIAL INTELLIGENCE TOOLS",

issn = "0218-2130",

publisher = "World Scientific Publishing Co. Pte Ltd",

number = "6",

}

TY - JOUR

T1 - Synthesis of Cost-Optimal Strong Plans in Non-Deterministic Domains

AU - Penna, Giuseppe Della

AU - Intrigila, Bedenetto

AU - Magazzeni, Daniele

AU - Mercorio, Fabio

PY - 2015/12/21

Y1 - 2015/12/21

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

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

KW - Cost-optimal strong planning

KW - explicit model checking

KW - non-deterministic systems

UR - http://www.scopus.com/inward/record.url?scp=84951286299&partnerID=8YFLogxK

U2 - 10.1142/S0218213015500256

DO - 10.1142/S0218213015500256

M3 - Article

SN - 0218-2130

VL - 24

JO - INTERNATIONAL JOURNAL ON ARTIFICIAL INTELLIGENCE TOOLS

JF - INTERNATIONAL JOURNAL ON ARTIFICIAL INTELLIGENCE TOOLS

IS - 6

M1 - 1550025

ER -

Synthesis of Cost-Optimal Strong Plans in Non-Deterministic Domains

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this