Bacalah tentang jenis kompetisi itu dan bagaimana kami berhasil memenangkannya (dan lebih dari 2000 solusi dari 51 negara dikirim ke kontes) di bawah pemotongan.
tim kita
Tim JBR_HSE terdiri dari lima anggota: Konstantin Makhnev (belajar di tahun ke-4 program sarjana " Matematika Terapan dan Ilmu Komputer ") Oleg Svidchenko dan Vladimir Egorov (keduanya belajar di gelar master " Pemrograman dan Analisis Data "), mahasiswa PhD Dmitry Ivanov dan kepala Pusat Analisis data dan pembelajaran mesin NRU HSE - St. Petersburg Alexey Shpilman. Semua orang kecuali Konstantin juga bekerja di lab Agent Systems and Reinforcement Learning di JetBrains Research - itulah nama tim tersebut. Saat mengikuti kompetisi, Kostya berlatih di laboratorium yang sama.
NeurIPS 2020: Flatland - apa itu?
Flatland adalah kompetisi yang berlangsung dari 10 Juli hingga 15 November berdasarkan platform AIcrowd dan didukung oleh konferensi internasional terkenal NeurIPS . Tujuan dari kompetisi ini adalah untuk mengembangkan algoritma yang dapat mengatur lalu lintas kereta api sebaik mungkin. Batasan penting adalah bahwa keputusan harus dibuat dalam waktu terbatas (5 detik per satu langkah simulator), yang tidak memungkinkan untuk hanya memilih tindakan yang optimal.
NeurIPS 2020: Flatland memiliki dua arah: general dan Reinforcement Learning (RL). Area pertama terbuka untuk keputusan apa pun, dan yang kedua hanya untuk mereka yang menggunakan pembelajaran penguatan.
Penyelenggara memberi peserta simulator Flatland, yang merupakan kisi dua dimensi, di mana setiap sel memiliki jenisnya sendiri: jalan, belokan, pertigaan, atau medan yang tidak dapat dilalui. Setiap kereta menempati tepat satu sel di grid dan memiliki arah pergerakannya saat ini. Simulasi berlangsung selangkah demi selangkah, di setiap langkah untuk setiap kereta Anda perlu menentukan tindakan apa yang harus dilakukan: berhenti, berjalan di jalur paling kiri, atau berjalan di jalur paling kanan. Karena dalam implementasi saat ini persimpangan lengkap tidak disediakan, yaitu tidak terjadi anda bisa maju, kanan dan kiri pada saat bersamaan, maka aksi “maju” juga tidak diperlukan. Dalam kasus ketika tidak ada belokan, tindakan kedua dan ketiga setara. Kereta bisa bertabrakan satu sama lain - ternyata jalan buntu.Tujuan dari kompetisi ini adalah agar semua kereta mencapai tujuan mereka secepat mungkin. Keputusan dinilai dari jumlah waktu yang dibutuhkan kereta untuk mencapai tujuan. Jika kereta belum mencapai, waktunya sama dengan waktu simulasi maksimum.
Solusi: bagaimana agen akan berinteraksi dengan simulator
Sudah ada cukup banyak posting di Habré tentang pembelajaran penguatan, jadi kami tidak akan membahas konsep dasar secara mendetail. Anggap saja dalam kasus Flatland, simulasi rel kereta api berperan sebagai lingkungan, dan kereta bertindak sebagai agennya. Penting untuk dicatat bahwa karena banyak kereta yang terlibat dalam simulasi, lingkungan ini bersifat multi-agen.
Saat memecahkan masalah, kami secara signifikan mengubah proses interaksi antara agen dan simulator, yang memungkinkan kami meningkatkan efisiensi algoritme kami secara signifikan. Secara umum, modifikasi seperti itu seringkali sangat mempengaruhi hasil, tetapi membutuhkan pengetahuan khusus untuk tugas tertentu.
Salah satu perubahan paling signifikan adalah kami memutuskan untuk tidak memberikan kebebasan bertindak kepada agen saat dia tidak berada di dekat persimpangan. Dengan demikian, seorang agen dapat mengambil keputusan hanya ketika di depan sebuah pertigaan atau di sebuah pertigaan, dan dalam kasus lain selalu bergerak maju sepanjang satu-satunya jalur yang memungkinkan. Ini sangat mempersingkat durasi episode, dan karenanya membuat tugas menjadi lebih mudah. Kami juga memutuskan bahwa agen akan mengakhiri episodenya baik ketika dia mencapai tujuan, atau ketika dia menemui jalan buntu dan tidak dapat bergerak (dalam simulator, dalam kasus seperti itu, episode berlanjut). Kemudian kami memutuskan bahwa episode tidak boleh segera dimulai untuk semua orang, kami akan memberi tahu Anda lebih banyak tentang ini di bawah.
Pengamatan untuk agen terdiri dari dua bagian: fitur yang terikat ke bagian tertentu dari jalur, dan fitur yang tidak terikat ke bagian jalur tertentu. Di sini, sebagian jalan berarti bagian jalan yang menghubungkan dua pertigaan.
Bagian pertama pengamatan dapat direpresentasikan sebagai pohon, yang puncaknya terdapat garpu, dan ujungnya adalah jalan di antara keduanya. Ke setiap tepi dan simpul yang dituju, kami mengaitkan vektor fitur yang dihitung untuk bagian jalur tertentu (misalnya, panjang jalur, jarak dari ujung tepi ke tujuan, dll.). Kami memperbaiki kedalaman pohon, sehingga membatasi jumlah vektor fitur yang diperoleh dari bagian pertama pengamatan. Di bawah ini adalah contoh bagaimana bagian observasi ini dibangun. Garis berwarna mewakili ruas jalan yang merupakan tepian pada pohon.
Bagian kedua dari pengamatan mencakup tanda-tanda seperti jarak minimum ke tujuan, apakah agen berada di persimpangan atau di depannya, agen mengalami kebuntuan, dll. Perlu juga dicatat bahwa setiap agen di awal episode diberi pengenal (nomor acak dari 0 banding 1), yang tetap bersamanya selama sisa episode dan memungkinkannya untuk bernegosiasi lebih baik dengan agen lainnya. Ada tanda-tanda tergantung pada pengidentifikasi agen di kedua bagian pengamatan.
Tetap hanya untuk menentukan fungsi penghargaan agen. Setelah beberapa pilihan, kami menetapkan yang agak sederhana: $ 0,01 \ cdot \ Delta d - 5 \ cdot \ text {is \ _deadlocked} + 10 \ cdot \ text {is \ _succeed} $, yaitu Hadiah tersebut mencerminkan seberapa jauh jarak $ d $ ke tujuan telah berubah sejak keputusan dibuat, dengan hadiah tambahan jika episode tersebut berhasil diselesaikan dan penalti jika menemui jalan buntu.
Algoritma PPO
Ada banyak algoritma pembelajaran penguatan yang dirancang untuk memecahkan masalah multi-agen. Namun, kami memutuskan untuk menggunakan algoritma PPO - Pengoptimalan Kebijakan Proksimal sebagai algoritma dasar , karena kodenya dapat digunakan kembali untuk mengimplementasikan algoritma RL multiagen (misalnya, COMA). Namun, kemudian, ternyata PPO (dengan beberapa modifikasi) sendiri menyelesaikan masalah dengan baik, tetapi metode multi-agen dilatih jauh lebih buruk, jadi PPO tetap menjadi bagian utama dari solusi akhir kami.
Algoritma PPO klasik terdiri dari dua bagian: aktor dan kritikus. Kritikus mendekati nilai-fungsi, dan aktor mengajarkan kebijakan acak $ \ pi_ \ theta (a | s) $ yang memaksimalkan nilai yang diharapkan dari total hadiah.
Salah satu modifikasi penting yang kami lakukan adalah penambahan modul ke arsitektur aktor yang memungkinkan agen untuk berkomunikasi dengan agen terdekat. Proses komunikasi dibangun cukup sederhana: agen secara bersamaan menghasilkan pesan dan mengirimnya ke semua kereta di sebelahnya, dan kemudian, setelah menerima pesan dari tetangga, menggabungkannya menjadi satu pesan dengan rata-rata tertimbang. Mekanisme perhatian-diri sederhana digunakan untuk menentukan bobot pesan yang akan dirata-ratakan. Dengan struktur proses komunikasi yang demikian, tidak perlu mengubah proses pembelajaran, karena itu cukup untuk membiarkan gradien melewati pesan selama backpropagation kesalahan.
Kami memutuskan untuk melatih PPO dengan peta kecil dan sedikit agen, dengan asumsi karena agen hanya mengamati apa yang ada di sebelahnya, setelah pelatihan dia akan bekerja dengan baik di lingkungan yang lebih besar.
Bagaimana Anda memutuskan kereta mana yang akan dimulai kapan?
Setelah mencoba menerapkan algoritme PPO, kami dengan cepat sampai pada kesimpulan bahwa sebagian besar kebuntuan terjadi justru karena kereta api mulai bergerak pada waktu yang sama dan saling mengganggu. Kami memecahkan masalah ini dengan cara berikut: kami mulai menjalankan hanya beberapa agen pada waktu yang bersamaan. Ketika salah satu agen menyelesaikan episodenya, agen lainnya diizinkan untuk mulai bergerak. Dalam pendekatan ini, penting untuk memahami dalam urutan apa kereta harus diluncurkan.
Pendekatan pertama yang kami coba adalah meluncurkan agen yang paling dekat dengan tujuan mereka. Saat digunakan di lingkungan kecil - jalan pendek dan sedikit agen - performanya cukup baik, tetapi untuk lingkungan besar performanya jauh lebih buruk. Oleh karena itu, kami memutuskan untuk menggunakan pendekatan ini hanya selama pelatihan agen, dan untuk aplikasi (yaitu, mengirimkan ke sistem pengujian) kami menggunakan algoritme yang berbeda. Ide dari algoritma ini adalah untuk melatih pengklasifikasi yang akan menentukan untuk setiap agen yang belum mulai bergerak apakah dia akan mencapai akhir atau tidak. Kemudian, jika probabilitas berhasil mencapai tujuan cukup besar, maka agen mulai bergerak, jika tidak, menunggu hingga probabilitasnya mencukupi.
Hasil kompetisi
Hasilnya, solusi kami menempati posisi pertama di track RL dan kedelapan secara keseluruhan. Artinya pendekatan non-RL masih lebih baik pada saat ini, namun hal ini menunjukkan bahwa pembelajaran penguatan memiliki potensi. Ada beberapa kelemahan dan masalah yang belum terselesaikan dalam pendekatan kami (misalnya, masalah serius dengan skalabilitas hingga lingkungan yang luas), jadi kami memiliki sesuatu untuk dikerjakan. Saat ini kami bersama dengan penyelenggara kompetisi sedang mempersiapkan artikel untuk dikirimkan ke buku kompetisi NeurIPS 2020.