4.7: Ejercicios

Última actualización
Guardar como PDF

Page ID: 84945

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Resumen y Perspectivas

La planificación de rutas es un problema de investigación permanente. Encontrar caminos libres de colisión para mecanismos con altos grados de libertad, como múltiples brazos que operan en un espacio común, sistemas multi-robot o sistemas que involucran dinámicas (y por lo tanto, agregar las derivadas de las variables de estado al problema de planeación) podría tomar inaceptablemente mucho tiempo para resolverse.

Aunque los planificadores de rutas basados en muestreo pueden acelerar drásticamente el tiempo para encontrar alguna solución, no son óptimos y luchan con situaciones específicas como pasajes estrechos. No existe un algoritmo de “bala de plata” para resolver todos los problemas de planificación de rutas y la heurística que conducen a una aceleración masiva en un escenario podría ser perjudicial en otros. Además, los parámetros algorítmicos son en su mayoría ad-hoc y sintonizarlos correctamente a un entorno específico podría aumentar drásticamente el rendimiento.

Clases para llevar a casa

El primer paso en la planificación de rutas es elegir una representación de mapa que sea apropiada para la aplicación.
Esto permite la aplicación de algoritmos genéricos de búsqueda de ruta más corta, los cuales tienen aplicaciones en una gran variedad de dominios, no limitados a la robótica.
Un algoritmo de planificación basado en muestreos encuentra rutas mediante el muestreo de puntos aleatorios en el entorno. La heurística se utiliza para maximizar la exploración del espacio y sesgar la dirección de búsqueda. Esto hace que estos algoritmos sean rápidos, pero ni óptimos ni completos.
Como las rutas resultantes son aleatorias, múltiples ensayos pueden conducir a resultados totalmente diferentes.
No existe un algoritmo de talla única para un algoritmo de planificación de rutas y se debe tener cuidado para seleccionar el paradigma correcto (consulta única vs. consulta múltiple), heurística y parámetros.

Ejercicios

¿Cómo cambia la complejidad computacional del algoritmo de Dijkstra al pasar de espacios de búsqueda 2D a 3D?
A* utiliza una “heurística” para sesgar la búsqueda en la dirección esperada de la meta. ¿Por qué solo puede usar una heurística, no la longitud real?
Suponiendo que los puntos se muestrean uniformemente al azar en un algoritmo de planeación aleatoria. Calcular el comportamiento limitante de la siguiente relación (número de puntos en árbol)/(número de puntos muestreados) a medida que el número de puntos muestreados va al infinito. Asumir el área _{total A total} y el área de espacio libre A _libre dentro son conocidos.
Suponiendo que se usa un árbol k como una estructura de datos del vecino más cercano, y los puntos se muestrean uniformemente al azar, calcule el tiempo de ejecución de insertar un punto en un árbol de tamaño N. Use la notación “Big-OH”, por ejemplo O (N).
¿Qué otras preocupaciones prácticas de tiempo de ejecución se deben considerar además de la complejidad computacional solo al hacer planificación de movimiento basada en muestreo? ¿Puedes sugerir formas de lidiar con estas otras preocupaciones?