Mobile Robot Global Path Planning Based on Improved Ant Colony System Algorithm with Potential Field

Xiaolu Ma, Hong MeiJournal of Mechanical Engineering 2021 · DOI

This paper, published in the Journal of Mechanical Engineering, presents a sophisticated upgrade to robot path planning by blending three distinct algorithmic approaches: Ant Colony Optimization (ACO), Artificial Potential Fields (APF), and Jump Point Search (JPS).

TL;DR

The researchers developed the JPACSPF algorithm, which fuses Ant Colony System (ACS) with Jump Point Search (JPS) and a dynamic Artificial Potential Field (APF). By introducing a "force decline coefficient" that gradually reduces the influence of the potential field, the algorithm avoids local optima and produces significantly smoother, faster-converging paths for mobile robots compared to traditional methods.

What Problem Does This Paper Address?

Global path planning is the "GPS" of robotics—finding the shortest, safest route from A to B in a known environment. While Ant Colony Optimization (ACO) is great at finding global optima, it is notoriously slow to converge and often produces "jagged" paths with too many turns.

Previous researchers tried adding Artificial Potential Fields (APF)—where the goal "pulls" the robot and obstacles "push" it away—to guide the ants. However, this often led to a new problem: the ants would get trapped in "local optima" (dead ends created by the balance of forces) or converge too quickly on a sub-optimal path. The authors set out to fix these jagged, inefficient, and trap-prone trajectories.

Methods

The authors propose the Jump Point Ant Colony System with Potential Field (JPACSPF). Key innovations include:

  1. JPS Integration: Instead of ants checking every adjacent grid cell (which is computationally expensive and leads to many turns), they use Jump Point Search logic. This allows ants to "jump" over redundant nodes and only consider "forced neighbors" or "jump points," inherently smoothing the path.
  2. Dynamic Force Decline Coefficient ($\xi$): This is the "secret sauce." Early in the search, the Artificial Potential Field strongly guides the ants toward the goal. As iterations progress, a coefficient $\xi$ reduces this force to zero. This prevents the potential field from "trapping" the algorithm in a local minimum, eventually allowing the pheromone-based search to refine the final path.
  3. Simplified JPS Pheromone Initialization: To prevent "blind searching" in the first few rounds, a simplified JPS run is used to lay down an initial pheromone trail, giving the ants a "head start."
  4. Path Interpolation: Since JPS skips nodes, the authors implemented a "path completion" step to ensure pheromones are updated correctly along the entire continuous path.

Datasets

The algorithm was evaluated using:

  • Simulated Raster Maps: Four different grid specifications (15×15, 20×20, 30×30, and 50×50) with varying obstacle densities.
  • Real-World Environment: A laboratory setting mapped using LiDAR for a physical robot test.
  • Hardware: A four-wheeled mobile robot equipped with an STM32 controller, LiDAR, and running ROS (Robot Operating System).

Key Insights and Ideas

  • The "Fading Guide": The most interesting insight is that the Artificial Potential Field is best used as a temporary guide rather than a permanent constraint. By letting the APF influence "fade out," the authors get the speed benefits of APF without the "local minima" baggage.
  • JPS as a Smoother: JPS is usually seen as a speed optimization for A*, but here it serves a dual purpose: it significantly reduces the number of turning points, which is critical for physical robots that lose energy and time during rotations.
  • Hybridization Wins: The paper demonstrates that the "blindness" of ACO and the "short-sightedness" of APF can be cancelled out by combining them with the structured pruning of JPS.

Key Results

The JPACSPF algorithm was compared against the standard Potential Field Ant Colony (ACSPF):

  • Efficiency: In a 30×30 grid, the search time dropped by 23.4%. In a 20×20 environment, search time was reduced by 33.9%.
  • Path Quality: The number of turning points was slashed. For example, in the 30×30 simulation, turns dropped from 27 to 12.
  • Convergence: The algorithm reached the optimal path in fewer iterations (e.g., 9 iterations vs. 12 in the 30×30 map).
  • Real-World Validation: In ROS-based robot trials, the JPACSPF path was visibly smoother and shorter, preventing the "stuttering" or "shaking" often seen when robots follow jagged, grid-based paths.

Limitations and Future Work

  • Static Environments: The paper focuses on global path planning in known, static environments. It does not explicitly address how the algorithm handles high-speed dynamic obstacles in real-time.
  • Complexity: While JPS reduces the number of nodes evaluated, the hybrid nature of the algorithm (calculating forces, jump points, and pheromones) adds implementation complexity.
  • Future Directions: The authors suggest that this framework could be further optimized for more complex, high-dimensional spaces or integrated with local obstacle avoidance for more robust navigation in crowded spaces.

Summary updated

Abstract

摘要: 针对势场蚁群算法路径转折点数量过多、收敛速度过快、容易陷入局部最优等问题,提出了基于势场跳点的蚁群算法。该算法融合了蚁群算法和跳点搜索算法的搜索策略,使规划出的路径更加平滑;引入了势场合力递减系数,减少了势场蚁群算法因势场而陷入的局部最优问题;引入了简化的跳点搜索算法对初始化信息素进行更新,提高了算法前期的搜索效率。为验证该算法的有效性,使用不同规格的栅格地图进行了仿真试验,仿真结果表明,相比于势场蚁群算法,该算法能够有效减少收敛迭代次数,其收敛搜索时间更短,且最终搜索到的路径更优。最后将该算法应用到实际的基于ROS的移动机器人导航试验中,试验结果表明,该算法能有效解决移动机器人全局路径规划问题,且能明显提升机器人全局路径规划的效率。
BibTeX
@article{ma2021mobile,
  author = {Xiaolu Ma and Hong Mei},
  title = {{Mobile Robot Global Path Planning Based on Improved Ant Colony System Algorithm with Potential Field}},
  journal = {Journal of Mechanical Engineering},
  year = {2021},
  doi = {10.3901/jme.2021.01.019},
}
Figure