Principle:CARLA simulator Carla A Star Route Planning
| Knowledge Sources | |
|---|---|
| Domains | Graph Search, Path Planning, Autonomous Driving |
| Last Updated | 2026-02-15 00:00 GMT |
Overview
A* Route Planning is the application of the A* graph search algorithm to compute optimal routes through the CARLA road network graph. Given an origin and destination location, the algorithm finds the shortest path through the networkx.DiGraph using Euclidean distance as both edge weight and heuristic, then post-processes the path into an annotated sequence of waypoints with maneuver instructions (LANEFOLLOW, LEFT, RIGHT, STRAIGHT, etc.).
Description
The route planning process in CARLA's GlobalRoutePlanner operates in three phases:
- Location-to-Node Mapping: The origin and destination
carla.Locationvalues are projected onto the nearest waypoints on the map, which are then mapped to their corresponding graph nodes via the(road_id, section_id, lane_id)identifier.
- A* Graph Search: The
networkx.astar_path()function is invoked on the road network graph with Euclidean distance as the heuristic. This produces an optimal sequence of graph node IDs from origin to destination.
- Route Annotation: The raw node path is converted into a list of
(carla.Waypoint, RoadOption)tuples. Each pair in the route is analyzed to determine the maneuver at transitions: lane following, turning left/right at intersections, going straight through intersections, or changing lanes. TheRoadOptionenum encodes these decisions.
Usage
Use A* route planning when you need to:
- Compute the shortest driving route between two arbitrary points on a CARLA map
- Generate a global route plan that local planners can follow waypoint by waypoint
- Annotate routes with turn-by-turn maneuver instructions for behavior planning
- Evaluate route alternatives by modifying edge weights (e.g., penalizing highways, preferring shorter roads)
Theoretical Basis
The A* Algorithm
A* is a best-first graph search algorithm that finds the least-cost path from a start node s to a goal node g. It maintains a priority queue ordered by:
f(n) = g(n) + h(n)
where:
- g(n) = actual cost from start node s to node n (sum of edge weights along the path so far)
- h(n) = heuristic estimate of cost from n to goal g
- f(n) = estimated total cost of the cheapest path through n
A* Pseudocode
function A_STAR(graph, start, goal, heuristic):
open_set = priority_queue()
open_set.insert(start, f=0 + heuristic(start, goal))
came_from = {}
g_score = {start: 0}
while open_set is not empty:
current = open_set.pop_min()
if current == goal:
return reconstruct_path(came_from, current)
for neighbor in graph.neighbors(current):
tentative_g = g_score[current] + weight(current, neighbor)
if tentative_g < g_score.get(neighbor, infinity):
came_from[neighbor] = current
g_score[neighbor] = tentative_g
f_score = tentative_g + heuristic(neighbor, goal)
open_set.insert_or_update(neighbor, f_score)
return failure # no path exists
Heuristic: Euclidean Distance
CARLA's implementation uses the straight-line Euclidean distance between node positions as the heuristic:
h(n, goal) = sqrt((n.x - goal.x)^2 + (n.y - goal.y)^2 + (n.z - goal.z)^2)
This heuristic is admissible (never overestimates the true shortest path distance, since the shortest path through roads is always at least as long as the straight line) and consistent (satisfies the triangle inequality), guaranteeing that A* returns the optimal path.
Optimality and Complexity
- Optimality: A* with an admissible and consistent heuristic is guaranteed to find the shortest path.
- Time complexity: O(|E| log |V|) in the worst case, where |V| is the number of nodes and |E| the number of edges. In practice, A* with a good heuristic explores far fewer nodes than Dijkstra's algorithm.
- Space complexity: O(|V|) for the open and closed sets.
Route Annotation: RoadOption Enum
After the path is found, each transition is classified:
| RoadOption | Value | Description |
|---|---|---|
| VOID | -1 | Default, used for initialization |
| LEFT | 1 | Left turn at an intersection |
| RIGHT | 2 | Right turn at an intersection |
| STRAIGHT | 3 | Go straight through an intersection |
| LANEFOLLOW | 4 | Follow the current lane (no maneuver) |
| CHANGELANELEFT | 5 | Change to the left adjacent lane |
| CHANGELANERIGHT | 6 | Change to the right adjacent lane |
The annotation logic computes the angle between consecutive edge vectors at intersection nodes to distinguish left turns, right turns, and straight passages.