algorithm - robots - Algoritmo de exploración del robot
campos potenciales matlab (8)
Estoy tratando de diseñar un algoritmo para un robot que intenta encontrar la bandera (ubicada en una ubicación desconocida), que se encuentra en un mundo que contiene obstáculos. La misión de Robot es capturar la bandera y llevarla a su base de operaciones (que representa su posición inicial). El robot, en cada paso, solo ve un vecindario limitado ( no sabe cómo se ve el mundo por adelantado ), pero tiene una memoria ilimitada para almacenar las celdas ya visitadas.
Estoy buscando sugerencias sobre cómo hacer esto de una manera eficiente. Especialmente la primera parte; es decir, llegar a la bandera.
Bueno, hay dos partes para esto. 1) Buscando la bandera 2) Regresando a casa
Para la parte de búsqueda, rodearía el punto de inicio moviéndome hacia afuera cada vez que hice un ciclo completo. De esta manera, puede buscar en cada cuadrado e identificar si es un punto despejado, un obstáculo, un límite del mapa o la bandera. De esta manera, puede crear un mapa de su entorno.
Una vez que se encuentra la bandera, puede retroceder de la misma manera o buscar una ruta más directa. Si es una ruta más directa, entonces tendría que usar el mapa que ha creado para encontrar una ruta directa.
Como muchos han mencionado, A * es bueno para la planificación global si sabes dónde estás y dónde está tu objetivo. Pero si no tiene este conocimiento global, hay una clase de algoritmos llamados algoritmos de "error" que debe analizar.
En cuanto a la exploración, si desea encontrar la bandera más rápido, dependiendo de la cantidad de vecindarios locales que pueda ver su robot, debe intentar que no se superponga este vecindario. Por ejemplo, si su robot puede ver una celda a su alrededor en todas las direcciones, debe explorar cada tercera columna. (columnas 1, 4, 7, etc.). Pero si el robot solo puede ver la celda que está ocupando actualmente, entonces lo mejor que puede hacer es no volver sobre lo que ya visitó.
Con una simple búsqueda DFS al menos encontrarás la bandera :)
Creo que el enfoque sería construir el gráfico a medida que el robot viaja. Habrá una función que devolverá al robot el estado particular de una cuadrícula. Esto es necesario ya que el robot no sabrá de antemano el estado de la red.
Puede aplicar heurísticas en la búsqueda para aumentar la probabilidad de alcanzar la bandera.
Lo que quieres es encontrar todo el árbol de expansión mínima en la vista del robot y luego dejar que el juego de robots que él quiere viajar.
Parte de ello será pathfinding, por ejemplo, con el algoritmo A * .
Parte de ello será la exploración. Cualquier celda con un vecino desconocido vale la pena explorar. Las mejores celdas para explorar son las más cercanas al robot y con el vecindario inexplorado más grande.
Si el robot ve a través de las paredes, algunos candidatos de exploración podrían ser inaccesibles y la exploración podría ser necesaria incluso si la bandera ya está visible.
Puede valer la pena reevaluar el objetivo actual cada vez que se revela una nueva celda. Mientras esto solo se haga cuando se revelen nuevas celdas, el progreso siempre se hará.
Si se encontró con un obstáculo, puede ir para determinar sus dimensiones precisas y, después de medirlo, volver al curso anterior. Sin obstáculos en el alcance de la vista, puede intentar dirigirse en dirección al área más cercana no comprobada.
Tal vez no parezca la forma más rápida, pero creo que es un buen punto para comenzar.
Una simple búsqueda en primer lugar / búsqueda en profundidad funcionará, aunque lentamente. Asegúrese de evitar que el bot verifique las rutas que tienen el mismo cuadrado varias veces, ya que esto hará que estos algoritmos se ejecuten por mucho más tiempo en los casos estándar, e indefinidamente en el caso de que no se pueda alcanzar la bandera.
A * es el enfoque más elegante, especialmente si conoce la ubicación de la bandera con respecto a usted. Wikipedia , como de costumbre, hace un trabajo decente con explicarlo. La heurística clásica que se debe utilizar es la distancia de personal (número de movimientos que no supone obstáculos) hasta el destino.
Estos algoritmos son útiles para el viaje de regreso, no tanto para la parte de "encontrar la bandera".
Edición: estos enfoques implican la creación de objetos que representan cuadrados en su mapa y la creación de "caminos" o series de cuadrados para golpear (o pasos a seguir). Una vez que construyes un marco para representar tu cuadrado, el problema de qué tipo de búsqueda utilizar se convierte en una tarea mucho menos desalentadora.
Esta clase deberá poder obtener una lista de cuadrados adyacentes y saber si es transitable.
Teniendo en cuenta que no tiene toda la información, intente simplemente tratar los mosaicos inexplorados como transitables y vuelva a calcular si no los encuentra.
Edición: En cuanto a buscar un área desconocida para un objeto desconocido ...
Puedes usar algo como here hasta que encuentres los límites de tu espacio, registrando toda la información a medida que avanzas. Luego, eche un vistazo a todos los cuadrados que no se ven con su algoritmo favorito de búsqueda / desplazamiento. Si, en algún punto del camino, ve la bandera, detenga lo que está haciendo y use su algoritmo favorito de búsqueda de caminos para ir a casa.