Tutorial · Intermedio · 30 min
Planificación de cobertura: barrer un suelo completo
Llegar a un punto y cubrirlo todo son problemas distintos. Barridos aleatorios, en espiral y bustrófedon medidos contra uno perfecto.
Un problema distinto al de llegar
A* encuentra una única ruta hacia un único objetivo. Un planificador de cobertura tiene que tocar todas las casillas alcanzables, lo que cambia por completo el objetivo: no hay una meta a la que acercarse, no hay heurística que guíe y el éxito no es binario.
La medida que lo sustituye es la distancia recorrida por metro cuadrado barrido. Con un área de suelo A y una herramienta de anchura w, un robot perfecto barre cada casilla una vez y nunca repite:
d_optima = A / wUna habitación de 20 m² con un cepillo de 250 mm necesita 80 m. Todas las cifras siguientes son múltiplos de esa, porque un múltiplo es la única comparación que sobrevive a un cambio de habitación.
La ley que gobierna el barrido sin mapa
Un robot que no tiene ni idea de dónde ha estado cubre suelo nuevo en proporción al suelo que sigue sin cubrir. Es una ecuación diferencial con una única respuesta:
cubierto(d) ≈ 1 − e^(−d / d_optima)Extrae tres puntos de ella y aparece la forma de todo el problema:
| Cobertura | Distancia |
|---|---|
| 63% | 1,0 × lo óptimo |
| 90% | 2,3 × lo óptimo |
| 99% | 4,6 × lo óptimo |
El último 9% cuesta más que el primer 90%. Es el problema del coleccionista de cupones con un cepillo incorporado, y es el único dato que explica todos los robots aspiradores que has visto funcionar.
Qué ocurre en realidad
La teoría supone que cada metro cae sobre suelo elegido de forma independiente. Un robot real conduce en línea recta, así que los metros consecutivos están correlacionados: vuelve a barrer una y otra vez el trozo donde ya está. Medido en cinco habitaciones en el simulador de cobertura:
| Estrategia | 50% | 90% | 99% | Termina en |
|---|---|---|---|---|
| Barrido planificado | 0,75× | 1,35× | nunca | 90,4% |
| Rebote aleatorio | 0,91× | 2,90× | 6,76× | 99,6% |
| Espiral + reubicacion | 0,87× | 5,54× | 10,96× | 99,5% |
Tres cosas de esa tabla valen mas que el resto de esta pagina.
Durante la primera mitad del suelo, nada importa. Las tres estrategias estan dentro de un 20% entre si al 50%. Un robot sin sensores y sin memoria es genuinamente tan bueno como un planificador durante la primera mitad del trabajo, que es exactamente por lo que el enfoque barato es comercialmente viable y por lo que la observacion casual nunca revela la diferencia.
El aleatorio rinde peor que su propia teoria. 6,76× frente a los 4,61× previstos al 99%, porque un rebote en linea recta no deja de revisitar el suelo que acaba de hacer. Trata 1 − e^(−d) como la cota optimista, no como la estimacion.
El planificador nunca termina. Se detiene en el 90,4% y ahi se queda, y esto no es un fallo.
Por que el planificador deja una decima parte del suelo
Un planificador de cobertura tiene que mantener el cuerpo del robot lejos de cada pared y cada pata de mesa, asi que infla cada obstaculo con el radio del robot mas un margen y planifica dentro de lo que queda. Todo lo que caiga fuera es suelo al que el robot nunca podra llegar.
En la prueba medida, 130 de las 133 casillas que el planificador no alcanzo estaban a menos de dos celdas de una pared o un mueble. Solo tres eran suelo abierto. Los fallos no estan dispersos: forman un anillo alrededor de cada obstaculo de la habitacion.
Lo que explica dos rasgos de toda maquina comercial:
- El cepillo lateral que sobresale del chasis. El cepillo es mas ancho que lo que colisiona, asi que llega al suelo que las ruedas nunca podran pisar.
- La pasada de seguimiento de pared. Es un comportamiento aparte, ejecutado aparte, porque el barrido sistematico estructuralmente no puede hacerlo.
El rebote aleatorio alcanza esos bordes con el tiempo, por suerte, que es lo unico que hace mejor.
Elegir las filas
Para un barrido sistematico el unico parametro real es la separacion entre filas.
Separa las filas exactamente una anchura de cepillo y cualquier error de rumbo, por minimo que sea, deja una franja sin limpiar entre ellas, y nada posterior la encontrara, porque el plan cree que ese suelo ya esta hecho. Solapa un 10–20% y las franjas se cierran, a un coste de exactamente ese porcentaje en distancia.
Ese solape, mas la distancia de transito alrededor de los muebles, es de donde sale el 1,35× del planificador. No es desperdicio: es el precio de un plan que sobrevive al contacto con un robot real.
Dos decisiones mas que importan mas de lo que parecen:
- Recorre las filas a lo largo del eje mayor de la habitacion. Cada giro cuesta tiempo y no cubre suelo nuevo, asi que reducir a la mitad el numero de filas reduce a la mitad el coste de los giros.
- Rutea entre tramos, no conduzcas entre ellos. Cuando un mueble parte una fila en dos tramos, el robot tiene que ir alrededor. Planificar ese transito como el camino mas corto por espacio libre es la diferencia entre un plan y un deseo.
Los sensores que exige cada estrategia
Esta es la razon real de que existan las tres.
El rebote aleatorio necesita un bit. He chocado con algo. Dos interruptores de choque y un generador de numeros aleatorios son todo el robot. Sin codificadores, sin mapa, sin localizacion y sin nada que derive.
La espiral necesita saber cuanto ha avanzado desde el centro de la espiral actual, lo que es una odometria tosca: suficiente para crecer un radio, no para cerrar un bucle.
Un barrido planificado necesita saber donde esta. Filas rectas, angulos de giro conocidos y un paso lateral de una anchura de cepillo son afirmaciones de odometria, y la odometria deriva. Diez filas despues, las filas ya no son paralelas. Por eso las maquinas comerciales que planifican tambien llevan un giroscopio, una camara de techo o una baliza: el planificador es barato y la localizacion que asume no lo es.
Asi que la estrategia la elige el presupuesto de sensores, no la elegancia del algoritmo. Construye primero el aleatorio: funciona, son veinte lineas y te da una linea base que el planificador tiene que batir.
Lo que cuesta en minutos
Toma esa habitacion de 20 m², un cepillo de 250 mm y un robot que circula a 0,25 m/s:
| Estrategia | Distancia | Tiempo |
|---|---|---|
| Barrido perfecto | 80 m | 5 min |
| Planificado | 108 m | 7 min |
| Aleatorio, hasta el 90% | 232 m | 15 min |
| Aleatorio, hasta el 99% | 541 m | 36 min |
| Espiral, hasta el 99% | 877 m | 58 min |
Una bateria es un presupuesto de distancia. Una autonomia de una hora a 0,25 m/s son 900 m, que cubren comodamente una habitacion al azar y no cubren tres, y eso, mas que cualquier idea algoritmica, es lo que empujo el mercado hacia los robots con mapeo.
Cuando algo sale mal
| Sintoma | Normalmente |
|---|---|
| El robot traza el mismo bucle para siempre | El angulo de rebote es determinista: un reflejo fijo en un suelo rectangular es un camino cerrado |
| Las filas pierden el paralelismo | La odometria, no el planificador. Anade una referencia de rumbo |
| Franjas de suelo sin cubrir entre filas | Separacion entre filas puesta exactamente a la anchura del cepillo, sin solape |
| No llega a los bordes de ninguna habitacion | Funciona como esta disenado: anade una pasada de seguimiento de pared o un cepillo mas ancho |
| Cubre el 90% rapido y luego parece detenerse | Tambien es el diseno previsto. Mira la curva de cobertura, no al robot |
| Nunca termina detras del sofa | El transito entre tramos de fila nunca se planifico |
| La bateria muere a mitad de habitacion | Presupuesto de distancia excedido; mide la cobertura por metro, no por minuto |
Haz correr las tres contra la misma habitacion en el simulador de cobertura: arrastra los muebles mientras funciona y las cifras se mueven con ellos. Luego construye el robot de cobertura de habitaciones, que empieza por la estrategia que no necesita nada y solo anade sensores donde la medicion demuestra que compensa.
Explora el grafo
Forma parte de estos montajes
Proyectos y rutas de aprendizaje que incluyen este tutorial.
Lecturas adicionales