Unveiling the Dynamic Path Planning Algorithm in AGVs

In modern warehousing, logistics, and manufacturing, automated guided vehicles (AGVs) are becoming increasingly common. Like industrious worker ants, they navigate complex environments autonomously, efficiently completing material handling tasks. One of the core technologies enabling AGVs to achieve intelligent navigation is path planning. Especially when the environment is not static, dynamic path planning capabilities become crucial. This article will delve into several mainstream dynamic path planning algorithms (such as A, Dijkstra, RRT, etc.) and explain how they are making a significant impact in the AGV industry.

Why Is Dynamic Path Planning Necessary?

Traditional static path planning assumes that the environment is completely known and remains unchanged while the AGV is performing its tasks. However, the real world is full of variables:

• Suddenly appearing temporary obstacles (such as fallen cargo, pedestrians, or other vehicles)
• Changing traffic control areas
• Temporary adjustments to target points or tasks

In these situations, AGVs need to be able to sense changes in their environment in real time and quickly replan their routes. This is where dynamic path planning comes into play. It gives AGVs the intelligence to adapt to changing circumstances, ensuring that they can continue to operate safely and efficiently in complex and dynamic environments.

Analysis of Mainstream Path Planning Algorithms

1. Dijkstra's Algorithm

Dijkstra's algorithm is a classic graph search algorithm used to find the shortest path from a single source node to all other nodes in a graph.

‍Core Idea:  

Starting from the source node, the algorithm spreads outward like ripples in water. Each time, it visits the nearest unvisited node to the source node and updates the distances to its neighbours.

Process:‍

• Initialisation: Set the distance from the starting point to 0 and the distances from other points to infinity. Create a priority queue of nodes to be visited (sorted by distance).
• Iteration: Remove the node u with the smallest distance from the queue.
• Relaxation: For each neighbour v of u, if the path from u to v is shorter, update v's distance and add it to the queue.
• Mark: Mark u as visited.  
• Repeat: Continue until the target node is retrieved or the queue is empty.  

AGV Application:  

• Advantages: Guarantees finding the global shortest path (when edge weights are non-negative).  
• Disadvantages: Large search range, no directionality, low computational efficiency (especially on large maps). Dynamic obstacles require recalculating the global path, resulting in poor real-time performance.
• Positioning: Often used as a foundation for other algorithms (such as A*) or in simple environments.

2. A* Algorithm

The A* (A-Star) algorithm is an optimisation of the Dijkstra algorithm. It introduces heuristic information to guide the search direction, thereby finding the target more quickly.

 Core idea: When selecting the next node to visit, consider the following simultaneously:

• g(n): The actual path cost from the starting point to node n.
• h(n): The estimated cost from node n to the goal (a heuristic function, such as Manhattan/Euclidean distance).  
• Evaluation function: f(n) = g(n) + h(n)  
• Key requirements: h(n) must satisfy admissibility (estimated value ≤ actual value) and consistency to ensure finding the optimal solution.

 Process: Similar to Dijkstra, but the priority queue is sorted by f(n), and nodes with the smallest f(n) are prioritised for expansion, making the search more directional towards the goal.

 AGV Application:

• Advantages: Guarantees the optimal path when the heuristic function meets the conditions and is typically much more efficient than Dijkstra. Widely used in AGV global path planning.
• Disadvantages: Performance is influenced by the choice of heuristic function; memory consumption may be high; re-planning is still required when the environment changes frequently.
• Dynamic Variants: To address dynamic environments, algorithms such as D*, LPA*, and D* Lite are available. These algorithms can incrementally update paths (rather than fully re-calculate them) when the environment changes, significantly improving response speed. D* Lite is a commonly used algorithm for dynamic obstacle avoidance in AGVs.

3. RRT* Algorithm

RRT* (Rapidly-exploring Random Tree Star) is a sampling-based path planning algorithm that is particularly suitable for high-dimensional spaces and complex constraints (such as vehicle kinematics).

Core idea:

By randomly sampling points in the state space, the algorithm progressively grows a tree starting from the origin to explore the space. RRT* is an optimised version of RRT, incorporating a rewiring step to enable the path to asymptotically approach optimality (the more sampling points, the closer the path is to optimality).  

Process:  

• Sampling: Randomly generate a point x_rand in the state space.
• Find nearest neighbour: Locate the node x_nearest in the tree that is closest to x_rand.
• Extend (Steer): Extend a step length from x_nearest to x_rand (avoiding obstacles) to obtain the new node x_new.
• Select Parent Node (RRT* Specific): Search for nodes near x_new and select the node x_min that minimises the total path cost from the starting point to x_new as its parent node (collisions must be avoided).
• Rewire (RRT* specific): Search for nodes near x_new. If connecting through x_new reduces their total path cost, update these nodes' parent nodes to x_new.  
• Add: Add x_new and its connected edges to the tree.  
• Repeat: Continue until the tree is expanded to the vicinity of the target area.  

 AGV Application:

• Advantages: Strong capability to handle high-dimensional states (pose, velocity, etc.) and complex constraints; no explicit environment map required; probabilistic completeness (if a path exists, it will eventually be found); RRT has asymptotic optimality.  
• Disadvantages: Paths are not strictly optimal (unless infinite sampling is used); paths may not be smooth (post-processing required); performance is sensitive to parameters; convergence may be slow.
• Dynamic variants:  e.g., Dynamic RRT, which achieves replanning by removing/updating parts of the tree that collide with dynamic obstacles and continuing to grow.

Practical Applications of Dynamic Path Planning in AGVs

AGV Obstacle Avoidance Application Scenarios

In actual AGV applications, a single algorithm is rarely used alone; instead, a combination of algorithms is typically employed:

1. Global Path Planning:

Using A* or its variants (such as D-Lite) or sometimes an optimised version of Dijkstra's algorithm, a global optimal or suboptimal path is planned from the starting point to the destination on a known map. This path is typically quite macro-level.

2. Local Path Planning/Dynamic Obstacle Avoidance:  

While following the global path, the AGV uses sensors (such as lidar or cameras) to continuously sense the surrounding environment. Once an unexpected obstacle (static or dynamic) is detected, the local planner (which may be based on DWA - Dynamic Window Approach, TEB - Timed Elastic Band, or a variant of A/RRT with fast replanning) intervenes to generate a short-term, safe, and vehicle kinematics-constrained local obstacle avoidance path under the guidance of the global path.

3. Path Tracking:

The control algorithm is responsible for precisely driving the AGV along the planned path (whether global or local).

This hierarchical planning strategy balances global optimality and local real-time performance. Algorithms like D Lite excel in handling local dynamic changes due to their efficient incremental re-planning capabilities. RRT and its variants, on the other hand, are more advantageous in handling complex environments and motion constraints.

Challenges and Future Trends

1. Challenges

Despite significant progress in dynamic path planning technology, challenges remain in AGV industry applications:

• Real-time requirements: Especially in high-speed operation or dense traffic scenarios, algorithms need to complete calculations in milliseconds.
• Environmental uncertainty: Sensor noise, positioning errors, and difficulties in predicting dynamic obstacles.
• Multi-AGV coordination: Avoid conflicts and deadlocks to achieve efficient collaboration.
• Complex kinematic constraints: Considering AGV size, turning radius, and acceleration/deceleration performance.

2. Future Trends

In the future, dynamic path planning will evolve toward smarter and more efficient solutions:

• Machine learning integration: Utilising reinforcement learning, imitation learning, and other methods to enable AGVs to autonomously learn optimal navigation strategies.
• Predictive Planning: Predict the intentions and trajectories of other dynamic obstacles (such as pedestrians and vehicles) to plan ahead.
• Semantic Understanding: Enable AGVs to understand semantic information in the environment (such as ‘sidewalk’ and ‘charging zone’) to make decisions more suited to the scenario.
• Human-Machine Collaboration: Achieve safer and more natural interaction and avoidance in human-machine coexistence environments.

결론

Dijkstra, A, RRT, and their dynamic variants are core tools in the AGV dynamic path planning algorithm library. They serve as the AGV's ‘intelligent eyes’ and ‘dynamic steering wheel,’ enabling it to navigate complex environments with flexibility and efficiency. Understanding the principles and characteristics of these algorithms is crucial for advancing AGV technology and the broader automation field. As algorithms evolve and computational power improves, future AGVs will undoubtedly become smarter, more reliable, and more efficient.

AiTEN Robotics, headquartered in Suzhou, China, is a global leader in autonomous industrial vehicles (AMR/AGV) and logistics automation solutions. AiTEN Robotics has developed ten product series to meet the needs of full-stack material handling scenarios. AiTEN Robotics has deployed more than 200 projects in over 30 countries and regions, and is trusted by numerous Fortune 500 companies across industries such as automotive, food and beverage, chemicals, pharmaceuticals, manufacturing, and third-party logistics, enhancing operational safety, efficiency, and future readiness.