A real-time multi-constraints obstacle avoidance method using LiDAR

Wei Chen, Jian Sun, Weishuo Li, Dapeng Zhao

This paper presents a practical approach to one of the "bread and butter" problems in robotics: how to get from point A to point B without hitting anything, especially when "anything" might be moving and wasn't on the map to begin with.

TL;DR

The researchers propose a real-time obstacle avoidance method that combines a multi-constraint cost function for selecting local "sub-goals" with an improved Ant Colony Optimization (ACO) algorithm for smooth path planning. By focusing on iterative local optimizations rather than a single global plan, the system achieves high-performance navigation on low-cost hardware in dynamic environments.

What Problem Does This Paper Address?

Navigating a robot through a dynamic, unknown environment is a balancing act. Global path planners (which create a map first and then a route) fail when unexpected obstacles appear. Local planners, like the popular Artificial Potential Field (APF) method, are fast but notorious for getting stuck in "local minima"—situations where the robot gets trapped behind a U-shaped obstacle because it can't see a way around.

Furthermore, many existing algorithms are computationally expensive or require high-end 3D LiDAR sensors. The authors aim to create a method that is:

  1. Real-time: Capable of processing sensor data at 5Hz or faster.
  2. Robust: Able to handle moving obstacles.
  3. Efficient: Light enough to run on low-cost, small-scale autonomous platforms using simple 2D LiDAR.

Methods

The proposed method operates in a continuous loop of two main phases:

1. Sub-goal Selection via Multi-Constraint Cost Function

Instead of trying to reach the final destination in one giant leap, the robot looks at its current 2D LiDAR scan and identifies the best "sub-goal" within its immediate field of view. This is determined by a cost function that balances three factors:

  • Distance to Goal ($ds$): Ensuring the sub-goal actually moves the robot closer to the final destination.
  • Robot-to-Sub-goal Angle ($\theta_1$): Minimizing the deviation from the robot's current heading to keep motion efficient.
  • Sub-goal-to-Final-Goal Angle ($\theta_2$): Ensuring the chosen sub-goal points the robot in the right general direction for the long term.

2. Local Path Planning via Improved ACO

Once a sub-goal is set, the robot needs a path to get there. The authors use Ant Colony Optimization (ACO), a meta-heuristic inspired by how ants find paths to food. They "improved" the standard ACO in two clever ways:

  • Corner Heuristic: They added a mathematical penalty for sharp turns. This forces the "ants" to find paths that are not just short, but smooth enough for a physical robot to follow.
  • Weighted Pheromone Update: Instead of letting every ant update the path, they rank the ants and only allow the "best" ones to leave pheromones, significantly speeding up the algorithm's convergence.

Datasets

The authors did not use standard public datasets. Instead, they evaluated their work through:

  • MATLAB Simulations: A 40m x 40m grid map with various obstacle configurations to tune weight parameters ($\alpha, \beta, \omega$).
  • Real-world Experiments: Conducted using an EAI differential drive mobile robot equipped with a 360° LiDAR and an onboard computer, navigating narrow corridors (2.1m wide) filled with 0.6m cubic obstacles.

Key Insights and Ideas

  • Local vs. Global: The "aha moment" here is that you don't need a perfect global map to achieve global convergence. By iteratively solving local optimizations that account for the final goal, the robot naturally "flows" toward the destination while remaining highly responsive to new sensor data.
  • Smoothing via Heuristics: Standard ACO often produces jagged, "stair-step" paths on grid maps. By integrating a "corner heuristic" directly into the transition probability, the authors effectively baked kinematics into a search algorithm.
  • Computational Thrift: By using 2D LiDAR and local grid maps (only 80 cells centered on the robot), the memory and CPU requirements are kept low enough for "low-cost autonomous platforms."

Key Results

The researchers compared their "Proposed Method" against standard ACO, Artificial Potential Field (APF), and Bacterial Foraging Optimization (BFO):

  • Efficiency: In real-world tests, the proposed method reached the goal in 81 seconds, compared to 92.5s for APF and 88s for BFO.
  • Path Optimality: The path length was significantly shorter (16.2m) compared to APF (18.5m), which often takes wider, less efficient turns to avoid the "local minima" trap.
  • Convergence: The improved ACO converged to an optimal path in roughly half the iterations required by traditional versions.
  • Dynamic Robustness: In experiments with "sudden external disturbances" (people or objects moving into the path), the robot's convergence curve showed only minimal jitter, proving it could re-plan nearly instantaneously.

Limitations and Future Work

  • 2D Constraints: The system relies on 2D LiDAR mounted at a fixed height (0.6m). It cannot "see" obstacles that are very low to the ground or hanging from the ceiling.
  • Velocity Dynamics: The current cost function focuses on position and heading but doesn't explicitly model the velocity or predicted trajectory of moving obstacles.
  • Future Directions: The authors suggest extending the method to 3D space (for drones) and incorporating "unseen" area prediction to anticipate threats before they enter the LiDAR's line of sight.

Summary updated

Abstract

Obstacle avoidance is one of the essential and indispensable functions for autonomous mobile robots. Most of the existing solutions are typically based on single condition constraint and cannot incorporate sensor data in a real-time manner, which often fail to respond to unexpected moving obstacles in dynamic unknown environments. In this paper, a novel real-time multi-constraints obstacle avoidance method using Light Detection and Ranging(LiDAR) is proposed, which is able to, based on the latest estimation of the robot pose and environment, find the sub-goal defined by a multi-constraints function within the explored region and plan a corresponding optimal trajectory at each time step iteratively, so that the robot approaches the goal over time. Meanwhile, at each time step, the improved Ant Colony Optimization(ACO) algorithm is also used to re-plan optimal paths from the latest robot pose to the latest defined sub-goal position. While ensuring convergence, planning in this method is done by repeated local optimizations, so that the latest sensor data from LiDAR and derived environment information can be fully utilized at each step until the robot reaches the desired position. This method facilitates real-time performance, also has little requirement on memory space or computational power due to its nature, thus our method has huge potentials to benefit small low-cost autonomous platforms. The method is evaluated against several existing technologies in both simulation and real-world experiments.
BibTeX
@article{chen2020real,
  author = {Wei Chen and Jian Sun and Weishuo Li and Dapeng Zhao},
  title = {{A real-time multi-constraints obstacle avoidance method using LiDAR}},
  journal = {Journal of Intelligent \& Fuzzy Systems},
  year = {2020},
  doi = {10.3233/jifs-190766},
}

Loading related content...

Figure