♓️ 👩🏾‍🤝‍👩🏻 ✍🏽 Mesin Kubus Rubik berbasis FAC 👨🏽‍🌾 👩🏻‍🎤 👘

Belum lama berselang, bersama Wilbert Swinkels, kami selesai mengerjakan mesin yang mengumpulkan Rubik's Cube. Mereka menulis tentang kami di blog resmi Raspberry Pi dan kami menerima banyak sambutan hangat. Namun demikian, di segmen jaringan Rusia, proyek itu entah bagaimana tidak diketahui. Jadi saya memutuskan untuk memperbaiki kelalaian ini dengan memposting di sini versi terjemahan dan augmented dari posting asli .

Di bawah potongan, kita akan berbicara (terutama) tentang bagian perangkat lunak dari mesin ini, bagian mekanis dapat ditemukan di halaman resmi proyek (ya, kita tahu bahwa itu sedikit "sekolah tua")

TL; DR

Untuk yang tidak sabar, beberapa tautan:

pengantar

Semuanya dimulai dengan fakta bahwa pada bulan Mei tahun ini, saya secara tidak sengaja bertemu dengan Wilbert Swinkels. Saya sangat terkejut ketika melihat ciptaannya : masing-masing mekanisme ini, dari kecil hingga besar, dapat dengan aman disebut sebagai karya seni. Dan semakin dekat Anda melihat perangkat mereka, semakin Anda dikejutkan oleh kecantikan mereka.

Tentu saja, ketika Wilbert mengundang saya untuk membantunya dengan Mesin Perakitan Kubus Rubik, saya tidak ragu untuk sesaat, terutama karena pada saat itu saya sudah menemukan hasrat untuk kubus berwarna. Pada saat itu, dia sudah mengerjakan mesin lebih dari 4 (!) Tahun, tetapi bagian perangkat lunaknya masih harus ditulis.

Saya tidak punya pengalaman dengan pemrograman untuk Raspberry Pi dan Arduino, tetapi secara keseluruhan tugas itu tampak cukup sederhana bagi saya. Tentu saja saya salah :)

Perangkat keras

Mesin itu sendiri dibangun menggunakan sistem FAC modular . Ini adalah sesuatu seperti perancang Soviet, tetapi diciptakan untuk membuat prototipe mekanisme yang serius dan kompleks. Pada paruh kedua abad terakhir, itu sangat aktif digunakan di laboratorium Philips dan perusahaan dan universitas lain.

Pada saat saya bertemu Wilbert, dia sudah mencoba dua kali untuk "menghidupkan kembali" mobil. Kedua kali, mahasiswa dari Universitas Amsterdam menangani kasus ini, dan, sayangnya, kedua kali mereka kehilangan minat pada proyek setelah beberapa upaya yang gagal. Salah satu dari mereka bahkan membela ijazah sarjana tentang topik ini, terlepas dari kenyataan bahwa sebagai akibatnya mesin tidak dapat mengumpulkan kubus (angkat tangan Anda kepada mereka yang mengenali diri mereka di sini).

Mikrokontroler

Pertama-tama, kami memutuskan untuk menggunakan Raspberry Pi, bukan Arduino. Hal ini terutama disebabkan oleh fakta bahwa algoritma "pintar" untuk menyelesaikan Rubik's Cube memerlukan sejumlah besar memori dan daya prosesor. Dalam upaya sebelumnya, algoritma tiga lapis primitif digunakan , tetapi kali ini kami memutuskan untuk menggunakan algoritma Kotsemba . Selain itu, saya tidak benar-benar ingin menulis semuanya dalam C (walaupun sebagian saya harus).

gambar

Dalam versi standar Raspberry Pi, kami tidak memiliki cukup pin untuk menghubungkan semua motor yang tersedia, jadi kami memesan Kit Pengembangan . By the way, saya sangat menyarankan: tidak hanya lebih banyak pin, tetapi mereka, menurut pendapat saya, lebih logis terpisah. Selain itu, board ini memiliki dua konektor untuk kamera, bukan satu.

Versi pertama dari pemindai

Untuk membaca konfigurasi awal kubus, diperlukan perangkat pemindaian. Idenya sangat sederhana: pada gilirannya, kita menerangi permukaan kubus dengan tiga LED: merah, hijau dan biru. Setiap kali kita mengukur cahaya yang dipantulkan menggunakan resistor fotosensitif. Secara teoritis, kita harus mendapatkan nilai RGB yang dapat digunakan untuk mengenali warna kotak. Dari programmer sebelumnya, kami masih memiliki kode proof-of-concept untuk Arduino, yang tampaknya, bahkan berfungsi dalam kondisi tertentu.

Masalah pertama yang kami temui adalah ketidakcocokan tegangan. Seperti yang Anda ketahui, unit logis pada pin Arduino adalah 5V, sedangkan Raspberry Pi adalah 3.3V. Untungnya, pengendali driver motor stepper yang kami gunakan terus bekerja meskipun mengubah amplitudo pulsa.

Ternyata jauh lebih penting bahwa Raspberry Pi tidak memiliki input analog. Karena itu, Raspberry tidak dapat dengan mudah mengambil dan membaca tegangan pada photoresistor. Ini mungkin jelas bagi mereka yang setidaknya pernah menemukan ini, tetapi pada awalnya saya bahkan tidak memikirkannya. Mencari solusi di internet, kami menemukan artikel ini. Singkatnya, kami menambahkan kapasitor ke sirkuit, dan mengukur waktu selama itu akan diisi dari nol ke unit logis (kami dapat mendeteksi ini menggunakan pin digital). Waktu pengisian akan sebanding dengan resistansi photoresistor, sehingga kita dapat menilai jumlah cahaya.

gambar

Pendekatan ini tidak hanya sangat tidak dapat diandalkan (meluangkan waktu dalam skrip Python Python di Linux dengan banyak proses latar belakang adalah hal yang tidak berterima kasih), tetapi juga tidak mungkin lama. Untuk memuluskan penyimpangan acak dalam bacaan, kami harus membaca beberapa kali, menyingkirkan outlier , dan rata-rata nilai yang tersisa. Namun, kami masih berhasil membuat pemindai ini berfungsi:

Versi pemindai kedua (final)

Pemindai kapasitor bekerja cukup baik, tetapi sangat lambat. Butuh waktu sekitar dua menit untuk memindai seluruh Rubik's Cube, dan pada saat pemindaian selesai, pemirsa telah kehilangan minat. Oleh karena itu, kami memutuskan untuk kembali ke Arduino dan membeli Arduino Mini kecil khusus untuk mengendalikan pemindai.

gambar

Membuat teman Arduino dengan Raspberry Pi ternyata sangat sederhana: dua kabel, konverter tegangan di antara mereka, dan voila - kami memiliki antarmuka Serial. Dan jika Anda mengacaukan protokol Min sederhana , maka memprogram bisnis ini adalah kesenangan.

Saya memindahkan semua logika kontrol pemindai ke Arduino. Kecepatan pemindaian telah meningkat secara signifikan. Berkat input analog, kita dapat membaca voltase langsung dari fotoresistor, dan nilai-nilai ini sangat akurat. Selain itu, karena Arduino dipasang langsung pada pemindai, kita membutuhkan lebih sedikit kabel dari pemindai ke Raspberry Pi!

Membangun algoritma

Merakit Rubik's Cube dari sudut pandang matematika adalah tugas yang agak melelahkan . Tentu saja, kita berbicara tentang menemukan solusi optimal, dan bukan "beberapa". Saya terkejut ketika saya menemukan bahwa jumlah Tuhan (batas bawah yang tepat untuk jumlah langkah yang diperlukan untuk menyelesaikan kubus yang berubah-ubah) ditemukan hanya pada tahun 2010 .

Dalam proyek ini, kami ingin mengurangi total waktu yang diperlukan untuk menghitung solusi dan perakitan, oleh karena itu baik algoritma tiga lapis yang sederhana tidak mendekati kami (ia bekerja dengan cepat, tetapi memberikan solusi yang seratus langkah panjang), atau algoritma yang optimal (solusi yang singkat, tetapi proses rendering pada Raspberry Pi akan butuh selamanya). Sebagai hasilnya, kami menetapkan algoritma "dua fase" yang luar biasaMatematikawan Jerman, Herbert Kociemba. Dia mampu mengeluarkan keputusan suboptimal (rata-rata 20 gerakan), sambil menjaga dalam waktu yang wajar.

Di situs penulis Anda dapat menemukan implementasi algoritma di Jawa. Hal pertama yang saya lakukan adalah menerjemahkan kode ini ke dalam Python. Itu sama sekali tidak sulit, karena sebagian besar program adalah operasi matematika dan enumerasi opsi. Namun, saya tidak memperhitungkan bahwa algoritma ini benar - benar membutuhkan banyak sumber daya. Menemukan solusi pada peluncuran pertama butuh lebih dari satu menit (!) Di laptop saya.

Di bawah pypydengan JIT diaktifkan, solusi membutuhkan waktu 1 detik pada laptop, tetapi pada Raspberry Pi masih membutuhkan waktu sekitar satu menit. Setelah beberapa upaya untuk mempercepat kerja program Python (numpy, multiprocessing), saya memutuskan untuk menulis ulang algoritme menjadi C. Namun demikian, solusinya sekarang membutuhkan waktu 1-2 detik, bahkan untuk Raspberry.

Saya memposting kedua implementasi algoritma di GitHub .

Kontrol mesin

Langkah selanjutnya adalah menulis program yang akan mengontrol bagian mekanis: memindahkan motor, dengan mempertimbangkan rasio roda gigi dan batasan mekanisme (misalnya, pemegang samping hanya dapat diputar ketika bagian bawah berada pada posisi tertentu, jika tidak maka akan mengganggu).

gambar

Selain program utama, saya membuat shell interaktif yang menghemat banyak waktu saat debugging. Secara umum, bagian ini tidak biasa dalam hal pemrograman. Untuk men-debug pemindaian, saya membuat hasilnya sebagai gambar.

Pindai dan pengenalan warna

Hingga saat ini, semuanya menarik, tetapi tidak sulit. Dua minggu setelah dimulainya pekerjaan, mesin sudah bisa mengumpulkan kubus dari keadaan tertentu. Tinggal mempelajari cara membaca konfigurasi awal kubus menggunakan pemindai. Kami sudah memiliki program "bekerja" untuk Arduino, jadi kami tidak mengharapkan kejutan apa pun. Namun, bagian dari proyek ini ternyata yang paling sulit, dan kami butuh 2 bulan kerja lagi.

Indikasi Fotoresistor

Seperti yang saya tulis di atas, kami mulai dengan rangkaian pemindai dengan kapasitor. Kesalahan pendekatan ini mengerikan, jadi untuk mendapatkan nilai yang dapat digunakan, saya harus melakukan pengukuran beberapa kali, dan kemudian membuang emisi. Setelah itu, kami mendapatkan sesuatu seperti ini (ini adalah hasil pemindaian kubus yang dirakit di ruangan gelap):

Seperti yang Anda lihat, hasilnya jauh dari ideal. Pertama, nilai-nilai untuk warna yang sama berbeda di posisi yang berbeda, karena fotoresistor dan LED “melihat” ke arah yang sedikit berbeda. Kedua, beberapa warna sangat dekat satu sama lain dalam ruang warna, dan kadang-kadang rentang nilai tumpang tindih (misalnya, oranye dan merah terkadang memberikan nilai yang sama). Dan akhirnya, bacaan sangat tergantung pada pencahayaan eksternal.

Secara visual, kesalahan pemindai pada kapasitor dapat dilihat pada diagram berikut (secara umum, ada versi interaktif di sini ):

Melihat ke belakang, saya bertanya-tanya bagaimana kami berhasil membuat pemindaian bekerja dengan hasil seperti itu, meskipun ini membutuhkan kalibrasi nilai-nilai yang dipermasalahkan dengan cermat dan rumit. akan sedikit lebih rendah.

Seperti yang saya katakan, pemindai kapasitor berfungsi, tetapi sangat lambat. Ketika kami menggantinya dengan yang lain, dengan Arduino bawaan, bacaan menjadi jauh lebih “ramai” ( versi interaktif ada di sini ):

Kalibrasi dan pengelompokan bacaan

Sekarang kami memiliki pembacaan RGB mentah dari fotoresistor, kami harus mengidentifikasi warna sendiri untuk memberi makan konfigurasi kubus ke algoritma build. Dua pendekatan yang berbeda segera disarankan di sini: penggunaan interval warna dan algoritma pengelompokan.

Pendekatan pertama adalah solusi "langsung": adalah mungkin untuk secara eksperimental menentukan interval nilai untuk setiap sisi kubus (pada kenyataannya, untuk membagi ruang warna menjadi area yang terpisah), dan kemudian hanya menggabungkan nilai-nilai sesuai dengan milik mereka pada interval tertentu. Dalam hal ini, masing-masing dari 9 posisi yang mungkin di tepi kubus harus dipertimbangkan secara terpisah. Metode ini sangat mudah diprogram, tetapi memiliki dua kelemahan signifikan. Pertama, itu mengikat kita dengan warna tertentu, yang berarti kita hanya bisa mengumpulkan kubus Rubik yang didefinisikan secara ketat. Dan kedua, interval nilai yang mungkin sangat tergantung pada pencahayaan eksternal. Selain itu, kami menemukan bahwa, tergantung pada cahaya sekitar, bacaan yang sama mungkin sesuai dengan warna yang berbeda.

Pendekatan kedua membutuhkan kalibrasi awal dari nilai-nilai sehingga warna yang sama memberikan hasil yang sama di semua 9 posisi di tepi kubus. Dalam hal ini, kita bisa menggunakan algoritma pengelompokan untuk menggabungkan nilai-nilai menjadi 6 kelompok. Pada saat yang sama, tidak masalah warna kubus mana yang dilukis, jika saja mereka berbeda. Sayangnya, metode ini juga harus "ditolak" karena sifat probabilistik dari algoritma pengelompokan: mereka dapat menghasilkan hasil "baik", tetapi tidak menjamin keakuratannya.

Kedua pendekatan memiliki pro dan kontra, sehingga kami menggunakan sesuatu di antaranya:

Pertama-tama, kami melakukan kalibrasi buatan dari pembacaan pemindai untuk menormalkan nilai. Koefisien diperoleh secara eksperimental.
mengkonversi nilai RGB yang dihasilkan ke HSV
, S ()
, .

Bahkan dengan algoritma pengelompokan yang baik, pemindaian sering gagal karena kondisi lingkungan. Algoritma, dikalibrasi di ruangan gelap, tidak bisa mengatasi tugas dalam kondisi siang hari, dan sebaliknya. Selain itu, jika pencahayaan eksternal sangat terang (sinar matahari langsung), pemindai umumnya berhenti bekerja, karena pengaruh LED menjadi hampir tidak terlihat. Wilbert melakukan pekerjaan yang sangat melelahkan mengisolasi pemindai dari cahaya sekitar. Saya harus melalui 3 iterasi: setiap kali kami berpikir itu akan cukup, dan setiap kali kami menemukan celah lain di mana pencahayaan eksternal jatuh pada photoresistor.

gambar

Kesimpulan

Bekerja pada proyek ini sangat menarik. Sungguh luar biasa menyaksikan mobil menjadi hidup di depan mata Anda, dan sangat keren melihat cara kerjanya, membenarkan semua upaya Anda. Namun, ini tidak bisa dibandingkan dengan penyimpanan pengetahuan yang kami berhasil peroleh dalam proses. Saya tidak dapat membayangkan bahwa saya harus mempelajari banyak materi tentang elektronik, mekanik, aljabar dan bahkan statistik matematika, dan di sepanjang jalan untuk menemukan selusin utilitas dan perpustakaan yang bermanfaat. Itu sebabnya saya sangat senang bahwa saya memiliki kesempatan untuk mengerjakan proyek ini.

gambar

Bagaimanapun, mobil ini hanyalah sebuah prototipe. Kami tidak menetapkan diri untuk memecahkan rekor kecepatan, dan tentu saja kami tidak menyadari potensi penuh dari bagian-bagian mekanik. Tetapi kami pasti akan mencoba melakukan ini di versi mesin yang berikutnya, yang sudah kami mulai bekerja. Di sana kita akan menggunakan kamera untuk memindai, dan desain dari manipulator telah mengalami perubahan signifikan. Dan tentu saja, jika Anda memiliki pertanyaan, saran atau kiat, saya akan senang mendengarnya di komentar.

Mesin Kubus Rubik berbasis FAC