Real-Time Dynamic Path Planning of Mobile Robots: A Novel Hybrid Heuristic Optimization Algorithm

Qing Wu, Zeyu Chen, Lei Wang, Hao Lin, Zijing Jiang, Shuai Li, Dechao ChenSensors 2019 · DOI

TL;DR

This paper introduces a novel hybrid algorithm, BAS-APF, for real-time dynamic path planning in mobile robots. By combining the Beetle Antennae Search (BAS) with the Artificial Potential Field (APF) method, it achieves faster planning times and smoother, safer paths compared to existing algorithms, even in environments with moving obstacles.

What Problem Does This Paper Address?

Mobile robots are increasingly used in various industries and daily life, but navigating them safely and efficiently in dynamic environments – where obstacles can move unexpectedly – remains a significant challenge. Traditional path planning methods often struggle with real-time performance or get stuck in local minima, leading to inefficient or unsafe paths. This paper tackles the problem of enabling mobile robots to plan and execute paths in real-time, effectively avoiding both static and dynamic obstacles, while optimizing for path length and smoothness.

Methods

The core of this work is the BAS-APF hybrid algorithm. It operates in two main phases:

  1. Initial Path Generation: This phase leverages a modified Beetle Antennae Search (BAS) algorithm. BAS is inspired by the foraging behavior of beetles and is used here to explore potential paths. The algorithm strategically selects candidate points within a dynamic detection range, using a cost function to evaluate their suitability. This process aims to find an initial feasible path from the start to the target.
  2. Path Tracking and Optimization: Once an initial path is generated, the robot begins to follow it. During tracking, the path is continuously optimized. A key innovation is the integration of the Artificial Potential Field (APF) method. APF creates an artificial landscape where the target point exerts an attractive force, and obstacles exert repulsive forces. This helps guide the robot and, crucially, mitigates the APF's tendency to get trapped in local minima. The paper also introduces a layered detection range and a cost function that penalizes proximity to obstacles, further enhancing the ability to escape local extrema. Finally, a B-spline curve fitting method is employed to smooth the generated path, making it more practical for robot execution.

The novelty lies in the synergistic combination of BAS for initial exploration and optimization, and APF for robust obstacle avoidance and local minima escape, all within a real-time framework.

Datasets

The paper uses simulated maps for evaluation. These include:

  • A pre-set simulation map (Map 1) of 600x600 cm with static and two moving dynamic obstacles.
  • Two processed real-world maps (Map 2 and Map 3) with dimensions 637x355 and 597x375 respectively, also featuring dynamic obstacles.

No new datasets were introduced; rather, existing map structures were used to simulate dynamic environments.

Key Insights and Ideas

  • Hybridization is Key: Combining the exploration capabilities of BAS with the obstacle avoidance and local minima escape properties of APF creates a more robust and efficient path planning solution than either method alone.
  • Layered Detection for Local Minima Escape: Dividing the robot's detection range into layers and applying different penalties for obstacles in each layer significantly improves the algorithm's ability to escape local minima, a common pitfall for APF.
  • Real-time Optimization During Tracking: Instead of re-planning the entire path at every step, the BAS-APF method optimizes the path during the tracking process. This is crucial for achieving real-time performance in dynamic environments.
  • Smoothness and Safety Balance: The B-spline fitting and the careful design of the cost function ensure that the final path is not only safe (maintaining a distance from obstacles) but also smooth, which is important for efficient robot movement.

Key Results

The BAS-APF method demonstrated superior performance across several metrics:

  • Planning Time: The BAS-APF method achieved significantly faster planning times compared to ACO, APF, and RRT. For example, on Map 1, BAS-APF took 0.287s, while ACO took 8.27s, APF took 1.75s, and RRT took 1.9s. This advantage was consistent across all tested maps.
  • Path Length: While the improvement was less dramatic than in planning time, BAS-APF generally produced shorter paths than APF and RRT, and comparable or slightly shorter paths than ACO. For instance, on Map 3, BAS-APF achieved a path length of 666.5, compared to APF (1203), RRT (670.9), and ACO (801.3).
  • Path Quality: Visualizations showed that BAS-APF produced smoother and safer paths, maintaining a better distance from obstacles compared to ACO and RRT, and avoiding unnecessary turns seen in APF.

Limitations and Future Work

  • Real-World Robot Testing: The current work is limited to simulations. The authors acknowledge that testing with actual mobile robots in real environments is crucial for validating the algorithm's practical applicability and further optimizing obstacle avoidance accuracy.
  • Limited Lab Resources: The authors cite limited laboratory conditions and the high cost of mobile robots as reasons for not conducting real-world experiments at this stage.
  • Future Directions:
    • Conducting experiments with real robots to refine the algorithm and demonstrate its advantages in real-world scenarios.
  • Extending the algorithm to multi-objective planning, enabling it to simultaneously plan paths for multiple mobile robots.

Summary updated

Abstract

Mobile robots are becoming more and more widely used in industry and life, so the navigation of robots in dynamic environments has become an urgent problem to be solved. Dynamic path planning has, therefore, received more attention. This paper proposes a real-time dynamic path planning method for mobile robots that can avoid both static and dynamic obstacles. The proposed intelligent optimization method can not only get a better path but also has outstanding advantages in planning time. The algorithm used in the proposed method is a hybrid algorithm based on the beetle antennae search (BAS) algorithm and the artificial potential field (APF) algorithm, termed the BAS-APF method. By establishing a potential field, the convergence speed is accelerated, and the defect that the APF is easily trapped in the local minimum value is also avoided. At the same time, by setting a security scope to make the path closer to the available path in the real environment, the effectiveness and superiority of the proposed method are verified through simulative results.
BibTeX
@inproceedings{wu2019real,
  author = {Qing Wu and Zeyu Chen and Lei Wang and Hao Lin and Zijing Jiang and Shuai Li and Dechao Chen},
  title = {{Real-Time Dynamic Path Planning of Mobile Robots: A Novel Hybrid Heuristic Optimization Algorithm}},
  booktitle = {Sensors},
  year = {2019},
  doi = {10.3390/s20010188},
}
Figure