Menemukan Cara Baru untuk Berkolaborasi Bersama demi Kawanan Cerdas

Algoritma baru menunjukkan bagaimana segerombolan robot sederhana dapat dibuat untuk bekerja bersama secara keseluruhan

Di laboratorium Institut Teknologi Georgia, fisikawan bereksperimen dengan robot yang terlihat seperti dibeli di toko "semuanya seharga $ 1". Robot tidak dapat bergerak di ruang angkasa atau berkomunikasi satu sama lain. Pada dasarnya, mereka melambaikan tangan kecil mereka, seperti kumbang yang dipunggung.

Tetapi jika Anda menyatukan banyak perangkat ini, Anda dapat memperoleh sesuatu dari ketiadaan: mereka saling mendorong, mendorong, dan saling mengunci. Dan sebagai hasilnya, mereka mulai bekerja secara keseluruhan.

Para peneliti sedang mempelajari cara mengendalikan sistem tersebut sehingga berfungsi dengan cara yang mirip dengan kawanan lebah atau koloni semut: setiap individu bertindak berdasarkan seperangkat aturan yang sama, tetapi beberapa individu yang berkumpul bersama dapat menunjukkan perilaku kompleks tanpa kontrol pusat.

“Pendekatan kami adalah sebagai berikut: untuk mencari tahu apa model komputasi paling sederhana yang diperlukan untuk mencapai tugas-tugas kompleks ini? Kata Dana Randall , seorang spesialis IT di Georgettech, salah satu pemimpin proyek. "Kami mencari keanggunan dan kesederhanaan."

Randol, sebagai seorang programmer, mendekati tugas dari sudut pandang algoritme: apa set instruksi paling sederhana berdasarkan pada mana unit individu dari kawanan dapat bekerja, berdasarkan pada sedikit data yang mereka dapat kumpulkan, pasti akan mengarah pada perilaku bersama kompleks yang diperlukan untuk para peneliti? November lalu, Randall dan rekannya menerbitkan algoritma untuk memastikan bahwa segerombolan partikel yang ideal dapat bergerak secara terkendali.

Bekerja dengan robot seperti itu, yang oleh para ilmuwan disebut "smarticles" [smarticles; pintar - pintar, partikel - partikel / kira-kira. terjemahan.] - bagian dari penelitian di bidang kemungkinan penciptaan dan kegunaan robot yang mengatur diri sendiri. Contoh lain seperti itu termasuk robot-robot berukuran sedang yang sedang dikembangkan di University of Colorado, segerombolan kilobot dari Universitas Harvard, dan svarmanoidy dari laboratorium Belgia. Dalam banyak kasus, idenya adalah meniru fenomena alam, seperti gerakan koloni semut yang terdesentralisasi atau kumpulan molekul-molekul DNA yang tidak disadari dan dirancang sendiri.

"Kami tahu apa yang kami inginkan dari segerombolan penuh, tetapi untuk memprogramnya, Anda perlu mengetahui apa yang harus dilakukan masing-masing agen secara terpisah," kata Melvin Gauchi , seorang peneliti di Harvard yang bekerja dalam robot kelompok . "Bagian tersulit adalah di antara dua level ini."


Dana Randall dan Dan Goldman di Lab Goldman

Hati-hati dengan para pemimpin

Daniel Goldman adalah seorang ahli fisika dari Georgetch yang menjalankan eksperimen Smarticle. Dia terutama tertarik pada fisika bahan granular aktif yang dapat mengubah bentuknya. Di antara slide konferensinya adalah sesaat dari film Spider-Man 3, menunjukkan kemunculan supercillain Sandman - butiran pasir individu yang tersebar di seluruh gurun berkumpul dalam bentuk seorang pria. Smartphone adalah cara Goldman menguji bahan granular aktif di laboratorium.

“Mereka memberi kita kesempatan untuk menggunakan geometri untuk mengontrol sifat material. Jika Anda memfokuskan mata, Anda dapat membayangkan bahwa sekelompok smartphone ini adalah bahan nyata, ”kata Goldman.

Smarticles memiliki anggota tubuh pendek yang dapat diayun bolak-balik. Mereka bereaksi terhadap cahaya dan suara dari frekuensi yang berbeda. Mereka dapat diprogram untuk mengubah kecepatan melambaikan anggota badan sebagai respons terhadap tindakan smartphone lain di dekat mereka.

Smartphone dapat dibuat untuk melakukan beberapa tindakan: menyusun (menumpuk), memperluas (mendistribusikan) dan bergerak. Manuver-manuver ini dapat berfungsi sebagai dasar untuk melakukan fungsi-fungsi yang lebih kompleks, tetapi bahkan tugas-tugas semacam itu cukup sulit untuk dipecahkan, karena smartphone tidak memahami bagaimana mereka berada dalam hubungannya dengan seluruh grup.

Untuk memahami kemungkinan dan kesulitan yang terkait dengan pemrograman perilaku kompleks, yang timbul dari bagian-bagian sederhana, perlu diingat apa sebenarnya yang diketahui masing-masing smarticle individu. Tidak terlalu banyak. Dia tidak bisa melihat, ingatannya terbatas, dan semua yang dia tahu tentang smartphone lain yang dengannya dia harus mengoordinasikan tindakan, dia belajar ketika dia bertemu tetangga terdekatnya.

"Bayangkan seorang pria di sebuah konser rock dengan mata tertutup," kata Joshua Daimad, seorang mahasiswa pascasarjana di bidang ilmu komputer dari Arizona University yang sedang mengerjakan proyek smartphone.



Salah satu strategi mungkin menunjuk seorang pemimpin untuk mengelola kawanan - tetapi pendekatan itu rentan. Jika pemimpin menderita, seluruh kawanan akan gagal. Yang lain adalah untuk memberi masing-masing robot tugas yang unik dalam kerumunan, tetapi dalam skala besar pendekatan ini tidak praktis. "Memprogram 1.000 robot secara individual hampir tidak mungkin," kata Jeff Dasek , seorang peneliti di Harvard College of Engineering di Olin dan mantan anggota kelompok penelitian sistem pengaturan-diri Harvard yang bekerja pada kawanan robot bawah air . "Tetapi ketika setiap anggota kelompok bekerja sesuai dengan aturan yang sama, kode Anda tidak berubah, terlepas dari apakah Anda memiliki 10 robot, 1.000 atau 10.000."

Algoritma swarm memiliki dua properti. Pertama, itu didistribusikan, yaitu, ia bekerja secara terpisah pada masing-masing partikel sistem (karena setiap semut nomaden melakukan set tindakan paling sederhana tergantung pada informasi yang diterima dari lingkungan). Kedua, ini mencakup unsur peluang. Ini berarti bahwa jika, misalnya, semut nomaden merasakan keberadaan lima semut lain di sekitarnya, maka dengan probabilitas 20% ia akan bergerak ke kiri, dan dengan 80% ke kanan. Algoritma berbeda secara acak dari algoritma deterministik di mana setiap tahap sepenuhnya ditentukan oleh yang sebelumnya.

Keacakan mungkin tampak tidak perlu untuk algoritma - setelah semua, ketika menerapkan suatu prosedur, Anda biasanya ingin mencapai hasil tertentu. Tetapi keacakan memiliki manfaat kinerja yang tidak terduga, yang membuat algoritma acak sangat cocok untuk digunakan dalam kawanan.

Jaminan acak

Pada 2015, Goldman dan Randall membahas kemungkinan menemukan aturan yang bisa digunakan bersama untuk smartphone secara keseluruhan. Randall menyadari bahwa perilaku yang diinginkan Goldman untuk memimpin gerombolan itu sangat mirip dengan perilaku sistem partikel ideal yang dipelajari dalam ilmu komputer.

"Dan saya langsung berpikir: Saya tahu persis apa yang harus dilakukan," kata Randall.

Bagi Randall, perilaku smartphone menyerupai fenomena yang dimodelkan oleh para ilmuwan komputer dalam banyak konteks lainnya. Salah satu contoh paling terkenal adalah munculnya daerah terpisah. Pada akhir 1960-an, ekonom Thomas Schelling ingin memahami bagaimana pemisahan berdasarkan wilayah terjadi tanpa adanya kekuatan sentral yang menyortir orang berdasarkan warna kulit. Dia membayangkan seseorang yang hipotetis memandang tetangganya dan memutuskan untuk bergerak berdasarkan berapa banyak tetangga yang mirip dengannya. Ketika seseorang pindah, Schelling memindahkannya ke tempat acak di pemukiman, tempat proses algoritmik pengamatan dan pengambilan keputusan diulang. Schelling menemukan bahwa menurut aturannya, munculnya segregasi penduduk hampir dijamin, bahkan jika beberapa orang lebih suka tinggal di daerah yang beragam.


William Savoy, mahasiswa pascasarjana di lab Goldman

Randall menyadari bahwa smartphone di gerombolan mereka menyerupai orang-orang dalam model Schelling. Dalam kedua kasus tersebut, masing-masing unit harus membuat keputusan tanpa mengetahui posisi mereka dalam skema global (mereka hanya tahu apa yang mereka lihat di sekitarnya). Dalam model Schelling, keputusan dapat dibuat dengan unsur keacakan - jika tetangga berbeda dari Anda, maka ada kemungkinan Anda akan pindah, dan ada kemungkinan Anda akan tetap tinggal.

Pada 2016, Randol dan rekannya menerbitkan sebuah karya yang menggambarkan partikel ideal yang hidup di kisi dan memutuskan apakah akan tinggal atau bergerak tergantung pada jumlah partikel yang diamati di sekitar mereka. Keputusan yang diambil adalah probabilistik - setiap kali partikel “melemparkan” kubus tertimbang untuk seleksi. Randall et al. Menunjukkan bahwa jika Anda menetapkan bobot cube dengan benar, Anda dapat menjamin terjadinya kawanan yang padat (seperti yang Schelling bisa buktikan bahwa jika Anda memberikan toleransi pada keanekaragaman pada penghuni area pada level yang tepat, maka segregasi akan muncul). Dengan menyesuaikan algoritme, mereka juga dapat memastikan bahwa segerombolan partikel akan bergerak dalam keadaan diperpanjang.

Keacakan algoritma membantu partikel-partikel dalam kerumunan untuk menghindari macet di segel lokal, ketika banyak subkelompok yang terisolasi terakumulasi bersama, tetapi seluruh kerumunan secara keseluruhan tidak padat. Keacakan memastikan bahwa ketika segel kecil muncul, beberapa unit masih memutuskan untuk pindah ke tempat lain, dan proses berlanjut sampai segel umum tercapai. Untuk menghindari anjing laut lokal, diperlukan sedikit keacakan; jauh lebih banyak diperlukan untuk transisi dari kondisi yang dikompresi secara global ke kondisi yang diperluas.

Ke dunia nyata

Untuk membuktikan bahwa partikel-partikel dalam dunia teoretis dapat, dengan melakukan algoritma sederhana, mencapai perilaku tertentu dalam suatu gerombolan adalah satu hal. Untuk mengimplementasikan algoritme dengan harga murah, rawan kegagalan, ponsel cerdas sungguhan, mengklik anggota badan dalam sebuah kotak - sama sekali berbeda.

"Rekan teori kami tahu cara memprogram hal-hal ini, tetapi kami masih di awal perjalanan dan tidak bisa mengatakan bahwa skema ini ditransfer secara langsung," kata Goldman.

Satu masalah adalah membuat smartphone bergerak bersama. Pada awalnya, ketika para peneliti menyertakan ponsel cerdas dalam ruang terbatas, grup ini secara tidak sengaja bergerak-gerak. Tetapi suatu kali, ketika fisikawan mengamati gerakan kacau ini, baterai mati di salah satu smartphone. Goldman dan rekannya memperhatikan bahwa gerombolan tiba-tiba mulai bergerak ke arah unit yang tetap. Para peneliti melaporkan penemuan yang tak terduga ini kepada para ahli teori, dan mereka memanfaatkan petunjuk ini. Pekerjaan ini mengarah pada pembuatan versi baru dari algoritma, memungkinkan segerombolan yang ideal untuk selalu bergerak ke arah tertentu.

Sedikit demi sedikit, eksperimen yang terjadi di komputer dan eksperimen fisik semakin dekat. Para peneliti berharap untuk akhirnya membuktikan secara teori bahwa algoritma dasar, yang diimplementasikan dengan metode umum dalam gerombolan besar robot murah kecil, dijamin akan mengarah pada perilaku gerombolan yang diinginkan.

"Kami ingin mencapai keadaan di mana kami tidak akan hanya mendeteksi fenomena ketika baterai mati," kata Daimad. "Kami ingin ini menjadi sesuatu dari kategori pencapaian yang disengaja."