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.

Informed search algorithms use a heuristic function h to estimate the cost remaining from any state to the goal, guiding the search toward promising nodes rather than expanding the frontier blindly. In Robotaxi Zoox, both informed algorithms — Greedy Best-First and A* — are exposed through a single function, busqueda_informada, and share the same Manhattan-distance heuristic. They differ only in what value drives the priority queue: Greedy uses h alone, while A* uses f = g + h, balancing real cost against estimated remaining cost.

​
Function signature

from algoritmosBusqueda.informada.wrapper import busqueda_informada

resultado = busqueda_informada(grid, inicio, destino, pasajeros, modo)
ParameterTypeDescription
gridGridThe map object that generates neighbour nodes and movement costs
iniciotuple[int, int]Starting position (row, col) — typically grid.inicio
destinotuple[int, int]Destination position (row, col) — typically grid.destino
pasajerosCollection[tuple[int, int]]All passenger positions that must be collected before reaching the destination
modostrSearch strategy: "avara" (Greedy) or "a_estrella" (A*)

​
The Manhattan heuristic

The heuristic estimates the cheapest possible remaining path using straight-line Manhattan distance — the sum of absolute row and column differences between two grid positions: 
h = |row1 - row2| + |col1 - col2|
Both helper functions are defined in algoritmosBusqueda/informada/wrapper.py: 
def heuristica_manhattan(pos1, pos2):
    """Calculates Manhattan distance between two (row, col) positions."""
    return abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1])


def calcular_heuristica(nodo, destino, pasajeros, meta_pasajeros):
    """Estimates distance to the next pending objective.

    If all passengers have been collected, returns distance to the destination.
    Otherwise, returns distance to the nearest uncollected passenger.
    """
    if nodo.pasajeros_recogidos == meta_pasajeros:
        return heuristica_manhattan(nodo.posicion, destino)

    pasajeros_faltantes = [p for p in pasajeros if p not in nodo.pasajeros_recogidos]
    return min(heuristica_manhattan(nodo.posicion, p) for p in pasajeros_faltantes)
The target for h adapts to the taxi’s current state:
  • Passengers still pending → h = distance to the nearest uncollected passenger
  • All passengers collected → h = distance to the destination

​
Admissibility

The Manhattan heuristic is admissible — it never overestimates the true cost to reach the goal. On a grid, the actual path between two cells must traverse at least as many steps as the Manhattan distance (which assumes movement in a straight line with no walls). Because h ≤ actual remaining cost at every node, A* is guaranteed to return an optimal solution.
Admissibility is preserved even with FLUJO_ALTO cells. Those cells cost 7 to enter, so the real cost can only be greater than or equal to the Manhattan estimate, never less.

​
Greedy Best-First Search ("avara")

Greedy search prioritises nodes purely by their heuristic value h, ignoring how much the path so far has cost. The node that looks closest to the goal is always expanded first.
  • Priority: h only (accumulated cost g is ignored)
  • Frontier: heapq min-heap ordered by h
  • Complete: no — on certain map configurations the algorithm can revisit states or exhaust the frontier without finding the goal (the visited set mitigates cycles but does not guarantee completeness)
  • Optimal: no — the cheapest-looking path at each step is not necessarily the cheapest overall
# Greedy uses a visited set (same pattern as uninformed BFS/DFS)
visitados = set()
heapq.heappush(frontera, (nodo_inicial.h, contador, nodo_inicial))

# During expansion — skip already-visited states
if estado in visitados:
    continue
visitados.add(estado)

# Neighbour priority is h alone
prioridad = vecino.h
heapq.heappush(frontera, (prioridad, contador, vecino))
When to use: speed matters more than optimality. On simple, open maps Greedy typically expands far fewer nodes than BFS or UCS and reaches a solution quickly, even if that solution costs more.

​
A* Search ("a_estrella")

A* combines the real accumulated cost g with the heuristic estimate h into a single priority value f = g + h. This balances exploration of cheap paths with guidance toward the goal, making it both complete and optimal.
  • Priority: f = g + h
  • Frontier: heapq min-heap ordered by f
  • Complete: yes
  • Optimal: yes (with an admissible heuristic)

​
best_g instead of a visited set

A* uses a best_g dictionary rather than a plain visited set. This allows a node to be re-expanded if a cheaper path to the same state is discovered later — something a simple visited set would prevent: 
# A* tracks the best known cost for each state
best_g = {}
heapq.heappush(frontera, (nodo_inicial.f, contador, nodo_inicial))

# During expansion — skip only if we have already found a cheaper or equal path
if estado in best_g and best_g[estado] <= nodo.g:
    continue
best_g[estado] = nodo.g     # record the new best cost for this state

# Neighbour priority is f = g + h
prioridad = vecino.f        # vecino.f = vecino.g + vecino.h
heapq.heappush(frontera, (prioridad, contador, vecino))
Because A* only skips a state when a cheaper or equal path has already been recorded, it can revisit a state via a newly found cheaper route. This is what makes it optimal on graphs with varying edge costs, such as maps with FLUJO_ALTO cells.
When to use: you want the best cost-optimality balance. A* typically finds the same optimal solution as UCS while expanding fewer nodes, because the heuristic prunes unpromising branches early.

​
Return value

On success, busqueda_informada returns a dictionary that extends the uninformed result with one extra key: 
{
    "camino":            [(row, col), ...],  # ordered list of positions
    "costo":             int,                # total accumulated movement cost
    "nodos_expandidos":  int,                # nodes popped from the frontier
    "profundidad":       int,                # depth of the goal node
    "heuristica":        int,                # h value at the goal node
}
None is returned when the frontier empties without finding a valid route. The "heuristica" key holds the final h at the destination. Because all passengers have been collected when the goal is reached, this value will always be 0 (Manhattan distance from the destination to itself) — it is included for reporting and verification purposes.

​
Full usage example

from mundo import Grid, leer_mapa
from algoritmosBusqueda.informada.wrapper import busqueda_informada

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

# Run A*
resultado = busqueda_informada(
    grid,
    grid.inicio,
    grid.destino,
    grid.pasajeros,
    'a_estrella'
)

if resultado:
    print(f"Cost: {resultado['costo']}")
    print(f"Nodes expanded: {resultado['nodos_expandidos']}")
    print(f"Heuristic (final h): {resultado['heuristica']}")
Replace 'a_estrella' with 'avara' to run Greedy Best-First instead — all other arguments remain the same.
Use A* when you need the optimal (lowest-cost) path with reasonable search time. Use Greedy when you need a fast approximate solution and can tolerate a suboptimal route.
Passing any modo value other than "avara" or "a_estrella" raises a ValueError. The UI keys ("avara" and "a_estrella") happen to match the internal mode strings for informed search, but the uninformed strings ("bfs", "dfs", "ucs") are not valid here.

Build docs developers (and LLMs) love

Get started for freeTalk to us