Premium
Planning with graded nondeterministic actions: A possibilistic approach
Author(s) -
Da Costa Pereira Célia,
Garcia Frédérick,
Lang Jérôme,
MartinClouaire Roger
Publication year - 1997
Publication title -
international journal of intelligent systems
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.291
H-Index - 87
eISSN - 1098-111X
pISSN - 0884-8173
DOI - 10.1002/(sici)1098-111x(199711/12)12:11/12<935::aid-int9>3.0.co;2-y
Subject(s) - nondeterministic algorithm , certainty , computer science , mathematical optimization , automated planning and scheduling , mathematics , integrated business planning , formalism (music) , algorithm , artificial intelligence , art , musical , management , economics , visual arts , geometry
This article proposes a framework for planning under uncertainty given a partially known initial state and a set of actions having nondeterministic (disjunctive) effects, some being more possible (normal) than the others. The problem, henceforth called possibilistic planning problem, is represented in an extension of the STRIPS formalism in which the initial state of the world and the graded nondeterministic effects of actions are described by possibility distributions. Two notions of solution plans are introduced: γ‐ acceptable plans that lead to a goal state with a certainty greater than a given threshold γ, and optimally safe plans that lead to a goal state with maximal certainty. It is shown that the search of a γ‐acceptable plan amounts to solve a derived planning problem that has only pure (nongraded) nondeterministic actions. A sound and complete partial order planning algorithm, called NDP, has been developed for such classical nondeterministic planning problems. The generation of γ‐acceptable and optimally safe plans is achieved by two sound and complete planning algorithms: POSPLAN that relies on NDP, and POSPLAN* that can be seen as a hierarchical version of POSPLAN. The possibilistic planning framework is illustrated throughout the article by an example in the agronomic domain. © 1997 John Wiley & Sons, Inc.