Melampaui A*: Perencanaan yang Lebih Baik dengan Memanfaatkan Transformer

Beyond A*: Perencanaan yang Lebih Baik dengan Memanfaatkan Transformer

• Model transformer telah mencapai kemajuan besar di berbagai bidang aplikasi, tetapi masih tertinggal dari metode perencanaan berbasis simbol tradisional dalam menyelesaikan tugas pengambilan keputusan yang kompleks.
• Para peneliti mengusulkan cara melatih transformer untuk menyelesaikan tugas perencanaan yang kompleks, dan mengembangkan model bernama Searchformer yang dapat menyelesaikan puzzle Sokoban yang belum pernah dilihat sebelumnya secara optimal dalam 93,7% waktu, sambil menggunakan hingga 26,8% lebih sedikit langkah pencarian dibandingkan pencarian A* konvensional.
• Searchformer adalah model transformer encoder-decoder yang dilatih untuk memprediksi perilaku pencarian A*, lalu disempurnakan melalui expert iteration sehingga dapat menghasilkan rencana optimal dengan lebih sedikit langkah pencarian daripada pencarian A*.

Metode Pelatihan dan Kinerja

• Dalam metode pelatihan, perilaku pencarian A* direpresentasikan sebagai urutan token yang menunjukkan kapan status ditambahkan ke dan dihapus dari pohon pencarian dalam perencanaan simbolik.
• Dalam studi ablasi untuk penelusuran labirin, Searchformer jauh melampaui model dasar yang secara langsung memprediksi rencana optimal, dengan ukuran model 5–10 kali lebih kecil dan dataset pelatihan 10 kali lebih kecil.
• Para peneliti menunjukkan bahwa Searchformer efektif untuk tugas pengambilan keputusan yang lebih besar dan lebih kompleks seperti Sokoban, baik dalam meningkatkan proporsi tugas yang berhasil diselesaikan maupun memperpendek perilaku pencarian.

Opini GN⁺

• Riset ini menunjukkan kemungkinan baru pemanfaatan model transformer di bidang kecerdasan buatan. Dengan menawarkan pendekatan yang lebih efisien daripada metode berbasis simbol yang ada untuk menyelesaikan tugas pengambilan keputusan yang kompleks, ini merupakan kemajuan penting yang memperluas cakupan penerapan AI.
• Model Searchformer menunjukkan kemampuan pemecahan masalah yang lebih cepat dan efisien dengan menggunakan sumber daya yang lebih sedikit. Ini dapat menjadi keunggulan besar khususnya saat menerapkan AI di lingkungan dengan sumber daya terbatas.
• Studi ini menunjukkan bahwa kemajuan teknologi AI tidak harus bergantung hanya pada lebih banyak data dan model yang lebih besar, tetapi juga dapat dicapai melalui metodologi yang lebih cerdas dan perbaikan algoritme. Ini adalah pendekatan yang sangat menarik dan bermanfaat dari sisi keberlanjutan serta efisiensi riset AI.

[GN⁺]

Komentar Hacker News

• Ada penelitian menarik tentang penggunaan transformer untuk perencanaan gerak robot. Menggerakkan lengan robot dari satu titik ke titik lain tanpa menabrak objek adalah masalah yang sangat sulit, karena masalah ini berdimensi tinggi dan kontinu. Metode perencanaan sebelumnya membutuhkan komputasi besar dan hasilnya tidak terlalu baik. Ini adalah salah satu alasan gerakan robot terlihat 'tidak alami' dan robot tidak mampu melakukan banyak tugas yang kita inginkan dengan baik. Pendekatan ini tampak kompetitif dengan metode perencanaan lain, serta menawarkan perencanaan jalur optimal yang lebih cepat.
• Penasaran apakah mereka mencoba algoritma J* yang dimodifikasi, yaitu versi optimalisasi dari algoritma A* untuk graph game/pencarian jalur, sebelum memulai jalur penelitian ini. Bagi yang tertarik, ada informasi tentang "Game AI Pro 2".
• Perencanaan sebenarnya sudah ditangani dengan baik oleh teknik yang ada seperti pencarian graf, SAT-solver, OR, Prolog, dan sebagainya. Masalahnya biasanya adalah optimisasi di antara banyak alternatif yang layak dijalankan, dan saya ragu transformer cocok untuk melakukan itu. Peran teknologi LLM tampaknya lebih dekat ke mengubah deskripsi bahasa alami menjadi program yang dapat dieksekusi, dan Prolog pada akhirnya dirancang untuk NLP klasik, jadi ini sangat dekat.
• Penerjemahan mesin dulu melibatkan penguraian tata bahasa yang kompleks dan pencarian, tetapi sekarang transformer digunakan untuk MT, dengan penguraian yang jauh lebih sederhana dan hampir tidak memerlukan pencarian. Mungkin kita bisa mencapai 'awal yang lengkap' untuk mencari blok saraf baru yang lebih baik daripada transformer dan Mamba, dengan mempelajari heuristik untuk neural architecture search (NAS) menggunakan model prediksi terbaik saat ini.
• Frasa "26.8% lebih sedikit langkah pencarian dibanding pencarian A* standar" menunjukkan kinerja yang sedikit lebih baik daripada A*, tetapi di Sokoban masih belum mencapai state of the art (SOTA). Saya bertanya-tanya apa yang mengesankan dari makalah ini, dan mengapa ini sampai muncul di Hacker News.
• Jika transformer bisa menyusun rencana, AGI (kecerdasan umum buatan) mungkin hanya membutuhkan pendidikan yang lebih baik.
• Untuk pembelajar auditori, tersedia format audiobook yang merangkum makalah ini.
• Makalah ini mengingatkan saya pada makalah Neural Network Diffusion yang kemarin ada di halaman depan HN. Dalam makalah sebelumnya, mereka melatih model yang melewati langkah SGD, dan dalam makalah ini mereka melewati langkah pencarian A*. Di sisi lain, pemilihan heuristik A* untuk Sokoban kurang baik. Saat membaca makalah ini, saya bermain Sokoban selama 20 menit dan merasa heuristik pencariannya sangat lemah, karena untuk maju sering kali harus menjauhkan kotak dari keadaan tujuan.
• Penasaran apakah ada orang yang memelihara daftar algoritma klasik atau masalah NP-complete yang kini bisa diselesaikan lebih baik dengan deep learning.
• Saya sangat optimistis tentang penggunaan heuristik yang dipelajari dalam algoritma diskret seperti A* atau pencarian Focal. Di sebagian besar library optimisasi diskret modern, seperti CPLEX, yang menjelaskan kinerja adalah heuristik dan tuning. Saya kurang paham soal penggunaan pendekatan end-to-end learning untuk menggantikan rutinitas pencarian optimal yang sudah dipahami dengan baik, tetapi mungkin itu kekhawatiran yang berlebihan. Saya rasa para penulis melewatkan peluang itu.