Con el artículo de hoy iniciamos una serie de artículos en el que trataremos de resolver un problema típico de ingeniería computacional adaptándolo al NXT. Queremos hacer que nuestro robot recorra distintos puntos, en los que tendeá que realizar cierta operación. Nuestro objetivo es que hallar el camino ideal, o sea que encuentre el camino más corto que le permita visitar todos los puntos. Este problema que un principio puede parecer sencillo es ni más ni menos uno de los problemas más complejos de resolver y existen demostraciones que equiparan la complejidad de su solución a la de otros problemas aparentemente mucho más complejos que han retado a los matemáticos desde hace siglos… estamos hablando del problema del viajante de comercio (TSP).

El problema del viajante de comercio (TSP de Travelling Salesman Problem) es un problema de optimización combinatoria estudiado en la ciencia computacional teórica. A partir de una lista de las ciudades y todas las distancias entre ellas el objetivo es encontrar el recorrido más corto posible que permita visitar cada ciudad una sila vez. El problema fue formulado por primera vez como un problema matemático en 1930 y se trata de
uno de los problemas más intensamente estudiados en optimización.

El TSP se utiliza como punto de referencia para muchos métodos de optimización. A pesar de que el problema es computacionalmente complejo, se conocen un gran número de métodos exactos y heurísticos, por lo que se pueden resolver algunos casos de hasta decenas de miles de ciudades.

Aplicaciones del TSP:

El TSP tiene varias aplicaciones, incluso en su más pura formulación, como la planificación, la logística y la fabricación de microchips. Ligeramente modificado aparece como un sub-problema en muchas áreas, como en la secuenciación del ADN. En estas aplicaciones, la ciudad representa el concepto, por ejemplo, los clientes, puntos de soldadura, o fragmentos de ADN, y el concepto distancia representa los tiempos de viaje o el costo, o una medida de similitud entre partes de ADN.

En muchas aplicaciones, las restricciones adicionales, como los recursos limitados o los limites de tiempo hacen que el problema sea considerablemente más difícil. También los cambios de las distancias mientras se va moviendo el viajante complicarían bastante el problema.

En nuestro caso particular pretendemos que un robot (NXT) sea capaz de por ejemplo transportar ladrillos a diferentes puntos, y que lo haga lo más rápido posible. No será un caso muy complejo comparado con otros debido a que no tendremos un número muy alto de puntos que visitar (unos diez a lo sumo). Nuestro objetivo es puramente didáctico.

Complejidad del problema:

En el ámbito de la teoría de complejidad computacional, el TSP pertenece a la clase de problemas NP-completos. Por lo tanto, se supone que no hay ningún algoritmo eficiente para la solución de TSP. En otras palabras, el número de posibles soluciones es tan elevado que si pretendemos que el algoritmo encargado de la búsqueda de la solución óptima deba verificar una a una no tendremos tiempo de cálculo para hallarlo: es probable que en el peor de los casos el tiempo de resolución de cualquier algoritmo para TSP aumente exponencialmente con el número de ciudades, por lo que incluso en algunos casos de tan sólo cientos de ciudades se tardarán bastantes años de CPU para resolverlos de manera exacta.

Por tanto, aunque en nuestro caso particular vayamos a usar pocos puntos no es posible que sea el NXT quien encargue de resolver el problema, sino será nuestro ordenador el que compute la solución, y se comunique con el NXT posteriormente a través de bluetooth para que a través de un fichero de datos ejecute el camino seleccionado. La capacidad de procesamiento del NXT es muy baja como para resolver problemas de este estilo.

Algoritmos:

Hay diversos algoritmos para resolver este problema, aunque no todos son exactos (no encuentran la solución óptima), sino que algunos hallan la solución por aproximación.

Algoritmos exactos:

La solución más directa sería probar todas las combinaciones posibles y ver cual es la más barata (usando búsqueda por fuerza bruta). El tiempo de ejecución para este método ronda un factor polinomial de O(n!), el factorial del número de ciudades, por lo que esta solución es poco práctica incluso para solo veinte ciudades.

Los métodos de ramificación y poda tradicionales son capaces de procesar problemas del viajante de comercio de entre 40 y 60 ciudades. Esté es el método que usaríamos en un principio ya que vamos a contar con pocas ciudades (puntos en este caso) y queremos calcular la solución óptima.

Algoritmos heurísticos y de aproximación:

Se han ideado varios algoritmos heurísticos y de aproximación que son capaces de llegar a una buena solución rápidamente. Los métodos modernos pueden encontrar soluciones para problemas extremadamente grandes (millones de ciudades) en un tiempo razonable, con una alta posibilidad de que solo se diferencien entre un 2 y 3% de la solución óptima.

El problema del viajante de comercio es ya un problema estándar para muchos algoritmos heurísticos del campo de la optimización combinatoria como los algoritmos genéticos, el recocido simulado (SA), la búsqueda tabú, el algoritmo hormiga el método Cross-entropy (entropía cruzada).

Planteamiento del problema:

En nuestro caso vamos a tener un NXT que quiere visitar diversos puntos, para lo que sea. El caso es que todos estos puntos deben estar conectados, ya sea por caminos que dibujemos o simplemente por distancias reales. Si hubiera algún punto que no estuviera conectado el problema no tendría solución ya que nunca se podría acceder a dicho punto. La forma más sencilla de representar el mapa con las “ciudades” es mediante un grafo. Los grafos tienen el siguiente aspecto:

Un grafo es un conjunto de nodos (puntos) que en este caso representarían los sitios que queremos visitar, y aristas que representan los posibles caminos. Sería un grafo completo que significa que todos los nodos tienen aristas que les conectan directamente a los demás nodos. Además es un grafo ponderado, que significa que cada arista tiene un peso que representa la distancia entre los puntos a visitar.

Los grafos son una estructura de datos informática muy usada. Hay que implementarla con todas las funciones necesarias para poder meterle los datos (los nodos y las aristas). Una vez tengamos un grafo con toda la información podemos operar sobre el para hallar la solución a nuestro problema.

Este problema se divide por tanto en tres partes:

– Implementar la estructura de datos grafo.

– Implementar un algoritmo que resuelva el TSP

– Implementar un programa que teniendo la solución al TSP en una estructura de datos haga que el robot realice el recorrido pertinente.

Este artículo forma parte de una serie de artículos en la que trataremos de resolver un TSP sencillo para un NXT.