PREGO: An Action Language for Belief-Based Cognitive Robotics in Continuous Domains

Vaishak Belle, Hector J. LevesqueAAAI 2014 · DOI

Introduction

In cognitive robotics, a persistent gap exists between high-level logical reasoning and low-level probabilistic sensing. High-level systems, often based on formalisms like the Situation Calculus, excel at handling complex rules and dynamic environments but struggle with the inherent noise of the physical world. Conversely, probabilistic systems manage sensor noise and effector uncertainty effectively but often lack the expressive power to reason about context-dependent logical rules.

This paper introduces PREGO, an action language designed to bridge this divide. PREGO maintains the representational richness of logic while natively handling continuous probability distributions, allowing robots to reason about their beliefs in noisy, continuous environments.

The PREGO Framework

PREGO is grounded in a dialect of the Situation Calculus and utilizes a LISP-like syntax. Its primary innovation lies in its computational methodology for projection—calculating a robot's belief state after a sequence of actions.

The system relies on three key technical components:

  1. Successor State Axioms (SSAs): These provide a logical description of how the world changes, adapted to accommodate continuous variables.
  2. Modular Regression Operator ($R$): This operator transforms complex logical queries into purely mathematical integrands. By decoupling the logic from the probability calculation, PREGO avoids the need for theorem-proving during numerical evaluation.
  3. Numerical Evaluation via Monte Carlo Sampling: Once a query is regressed into a mathematical formula, the system uses Monte Carlo methods to compute the result. This approach allows PREGO to handle "mixed" distributions, such as discrete probabilities of hitting an obstacle combined with continuous distributions of the robot's position.

Experimental Evaluation

To evaluate PREGO, the authors utilized a simulated 1D robot domain. In this benchmark, a robot moves toward a wall with noisy effectors (imprecise movement) and employs a noisy sonar sensor to estimate its distance $h$.

The 1D robot domain used for evaluation, where a robot moves toward a wall at distance $h$.

The authors also tested context-dependent scenarios, such as a "wet floor" where movement noise increases, demonstrating the system's ability to handle complex logical conditions within a probabilistic framework.

Key Results and Performance

PREGO demonstrates significant advantages in both expressiveness and computational efficiency. A major finding is that PREGO avoids the "discretization trap"—the combinatorial explosion that occurs when continuous spaces are broken into discrete blocks for classical logic-based reasoning.

Scalability

The regression engine is highly efficient. In tests involving extremely long action sequences, PREGO maintained near-linear scaling. As shown in the table below, the system can process a plan with one million noisy actions in under 7 seconds.

Runtime performance of PREGO across varying plan lengths, demonstrating high scalability.

Comparison with Discretization

In a scenario involving 96 noisy actions, PREGO calculated the robot's belief in just 472 milliseconds. The authors estimate that achieving comparable precision using standard discretization methods would require approximately 50 minutes (3,000,000 ms), highlighting the efficiency of the continuous approach.

Conclusion and Future Work

PREGO successfully integrates logical expressiveness with probabilistic robustness. By using logic as a "pre-processor" to unroll events into mathematical formulas, it enables efficient belief projection in complex domains.

Current limitations include a focus solely on projection rather than full high-level control (like loops). Future work aims to incorporate "progression" (updating beliefs forward in time) to handle long-lived agents more efficiently and to integrate GOLOG-style program structures for more complex robot behaviors.

Summary updated

BibTeX
@inproceedings{belle2014prego,
  author = {Vaishak Belle and Hector J. Levesque},
  title = {{PREGO: An Action Language for Belief-Based Cognitive Robotics in Continuous Domains}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  doi = {10.1609/aaai.v28i1.8865},
}
Figure