Qualitative and probabilistic uncertainty in reasoning about actions with sensing

Luca Iocchi, Thomas Lukasiewicz, Daniele Nardi, Riccardo RosatiNMR 2004 · OpenReview

Introduction

In autonomous robotics, decision-making is often hampered by two distinct forms of uncertainty. The first is probabilistic uncertainty, where outcomes of actions are known but occur with specific frequencies (e.g., a kick having an 80% success rate). The second is qualitative (nondeterministic) uncertainty, where the robot faces purely unknown states without a known distribution (e.g., whether a ball is within a specific zone). Traditional AI planning frameworks typically prioritize one over the other. This paper introduces $PN\text{-}ALCK^\alpha_{NF}$, a novel description logic framework that treats these two types of uncertainty as orthogonal, allowing for robust planning in complex, real-world environments.

Methodology

The proposed framework extends the Description Logic (DL) $ALCK^\alpha_{NF}$ to incorporate actions with both nondeterministic and probabilistic effects. Central to this approach is the concept of an epistemic state, where the robot maintains a set of all possible worlds it might inhabit rather than a single definitive state.

Planning and Belief Trees

To generate and evaluate plans, the authors utilize "belief trees." These structures capture the branching paths created by sensing actions—which update the robot's knowledge without altering the physical world—and the probabilistic outcomes of physical actions.

Figure 4: Belief trees representing conditional plans with probabilistic and sensing outcomes.

The planning algorithm follows a three-stage process:

  1. First-Order Extension (FOE) Generation: Complex epistemic knowledge is reduced to a standard DL format.
  2. Plan Extraction: The simplified space is searched to identify all valid conditional plans (flowcharts of behavior).
  3. Optimal Selection: Plans are ranked using a "goodness" metric that calculates success probability while adopting a worst-case perspective on nondeterministic elements.

Case Study: RoboCup Soccer

The framework was evaluated using a scenario from the RoboCup Four-Legged League. A goalkeeper robot must decide between actions like diving, aligning, or kicking based on uncertain perception of the ball. This domain perfectly illustrates the need for the dual-uncertainty model: the ball's trajectory is probabilistic, while its initial presence in a "blind spot" is nondeterministic.

Key Results

The authors formally demonstrate the soundness and completeness of their algorithm, ensuring it identifies all optimal plans and that every identified plan is valid. In the soccer domain, the system successfully generated sophisticated conditional plans. For instance, a robot might sense if the ball is close; if so, it kicks; if not, it senses if the path is clear before choosing between a straight or side kick.

A significant technical contribution is the reduction of the planning problem to standard Description Logic reasoning. This allows the framework to leverage existing, highly-optimized DL solvers, bridging the gap between theoretical logic and practical robotic application.

Conclusion and Future Work

While $PN\text{-}ALCK^\alpha_{NF}$ provides a rigorous foundation for reasoning under mixed uncertainty, several avenues for future research remain. Currently, the model assumes "perfect" sensing; extending it to handle noisy or erroneous sensor data is a priority. Additionally, the current algorithm is limited to Directed Acyclic Graphs (DAGs), precluding cyclic plans (loops) necessary for repetitive tasks. Future work will also focus on the computational complexity and scalability of the FOE generation process in larger environments.

Summary updated

BibTeX
@inproceedings{iocchi2004qualitative,
  author = {Luca Iocchi and Thomas Lukasiewicz and Daniele Nardi and Riccardo Rosati},
  title = {{Qualitative and probabilistic uncertainty in reasoning about actions with sensing}},
  booktitle = {NMR},
  year = {2004},
  url = {https://openreview.net/forum?id=XE5dPk0nitN},
}
Figure