👩🏻‍⚕️ 👐🏿 🍨 Máquina de cubo de Rubik baseada em FAC 🛀🏻 😰 🐓

Há pouco tempo, juntamente com Wilbert Swinkels, terminamos o trabalho em uma máquina que coleta o Cubo de Rubik. Eles escreveram sobre nós no blog oficial do Raspberry Pi e recebemos muitas críticas elogiosas. No entanto, no segmento russo da rede, o projeto de alguma forma passou despercebido. Então, decidi corrigir essa omissão postando aqui uma versão traduzida e aumentada da postagem original .

Sob o corte, falaremos (principalmente) sobre a parte do software desta máquina, a parte mecânica pode ser encontrada na página oficial do projeto (sim, sabemos que é uma pequena "velha escola")

TL; DR

Para os impacientes, alguns links:

Introdução

Tudo começou com o fato de que, em maio deste ano, conheci acidentalmente Wilbert Swinkels. Fiquei simplesmente chocado ao ver suas criações : cada um desses mecanismos, de pequenos a grandes, pode ser chamado com segurança de obra de arte. E quanto mais você olha para o dispositivo deles, mais impressionado com a beleza deles.

É claro que, quando Wilbert me convidou para ajudá-lo com a máquina de montagem de cubos de Rubik, não hesitei nem um segundo, principalmente porque já havia descoberto uma paixão por cubos coloridos. Naquela época, ele já trabalhava na máquina há mais de 4 (!) Anos, mas a parte do software ainda estava para ser escrita.

Eu não tinha experiência com programação para Raspberry Pi e Arduino, mas no geral a tarefa me pareceu bastante simples. Claro, eu estava errado :)

Hardware

A própria máquina é construída usando um sistema FAC modular . É como um designer soviético, mas criado para prototipar mecanismos sérios e complexos. Na segunda metade do século passado, foi usado ativamente nos laboratórios da Philips e outras empresas e universidades.

Quando conheci Wilbert, ele já havia tentado duas vezes "reviver" o carro. Nas duas vezes, os estudantes da Universidade de Amsterdã aceitaram o caso e, infelizmente, ambas perderam o interesse no projeto após várias tentativas frustradas. Um deles chegou a defender um diploma de bacharel nesse assunto, apesar de a máquina não ter conseguido coletar o cubo (levante sua mão para aqueles que se reconhecem aqui).

Microcontrolador

Primeiro, decidimos usar o Raspberry Pi em vez do Arduino. Isso se deve principalmente ao fato de que algoritmos "inteligentes" para resolver o Cubo de Rubik exigem uma quantidade significativa de memória e energia do processador. Nas tentativas anteriores, um algoritmo primitivo de três camadas foi usado , mas desta vez decidimos usar o algoritmo de Kotsemba . Além disso, eu realmente não queria escrever tudo em C (embora em parte fosse necessário).

imagem

Na versão padrão do Raspberry Pi, como não tínhamos pinos suficientes para conectar todos os motores disponíveis, solicitamos o Kit de Desenvolvimento . A propósito, eu recomendo fortemente: não apenas mais pinos, mas eles são, na minha opinião, mais lógicos à parte. Além disso, esta placa possui dois conectores para a câmera em vez de um.

A primeira versão do scanner

Para ler a configuração inicial do cubo, era necessário um dispositivo de digitalização. A ideia é muito simples: por sua vez, iluminamos a superfície do cubo com três LEDs: vermelho, verde e azul. Cada vez que medimos a luz refletida usando um resistor fotossensível. Teoricamente, devemos obter valores RGB que possam ser usados para reconhecer a cor do quadrado. Dos programadores anteriores, ainda temos código de prova de conceito para o Arduino, que, ao que parece, funcionou sob certas condições.

O primeiro problema que encontramos foi uma incompatibilidade de tensão. Como você sabe, a unidade lógica nos pinos do Arduino é de 5V, enquanto o Raspberry Pi é de 3,3V. Felizmente, os controladores de motor de passo que usamos continuaram a funcionar, apesar de alterar a amplitude dos pulsos.

Acabou sendo muito mais crítico que o Raspberry Pi não possua entradas analógicas. Por causa disso, o Raspberry não pode simplesmente captar e ler a tensão no fotorresistor. Provavelmente isso é óbvio para aqueles que pelo menos uma vez se depararam com isso, mas a princípio nem pensei nisso. Pesquisando na rede por uma solução, deparamos com este artigo. Em poucas palavras, adicionamos um capacitor ao circuito e medimos o tempo durante o qual ele cobrará de zero a uma unidade lógica (podemos detectá-lo usando um pino digital). O tempo de carregamento será proporcional à resistência do fotorresistor, para que possamos avaliar a quantidade de luz.

imagem

Essa abordagem não é apenas extremamente confiável (dedicar tempo em um script Python Python no Linux com vários processos em segundo plano é uma coisa ingrata), mas também é impossível demorar muito. Para suavizar os desvios aleatórios nas leituras, tivemos que ler várias vezes, livrar-se dos valores extremos e calcular a média dos valores restantes. No entanto, ainda conseguimos fazer com que esse scanner funcionasse:

A segunda versão (final) do scanner

O scanner de capacitor funcionou muito bem, mas foi muito lento. Demorou cerca de dois minutos para varrer todo o cubo de Rubik e, quando a varredura foi concluída, o espectador havia perdido todo o interesse. Portanto, decidimos retornar ao Arduino e compramos um pequeno Arduino Mini especificamente para controlar o scanner.

imagem

Fazer amigos do Arduino com o Raspberry Pi acabou incrivelmente simples: dois fios, um conversor de voltagem entre eles e pronto - temos uma interface serial. E se você estragar um protocolo Min simples , programar esse negócio é um prazer.

Transferi toda a lógica de controle do scanner para o Arduino. A velocidade da digitalização aumentou significativamente. Graças às entradas analógicas, podemos ler a tensão diretamente dos fotorresistores, e esses valores são muito precisos. Além disso, como o Arduino é montado diretamente no scanner, precisamos de muito menos fios do scanner para o Raspberry Pi!

Algoritmo de construção

Montar o cubo de Rubik do ponto de vista matemático é uma tarefa bastante trabalhosa . Obviamente, estamos falando em encontrar a solução ideal, e não "algumas". Fiquei surpreso quando descobri que o número de Deus (o limite inferior exato para o número de movimentos necessários para resolver um cubo arbitrário) foi encontrado apenas em 2010 .

Neste projeto, queríamos reduzir o tempo total necessário para calcular a solução e montar, portanto, nem um algoritmo simples de três camadas se aproximou de nós (ele funciona rapidamente, mas oferece soluções com cem movimentos), nem um algoritmo ideal (as soluções são curtas, mas o processo de renderização no Raspberry Pi levaria uma eternidade). Como resultado, decidimos pelo magnífico algoritmo "bifásico"Matemático alemão Herbert Kociemba. Ele é capaz de emitir decisões abaixo do ideal (uma média de 20 movimentos), mantendo-o dentro de um tempo razoável.

No site do autor, você pode encontrar a implementação do algoritmo em Java. A primeira coisa que fiz foi traduzir esse código em Python. Não foi nada difícil, pois a maior parte do programa é operações matemáticas e enumeração de opções. No entanto, não levei em conta que o algoritmo realmente requer muitos recursos. Encontrar uma solução no primeiro lançamento levou mais de um minuto (!) No meu laptop.

Sob pypycom o JIT ativado, a solução demorou 1 segundo no laptop, mas no Raspberry Pi ainda demorou cerca de um minuto. Após várias tentativas de acelerar o trabalho do programa Python (numpy, multiprocessamento), decidi reescrever o algoritmo em C. No entanto, a solução agora leva de 1 a 2 segundos, mesmo para Raspberry.

Postei as duas implementações do algoritmo no GitHub .

Controle da máquina

O próximo passo foi escrever um programa que controlasse a parte mecânica: mover os motores, levando em consideração as relações de transmissão e as limitações do mecanismo (por exemplo, os suportes laterais só podem ser girados quando o fundo estiver em uma determinada posição, caso contrário, isso interferirá).

imagem

Além do programa principal, criei um shell interativo que me salvou muito tempo ao depurar. Em geral, essa parte não era incomum em termos de programação. Para depurar a verificação, gerei os resultados como imagens.

Digitalização e reconhecimento de cores

Até esse ponto, tudo era interessante, mas não difícil. Duas semanas após o início do trabalho, a máquina já podia coletar um cubo de um determinado estado. Restou apenas aprender a ler a configuração inicial do cubo usando um scanner. Já tínhamos um programa de trabalho para o Arduino, por isso não esperávamos surpresas. No entanto, essa parte do projeto acabou sendo a mais difícil e levamos mais 2 meses de trabalho.

Indicações Photoresistor

Como escrevi acima, começamos com um circuito de scanner com capacitores. O erro dessa abordagem foi horrível; portanto, para obter valores utilizáveis, tive que fazer medições várias vezes e depois me livrar das emissões. Depois disso, obtivemos algo assim (este é o resultado da digitalização do cubo montado em uma sala escura):

Como você pode ver, o resultado está longe de ser o ideal. Primeiro, os valores para a mesma cor são diferentes em posições diferentes, pois os fotorresistores e os LEDs “olham” em direções ligeiramente diferentes. Em segundo lugar, algumas cores estão muito próximas umas das outras no espaço de cores e, às vezes, os intervalos de valores se sobrepõem (por exemplo, laranja e vermelho às vezes dão o mesmo valor). E, finalmente, as leituras dependem muito da iluminação externa.

Visualmente, o erro do scanner nos capacitores pode ser visto no diagrama a seguir (em geral, há uma versão interativa aqui ):

Olhando para trás, pergunto-me como conseguimos fazer a digitalização funcionar com esses resultados, embora isso exigisse uma calibração cuidadosa e complicada dos valores em questão vai um pouco mais baixo.

Como eu disse, o scanner de capacitor funcionou, mas foi muito lento. Quando o substituímos por outro, pelo Arduino embutido, as leituras ficaram muito mais "cheias" (a versão interativa está aqui ):

Calibração e agrupamento de leituras

Agora que tínhamos as leituras brutas de RGB dos fotorresistores, tivemos que identificar as cores para fornecer a configuração do cubo ao algoritmo de construção. Duas abordagens diferentes foram imediatamente sugeridas aqui: o uso de intervalos de cores e o algoritmo de agrupamento.

A primeira abordagem é uma solução "frontal": foi possível determinar experimentalmente os intervalos de valores para cada lado do cubo (de fato, para dividir o espaço de cores em áreas separadas) e, em seguida, simplesmente combinar os valores de acordo com sua pertença a um determinado intervalo. Nesse caso, cada uma das 9 posições possíveis na borda do cubo deve ser considerada separadamente. Este método é muito fácil de programar, mas possui duas desvantagens significativas. Primeiro, ele nos liga a cores específicas, o que significa que só podemos coletar um cubo de Rubik estritamente definido. E segundo, os intervalos de valores possíveis dependem muito da iluminação externa. Além disso, descobrimos que, dependendo da luz ambiente, a mesma leitura pode corresponder a cores diferentes.

A segunda abordagem requer calibração preliminar dos valores para que a mesma cor produz os mesmos resultados em todas as 9 posições na borda do cubo. Nesse caso, podemos usar o algoritmo de agrupamento para combinar os valores em 6 grupos. Ao mesmo tempo, não importa em que cores o cubo é pintado, se elas forem diferentes. Infelizmente, esse método também teve que ser "rejeitado" devido à natureza probabilística dos algoritmos de agrupamento: eles podem produzir um resultado "bom", mas não garantem sua precisão.

Ambas as abordagens têm seus prós e contras, portanto, como resultado, usamos algo entre:

Antes de tudo, fazemos uma calibração artificial das leituras do scanner para normalizar os valores. Os coeficientes são obtidos experimentalmente.
converta os valores RGB resultantes em HSV
, S ()
, .

Mesmo com um bom algoritmo de agrupamento, a verificação frequentemente falhava devido às condições ambientais. O algoritmo, calibrado em um quarto escuro, não conseguiu lidar com a tarefa em condições diurnas e vice-versa. Além disso, se a iluminação externa era muito brilhante (luz solar direta), o scanner geralmente parava de funcionar, pois a influência dos LEDs se tornava quase imperceptível. Wilbert fez um trabalho minucioso ao isolar o scanner da luz ambiente. Eu tive que passar por três iterações: cada vez que pensávamos que seria suficiente, e cada vez que encontramos outra lacuna através da qual a iluminação externa caía no fotorresistor.

imagem

Conclusão

Trabalhar neste projeto foi incrivelmente empolgante. É muito bom ver o carro ganhar vida diante de seus olhos e é especialmente legal ver como ele funciona, justificando todos os seus esforços. No entanto, isso não pode ser comparado ao estoque de conhecimento que conseguimos obter no processo. Eu não poderia imaginar que teria que estudar um monte de materiais sobre eletrônica, mecânica, álgebra e até estatística matemática, e ao longo do caminho para encontrar uma dúzia de utilitários e bibliotecas úteis. É por isso que estou tão feliz por ter tido a oportunidade de trabalhar neste projeto.

imagem

Seja como for, este carro é apenas um protótipo. Não estabelecemos o objetivo de quebrar o recorde de velocidade e certamente não percebemos todo o potencial das peças mecânicas. Mas definitivamente tentaremos fazer isso na próxima versão da máquina, na qual já começamos a trabalhar. Lá vamos usar a câmera para digitalizar, e o design dos manipuladores sofreu mudanças significativas. E, claro, se você tiver alguma dúvida, sugestão ou dica, ficarei feliz em ouvi-los nos comentários.

Máquina de cubo de Rubik baseada em FAC