Probabilistic Roadmap Planner

Hace aproximadamente un año y medio, hice un verano, el único en mi vida. En él tomé un curso que impartió el profesor Seth Hutchinson: Robot Motion Planning.

Dicho curso se imparte generalmente a lo largo de un semestre, pero por ser verano, a mi me tocó hacerlo en un mes :| Fue un mes realmente intenso de noches sin dormir y mucha cafeína,… aún recuerdo el sabor de ése verano.

Para evaluarnos, el profesor dejaba cada semana un proyecto. Uno de ellos y que me pareció el más interesante, fue el Probabilistic Roadmap Planner.

Dicho algoritmo sirve para encontrar un camino que puede seguir un robot de una configuración inicial (home) a una final (goal) evitando los obstáculos que existen en su espacio.

Configuración inicial, final, una configuración que no colisiona con los obstáculos
y obstáculos.

Para lograr esto, el algoritmo calcula un número dado de posibles configuraciones del robot de manera aleatoria, tales que no colisionen con los obstáculos. Desde la posición inicial intenta encontrar el camino más corto pasando por las configuraciones que están libres de colisiones hasta llegar a la posición final, evitando colisionar con los obstáculos en su camino de una configuración a otra.

Con 200 configuraciones aleatorias

Por desgracia no alcancé a terminar dicho proyecto, le faltaron unos cuantos detalles, afortunadamente el profesor comprendió que tomar su curso en un mes es para suicidas (just the way i like it).

con 800 configuraciones aleatorias.

El proyecto lo desarrollé usando Visual C# 2005 Express. El código me gusto mucho y puede ser útil para estudiar cosas como la detecciones de colisiones entre polígonos, el cálculo de la cinemática directa para un robot articulado, la animación con OpenGL (Tao Framework), y en si, el algoritmo de un RPM. Pensé en terminarlo algún día y publicarlo orgulloso en mi blog, pero cada vez veo más lejano ese día así que aquí lo tienen, incompleto.

Me quedó pendiente hacer la cinemática inversa o algún otro método para realizar la animación adecuada del robot de una configuración a otra, e implementar algún algoritmo que calcule el camino más corto (Dijktra o alguno similar).

Las características de mi aplicación son:

• Zoom in o out con las teclas: i y o
• Panning: con las flechas del teclado
• Mostrar u ocultar las posibles configuraciones del robot con la tecla: c
• Se pueden agregar cualquier número de obstáculos, se puede calcular cualquier número de configuraciones probabilísticas del robot.
• El robot es un brazo de 4 articulaciones.

Por cierto recomiendo mucho el libro del profesor Hutchinson:

CHOSET, HUTCHINSON. Principles of Robot Motion, Theory, Algorithms and Implementation. The MIT Press.

Aquí el código fuente.