A Numerical Technique for Planning Motion Strategies of a Mobile Robot in Presence of Uncertainty

Bertrand Bouilly, Thierry Siméon, Rachid Alami

TL;DR

This paper presents a novel numerical approach for planning robust motion strategies for mobile robots operating with inherent uncertainties in their control and sensing. The key innovation lies in a potential-based propagation algorithm that explicitly models and manages accumulated errors, allowing robots to navigate safely and efficiently even in complex environments.

What Problem Does This Paper Address?

Mobile robots operating in the real world face significant challenges due to uncertainties in their movement (control errors) and perception (sensing inaccuracies). These errors can accumulate over time, leading to a growing uncertainty about the robot's true position. Traditional motion planning techniques often assume perfect knowledge of the robot's state and environment, rendering them insufficient for real-world applications. This paper tackles the problem of planning motion strategies that can reliably guide a mobile robot to its goal while explicitly accounting for and mitigating these uncertainties, ensuring collision avoidance and successful task completion.

Methods

The core of the proposed solution is a numerical potential propagation algorithm that operates on a grid representation of the workspace. Here's a breakdown of the key techniques:

  • Uncertainty Modeling:
    • Control Uncertainty: Modeled as a "cone" representing the deviation between commanded and actual motion.
  • Position Uncertainty: Modeled as a disk (or segment for edge contacts) around the robot's estimated position, with its size linearly dependent on the distance traveled since the last reliable localization.
  • Sensor Uncertainty: * Dead-reckoning: Error accumulates over time.
  • Proximity Sensors (bumpers): Provide perfect information about obstacle edges/corners, allowing for precise localization along the detected feature.
  • Landmark Areas: Regions where specific sensors (e.g., vision) can be used to reduce uncertainty to a bounded disk.
  • Motion Primitives: The planner utilizes a set of motion primitives, each with a defined model of how it affects the robot's uncertainty:
  • Free-space motions (e.g., Move, Move_Landmark): Accumulate uncertainty.
  • Contact-space motions (e.g., Follow, Follow_to_Corner): Used for localization against obstacles, reducing uncertainty.
  • Potential Propagation Algorithm:
    • A grid-based potential function is built, where each grid point stores the minimum uncertainty required to reach it from the initial position.
  • The algorithm iteratively expands from the initial position, exploring neighbors.
  • A neighbor is considered only if the robot's uncertain footprint (grown by its radius and current uncertainty) remains collision-free with respect to obstacles (checked using a distance bitmap).
  • If a neighbor can be reached with lower uncertainty than previously recorded, its potential is updated, and it's added to an "OPEN" list for further exploration.
  • Relocalization: When collision-free conditions are violated due to high uncertainty, the algorithm performs a "visibility test" to identify edges that can be reliably reached by Move_to_Wall primitives. This allows for sensor-based relocalization, resetting uncertainty.
  • Landmark Integration: When the robot's uncertain footprint enters a landmark area, the uncertainty is reset to a predefined bound (EL).
  • Motion Plan Computation: Once the propagation algorithm successfully reaches the goal with acceptable uncertainty, a "bitmap path" is traced back from the goal to the start. Labels associated with the nodes in the potential grid are used to determine the sequence of motion primitives that constitute the final robust motion plan.

Datasets

Not discussed in the paper. The paper focuses on a general framework and demonstrates its capabilities with simulated examples.

Key Insights and Ideas

  • Explicit Uncertainty Management is Crucial: The paper strongly advocates for explicitly modeling and managing uncertainty throughout the planning process, rather than treating it as an afterthought.
  • Sensor-Based Relocalization as a Core Component: The integration of sensor-based relocalization (using proximity sensors and landmarks) is not just an add-on but a fundamental part of the strategy to combat accumulated errors.
  • Potential Function for Uncertainty Propagation: Using a potential function to represent the minimum uncertainty to reach a state is an elegant way to guide the search and find near-optimal robust paths.
  • Balancing Uncertainty and Distance: The planner can be configured to prioritize minimizing distance or minimizing uncertainty, offering flexibility in strategy selection.
  • "Sensorless" Navigation When Possible: A significant advantage is the ability to navigate without explicit relocalization when the task and environment allow, potentially leading to faster execution.

Key Results

The paper presents simulation results demonstrating the planner's effectiveness on various workspaces with obstacles and landmarks.

  • Robust Motion Plans: The planner successfully generates motion plans that guarantee collision-free navigation and reach the goal with an error below a specified threshold, even with significant initial uncertainty.
  • Influence of Landmarks: Examples show how landmark areas can be strategically used to reset uncertainty and enable navigation through challenging passages.
  • Effectiveness of Relocalization: The simulations highlight how wall-following primitives and obstacle relocalization effectively manage uncertainty, especially when minimizing path length.
  • Computational Efficiency: The planner is shown to be reasonably efficient, with computation times in the order of seconds for 256x256 bitmaps on a Silicon Graphics Indy workstation. For instance, one example achieved a 13% uncertainty rate with a total distance of 56.9m in 19.8s.

Limitations and Future Work

  • Circular Robot Model: The current model assumes a circular robot and a simplified representation of position error. Future work aims to incorporate more directional uncertainty models.
  • Perfect Sensor Information (for some): While proximity sensors are modeled as perfect, real-world sensors have limitations.
  • Known Environment: The environment is assumed to be perfectly known.
  • Future Work: The authors plan to extend the approach to more complex uncertainty models, implement sensor-based primitives for real-world testing, and relax assumptions to improve robustness and applicability. They also aim to explore how to better model the effects of obstacle relocalizations on the motion plan.

Summary updated

Abstract

International audience
BibTeX
@inproceedings{bouilly1995numerical,
  author = {Bertrand Bouilly and Thierry Siméon and Rachid Alami},
  title = {{A Numerical Technique for Planning Motion Strategies of a Mobile Robot in Presence of Uncertainty}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {1995},
  doi = {10.1109/robot.1995.525463},
}
Figure