¿Cuál es la mejor manera de navegar y evitar obstáculos para un robot de servicio?
Los robots son sistemas mecánicos y de software que interactúan con el mundo real. Para un robot de servicio, es extremadamente importante comprender su posición actual en el espacio, la posición del objetivo y la capacidad de construir una ruta hacia el objetivo evitando posibles obstáculos. Estamos desarrollando un
robot para recoger pelotas de golf en el campo de prácticas . Consideramos diferentes opciones para construir una ruta con el fin de encontrar la mejor para nosotros, tal vez esta información sea interesante para alguien.
La forma más fácil de hacer que el robot se dirija a su objetivo final en un espacio bidimensional. El rover mismo aquí es un pequeño punto frente al cual no hay obstáculos. Por lo tanto, el robot en esta situación se mueve en línea recta, y cuando alcanza la meta se detiene.
Este método es adecuado si solo hay un robot en el mundo y el objetivo que debe alcanzar. Direct le permitirá alcanzar la configuración final lo más rápido posible.
Pero este algoritmo no se puede aplicar si de repente surge un obstáculo frente al robot. Moviéndose en línea recta, el rover no podrá rodearlo ni pasar. A este respecto, simplemente se detiene frente a un obstáculo y no avanza.
¿Cómo sortear un obstáculo? La forma más fácil de resolver el problema es la opción de comportamiento llamada "Evitar obstáculos". En la práctica, está representado por varios algoritmos.
Caminar al algoritmo
Si no se logra el objetivo:
- Avanzar hacia la meta.
- De lo contrario: detente.
Este método es adecuado si solo hay un robot en el mundo y el objetivo que debe alcanzar. Direct le permitirá alcanzar la configuración final lo más rápido posible. Pero, ¿qué algoritmo se debe aplicar si surge un obstáculo frente al objetivo frente al robot?
Un obstáculo no permite que el robot llegue a su destino en línea recta, el rover en esta situación simplemente se detiene frente a él. En este caso, también puede usar el algoritmo "Walk To", pero debe complementarse.
Algoritmo de error
En la vida ordinaria, una persona, cuando va de un punto a otro a la meta y se encuentra con un obstáculo, simplemente lo pasa por alto. Este comportamiento se llama "evitar obstáculos". Será aplicado para lograr el objetivo por el robot. La forma más fácil de aplicar el algoritmo escarabajo.
Los expertos llaman al algoritmo Bug de esta manera porque el comportamiento del escarabajo se toma como base: si ve un obstáculo, lo pasa por alto.
Los pasos que da el robot mientras se mueve hacia el objetivo (incluso al caminar alrededor de un obstáculo) se denominan trayectoria.
El algoritmo de error sirvió de base para los conceptos que se utilizan en la construcción de rutas de un tipo más complejo. Estos incluyen:
Concepto de trayectoria. Esta es una secuencia simple de movimientos del robot, que realiza para lograr el objetivo final. El algoritmo del escarabajo también es un "Planificador de trayectoria". Habiendo recibido las coordenadas de los puntos en los que se ubican el robot y su objetivo, el algoritmo desarrolla una trayectoria de movimiento apropiada.
Concepto de política . Si se utiliza el algoritmo del escarabajo, ciertas instrucciones de movimiento se transmiten al robot, entonces esta forma de construir la ruta se denomina "Política de gestión".
Concepto heurístico. Este es el nombre de la regla utilizada para informar al robot sobre la siguiente etapa del algoritmo. En esta situación, la heurística es la línea a lo largo de la cual se mueve el objeto. Al crear una ruta, debe determinar correctamente la heurística. Si esto se hace incorrectamente, la ruta construida no funcionará.
Sin embargo, dicho algoritmo limita al desarrollador, porque con su ayuda será posible construir una ruta de tamaño limitado. Cuando se utiliza dicho algoritmo para construir una ruta, es necesario que todos los obstáculos tomen la forma de un polígono convexo.
El algoritmo Bug también tiene limitaciones:
- los obstáculos deben estar a cierta distancia el uno del otro, es imposible que tengan un terreno común;
- los límites de los obstáculos son curvas cerradas, mientras que deben ser tales que la línea recta a lo largo de la cual se mueve el robot se cruza con cada uno de ellos por un número limitado de veces;
- un robot es un punto desproporcionadamente pequeño, por lo que puede moverse entre obstáculos independientemente del paso entre ellos.
Algunas de estas limitaciones pueden superarse mediante el uso del algoritmo DH-Bug avanzado. Su característica es que, con su ayuda, el robot podrá hacer frente a obstáculos en movimiento. Además, dicho algoritmo consta de dos capas. El primero es asesor. Le permite evaluar previamente la ruta sin utilizar información adicional. La segunda capa es adaptativa. Gracias a él, el robot responde oportunamente a obstáculos que inicialmente no se establecieron en el programa.
Algoritmo CBUG
El algoritmo CBUG es una versión de la construcción de rutas de tal manera que tiene en cuenta todos los detalles. Durante su desarrollo, los especialistas tomaron en cuenta el tamaño del robot y también resolvieron problemas relacionados con la optimización de la ruta creada. Una característica distintiva de tal algoritmo mejorado es que para generar una ruta, es necesario que el punto de partida permanezca siempre en la memoria del objeto. Invariablemente para el algoritmo CBUG, solo que para su aplicación es necesario tener una cantidad fija de memoria.
Algoritmo de Dijkstra
El algoritmo utilizado en los gráficos fue creado por E. Dijkstroy en la segunda mitad del siglo pasado. Con su ayuda, será posible determinar la ruta más corta desde uno de los vértices del gráfico hasta otros. Tal algoritmo termina cuando el robot ha visitado todos los picos. Si aquellos a quienes no ha visitado aún viajan, se selecciona un pico con una marca mínima.
Las ventajas del algoritmo Deister incluyen:- prestando atención a la longitud del camino y su costo;
- los nodos se actualizan si se encuentra uno más óptimo.
La desventaja de este método de construir una ruta es que es adecuado solo para gráficos donde no hay bordes de peso negativo. Es inconveniente que esté mal orientado cuando busca en ancho.
Algoritmo de Bellman-Ford
Pero a menudo surgen situaciones en las que es necesario construir una ruta donde haya costillas con peso negativo. El algoritmo Bellman-Ford ayudará a resolver este problema. Si, como resultado, la suma de los pesos de los bordes de la ruta final toma un valor negativo, entonces se llama un ciclo negativo.
Algoritmo Johnson
Este algoritmo fue introducido por DB Johnson para identificar todas las rutas más cortas de un pico a otro. En este caso, el método se puede usar para bordes con pesos positivos y negativos. El único inconveniente del algoritmo es que no hay ciclos negativos.
Algoritmo A *
Para encontrar la forma más óptima de usar gráficos, debe aplicar el algoritmo A *. Le permite determinar la mejor ruta desde el robot hasta el objetivo mediante la primera coincidencia en el gráfico. La base de este algoritmo es la fórmula heurística, que es la siguiente:
f(n)=g(n)+h(n).
f(n) - , n.
g(n) - n .
h(n) - .Este algoritmo le permite encontrar el camino más corto hacia la meta hasta que h (n) tome el valor máximo permitido. Una característica del algoritmo A * es su flexibilidad. Muy a menudo, el estado es la celda o ubicación del robot. Pero también puede ser velocidad u orientación.
Al mismo tiempo, los estados cercanos varían según el caso específico.
La flexibilidad del algoritmo también se manifiesta en el hecho de que el objetivo que el robot necesita alcanzar puede consistir en varias posiciones a la vez. En tal situación, la aproximación heurística h (n) debe ser válida de inmediato para todos los fines disponibles.
El funcionamiento del algoritmo A * depende del exponente h (n). Cuanto mejor sea la calidad de aproximación heurística, mayor será la eficiencia. Además, la cantidad de memoria libre y el tiempo del procesador afecta el funcionamiento del algoritmo.
Algoritmo de trazado de onda
Además, a menudo se usa un algoritmo de onda para dibujar una ruta en un gráfico. Al construir una ruta de esta manera, se utiliza el método de búsqueda de amplitud.
El algoritmo en sí incluye los siguientes pasos:- inicialización
- construcción de olas;
- ruta de recuperación.
En la etapa inicial, se crea la imagen de muchas celdas, cada una de las cuales se vuelve pasable o intransitable para el robot.
El robot, moviéndose de una celda a otra, determina secuencialmente si es posible pasarlo y si no lo ha marcado antes.
Después de eso, el camino más corto desde la celda inicial hasta la final se crea por la fuerza bruta, cuyo logro es el propósito del rover.
Discretizar algoritmo espacial
- El espacio de configuración tiene un tamaño constante en todas las dimensiones.
- Discretice todas las mediciones para que tengan un número constante de células.
- Todas las celdas ubicadas en el espacio de configuración dentro del obstáculo deben marcarse como intransitables.
- Como resultado, todas las celdas pasables se convirtieron en nodos.
- Cada nodo se conecta a todos los vecinos en el gráfico.
Buscador de ruta aleatorizado
Los aspectos más difíciles al planificar una ruta son calcular el espacio de configuración y determinar la ruta más conveniente al pasar por este espacio. Gracias a las hojas de ruta, será posible resolver estos problemas. La esencia del método es dividir el espacio en cuadrados idénticos, conectando todos los vértices más cercanos. Iterar sobre todos los caminos. Ordene todas las rutas para encontrar la ruta con el menor valor.
Algoritmo de mapas de carreteras probabilísticos
- 1. Cree un gráfico vacío G.
- 2. Agregue al gráfico G los nodos del robot y su objetivo final.
- 3. Para el enésimo número de integraciones:
- Encuentre una muestra aleatoria uniforme del espacio de configuración y asígnele el nombre R.
- Si el robot está en conflicto con la configuración R, puede continuar.
- De lo contrario: agregue R a la columna G.
- 4. Identifique todos los nodos en el gráfico que se encuentran dentro de los puntos d y R.
- 5. Para todos los N nodos que se ajustan a este parámetro:
Algoritmo de árboles aleatorios de exploración rápida
A veces necesita construir una ruta sin aplicar consultas de planificación anteriores. En tales situaciones, debe utilizar el siguiente método:
- Crea un árbol T. vacío
- Agregar a T la configuración inicial del robot.
- Hasta que se alcanza la meta:
- Obtener para el nodo R.
- Defina en T el nodo más cercano a R. Dale el nombre K.
- Mueva el robot de K a R hasta que se cumpla la siguiente condición:
- En caso de colisión, proceda a la definición de una muestra aleatoria.
- De lo contrario: agregue un nuevo nodo a T en esta configuración.
- Si se alcanza la distancia máxima entre d y K, comience a trabajar en un muestreo aleatorio nuevamente.
- La solución se obtiene si el nodo de la cadena se encuentra dentro de la distancia d desde cualquier nodo T.
Conclusión
Para nosotros, es óptimo separar el tema de la construcción de rutas en global y local. Una ruta global es una lista de puntos de destino para evitar el campo o el objetivo de regresar a la base. Una ruta local comienza cuando los sensores ultrasónicos o un parachoques detectan un obstáculo.
Dado que en nuestros detalles todos los obstáculos son convexos, utilizamos el algoritmo BUG más simple e incluso más simple. Un cierto método de navegación "infantil". Cuando un ultrasonido detecta un obstáculo, el vehículo gira 90 grados en el sentido de las agujas del reloj, pasa 1 metro y gira 90 en sentido antihorario. Si el parachoques detecta un obstáculo, antes de girar el robot 0,5 metros hacia atrás.
Planes
Durante el inicio del proyecto en el verano de 2018. Una gran cantidad de eventos sucedieron. Estamos preparando una publicación sobre el desarrollo de nuestro proyecto. Gracias por su atencion!
Referencias