4.6: Otras aplicaciones de planificación de rutas

Última actualización
Guardar como PDF

Page ID: 84936

\( \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}}\)

Una vez que el entorno ha sido discretizado en una gráfica, podemos emplear otros algoritmos de la teoría de grafos para planificar trayectorias deseables de robots. Por ejemplo, la cobertura del piso se puede lograr realizando una búsqueda de profundidad primero (DFS) o una búsqueda de amplitud primero (BFS) en una gráfica donde cada vértice tiene el tamaño de la herramienta de cobertura del robot. “Cobertura” no sólo es interesante para limpiar un piso: los mismos algoritmos pueden ser utilizados para realizar una búsqueda exhaustiva de un espacio de configuración, como en el ejemplo mostrado en la Figura 3.10, donde trazamos el error de un brazo manipulador al alcanzar una posición deseada sobre su espacio de configuración. Encontrar un mínimo en esta parcela mediante una búsqueda exhaustiva resuelve el problema de la cinemática inversa. Del mismo modo, se puede utilizar el mismo algoritmo para seguir sistemáticamente todos los enlaces en un sitio web hasta una profundidad deseada (o realmente recuperar toda la web mundial).

Hacer un DFS o un BFS podría generar rutas de cobertura eficientes, pero están lejos de ser óptimas ya que muchos vértices pueden visitarse dos veces. Un camino que conecta todos los vértices en una gráfica pero que pasa cada vértice solo una vez se conoce como Sendero Hamiltoniano. Un camino hamiltoniano que vuelve a su vértice inicial es conocido como Ciclo Hamiltoniano. Este problema también se conoce como el Problema del Vendedor Viajero (TSP), en el que se necesita calcular una ruta que visita cada ciudad en su recorrido solo una vez y se sabe que es NP Complete.