Towards Path Planning Algorithm Combining with A-Star Algorithm and Dynamic Window Approach Algorithm

Kaiyu Li, Xiugang Gong, Muhammad Tahir, Tao Wang, Rajesh KumarInternational Journal of Advanced Computer Science and Applications 2023 · DOI

TL;DR

This paper proposes a hybrid path-planning strategy for Automated Guided Vehicles (AGVs) that fuses an enhanced A-Star (A*) algorithm for global navigation with the Dynamic Window Approach (DWA) for local obstacle avoidance. By optimizing sub-node selection and pruning redundant path points, the authors achieved smoother, shorter paths that can intelligently dodge moving obstacles in real-time.

What Problem Does This Paper Address?

In modern smart warehouses, AGVs are the backbone of logistics. However, traditional path-planning algorithms often struggle with two conflicting requirements:

  1. Global Efficiency: Finding the shortest path across a large map without getting stuck in "deadlocks" or taking jagged, inefficient routes.
  2. Local Safety: Reacting to dynamic obstacles (like humans or other robots) that weren't on the original map.

Standard A* is great for static maps but produces "rough" paths with too many turns and often clips corners too closely for safety. Conversely, local planners like DWA are excellent at dodging moving objects but lack the "big picture" perspective, often leading the robot into cul-de-sacs. This paper aims to bridge that gap.

Methods

The authors introduce a multi-stage optimization process:

  • Enhanced A-Star (Global):
    • Sub-node Optimization: They classify nodes into "X-type" and "N-type." By selectively removing child nodes adjacent to obstacle corners, they prevent the robot from cutting corners too tightly, increasing safety.
  • Evaluation Function Tweaks: They introduced a dynamic weight to the heuristic function ($h(n)$) that adjusts based on the distance to the goal, speeding up search time.
  • Redundant Point Removal: A two-step smoothing process identifies and deletes collinear nodes and unnecessary right-angle turns, resulting in a much "cleaner" trajectory.
  • DWA Integration (Local):
    • The optimized A* path serves as a reference. The DWA then samples possible velocities $(v, \omega)$ and trajectories to follow this global path while using a new evaluation function to steer clear of dynamic obstacles detected in real-time.

Datasets

The study does not use external public datasets. Instead, the authors developed custom simulation environments within MATLAB R2023a:

  • Simple Environment: A 10x10 grid map.
  • Complex Environment: A 20x20 grid map with high obstacle density.
  • Dynamic Environment: A 20x20 grid containing both unknown static obstacles and moving obstacles (represented as moving coordinates in the simulation).

Key Insights and Ideas

  • The "Safety Buffer" via Logic, not just Math: Instead of just adding a cost-map inflation (which is computationally expensive), the sub-node optimization effectively "hard-codes" a safety distance by limiting which adjacent grid cells the algorithm is allowed to transition into near corners.
  • Global Strategy vs. Local Tactics: The paper emphasizes that DWA alone is "blind." By feeding the DWA a sub-target point from the optimized A* path, the robot maintains global optimality while exercising local "reflexes."
  • Smoothing is Efficiency: Removing redundant vertices doesn't just make the path look better; it reduces the mechanical wear on AGVs by minimizing unnecessary deceleration and acceleration at inflection points.

Key Results

The authors compared their "Improved A" against traditional A and the Ant Colony Algorithm. In complex environments, the improvements were significant:

  • Path Smoothness: A 44% reduction in the number of breakpoints (inflection points).
  • Path Length: A 17.18% reduction in total distance traveled compared to traditional A*.
  • Efficiency: A 14.68% reduction in total planning time.
  • Dynamic Performance: In simulations with moving obstacles, the fused algorithm successfully adjusted the robot's attitude angle and velocity to avoid collisions without losing track of the global goal.

Limitations and Future Work

While the results are promising, the authors acknowledge a few hurdles:

  • Planning Latency: Although faster than traditional A*, the planning time in very high-density dynamic environments still needs improvement for high-speed robotics.
  • Adaptive Proficiency: The integration technique currently struggles with "adaptive proficiency"—essentially how gracefully the robot switches between following the global path and deviating for an obstacle.

Future Direction: The authors aim to refine the algorithm to reduce total planning time by an additional 80%, making it viable for high-speed, real-world industrial deployments.

Summary updated

Abstract

In the Automated Guided Vehicle (AGV) warehouse automatic guided vehicle system, the path planning algorithm for intelligent logistics vehicles is a key factor to ensure the stable and efficient operation of the system. However, the existing planning algorithms have problems such as single designing a route and the inability to intelligently evade moving barriers. The academic community has proposed various solutions to these problems, although they have improved the efficiency and quality of path planning to some extent, they have not completely solved problems such as poor safety in planning, the high number of path inflection points, poor path smoothness, easily getting stuck in deadlocks, and have not fully considered the running cost and practical implementation difficulty of algorithms. To address these issues, the article deeply researched traditional A* scheme and Dynamic Window Approach (DWA) technology and proposed designing a route method according to the fusion of the A* algorithm and DWA technology. The algorithm improved the A algorithm by introducing a sub-node optimization algorithm to solve problems for instance poor global path planning safety and easy deadlock. Moreover, the algorithm reduced the amount of global route reversal locations and increased path consistency by improving the evaluation function and removing redundant points of the A algorithm. Finally, by integrating the DWA algorithm, the intelligent logistics vehicle achieved dynamic obstacle avoidance capabilities for moving objects in the real world. Our simulations-based results on MATLAB framework show that the algorithm significantly improves path smoothness, path length, path planning time, and environmental adaptability compared to traditional algorithms, and basically meets the path planning requirements of the AGV system for intelligent logistics vehicles.
BibTeX
@article{li2023towards,
  author = {Kaiyu Li and Xiugang Gong and Muhammad Tahir and Tao Wang and Rajesh Kumar},
  title = {{Towards Path Planning Algorithm Combining with A-Star Algorithm and Dynamic Window Approach Algorithm}},
  journal = {International Journal of Advanced Computer Science and Applications},
  year = {2023},
  doi = {10.14569/ijacsa.2023.0140655},
}
Figure