Planificación de caminos y mapeo: de Flood Fill a SLAM
Podrá planificar rutas en rejillas conocidas, replanificar ante nuevos obstáculos y comprender cómo un robot construye el mapa sobre el que navega.
La navegación reactiva saca a un robot de una habitación sin saber nunca dónde está. Eso se agota rápido: un robot puramente reactivo no puede recibir la orden de ve a la cocina, y le dará vueltas perpetuamente en una habitación con forma de herradura. La planificación es la respuesta, y necesita algo que el control reactivo nunca tiene: un mapa.
Esta ruta empieza donde el mapa es gratis. En un laberinto, el flood fill inunda distancias hacia fuera desde la meta y el robot simplemente baja por el gradiente, replanificando en el instante en que descubre una pared que había dado por abierta. Después el mundo se complica: A* planifica sobre una rejilla de ocupación donde las celdas tienen coste, los obstáculos necesitan inflarse, y la heurística decide si su planificador es rápido o solo correcto.
El último nodo es el honesto. Todo planificador anterior asume que tiene un mapa, y un robot real tiene que construirlo mientras se mueve sobre ruedas que le mienten. SLAM es lo que pasa cuando el mapeo y la localización se niegan a separarse, y el cierre de bucle es lo que evita que el mapa se deforme a medida que deriva la odometría. Una IMU se gana su sitio aquí por la misma razón: mide la rotación directamente, cosa que unas ruedas que patinan sencillamente no pueden.
Antes de empezar
Debe sentirse cómodo con arrays bidimensionales y pensamiento algorítmico básico: colas, y la idea de visitar celdas en un orden. Vale la pena hacer antes la ruta de control de motores, porque todos los planificadores de aquí asumen que el robot puede ejecutar un movimiento ordenado e informar aproximadamente cuánto ha avanzado.
Lo que podrá hacer
- Inundar una rejilla con distancias desde una meta y seguir el gradiente hasta ella.
- Ejecutar A* con una heurística que usted pueda demostrar que nunca sobreestima, y explicar por qué esa propiedad es lo que hace que el resultado sea el más corto.
- Convertir lecturas de distancia en una rejilla de ocupación por trazado de rayos, actualizando por separado las celdas libres y las ocupadas.
- Decir por qué la odometría sola no puede producir un mapa utilizable en un recorrido largo, y qué aporta SLAM.
Dónde se atasca la gente
Una heurística que sobreestima. A* solo garantiza el camino más corto cuando la heurística nunca reclama una distancia mayor que el coste restante real. Usar la distancia euclidiana en una rejilla de 4 conexiones, o escalar una heurística para acelerar la búsqueda, devuelve en silencio rutas que no son las más cortas.
Planificar para un robot puntual. La ruta se calcula a través de la rejilla, pero el robot tiene ancho. Una ruta que roza una esquina es geométricamente válida y físicamente una colisión. Infle los obstáculos por el radio del robot antes de planificar, y el problema desaparece.
Tratar lo desconocido como libre. Una celda que nada ha observado no está vacía: está sin medir. Si planifica a través de ella como espacio libre, el robot se mete con toda confianza en lo que nunca se vio. Lo desconocido es un tercer estado, y tiene que seguir siendo un tercer estado.
Pasos diagonales que cuestan uno. En una rejilla de 8 conexiones un paso diagonal cubre √2 celdas, no una. Cobrarlo como uno produce rutas que prefieren escaleras y distancias que sencillamente están mal.
Suponer que el robot está donde dice la odometría. Todos los planificadores de aquí operan sobre una postura. La odometría de rueda deriva sin límite, así que un plan perfecto se ejecuta desde una posición cada vez más ficticia. Esa brecha es toda la motivación del último nodo de esta ruta.
Qué necesita
| Qué | Por qué lo necesita esta ruta | Notas |
|---|---|---|
| Dominio de arrays 2D y colas | Todos los algoritmos de aquí son un bucle sobre una rejilla | Sin matemáticas avanzadas: una cola y un bucle anidado es todo el instrumental |
| Un robot que ejecute movimientos ordenados | Un plan no vale nada si el robot no puede recorrerlo | La ruta de control de motores le trae hasta aquí |
| Un giróscopo o IMU | Las ruedas no pueden medir una rotación por la que han patinado | MPU-6050; los nodos de mapeo dependen del rumbo |
| Un sensor de distancia, idealmente barredor | Las celdas solo se conocen midiéndolas | Un sonar barrido por un servo basta para construir una rejilla burda |
| Un sitio donde visualizar una rejilla | Depurar un planificador mirando un robot es casi imposible | Imprima ASCII por serie, o use los laboratorios de esta ruta |
Los dos laboratorios se ejecutan enteramente en el navegador, así que puede completar los nodos de flood fill y de cobertura sin hardware alguno.
Por qué la ruta sigue este orden
El laberinto va primero porque el mapa es gratis. En un laberinto de micromouse el mundo es una rejilla por construcción: las celdas tienen un tamaño conocido, las paredes están en los límites de las celdas, y la posición del robot es siempre un índice de celda. Eso elimina todos los problemas de percepción de una vez y deja solo la planificación, que es lo que usted está aquí para aprender. El flood fill en una rejilla conocida es la introducción más limpia posible a «calcule un campo de distancias y luego baje por el gradiente».
A* va segundo porque elimina las comodidades del laberinto una a una. Ahora las celdas tienen coste y no solo paredes. La rejilla es más grande, así que expandirla entera es un desperdicio y una heurística empieza a compensar. El robot tiene ancho, así que los obstáculos necesitan inflarse. Y las celdas pueden ser desconocidas, que es una idea realmente nueva que el laberinto nunca necesitó.
Las rejillas de ocupación van terceros porque son donde el mapa deja de dárselo. El trazado de rayos convierte una lectura de distancia en evidencia sobre muchas celdas a la vez —todo a lo largo del rayo es más probablemente libre, el extremo es más probablemente ocupado— y actualizar esas dos cosas por separado es toda la técnica.
La IMU está aquí deliberadamente. Llega exactamente en el nodo donde el error de rumbo empieza a escribirse en el mapa, porque un giróscopo mide la rotación directamente y unas ruedas que patinan sencillamente no pueden.
SLAM va al final porque es la confesión de que los nodos anteriores estaban asumiendo algo falso. Todo planificador anterior opera sobre una postura, y toda postura anterior vino de una odometría que deriva sin límite. SLAM es lo que pasa cuando deja de fingir que el mapeo y la localización se pueden resolver por separado.
La cobertura cierra la ruta porque es el problema que más obviamente necesita un mapa y menos obviamente se puede resolver de forma reactiva. «¿He estado en todas partes?» es una pregunta que solo la memoria puede responder.
Puntos de control: cómo saber que una etapa caló
| Etapa | La comprobación | Qué es un aprobado |
|---|---|---|
| Flood fill | Imprimir el campo de distancias de un laberinto pequeño | La meta es 0, los valores crecen hacia fuera, y las paredes crean los desvíos que usted espera |
| Replanificación | Revelar una pared que el robot daba por abierta | El campo se actualiza y el siguiente movimiento del robot cambia, sin reexplorar |
| Corrección de A* | Ejecutarlo sobre una rejilla cuya respuesta conoce a mano | La misma longitud que el camino más corto calculado a mano, siempre |
| Admisibilidad | Escalar a propósito su heurística ×2 | La búsqueda se acelera y la ruta se alarga: ahora ha visto el intercambio |
| Coste diagonal | Planificar a través de espacio abierto en una rejilla de 8 conexiones | La ruta es una diagonal recta, no una escalera; las diagonales cuestan √2 |
| Inflación de obstáculos | Planificar pasando una esquina con la inflación apagada y luego encendida | Apagada, la ruta roza la esquina; encendida, la despeja por el radio del robot |
| Rejilla de ocupación | Barrer un sensor a través de un vano y renderizar la rejilla | Aparece espacio libre a lo largo de los rayos, celdas ocupadas en los extremos, desconocido tras las paredes |
| Tratamiento de lo desconocido | Pedirle a su planificador una ruta hacia espacio no cartografiado | Se niega, o se compromete deliberadamente: cualquier cosa vale, adivinar no |
| Deriva | Recorrer un bucle cerrado y comparar el inicio y el final del mapa | El mapa no cierra: esa brecha es exactamente lo que el cierre de bucle existe para arreglar |
| Cobertura | Ejecutar un barrido planificado y una marcha aleatoria el mismo tiempo | El barrido planificado cubre mucho más, y puede dar los dos porcentajes |
Dónde termina esta ruta
Esta ruta planifica en un mundo estático, bidimensional y de tamaño conocido. Cada una de esas palabras es una limitación que conviene nombrar.
Estático. Nada de esto contempla que alguien cruce el plan andando. Los obstáculos dinámicos necesitan un planificador local corriendo por debajo del global, replanificando mucho más rápido de lo que A* sobre una rejilla entera puede.
Bidimensional. Una rejilla de celdas libres y ocupadas es un plano de planta. No puede representar una mesa por debajo de la que se puede pasar pero no atravesar, y por eso los robots serios usan representaciones 3D o mapas de coste por capas.
Basado en rejilla. Los planificadores por muestreo como RRT y RRT* manejan espacios de alta dimensión —el espacio articular de un brazo robótico, por ejemplo— donde una rejilla no tiene ninguna esperanza. Cambian la garantía de camino más corto por la capacidad de trabajar.
La ruta tampoco cubre los filtros de partículas o la localización de Monte Carlo, que es como un robot se encuentra a sí mismo en un mapa que le dieron en vez de uno que está construyendo. Ese es el problema más sencillo y con mucha más frecuencia, y conviene saber que existe antes de recurrir al SLAM completo.
Ruta de aprendizaje
La ruta
Sigue los nodos en orden: cada uno desbloquea el siguiente cuando lo completas. Tu progreso se guarda en este dispositivo.
0 / 9 completados
Preguntas comunes
Preguntas frecuentes
¿Cuál es la diferencia entre Flood Fill y A* para navegación robótica?
Flood Fill calcula de forma masiva la distancia desde el objetivo a todas las celdas de la cuadrícula, permitiendo al robot descender por el gradiente desde cualquier posición. A* busca desde un origen puntual hacia un destino único guiado por una función heurística que expande solo las celdas prometedoras. Flood Fill es ideal en laberintos tipo micromouse donde se descubren muros constantemente y se replanifica en cada casilla. A* es superior en mapas extensos donde se planifica una ruta global entre dos puntos fijos.
¿Por qué las rutas generadas por A* rozan las esquinas de los obstáculos?
Porque el algoritmo asume un robot puntual sin dimensiones físicas. La trayectoria es matemáticamente correcta en la rejilla discreta pero físicamente inviable al provocar colisiones mecánicas del chasis. La solución consiste en aplicar inflación de obstáculos: dilatar las celdas ocupadas en una distancia igual al radio del robot más un margen de seguridad, asegurando que cualquier celda libre calculada sea transitable.
¿Qué convierte en admisible a una heurística de A* y por qué es crucial?
Una heurística es admisible si nunca sobrestima el coste real restante hasta la meta. Esta condición matemática garantiza que A* devolverá siempre el camino óptimo de menor coste. Si la heurística sobrestima la distancia en algún punto, el algoritmo puede descartar ramas válidas y seleccionar trayectos subóptimos. Romper la admisibilidad ocurre habitualmente al aplicar distancia euclidiana en cuadrículas de 4 direcciones (donde la métrica real es Manhattan) o al sobredimensionar la heurística para acelerar el cálculo.
¿Es realmente necesario implementar SLAM en un robot educativo?
Únicamente si la plataforma debe desplazarse de forma autónoma en recintos desconocidos de gran tamaño durante periodos prolongados. Si el mapa del entorno puede cargarse previamente en memoria, basta con aplicar algoritmos de localización pura. Si el espacio es reducido (una habitación o un laberinto) y la duración breve, la odometría con IMU resulta suficiente. SLAM justifica su complejidad matemática cuando ambas simplificaciones resultan inviables simultáneamente.
¿Por qué el mapa de celdas de ocupación se distorsiona y curva al avanzar?
Porque la deriva acumulada en la odometría se proyecta directamente sobre la rejilla. Cada barrido sensor se posiciona según la pose que el robot cree tener; si el rumbo angular está desviado unos grados, un pasillo recto se cartografiará como una curva. El mapeo no falla: transcribe fielmente una postura errónea. Esta inconsistencia se solventa mediante el cierre de lazo (loop closure), que detecta zonas previamente visitadas y reajusta la trayectoria histórica.
¿Por qué las celdas desconocidas no deben tratarse como espacio libre?
Porque una celda que ningún sensor ha explorado carece de información, no está vacía. Asumirla transitable induce al planificador a trazar rutas a través de zonas ciegas o detrás de esquinas, precisamente donde suelen ubicarse obstáculos ocultos. Mantener el estado 'desconocido' como una tercera categoría independiente de 'libre' y 'ocupado' permite decidir conscientemente si se autoriza la exploración o se prohíbe el tránsito.