Principle:CARLA simulator Carla Waypoint Queue Completion

Knowledge Sources	CARLA Simulator CARLA Documentation LaValle, "Planning Algorithms", Cambridge University Press, Chapter 8 - Feedback Motion Planning, 2006
Domains	Motion Planning, Route Tracking, Autonomous Driving
Last Updated	2026-02-15 00:00 GMT

Overview

Waypoint Queue Completion is the mechanism by which the CARLA navigation agent determines that a vehicle has reached its destination. The local planner maintains a double-ended queue (deque) of upcoming waypoints extracted from the global route. As the vehicle traverses the route, waypoints are consumed from the front of the queue. When the queue is depleted (empty), the agent concludes that the destination has been reached.

Description

The route completion detection relies on the interplay between three components:

1. Global route plan: The GlobalRoutePlanner.trace_route() method produces a complete list of (carla.Waypoint, RoadOption) tuples from origin to destination.

1. Local planner waypoint queue: The LocalPlanner loads this route into a collections.deque with a configurable maximum size (default: 10000). At each simulation tick, the local planner:
   • Checks if the vehicle has passed the front waypoint (based on proximity and dot-product direction check)
   • If passed, pops the waypoint from the front of the queue
   • Selects the new front waypoint as the next control target for the PID controller

1. Completion check: BasicAgent.done() simply queries LocalPlanner.done(), which returns True when the waypoint queue is empty -- meaning every waypoint in the route has been consumed.

Usage

Use waypoint queue completion when you need to:

• Determine when an agent has finished navigating to its destination
• Trigger post-arrival actions (e.g., park the vehicle, assign a new destination, log results)
• Implement multi-destination route sequences by checking done() before setting the next waypoint
• Build termination conditions for simulation episodes or benchmarking runs

Theoretical Basis

Queue-Based Route Tracking

The route tracking mechanism is a FIFO (First-In, First-Out) consumption model:

INITIAL STATE:
    queue = deque([wp_0, wp_1, wp_2, ..., wp_n])   # Full route
    done = False

EACH TICK:
    if vehicle has passed queue[0]:
        queue.popleft()                              # Consume waypoint

    if len(queue) == 0:
        done = True                                  # Destination reached
    else:
        target = queue[0]                            # Next waypoint to track
        control = pid_controller(target)

Waypoint Consumption Criteria

A waypoint w_i is considered "passed" when:

# Distance check: vehicle is close enough to the waypoint
distance(vehicle.location, w_i.location) < threshold

# Direction check: vehicle has moved beyond the waypoint
dot(vehicle.forward_vector, w_i.location - vehicle.location) < 0

The direction check (negative dot product) ensures that waypoints behind the vehicle are consumed even if the distance threshold hasn't been met precisely, preventing the agent from getting stuck trying to reach a waypoint it has already passed.

Edge Cases

Scenario	Behavior
Vehicle overshoots a waypoint	Consumed by direction check (negative dot product)
Vehicle stops far from destination	Queue retains remaining waypoints; done() returns False
Route has only one waypoint	Queue depletes after passing that single waypoint
set_destination() called again	Queue is refilled with the new route; done() resets to False
Queue buffer overflow (route > max_size)	Deque silently drops oldest waypoints from the back; this is unlikely with default size of 10000

Completeness Guarantee

The waypoint queue provides a strong termination guarantee: assuming the vehicle makes forward progress along the route, every waypoint will eventually be consumed. The agent cannot falsely report completion because:

• Waypoints are only removed when the vehicle physically passes them
• The queue starts fully loaded with the entire route
• No waypoints are added after initialization (unless set_destination() is called again)

Related Pages

Implemented By

• Implementation:CARLA_simulator_Carla_BasicAgent_Done