Introduction
ALLEGRO (ALGOL in PREGO) is a high-level programming language designed for robots operating in "messy" real-world environments characterized by noisy sensors and unpredictable actuators. By combining the logical reasoning of the Situation Calculus with a sampling-based "progression" mechanism, ALLEGRO allows robots to efficiently track their beliefs over long-term, iterative tasks in continuous domains. This approach bridges the gap between the expressive power of logic-based programming and the robustness of probabilistic robotics.
The Challenge of Real-World Robotics
Cognitive Robotics traditionally uses high-level languages like GOLOG to define complex agent behaviors. These languages excel at handling loops and branches based on logical knowledge but often assume a "clean world" where sensors and motors are perfect. In reality, robotic hardware is inherently noisy; a motor might move a robot 1.9 meters when 2.0 was intended, and sensors report distances with significant margins of error.
Previous attempts to address this, such as the PREGO system, relied on regression. To calculate a robot's current belief, regression must look back to the initial state and solve massive, multi-dimensional integrals. For programs running for thousands of steps, this leads to a "computational explosion" that makes real-time operation impossible. ALLEGRO addresses this bottleneck by shifting from regression to progression, allowing robots to update their beliefs step-by-step as they act.
The ALLEGRO Framework: Progression via Sampling
ALLEGRO introduces several technical innovations to enable efficient belief tracking:
- Belief-Based Programming: It provides a LISP-like syntax where programmers can write conditions based on the robot's confidence level. For example, a robot can be programmed to keep sensing until it is 80% sure a distance $h$ is within a specific range.
- Progression via Sampling: Instead of solving complex integrals, the ALLEGRO interpreter maintains a set of "sampled states" (particles). When an action occurs, these samples are updated forward in time. This is inspired by particle filters but integrated directly into a logical framework.
- Handling Non-Invertibility: Traditional mathematical progression often fails when actions are not invertible (e.g., information-losing functions). ALLEGRO’s sampling approach sidesteps this, allowing for more flexible and realistic Basic Action Theories (BATs).
- Online Interpreter: The system supports an online mode that can connect to physical robots via TCP, updating internal belief states in real-time based on live sensor data.
Experimental Evaluation
The system was evaluated using simulated stochastic robot domains designed to test both logic and probabilistic accuracy.
In the "Wall Domain," a robot must move to a specific distance from a wall using noisy movement (nfwd) and noisy sensing (sonar). Additionally, scalability benchmarks were conducted using synthetic domains with increasing numbers of fluents (variables) and actions to test the system's computational limits.
Results and Discussion
ALLEGRO demonstrates significant performance improvements over previous regression-based methods. While PREGO's runtime grows exponentially with the number of actions, eventually leading to memory exhaustion, ALLEGRO maintains a constant update time per action, even over sequences exceeding 500 steps.
Key findings include:
- Linear Scalability: The system scales linearly with the number of environment variables, making it suitable for complex robotic setups.
- Noise Awareness: Qualitative tests confirmed that the program correctly adapts to environmental noise. When sensor noise increases, the robot automatically performs more sensing actions to reach the required confidence threshold before proceeding.
- Efficiency: The move to progression allows for long-lived agents that can operate indefinitely without the performance degradation seen in regression-based systems.
Conclusion and Future Work
ALLEGRO proves that the expressive power of logic (loops, nested conditions) can be successfully integrated with the robustness of probabilistic robotics. By using sampling as a "universal solvent" for complex noise models, the authors provide a viable path for high-level programming in continuous, stochastic domains. Future work will focus on integrating the interpreter with "look-ahead" planning and exploring the trade-offs between sample size and belief drift in extremely long-duration deployments.
Summary updated