Reasoning about Actions with Sensing under Qualitative and Probabilistic Uncertainty

Abstract

We focus on the aspect of sensing in reasoning about actions under qualitative and probabilistic uncertainty. We extend an A-related action language by actions with nondeterministic and probabilistic effects, and define a formal semantics in terms of deterministic, nondeterministic, and probabilistic transitions between epistemic states. We then introduce the notions of a conditional plan and its goodness in this framework, and we formulate the conditional planning problem. We present an algorithm for solving it, which is proved to be sound and complete in the sense that it produces all optimal plans. We also report on a first prototype implementation of this algorithm. An application in a robotic-soccer scenario underlines the usefulness of our formalism in realistic applications.