Skip to main content

Documentation Index

Fetch the complete documentation index at: https://mintlify.com/Juan-Carlos-Cruz/robotaxi-zoox/llms.txt

Use this file to discover all available pages before exploring further.

In a simple single-goal pathfinding problem, the search state is just the agent’s position — each cell is either visited or not, and the algorithm never needs to return to a cell it has already seen. Robotaxi Zoox cannot use that shortcut. Because the taxi must collect every passenger before reaching the destination, revisiting a cell is sometimes necessary: the taxi might need to backtrack through an already-visited corridor after picking up a passenger. A position-only state would incorrectly block those revisits. The solution is a composite state that encodes not just where the taxi is, but also which passengers it has already collected — making two visits to the same cell genuinely different states if the set of collected passengers has changed between them.

​
The Composite State

Every point in the search space is fully described by two pieces of information, both stored as attributes on a Node object:
AttributeTypeMeaning
posiciontuple[int, int]Current (row, col) of the taxi
pasajeros_recogidosfrozenset[tuple[int, int]]Positions of all passengers collected so far
A newly created root node starts with an empty pasajeros_recogidos: 
from mundo import Node

raiz = Node((2, 0))  # taxi at row=2, col=0, no passengers collected
hijo = Node((2, 1), pasajeros_recogidos=frozenset({(0, 0)}), padre=raiz, g=1)

print(hijo.profundidad)          # 1
print(hijo.pasajeros_recogidos)  # frozenset({(0, 0)})
Each Node also carries g (accumulated cost from the start), h (heuristic estimate), f = g + h (total priority for informed search), profundidad (depth from the root), and a padre pointer for path reconstruction.

​
Why a frozenset?

The collected-passenger component of the state is stored as a frozenset rather than a list or a regular set for two reasons:
  1. Immutability — a frozenset cannot be changed after creation. When Grid.get_vecinos builds a new successor node, it creates a brand-new frozenset by converting a temporary mutable set. The parent node’s state is never touched.
  2. Hashability — because it is immutable, a frozenset can participate in a hash computation. The Node.__hash__ method combines the position tuple and the frozenset into a single hash value, which lets nodes be stored directly in Python set and dict structures for O(1) visited-state lookup:
def __hash__(self):
    return hash((self.posicion, self.pasajeros_recogidos))
The equality check mirrors this exactly — two nodes represent the same state only when both their position and their collected-passenger set match: 
def __eq__(self, other):
    return (
        self.posicion == other.posicion
        and self.pasajeros_recogidos == other.pasajeros_recogidos
    )

​
State Transitions

Grid.get_vecinos(nodo) is the successor function. Given a node, it attempts all four directional moves and, for each passable target cell, constructs a new Node with an updated state:
  1. The new posicion is the (row, col) of the target cell.
  2. The new g is nodo.g + costo_movimiento(target) — cost 7 for FLUJO_ALTO, cost 1 for everything else.
  3. If the target cell contains a passenger (Grid.PASAJERO), that cell’s coordinates are added to pasajeros_recogidos before the new frozenset is frozen. The pickup is automatic — the taxi does not need a separate action.
nuevos_pasajeros = set(nodo.pasajeros_recogidos)          # mutable copy

if self.matriz[nueva_fila][nueva_columna] == Grid.PASAJERO:
    nuevos_pasajeros.add((nueva_fila, nueva_columna))     # record pickup

vecinos.append(Node(
    posicion=(nueva_fila, nueva_columna),
    pasajeros_recogidos=frozenset(nuevos_pasajeros),       # freeze it
    padre=nodo,
    g=costo,
))

​
Avoiding Cycles While Allowing Revisits

The search algorithms maintain a visitados set of already-expanded composite states. Before expanding a node, the algorithm checks: 
estado = (nodo.posicion, nodo.pasajeros_recogidos)

if estado in visitados:
    continue          # same position AND same passengers — genuine duplicate

visitados.add(estado)
Because the state includes pasajeros_recogidos, visiting a cell a second time after collecting a new passenger produces a different composite state — (pos, {passenger_A}) is not the same as (pos, frozenset()) — and is therefore not filtered out. This is what allows the taxi to legally backtrack through previously visited corridors after a pickup.
This design means the taxi is never unfairly stuck. If the only path to the destination runs back through the start cell, the search will find it — because the state on the return visit will include passengers that were not present on the first visit, making it a distinct, unvisited state.

​
Goal Test

A node is the goal when both components of its state simultaneously satisfy the terminal conditions: 
if nodo.posicion == grid.destino and nodo.pasajeros_recogidos == pasajeros_totales:
    return {
        "camino": nodo.obtener_camino(),
        "nodos_expandidos": nodos_expandidos,
        "profundidad": nodo.profundidad,
        "costo": nodo.g,
    }
pasajeros_totales is a frozenset of all passenger positions read from the map — constructed once before the search starts as frozenset(grid.pasajeros). The equality check nodo.pasajeros_recogidos == pasajeros_totales is an O(n) frozenset comparison that confirms every passenger has been collected.
The goal test is evaluated after the node is dequeued, not when it is generated. For BFS this makes no practical difference, but for UCS and A* it ensures the returned cost is the true optimal cost, not an underestimate from the generation step.

​
State Space Size

The total number of distinct states the search may need to explore is bounded by: 
|states| ≤ (number of cells) × 2^(number of passengers)
With P passengers on the map, each cell can appear in up to 2^P different states — one for each possible subset of collected passengers. For the built-in test maps, P is small (typically 2–4), so the state space remains tractable. A map with 10 passengers and a 20×20 grid would yield up to 400 × 1 024 ≈ 409 600 distinct states — still manageable, but growing rapidly with passenger count.
Adding many passengers to a custom map can cause exponential growth in the state space. If a search runs for a very long time or exhausts available memory, consider reducing the number of passenger cells or using an informed algorithm (Greedy or A*) that prunes the space more aggressively.

Build docs developers (and LLMs) love

Get started for freeTalk to us