article · International Journal of Intelligent Systems · 1997

Planning with graded nondeterministic actions: A possibilistic approach

Célia da Costa Pereira, Fr�d�rick Garcia, J�r�me Lang, Roger Martin-Clouaire

Cited by 18Abstract and details only

Abstract

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.

Cite this paper

APA 7

Pereira, C. D. C., Garcia, F., Lang, J., & Martin-Clouaire, R. (1997). Planning with graded nondeterministic actions: A possibilistic approach. International Journal of Intelligent Systems, 12(11-12), 935–962. https://doi.org/10.1002/(sici)1098-111x(199711/12)12:11/12<935::aid-int9>3.0.co;2-y

MLA 9

Pereira, Célia da Costa, et al. “Planning with graded nondeterministic actions: A possibilistic approach.” International Journal of Intelligent Systems, vol. 12, no. 11-12, 1997, pp. 935–62, https://doi.org/10.1002/(sici)1098-111x(199711/12)12:11/12<935::aid-int9>3.0.co;2-y.

Chicago

Pereira, Célia da Costa, Fr�d�rick Garcia, J�r�me Lang, and Roger Martin-Clouaire. 1997. “Planning with graded nondeterministic actions: A possibilistic approach.” International Journal of Intelligent Systems 12 (11-12): 935–62. https://doi.org/10.1002/(sici)1098-111x(199711/12)12:11/12<935::aid-int9>3.0.co;2-y.

Harvard

Pereira, C.D.C. et al. (1997) ‘Planning with graded nondeterministic actions: A possibilistic approach’, International Journal of Intelligent Systems, 12(11-12), pp. 935–962. Available at: https://doi.org/10.1002/(sici)1098-111x(199711/12)12:11/12<935::aid-int9>3.0.co;2-y.

BibTeX

@article{pereira1997planning,
  title = {{Planning with graded nondeterministic actions: A possibilistic approach}},
  author = {Pereira, Célia da Costa and Garcia, Fr�d�rick and Lang, J�r�me and Martin-Clouaire, Roger},
  journal = {International Journal of Intelligent Systems},
  volume = {12},
  number = {11-12},
  pages = {935--962},
  year = {1997},
  doi = {10.1002/(sici)1098-111x(199711/12)12:11/12<935::aid-int9>3.0.co;2-y}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.