¿Cuál es una manera eficiente de visitar cada espacio accesible en una cuadrícula con obstáculos desconocidos?

Estoy tratando de crear un mapa de los obstáculos en un espacio de cuadrícula 2D bastante grueso, utilizando la exploración. Detecto obstáculos al intentar moverme de un espacio a un espacio adyacente, y si eso falla, entonces hay un obstáculo en el espacio de destino (no hay un concepto de sensor de detección de alcance en este problema).

cuadrícula de ejemplo http://www.eriding.net/resources/general/prim_frmwrks/images/asses/asses_y3_5d_3.gif (por ejemplo)

El proceso se completa cuando se han visitado todos los cuadrados accesibles. En otras palabras, algunos espacios pueden ser completamente inalcanzables incluso si no tienen obstáculos porque están rodeados. Esto es de esperarse.

En el caso más simple, podría usar un algoritmo DFS , pero me preocupa que esto tarde demasiado tiempo en completarse: el robot pasará más tiempo retrocediendo que explorando nuevos territorios. Espero que esto sea especialmente problemático cuando intente alcanzar los cuadrados inalcanzables, porque el robot agotará todas las opciones.

En el método más sofisticado, lo más apropiado parece ser la descomposición de células de Boustrophedon .

Sin embargo, parece que no puedo encontrar una buena descripción del algoritmo de descomposición de células de Boustrophedon (es decir, una descripción completa en términos simples). Existen recursos como este , o este más general sobre la descomposición de celdas verticales, pero no ofrecen mucha información sobre los algoritmos de alto nivel ni las estructuras de datos de bajo nivel involucradas.

¿Cómo puedo visitar (mapear) esta cuadrícula de manera eficiente? Si existe, me gustaría un algoritmo que funcione mejor que $O(n^2)$ con respecto al número total de cuadrados de la cuadrícula ( es decir, mejor que $O(n^4)$ para una cuadrícula $n*n$ ).

La descomposición de células de boustrofedon es simplemente subdividir un ambiente en áreas que pueden ser cubiertas eficientemente por un camino de boustrofedon. Una descomposición trapezoidal servirá, y puede lograrse usando un algoritmo de barrido de línea. Ver [Choset 2000], este sitio web , o (¡lo recomiendo!) El excelente libro "Geometría computacional" de Mark de Berg, et. al, para una descripción completa de las estructuras de datos y algoritmos requeridos.

Choset, Howie. "Cobertura de espacios conocidos: la descomposición celular de Boustrophedon" Autonomous Robots , 2000.

Por ejemplo, considere el conjunto de obstáculos como aristas y vértices. Digamos que el entorno también está limitado por un polígono especial. Tenemos algo como lo siguiente. Para descomponer este espacio, simplemente agregamos bordes verticales entre cada vértice y la línea o vértice más cercano.

Para lograr esto en el código, solo necesita una prueba de intersección de segmento de línea, una lista ordenada de bordes y una lista ordenada de vértices.

1. $v_i$
2. $l_i$$v_i$
3. En cada intersección, crea un nuevo vértice.

Cuando se hace esto, el conjunto de nuevos bordes y vértices encierra solo trapecios. Pero enfatizo, no puedes hacer esto en línea (sin conocimiento previo de los obstáculos). Si desea hacer una cobertura sólida sin conocimiento previo, puede buscar "algoritmos de error". En particular, aquí hay un algoritmo simple, suponiendo que el entorno esté limitado.

1. Desde la posición inicial, muévase hacia arriba y hacia la izquierda hasta llegar a la esquina superior izquierda del entorno. Si encuentra un obstáculo primero, debe viajar alrededor de él. Sabes que algo es un obstáculo si se puede circunnavegar (golpear y mover).

2. Desde la esquina superior izquierda, muévete a la derecha hasta que encuentres el límite. Luego muévete hacia abajo y hacia la izquierda (estamos haciendo un boustrofedón de todo el espacio).

3. Cuando estás en una línea izquierda-derecha y encuentras un obstáculo, tienes dos opciones. (i) Podemos circunnavegar hasta llegar a la línea izquierda-derecha que estamos tratando de cubrir, luego continuar. (ii), podemos dar la vuelta y cubrir una nueva línea izquierda-derecha hasta encontrar el camino más allá del obstáculo o terminar en esta situación nuevamente. Ilustraré

A la izquierda, nos movemos alrededor del obstáculo hasta que podamos volver a la "línea" que estábamos tratando de seguir. A la derecha, continuamos cubriendo el área (más pequeña) a un lado del obstáculo.

La ventaja del primer método es que siempre traza el obstáculo por completo antes de tomar una decisión sobre cómo sortearlo, por lo que puede tomar el camino más corto. La ventaja del segundo método es que no tiene que sortear el obstáculo, simplemente puede proceder a cubrir el área en la que se encuentra.

Tenga en cuenta que esto define su descomposición de boustrophedon de una manera en línea : Usted cubre el área entre los obstáculos o entre los obstáculos y el límite.

Sin embargo, hasta donde yo sé, el primer método es más fácil de analizar. Los algoritmos más complicados (como BFS, etc.) se eligen ya sea porque el entorno es ilimitado (no desea gastar para siempre buscando un límite) o hay un obstáculo realmente desagradable en la forma en que básicamente divide el entorno. ¿Por qué es esto malo? mira este ejemplo:

Mover de izquierda a derecha, a continuación, rodeando cada obstáculo produce manera demasiadas portadas de las pequeñas piezas entre cada obstáculo. De hecho, sin una planificación de ruta global, puede hacer que esto sea tan malo como la resolución de su cuadrícula colocando estas columnas de 1 px de ancho, tan altas como todo el entorno y separadas por 1 px. Entonces tendrías que moverte alrededor del obstáculo cada vez que lo golpees.

Es por eso que le pregunté si tenía alguna idea de dónde se encontraba en el entorno o si podría hacer una planificación global de la ruta. Pero la discusión en línea vs fuera de línea y los algoritmos óptimos para esto no es lo que realmente quería.

Actualización: tuve que eliminar las imágenes (no https), y publicaré esto, que a menudo se usa en aplicaciones prácticas del mundo real. http://www.cs.cmu.edu/~motionplanning/papers/sbp_papers/integrated1/yamauchi_frontiers.pdf

Al final, descubrí que la mejor manera de hacerlo era emplear un concepto muy simple: Flood Fill . Utilicé un enfoque iterativo basado en la pila en lugar de la opción recursiva, y lo modifiqué para el espacio físico mediante una búsqueda A * para encontrar una ruta desde la ubicación actual a la siguiente ubicación en la pila (usando solo aquellos cuadrados de cuadrícula que ya tienen visitado, ya que estoy garantizado para tener un camino entre ellos).

La eficiencia parece bastante razonable.