A* Path Planning Algorithm

The A* algorithm is one of the most classic and widely adopted global path planning algorithms in autonomous driving. By striking an optimal balance between the explored path cost (g(n)) and the estimated cost to the destination (h(n)), it efficiently plots the shortest path from start point to destination within a static environment.

💡 Core Principle: One Formula, Two Costs

The elegance of the A* algorithm lies in its use of a straightforward formula to evaluate every single node on a map:

f(n) = g(n) + h(n)

• g(n) – The Path Traveled: Represents the actual cost incurred from the start point to the current node n, such as the actual distance already driven.

• h(n) – The Road Ahead: Represents the estimated cost from current node n to the destination. This is a heuristic value, typically calculated via straight-line Euclidean distance or grid-bound Manhattan distance.

The A* algorithm prioritises expanding nodes with the lowest f(n) value. This ensures the planned route is neither short-sighted (relying solely on g(n)) nor purely speculative (relying solely on h(n)), achieving overall global optimality.

🚗 Algorithm Workflow: Navigating the Grid

Think of the A* execution process as systematically plotting a route across a grid map:

1. Initialisation: Place the start point into the "Open List" (nodes pending evaluation).

2. Iterative Search:

   • Extract the node with the lowest f(n) value from the Open List.

   • Move this node into the "Closed List" (nodes already evaluated) to mark it as explored.

   • Inspect all adjacent neighbours around this node (horizontal, vertical, and diagonal):

     • If a neighbour is an obstacle or already in the Closed List, disregard it.

     • If a neighbour is not in the Open List, compute its f(n), g(n), and h(n) values, set the current node as its parent, and append it to the Open List.

     • If the neighbour is already in the Open List, check whether reaching it via the current node yields a lower g(n); if so, update its parent node and revise its cost values.

3. Path Resolved: Once the destination node is moved into the Closed List, the path is secured. Backtracking along the parent node pointers from the destination all the way to the start point reconstructs the complete optimal route.

⚠️ Challenges in Autonomous Driving

While highly effective across static road networks, deploying the classic A* algorithm directly into autonomous driving environments presents several critical hurdles:

• Restricted to Static Environments: The standard A* algorithm assumes a static, unchanging map, rendering it ill-equipped to react to dynamic obstacles like crossing pedestrians or oncoming vehicles suddenly appearing on the road.

• Lack of Path Smoothness: Routes generated by A* often consist of jagged, segmented lines with sharp angular turns. These do not conform to vehicle kinematic characteristics (such as minimum turning radius), preventing the vehicle from executing the path seamlessly.

• Computational Efficiency: Across large and complex maps, the volume of nodes requiring exploration can escalate rapidly, leading to prolonged processing times that compromise real-time decision-making.

🔧 Autonomous Driving Adaptations

To address these constraints, engineers have introduced tailored enhancements to optimise the A* algorithm for autonomous vehicle applications:

• Hybrid A (Hybrid A*)**：Incorporates vehicle kinematic constraints (such as turning radius) directly into the search heuristic while factoring in trajectory smoothness, ensuring the generated path is drivable from the outset. Research indicates that the refined Hybrid A* algorithm can slash search time by over 50%.

• Jump Point Search (JPS) + A* Integration: By intelligently "skipping" over large numbers of redundant nodes across the map, search efficiency is drastically improved. When paired with the Dynamic Window Approach (DWA), it handles local dynamic obstacles effectively for smarter obstacle avoidance.

• Algorithm Fusion: Utilises the global path generated by A* as a high-level guide, combined with dynamic-ready approaches such as the Ant Colony Algorithm to reliably navigate complex driving scenarios.