Resolvedor del cubo de Rubik

rubik_cubeSi ya supone un reto el resolver este conocido rompecabezas tridimensional, el montar un robot que sea capaz de resolverlo por sí solo es un reto todavía mayor. El objetivo de este proyecto es lograr un robot capaz de resolver un cubo de Rubik cuyo mapa inicial es desconocido. Además, debemos de ser capaces de minimizar el hardware empleado y de resolver el cubo en el menor tiempo posible. Normalmente una reducción del hardware implicará un mayor número de movimientos y, por ende, un aumento del tiempo de resolución.

Descomposición del problema

El problema puede descomponerse en 3 partes bien diferenciadas:

  • Reconocimiento del cubo para extraer el mapa de posicionamiento inicial. El estudio del estado inicial puede realizarse bien con la ayuda de una cámara y un software de reconocimiento de imágenes, o bien con un sensor de luminosidad o color que realicen un barrido de cada uno de los 9 cuadrados de las 6 caras.
  • Aplicación de un algoritmo de resolución que, partiendo del mapa anterior, nos presente la secuencia de movimientos cuya ejecución resuelva el modelo.
  • Ejecución física de los movimientos extraídos anteriormente. Para poder resolver el cubo, debemos de ser capaces de rotarlo 90º en dos ejes perpendiculares y, además, de poder girar 90º una cara respecto del resto del cubo.

Historia

El mérito del primer resolvedor del cubo se debe a JP Brown. Esta ha sido durante mucho tiempo una de las creaciones Mindstorms más espectaculares. Para el proyecto empleó 2 unidades RCX, una cámara Vision Command y muchas horas de programación e ingenio. Tal como explica en su página, Brown admite que el aspecto más complicado del proyecto fue la realización del software de reconocimiento de imágenes.

cube_solver_jpbrown

El siguiente modelo fue desarrollado por Daniele Benedettelli con la tecnología NXT y haciendo uso de las experiencias del anterior. Daniele Benedettelli, cuya tesis está basada en el uso del Mindstorms como plataforma de robótica móvil, consiguió reducir el hardware de los 2 NXTs que se comunican via bluetooth, 4 servos y 2 sensores de luz de las primeras versiones, a tan solo:

  • 1 NXT
  • 3 servos
  • 1 sensor de luz para detectar la posición inicial de la base giratoria, y
  • 2 sensores de contacto que detectan el límite de carrera del movimiento de los brazos.

cube_solver_benedettelli

El algoritmo para resolver el cubo que empleó JP Brown era subóptimo, el que pudo encontrar en internet en su momento, mientras que el diseño de Daniele hace uso de un algoritmo óptimo, cuyo tiempo de resolución es de 1 minuto como máximo. Para el reconocimiento del cubo emplea una webcam y software de desarrollo propio.

El siguiente modelo, desarrollado por Han Anderson, no es más veloz que el anterior, pero tiene el mérito de ser totálmente autónomo: la solución del algoritmo no se realiza con ayuda de un PC externo, sino que se calcula en el mismo NXT. Por otro lado el reconocimiento del cubo tampoco se realiza con una cámara, sino con un sensor de luz. Esto fuerza al uso de un algoritmo más simple, que resulta en un tiempo total entre escaneado, cálculo de solución y ejecución de unos 6 minutos. Este sistema emplea:

  • 1 NXT
  • 1 sensor ultrasónico para detectar la presencia del cubo e iniciar el procesado
  • 1 sensor de luz que realiza el escaneado
  • 1 sensor de presión para detectar el fin de carrera del motor que posiciona el sensor de luz y
  • 3 servos: 2 para mover el cubo y el tercero para posicionar el sensor de luminosidad.

Hans proporciona el código fuente e instrucciones de montaje del modelo, aunque la incapacidad del sensor de luz de diferenciar algunos de los colores del cubo obliga a modificar los colores mediante el uso de pegatinas. Con el paso del tiempo Hans creo una segunda versión que tenía en cuenta la posibilidad de trabajar con sensor de color.

La siguiente variante, de ARMflix, hace uso de una cámara, sólo que en este caso la cámara es la de un móvil. En el Nokia N95 se capturan las imágenes y se realiza el reconocimiento del cubo y posterior resolución mediante una aplicación Java. A la solución se llega en unos 2 segundos de procesamiento del móvil, que devuelve una secuencia de unos 30 movimientos. El N95 transmite esta secuencia al NXT mediante bluetooth y el NXT ejecuta la secuencia de movimientos en unos 3-4 minutos.

Por último, si ya hemos realizado el robot que resuelve el cubo y queremos batir un récord de velocidad, debemos tener en cuenta que nos interesa que el cubo haya “rodado” lo suficiente como para que ofrezca menos resistencia que los cubos acabados de salir de fábrica. Para realizar ese entrenamiento podemos seguir los consejos de JP Brown o realizar máquinas como la de Toshiya Hirohata:

Comments are closed.