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.

Robotaxi Zoox implements two families of search to solve the same multi-passenger pickup problem: uninformed algorithms that explore the grid with no knowledge of how far away the goal is, and informed algorithms that use a heuristic to estimate remaining distance. Every algorithm must collect all passengers and then reach the destination, but each makes different trade-offs between completeness, optimality, memory use, and speed.

​
Algorithm families

Uninformed algorithms treat every unexplored state equally — they differ only in the order they pull nodes from the frontier. Informed algorithms attach a heuristic estimate h to each node, so the frontier is always sorted toward the most promising state. The ALGORITHM_CONFIG dictionary in application/config.py maps the UI key for each algorithm to its family and internal mode string: 
ALGORITHM_CONFIG = {
    "a_estrella":  ("informada",    "a_estrella"),
    "avara":       ("informada",    "avara"),
    "amplitud":    ("no_informada", "bfs"),
    "costo":       ("no_informada", "ucs"),
    "profundidad": ("no_informada", "dfs"),
}
UI KeyAlgorithmFamily
amplitudBreadth-First Search (BFS)Uninformed
costoUniform-Cost Search (UCS)Uninformed
profundidadDepth-First Search (DFS)Uninformed
avaraGreedy Best-First SearchInformed
a_estrellaA*Informed

​
Algorithm comparison

AlgorithmKeyCompleteOptimalFrontierNotes
BFSamplitudYesYes (uniform cost)Queue (FIFO)Guaranteed shortest path in steps
UCScostoYesYesPriority queue by gOptimal for weighted graphs
DFSprofundidadYes (cycle-avoidance)NoStack (LIFO)Low memory, no cost guarantee
GreedyavaraNoNoPriority queue by hFast but may miss optimal routes
A*a_estrellaYesYes (admissible h)Priority queue by f = g + hBest overall cost-optimality balance
“Complete” means the algorithm will always find a solution if one exists. “Optimal” means it always finds the lowest-cost solution. DFS is complete here because the implementation tracks a visited set to prevent cycles.

​
The heuristic

Informed algorithms compute a Manhattan distance estimate h at every node: 
h = |row1 - row2| + |col1 - col2|
The target for h depends on the current state:
  • Passengers remain uncollected — h is the Manhattan distance to the nearest uncollected passenger.
  • All passengers collected — h is the Manhattan distance to the destination.
This heuristic is admissible: it never overestimates the true cost because Manhattan distance is a lower bound on any path through a grid (a direct diagonal shortcut is always shorter than or equal to the real route through passable cells). Admissibility guarantees that A* will always return an optimal solution.

​
Result metrics

Both busqueda_no_informada and busqueda_informada return a dictionary when a solution is found, or None when the goal is unreachable:
KeyTypeDescription
caminolist[tuple[int, int]]Ordered sequence of grid positions from start to destination
nodos_expandidosintTotal nodes popped from the frontier during the search
profundidadintDepth of the solution node in the search tree
costointAccumulated movement cost along the solution path
heuristicaintFinal h value at the goal node — informed algorithms only
FLUJO_ALTO (high-traffic) cells carry a movement cost of 7, while all other traversable cells cost 1. This cost difference makes UCS and A* more meaningful than BFS or DFS on maps with traffic zones.

​
Explore each family

Uninformed Search

BFS, UCS, and DFS via the busqueda_no_informada function — frontier strategies, cycle avoidance, and when to use each.

Informed Search

Greedy Best-First and A* via the busqueda_informada function — the Manhattan heuristic, admissibility, and best_g optimisation.

Build docs developers (and LLMs) love

Get started for freeTalk to us