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.

busqueda_informada implements two heuristic-guided algorithms — Greedy Best-First (priority by h) and A* (priority by f = g + h) — using the same Manhattan-distance heuristic function to estimate distance to the next uncollected passenger or the final destination. Both algorithms share the same goal condition: every passenger must be collected before the taxi reaches destino. The heuristic is admissible on a grid (it never overestimates), which guarantees that A* returns a cost-optimal solution.

​
Import

from algoritmosBusqueda.informada.wrapper import busqueda_informada
The module also exports two heuristic helpers used internally and available for external use: 
from algoritmosBusqueda.informada.wrapper import heuristica_manhattan, calcular_heuristica

​
Heuristic helper functions

​
heuristica_manhattan

heuristica_manhattan(pos1, pos2) -> int
Calculates the Manhattan distance between two grid positions. Returns abs(r1 - r2) + abs(c1 - c2). Because the taxi can only move in four cardinal directions, this value never overestimates the true path cost, making it an admissible heuristic. 
>>> heuristica_manhattan((0, 0), (2, 3))
5

​
calcular_heuristica

calcular_heuristica(nodo, destino, pasajeros, meta_pasajeros) -> int
Estimates the cost-to-go for a given node. If the node has already collected all required passengers (nodo.pasajeros_recogidos == meta_pasajeros), it returns the Manhattan distance to destino. Otherwise it returns the minimum Manhattan distance to any uncollected passenger — the nearest unvisited pickup. 
>>> nodo = Node((0, 0))
>>> calcular_heuristica(nodo, (2, 2), [(0, 2)], frozenset({(0, 2)}))
2

​
busqueda_informada signature

busqueda_informada(grid, inicio, destino, pasajeros, modo) -> dict | None
​
grid
Grid
required
The map object that provides get_vecinos for neighbour generation and movement costs.
​
inicio
tuple[int,int]
required
Starting (row, column) position of the taxi on the grid.
​
destino
tuple[int,int]
required
Terminal (row, column) position the taxi must reach after collecting all passengers.
​
pasajeros
Collection[tuple[int,int]]
required
All passenger positions that must be collected before the goal is satisfied. Pass grid.pasajeros directly.
​
modo
str
required
Algorithm variant to run. Must be 'avara' (Greedy Best-First) or 'a_estrella' (A*). Any other value raises a ValueError.

​
Return value

Returns a dict with the following keys on success, or None when the destination is unreachable.
​
camino
list[tuple[int,int]]
Ordered list of grid positions from start to destination, inclusive.
​
costo
int
Total accumulated movement cost g of the solution node.
​
nodos_expandidos
int
Number of nodes popped from the frontier and processed during the search.
​
profundidad
int
Depth of the solution node in the search tree.
​
heuristica
int
The h value of the solution node at the moment it was identified as the goal. This is 0 for A* when the destination is reached with all passengers collected.
Returns None when no valid route exists. Always guard against None before accessing result keys. Passing an unrecognised modo string raises ValueError immediately.

​
Greedy vs A* comparison

Property'avara' (Greedy)'a_estrella' (A*)
Priority keyh onlyf = g + h
Cost-optimalNoYes (with admissible h)
Visited trackingvisited set — a state is never re-expandedbest_g dict — re-expands a state if a cheaper path is found later
SpeedOften faster in practiceSlower but guarantees optimal cost
A* uses a best_g dictionary instead of a plain visited set. When a state is popped from the frontier, the search only skips it if the previously recorded cost is already less than or equal to the current node’s g. This allows A* to re-expand a state via a newly discovered cheaper path — a key difference from Greedy.

​
Heuristic details

FunctionFormulaWhen used
heuristica_manhattanabs(r1−r2) + abs(c1−c2)Base distance calculation between any two cells
calcular_heuristicamin Manhattan to uncollected passengerWhen passengers remain to be picked up
calcular_heuristicaManhattan to destinoWhen all passengers have been collected
The heuristic is computed for every newly generated neighbour node before it is pushed onto the frontier, so the h and f attributes of each Node are always up to date.

​
Usage example

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

matriz = leer_mapa()
grid = Grid(matriz)

resultado = busqueda_informada(
    grid,
    grid.inicio,
    grid.destino,
    grid.pasajeros,
    'a_estrella'
)
if resultado:
    print(f"Cost: {resultado['costo']}")
    print(f"Heuristic (h): {resultado['heuristica']}")

Build docs developers (and LLMs) love

Get started for freeTalk to us