Dynamic Obstacle Avoidance Using Bayesian Occupancy Filter and Approximate Inference

Angel Llamazares, Vladimir Ivan, Eduardo J. Molinos, Manuel Ocaña, Sethu Vijayakumar2013 · DOI

TL;DR

This paper tackles the challenge of dynamic obstacle avoidance for mobile robots by integrating a probabilistic model of the environment with a stochastic optimal control framework. The authors propose a 3D extension of the Bayesian Occupancy Filter for improved perception and use Approximate Inference Control (AICO) to optimize robot trajectories for both safety and energy efficiency, outperforming traditional reactive methods.

What Problem Does This Paper Address?

Autonomous navigation systems for mobile platforms, especially in dynamic environments, face the critical challenge of safely and efficiently avoiding obstacles. Traditional methods often treat obstacles as static or rely on reactive control, which can be suboptimal in terms of energy consumption and may not adequately predict the motion of dynamic obstacles. This paper addresses the need for a navigation system that can:

  • Perceive dynamic obstacles accurately: This includes estimating their position and velocity in a 3D environment, even with noisy sensor data.
  • Plan safe and energy-efficient paths: The system must consider not only avoiding collisions but also minimizing energy expenditure, which is crucial for battery-powered robots.
  • Combine multiple objectives: Integrating safety, optimality, and energy constraints in a structured way is a significant challenge.

The authors highlight that reactive methods, while computationally efficient, fail to account for the dynamic nature of the environment and cannot predict obstacle motion, making them unsuitable for scenarios with high uncertainty.

Methods

The proposed approach combines a novel perception stage with an advanced planning framework:

  • 3D Bayesian Occupancy Filter (BOF): The authors extend the standard 2D BOF to a 3D representation by discretizing the environment into cubes and incorporating height information from a laser range sensor. This allows for a more robust estimation of obstacle positions in three dimensions.
  • Velocity Estimation using Optical Flow and Blob Filtering: To reduce computational cost and improve efficiency, the system estimates obstacle velocities by employing the Lucas-Kanade optical flow algorithm and a blob filtering stage. This stage detects object boundaries and computes the average motion of cells within these boundaries, providing relative velocities with respect to the robot.
  • Approximate Inference Control (AICO): For the planning stage, the paper utilizes the AICO framework, which formulates the path optimization problem within a stochastic optimal control paradigm. AICO combines multiple task variables (position, power demand, turning velocity, collision avoidance) into a graphical model. This allows for the computation of optimal paths that minimize a cost function incorporating both state-dependent costs (related to safety and proximity to obstacles) and control costs (related to energy consumption). The authors also adapt AICO to handle the holonomic constraint by introducing a penalty for angular velocity, effectively turning a hard constraint into a soft one.
  • Global Planning Initialization: A Voronoi graph-based global path planner is used to generate an initial path, which then serves as an initialization for AICO. This helps to guide the inference-based planner and mitigate issues with local minima.

Datasets

Not discussed in the paper. The experiments were conducted on a real robot platform (Seekur Jr.) and a simulator.

Key Insights and Ideas

  • 3D BOF significantly improves perception: Extending the Bayesian Occupancy Filter to 3D, even with a simplified discretization, leads to a more accurate representation of the environment and better obstacle detection compared to 2D methods.
  • Optical flow and blob filtering offer an efficient velocity estimation: This approach effectively estimates obstacle velocities without the high computational cost associated with discretizing velocity spaces, making the perception stage more efficient.
  • AICO effectively balances safety and energy: By formulating the problem as a stochastic optimal control task with multiple cost functions, AICO can find paths that are not only safe but also minimize energy consumption, a critical factor for autonomous systems.
  • Smoother trajectories lead to lower energy consumption: The experimental results demonstrate that the optimized paths generated by AICO are smoother, with lower curvature, acceleration, and velocity profiles, directly translating to reduced energy usage.
  • Probabilistic model enhances classical algorithms: Even when integrated into existing reactive algorithms like VFH+, the proposed probabilistic model leads to significant improvements in energy efficiency and smoother motion.

Key Results

  • Energy Consumption Reduction:
    • Integrating the probabilistic model into classical algorithms (VFH+, CVM, LCM, BCM) resulted in energy consumption reductions of up to 45.5% in the tested scenarios.
  • The AICO planner, using the probabilistic model, achieved further energy savings, reducing consumption by approximately 10% compared to the best reactive methods.
  • Smoother Trajectories and Motion Profiles:
    • Figures 8 and 9 show that paths generated by the proposed method (AICO with probabilistic model) exhibit lower curvature compared to traditional VFH+.
  • Figures 10 and 11 demonstrate that linear and angular velocities and accelerations are significantly smoother and lower when using the probabilistic model with LCM and AICO.
  • Improved Perception: The 3D BOF extension, even at a single level (L2), improved the perception stage of classical avoidance systems.

Limitations and Future Work

  • Computational Cost of AICO: The authors acknowledge that the computational cost of AICO is currently too high for real-time planning applications.
  • Replanning Time: The replanning time of 3 seconds on average is too long to be used as a reactive controller.
  • Finite Horizon Optimization: AICO solves finite horizon optimization problems, requiring the trajectory duration to be specified a priori.
  • Accuracy of Probabilistic Model: Future work aims to improve the accuracy of the probabilistic model by refining the discretization and optimizing the calculation for a higher number of cells.
  • Speeding up the Algorithm: Efforts will be made to speed up the algorithm to accommodate more cells and potentially enable real-time applications.
  • Multi-Scale Inference and Parallel Computation: The planning algorithm can be improved by solving inference at multiple scales and exploiting parallel computation.
  • Coverage Planning: The authors intend to address coverage issues using topology-based properties (e.g., winding numbers) to plan optimal routes for tasks like surveying parking lots.

Summary updated

BibTeX
@misc{llamazares2013dynamic,
  author = {Angel Llamazares and Vladimir Ivan and Eduardo J. Molinos and Manuel Ocaña and Sethu Vijayakumar},
  title = {{Dynamic Obstacle Avoidance Using Bayesian Occupancy Filter and Approximate Inference}},
  year = {2013},
  doi = {10.3390/s130302929},
}
Figure