Qualitative and Probabilistic Uncertainty in Reasoning about Actions with Sensing

Abstract

We present the description logic PN-ALCK_NF^alpha for reasoning about actions with sensing under qualitative and probabilistic uncertainty, which is an extension of the description logic ALCK_NF^alpha by actions with nondeterministic and probabilistic effects. We define a formal semantics of PN-ALCK_NF^alpha in terms of deterministic, nondeterministic, and probabilistic transitions between epistemic states, which are sets of possible states of the world. We introduce the notions of a conditional plan and its goodness under qualitative and probabilistic uncertainty. We then formulate the problem of conditional planning in this framework, and we present an algorithm for solving it. This algorithm is based on a reduction to reasoning in description logics, and is shown to be sound and complete in the sense that it generates all optimal plans. We also describe an application in a robotic-soccer scenario.