Máquina de cubos de Rubik basada en FAC
No hace mucho tiempo, junto con Wilbert Swinkels, terminamos de trabajar en una máquina que recoge el cubo de Rubik. Escribieron sobre nosotros en el blog oficial de Raspberry Pi y recibimos muchas críticas muy favorables. Sin embargo, en el segmento ruso de la red, el proyecto de alguna manera pasó desapercibido. Así que decidí corregir esta omisión publicando aquí una versión traducida y aumentada de la publicación original .Bajo el corte, hablaremos (principalmente) sobre la parte del software de esta máquina, la parte mecánica se puede leer en la página oficial del proyecto (sí, sabemos que es una pequeña "vieja escuela")TL; DR
Para los impacientes, algunos enlaces:Introducción
Todo comenzó con el hecho de que en mayo de este año, conocí accidentalmente a Wilbert Swinkels. Simplemente me sorprendí cuando vi sus creaciones : cada uno de estos mecanismos, de pequeño a grande, se puede llamar con seguridad una obra de arte. Y cuanto más miras su dispositivo, más te sorprende su belleza.Por supuesto, cuando Wilbert me invitó a ayudarlo con la máquina de ensamblar cubos de Rubik, no dudé ni un segundo, especialmente porque para entonces ya había descubierto una pasión por los cubos de colores. En ese momento, ya había estado trabajando en la máquina durante más de 4 (!) Años, pero la parte del software aún no se había escrito.No tenía experiencia con la programación para Raspberry Pi y Arduino, pero en general la tarea me pareció bastante simple. Por supuesto, me equivoqué :)Hardware
La máquina en sí está construida con un sistema modular FAC . Esto es algo así como un diseñador soviético, pero creado para crear prototipos de mecanismos serios y complejos. En la segunda mitad del siglo pasado, se utilizó muy activamente en los laboratorios de Philips y otras empresas y universidades.Cuando conocí a Wilbert, ya había intentado dos veces "revivir" el auto. En ambas ocasiones, los estudiantes de la Universidad de Amsterdam tomaron el caso y, desafortunadamente, en ambas ocasiones perdieron interés en el proyecto después de varios intentos fallidos. Uno de ellos incluso defendió un diploma de licenciatura en este tema, a pesar de que, como resultado, la máquina no pudo recoger el cubo (levante la mano a los que se reconocen aquí).Microcontrolador
En primer lugar, decidimos usar Raspberry Pi en lugar de Arduino. Esto se debe principalmente al hecho de que los algoritmos "inteligentes" para resolver el Cubo de Rubik requieren una cantidad significativa de memoria y potencia de procesador. En intentos anteriores, se usó un algoritmo primitivo de tres capas , pero esta vez decidimos usar el algoritmo de Kotsemba . Además, realmente no quería escribir todo en C (aunque en parte tenía que hacerlo).
En la versión estándar de Raspberry Pi, no teníamos suficientes pines para conectar todos los motores disponibles, por lo que pedimos el Kit de desarrollo . Por cierto, recomiendo encarecidamente: no solo más pines, sino que, en mi opinión, son más lógicos aparte. Además, esta placa tiene dos conectores para la cámara en lugar de uno.La primera versión del escáner.
Para leer la configuración inicial del cubo, se necesitaba un dispositivo de escaneo. La idea es muy simple: a su vez, iluminamos la superficie del cubo con tres LED: rojo, verde y azul. Cada vez que medimos la luz reflejada usando una resistencia fotosensible. Teóricamente, deberíamos obtener valores RGB que puedan usarse para reconocer el color del cuadrado. De los programadores anteriores, todavía tenemos código de prueba de concepto para Arduino, que, al parecer, incluso funcionó bajo ciertas condiciones.El primer problema que encontramos fue un desajuste de voltaje. Como saben, la unidad lógica en los pines Arduino es de 5V, mientras que la Raspberry Pi es de 3.3V. Afortunadamente, los controladores de controlador de motor paso a paso que utilizamos continuaron funcionando a pesar de cambiar la amplitud de los pulsos.Resultó ser mucho más crítico que Raspberry Pi no tenga entradas analógicas. Debido a esto, la Raspberry no puede simplemente tomar y leer el voltaje en el fotorresistor. Esto es probablemente obvio para aquellos que al menos una vez se encontraron con esto, pero al principio ni siquiera lo pensé. Buscando en la red una solución, nos topamos con este artículo. En pocas palabras, agregamos un condensador al circuito y medimos el tiempo durante el cual se cargará desde cero a una unidad lógica (podemos detectar esto usando un pin digital). El tiempo de carga será proporcional a la resistencia de la fotorresistencia, por lo que podemos juzgar la cantidad de luz.
Este enfoque no solo es terriblemente poco confiable (tomarse un tiempo en un script Python Python en Linux con un montón de procesos en segundo plano es algo desagradecido), sino que también es imposible prolongarlo. Para suavizar las desviaciones aleatorias en las lecturas, tuvimos que leer varias veces, eliminar los valores atípicos y promediar los valores restantes. Sin embargo, todavía logramos que este escáner funcione:La segunda versión (final) del escáner
El escáner de condensadores funcionó bastante bien, pero fue muy lento. Tomó alrededor de dos minutos escanear todo el Cubo de Rubik, y para cuando se completó el escaneo, el espectador había perdido todo interés. Por lo tanto, decidimos regresar al Arduino y compramos un Arduino Mini pequeño específicamente para controlar el escáner.
Hacer que Arduino se hiciera amigo de Raspberry Pi resultó ser increíblemente simple: dos cables, un convertidor de voltaje entre ellos y listo, tenemos una interfaz en serie. Y si atornillas un protocolo Min simple , entonces programar este negocio es un placer.Transferí toda la lógica de control del escáner al Arduino. La velocidad de escaneo ha aumentado significativamente. Gracias a las entradas analógicas, podemos leer el voltaje directamente de los fotoresistores, y estos valores son muy precisos. Además, dado que el Arduino está montado directamente en el escáner, ¡necesitamos muchos menos cables del escáner a la Raspberry Pi!Construir algoritmo
Montar el cubo de Rubik desde un punto de vista matemático es una tarea bastante laboriosa . Por supuesto, estamos hablando de encontrar la solución óptima, y no "alguna". Me sorprendí cuando descubrí que el número de Dios (el límite inferior exacto para el número de movimientos necesarios para resolver un cubo arbitrario) se encontró solo en 2010 .En este proyecto, queríamos reducir el tiempo total requerido para calcular la solución y el ensamblaje, por lo tanto, ni un algoritmo simple de tres capas se nos acercó (funciona rápidamente, pero da soluciones de cien movimientos de largo), ni un algoritmo óptimo (las soluciones son cortas, pero el proceso de renderizado en Raspberry Pi tomaría una eternidad). Como resultado, nos decidimos por el magnífico algoritmo de "dos fases"El matemático alemán Herbert Kociemba. Es capaz de emitir decisiones subóptimas (un promedio de 20 movimientos), mientras se mantiene dentro de un tiempo razonable.En el sitio del autor puede encontrar la implementación del algoritmo en Java. Lo primero que hice fue traducir este código a Python. No fue del todo difícil, ya que la mayor parte del programa son operaciones matemáticas y enumeración de opciones. Sin embargo, no tomé en cuenta que el algoritmo realmente requiere muchos recursos. Encontrar una solución en el primer lanzamiento tardó más de un minuto (!) En mi computadora portátil.Bajo pypycon JIT habilitado, la solución tardó 1 segundo en la computadora portátil, pero en la Raspberry Pi aún tardó aproximadamente un minuto. Después de varios intentos de acelerar el trabajo del programa Python (numpy, multiprocesamiento), decidí volver a escribir el algoritmo en C. Sin embargo, la solución ahora toma 1-2 segundos, incluso para Raspberry.Publiqué ambas implementaciones del algoritmo en GitHub .Control de maquina
El siguiente paso fue escribir un programa que controlara la parte mecánica: mover los motores, teniendo en cuenta las relaciones de transmisión y las limitaciones del mecanismo (por ejemplo, los soportes laterales solo se pueden girar cuando la parte inferior está en una posición determinada, de lo contrario interferirá).
Además del programa principal, hice un shell interactivo que me ahorró mucho tiempo al depurar. En general, esta parte no era inusual en términos de programación. Para depurar el escaneo, generé los resultados como imágenes.Escaneo y reconocimiento de color
Hasta este punto, todo era interesante, pero no difícil. Dos semanas después del comienzo del trabajo, la máquina ya podría recoger un cubo de un estado determinado. Solo quedaba aprender a leer la configuración inicial del cubo usando un escáner. Ya teníamos un programa de "trabajo" para Arduino, por lo que no esperábamos sorpresas. Sin embargo, esta parte del proyecto resultó ser la más difícil y nos llevó otros 2 meses de trabajo.Indicaciones de fotoresistencia
Como escribí anteriormente, comenzamos con un circuito de escáner con condensadores. El error de este enfoque fue horrible, por lo que para obtener valores utilizables, tuve que tomar medidas varias veces y luego eliminar las emisiones. Después de eso, obtuvimos algo como esto (este es el resultado de escanear el cubo ensamblado en una habitación oscura):
Como puede ver, el resultado está lejos de ser ideal. En primer lugar, los valores para el mismo color son diferentes en diferentes posiciones, ya que los fotoresistores y los LED "miran" en direcciones ligeramente diferentes. En segundo lugar, algunos colores están muy cerca uno del otro en el espacio de color y, a veces, los rangos de valores se superponen (por ejemplo, el naranja y el rojo a veces dan el mismo valor). Y finalmente, las lecturas dependen mucho de la iluminación externa.Visualmente, el error del escáner en los condensadores se puede ver en el siguiente diagrama (en general, hay una versión interactiva aquí ):
Mirando hacia atrás, me pregunto cómo logramos que el escaneo funcione con tales resultados, aunque esto requirió una calibración cuidadosa y complicada de los valores en cuestión irá un poco más abajo.Como dije, el escáner de condensadores funcionaba, pero era muy lento. Cuando lo reemplazamos con otro, con el Arduino incorporado, las lecturas se volvieron mucho más "abarrotadas" (la versión interactiva está aquí ):
Calibración y agrupamiento de lecturas
Ahora que teníamos las lecturas de RGB sin procesar de los fotorresistores, tuvimos que identificar los colores nosotros mismos para alimentar la configuración del cubo al algoritmo de construcción. Aquí se sugirieron inmediatamente dos enfoques diferentes: el uso de intervalos de color y el algoritmo de agrupamiento.El primer enfoque es una solución "frontal": fue posible determinar experimentalmente los intervalos de valores para cada lado del cubo (de hecho, dividir el espacio de color en áreas disjuntas), y luego simplemente combinar los valores de acuerdo con su pertenencia a un determinado intervalo. En este caso, cada una de las 9 posiciones posibles en el borde del cubo debe considerarse por separado. Este método es muy fácil de programar, pero tiene dos inconvenientes importantes. En primer lugar, nos une a colores específicos, lo que significa que solo podemos recolectar un cubo de Rubik estrictamente definido. Y en segundo lugar, los intervalos de valores posibles dependen mucho de la iluminación externa. Además, descubrimos que, dependiendo de la luz ambiental, la misma lectura puede corresponder a diferentes colores.El segundo enfoque requiere una calibración preliminar de los valores para que el mismo color dé los mismos resultados en las 9 posiciones en el borde del cubo. En este caso, podemos usar el algoritmo de agrupamiento para combinar los valores en 6 grupos. Al mismo tiempo, no importa en qué colores está pintado el cubo, si solo son diferentes. Desafortunadamente, este método también tuvo que ser "rechazado" debido a la naturaleza probabilística de los algoritmos de agrupamiento: pueden producir un "buen" resultado, pero no garantizan su precisión.Ambos enfoques tienen sus pros y sus contras, por lo que utilizamos algo intermedio:- En primer lugar, hacemos una calibración artificial de las lecturas del escáner para normalizar los valores. Los coeficientes se obtienen experimentalmente.
- convertir los valores RGB resultantes a HSV
- , S ()
- , .
Incluso con un buen algoritmo de agrupamiento, el escaneo a menudo fallaba debido a las condiciones ambientales. El algoritmo, calibrado en una habitación oscura, no pudo hacer frente a la tarea en condiciones diurnas, y viceversa. Además, si la iluminación externa era muy brillante (luz solar directa), el escáner generalmente dejaba de funcionar, ya que la influencia de los LED apenas se notaba. Wilbert hizo un trabajo muy minucioso al aislar el escáner de la luz ambiental. Tuve que pasar por 3 iteraciones: cada vez que pensábamos que sería suficiente, y cada vez que encontramos otra brecha a través de la cual la iluminación externa cayó sobre la fotorresistencia.
Conclusión
Trabajar en este proyecto fue increíblemente emocionante. Es genial ver cómo el coche cobra vida ante tus ojos, y es especialmente genial ver cómo funciona, justificando todos tus esfuerzos. Sin embargo, esto no se puede comparar con la reserva de conocimiento que logramos obtener en el proceso. No podría haber imaginado que tendría que estudiar un montón de materiales sobre electrónica, mecánica, álgebra e incluso estadística matemática, y en el camino encontrar una docena de utilidades y bibliotecas útiles. Por eso estoy tan feliz de haber tenido la oportunidad de trabajar en este proyecto.
Sea como fuere, este automóvil es solo un prototipo. No nos propusimos el objetivo de romper el récord de velocidad, y ciertamente no nos dimos cuenta del potencial total de las partes mecánicas. Pero definitivamente intentaremos hacer esto en la próxima versión de la máquina, en la que ya hemos comenzado a trabajar. Allí vamos a usar la cámara para escanear, y el diseño de los manipuladores ha sufrido cambios significativos. Y, por supuesto, si tiene alguna pregunta, sugerencia o sugerencia, me complacerá escucharla en los comentarios. Source: https://habr.com/ru/post/es384503/
All Articles