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.

All three uninformed search strategies in Robotaxi Zoox share a single entry point — busqueda_no_informada — and differ only in how they manage the frontier. Pass "bfs" to get a FIFO queue, "dfs" to get a LIFO stack, or "ucs" to get a min-heap ordered by accumulated cost. Every other piece of logic — the visited set, goal test, and result dictionary — is identical across all three modes.

​
Function signature

from algoritmosBusqueda.noinformada.wrapper import busqueda_no_informada

resultado = busqueda_no_informada(grid, nodo_inicial, pasajeros_totales, modo)
ParameterTypeDescription
gridGridThe map object that generates neighbour nodes and movement costs
nodo_inicialNodeStarting state with position and an empty pasajeros_recogidos set
pasajeros_totalesfrozenset[tuple[int, int]]All passenger positions that must be collected before reaching the destination
modostrFrontier strategy: "bfs", "dfs", or "ucs"

​
Breadth-First Search (BFS / "amplitud")

BFS explores all nodes at the current depth before moving deeper. The frontier is a deque and nodes are enqueued at the back and dequeued from the front, guaranteeing that shallower nodes are always processed first.
  • Frontier: collections.deque — FIFO queue
  • Strategy: expand the shallowest node first
  • Complete: yes
  • Optimal: yes for uniform-cost graphs (all edges cost 1)
from collections import deque

# Initialise
frontera = deque([nodo_inicial])

# Enqueue a neighbour
def push(nodo):
    frontera.append(nodo)       # add to the right (back)

# Dequeue the oldest node
def pop():
    return frontera.popleft()   # remove from the left (front)
BFS optimality holds when every step costs the same. On maps with FLUJO_ALTO cells (cost 7), BFS may return a path with fewer steps that is more expensive than a longer route that avoids traffic. Use UCS when movement costs vary.
When to use: you want the fewest grid steps regardless of traffic cost, or you need a simple baseline to compare against other algorithms.

​
Uniform-Cost Search (UCS / "costo")

UCS generalises BFS to weighted graphs. The frontier is a min-heap ordered by g — the accumulated cost from the start. The node with the lowest g is always expanded next, ensuring the cheapest path is found regardless of depth.
  • Frontier: heapq min-heap ordered by g
  • Strategy: expand the lowest-cost node first
  • Complete: yes
  • Optimal: yes
import heapq

# Initialise — (cost, tie-break counter, node)
frontera = []
contador = 0
heapq.heappush(frontera, (nodo_inicial.g, contador, nodo_inicial))

# Enqueue a neighbour, ordered by accumulated cost
def push(nodo):
    nonlocal contador
    contador += 1
    heapq.heappush(frontera, (nodo.g, contador, nodo))

# Dequeue the cheapest node
def pop():
    return heapq.heappop(frontera)[2]
The contador tie-breaker prevents Python from comparing Node objects directly when two nodes share the same g value. When to use: you want the cheapest total route, especially on maps where FLUJO_ALTO cells (cost 7) significantly inflate some paths.

​
Depth-First Search (DFS / "profundidad")

DFS always expands the most recently added node. The frontier is a plain Python list used as a LIFO stack: append pushes to the top and pop removes from it.
  • Frontier: list — LIFO stack
  • Strategy: expand the deepest node first
  • Complete: yes (with a visited set to avoid cycles)
  • Optimal: no — may return a longer or more expensive path
# Initialise
frontera = [nodo_inicial]

# Push a neighbour onto the stack
def push(nodo):
    frontera.append(nodo)   # add to the top

# Pop the most recent node
def pop():
    return frontera.pop()   # remove from the top
Without cycle avoidance DFS can loop indefinitely. The shared visitados set (see below) prevents this by tracking (posicion, pasajeros_recogidos) state pairs that have already been expanded.
When to use: memory is constrained and a suboptimal path is acceptable, or you want fast exploration depth before width.

​
Visited set and cycle avoidance

All three modes share the same visitados set. A state is the pair (posicion, pasajeros_recogidos): 
visitados = set()

# Inside the main loop:
nodo = pop()
estado = (nodo.posicion, nodo.pasajeros_recogidos)

if estado in visitados:
    continue            # already expanded this state — skip it

visitados.add(estado)
nodos_expandidos += 1
Encoding both position and the set of collected passengers as the state is intentional. The same grid cell can be visited multiple times as long as the set of collected passengers is different — for example, the taxi might backtrack through a previously visited cell after picking up a new passenger. This design allows the search to find multi-passenger routes without false cycle detection.

​
Return value

On success, the function returns a plain dictionary: 
{
    "camino":            [(row, col), ...],  # ordered list of positions
    "nodos_expandidos":  int,                # nodes popped from the frontier
    "profundidad":       int,                # depth of the goal node
    "costo":             int,                # total accumulated movement cost
}
None is returned when the frontier empties without reaching the goal — either because the map has no valid route or a required passenger is blocked by walls.

​
Full usage example

from mundo import Grid, Node, leer_mapa
from algoritmosBusqueda.noinformada.wrapper import busqueda_no_informada

# Load a map from a text file
matriz = leer_mapa('mapas/test/Prueba1.txt')
grid = Grid(matriz)

# Build the initial node — no passengers collected yet
nodo_inicial = Node(posicion=grid.inicio, pasajeros_recogidos=frozenset())
pasajeros_totales = frozenset(grid.pasajeros)

# Run BFS
resultado = busqueda_no_informada(grid, nodo_inicial, pasajeros_totales, 'bfs')

if resultado:
    print(f"Path length: {len(resultado['camino'])}")
    print(f"Cost: {resultado['costo']}")
    print(f"Nodes expanded: {resultado['nodos_expandidos']}")
Swap 'bfs' for 'ucs' or 'dfs' to use a different strategy — the rest of the code stays the same.
Passing any modo value other than "bfs", "dfs", or "ucs" raises a ValueError. Always use one of these exact strings; the UI keys ("amplitud", "profundidad", "costo") are translated to mode strings by ejecutar_algoritmo in application/ejecucion.py before the wrapper is called.

Build docs developers (and LLMs) love

Get started for freeTalk to us