BerandaComputers and TechnologyAbstraksi Status Pembelajaran untuk Perencanaan Horizon Panjang

Abstraksi Status Pembelajaran untuk Perencanaan Horizon Panjang

Banyak tugas yang kami lakukan secara teratur, seperti menjelajahi kota, memasak makan, atau memuat mesin pencuci piring, memerlukan perencanaan dalam waktu lama. Menyelesaikan tugas-tugas ini mungkin tampak sederhana bagi kita; Namun, penalaran terlalu lama cakrawala waktu tetap menjadi tantangan utama untuk Reinforcement Learning (RL) hari ini algoritma. Meskipun tidak dapat merencanakan dalam jangka panjang, algoritme RL yang dalam sangat unggul mempelajari kebijakan untuk tugas-tugas jangka pendek, seperti penggenggam robot, langsung dari piksel. Pada saat yang sama, metode perencanaan klasik seperti Algoritme Dijkstra dan penelusuran A $ ^ $ dapat direncanakan dalam jangka waktu yang lama, tetapi mereka membutuhkan representasi abstrak yang ditentukan dengan tangan atau tugas-spesifik dari lingkungan sebagai masukan.

Untuk mencapai yang terbaik dari kedua dunia, metode navigasi visual yang canggih telah menerapkan metode pencarian klasik untuk grafik yang dipelajari. Secara khusus, SPTM [2] dan SoRB [3] menggunakan buffer replay observasi sebagai node dalam grafik dan belajar fungsi jarak parametrik untuk menggambar tepi pada grafik. Metode ini memiliki telah berhasil diterapkan pada tugas navigasi simulasi cakrawala panjang terlalu menantang untuk dipecahkan oleh metode sebelumnya.

Meskipun demikian, metode ini masih terbatas karena sangat sensitif kesalahan dalam grafik yang dipelajari. Bahkan satu sisi yang salah berfungsi seperti lubang cacing dalam topologi grafik yang coba dieksploitasi oleh algoritma perencanaan metode yang ada yang menggabungkan pencarian grafik dan RL sangat rapuh. Untuk Misalnya, jika agen buatan menavigasi labirin berpikir bahwa dua pengamatan di kedua sisi tembok ada di dekatnya, rencananya akan melibatkan transisi itu bertabrakan ke dinding. Mengadopsi model sederhana yang mengasumsikan konstanta probabilitas $ p $ dari setiap sisi yang salah, kita melihat bahwa jumlah yang diharapkan dari tepi yang salah adalah $ p | E |=O (| V | ^ 2) $. Dengan kata lain, kesalahan dalam skala grafik secara kuadrat dengan jumlah node pada grafik .

Kami dapat melakukan jauh lebih baik jika kami dapat meminimalkan kesalahan pada grafik. Tapi bagaimana caranya? Grafik atas pengamatan di lingkungan simulasi dan dunia nyata bisa jadi sangat besar, sehingga sulit untuk bahkan mengidentifikasi tepi yang mana salah. Untuk meminimalkan kesalahan dalam grafik, kami menginginkan ketersebaran; kami ingin pertahankan set node minimal yang cukup untuk perencanaan. Jika kita punya cara untuk menggabungkan pengamatan serupa menjadi satu simpul dalam grafik, kita bisa mengurangi jumlah kesalahan dan meningkatkan akurasi rencana kami. Kunci tantangannya adalah untuk mengumpulkan pengamatan dengan cara yang menghormati duniawi kendala. Jika pengamatan serupa dalam penampilan tetapi sebenarnya jauh, maka mereka harus digabungkan ke dalam node yang berbeda.

Jadi bagaimana kita bisa membagi grafik kita sambil menjamin bahwa grafik tetap ada berguna untuk perencanaan? Wawasan utama kami adalah kriteria penggabungan baru yang disebut konsistensi dua arah . Konsistensi dua arah dapat dilihat sebagai generalisasi dari nilai tidak relevan dengan pengaturan yang dikondisikan oleh tujuan. Secara intuitif, konsistensi dua arah menggabungkan node (i) yang dapat dipertukarkan sebagai status awal dan (ii) yang dapat dipertukarkan sebagai status tujuan.

Untuk contoh konsistensi dua arah, perhatikan gambar di atas. Seharusnya selama prosedur penggabungan node kami, kami bertanya: dapatkah kami menggabungkan node dengan warna pink dan botol oranye menurut konsistensi dua arah? Pertama, kami mencatat bahwa bergerak dari botol biru ke botol merah muda membutuhkan pekerjaan yang kurang lebih sama seperti pindah dari botol biru ke botol oranye. Jadi simpul dengan warna merah muda dan botol oranye memenuhi kriteria (ii) karena dapat dipertukarkan sebagai tujuan negara bagian. Namun, meskipun mungkin untuk memulai dari botol merah muda dan pindah ke botol biru, jika kita mulai dari botol oranye, botol oranye akan jatuh ke lantai dan jatuh! Jadi bening dengan botol pink dan orange kriteria gagal (i) karena tidak dapat dipertukarkan sebagai status awal.

Dalam praktiknya, kami tidak dapat berharap untuk menemukan dua node yang bisa sempurna dipertukarkan. Sebagai gantinya, kami menggabungkan node yang dapat dipertukarkan hingga a parameter ambang $ tau $. Dengan meningkatkan $ tau $, kita bisa membuat hasilnya grafik sesingkat yang kami inginkan. Yang terpenting, kami membuktikan di koran bahwa penggabungan menurut konsistensi dua arah menjaga kualitas grafik hingga terjadi kesalahan istilah yang hanya berskala linier dengan ambang penggabungan $ tau $.

Motivasi kami untuk ketersebaran, yang dibahas di atas, adalah ketangguhan: kami berharap lebih kecil grafik memiliki lebih sedikit kesalahan. Lebih jauh, teorema utama kita mengatakan bahwa kita bisa menggabungkan node sesuai dengan konsistensi dua arah sambil mempertahankan grafik kualitas. Namun, secara eksperimental, apakah grafik renggang yang dihasilkan lebih kuat?

Untuk menguji ketahanan Memori Grafis Jarang terhadap kesalahan dalam jarak yang dipelajari metrik, kami menipiskan dinding di labirin PointEnv dari [3]. Sedangkan PointEnv adalah a lingkungan sederhana dengan pengamatan koordinat $ (x, y) $, penipisan dinding tantangan utama untuk fungsi jarak parametrik; setiap kesalahan dalam belajar fungsi jarak akan menyebabkan tepi rusak di dinding yang menghancurkan kelayakan rencana. Untuk alasan ini, cukup menipiskan dinding labirin saja sudah cukup untuk melanggar state-of-the-art [3] sebelumnya yang menghasilkan tingkat keberhasilan 0%.

Bagaimana tarif Sparse Graphical Memory? Dengan lebih sedikit tepi, itu menjadi patuh untuk melakukan pembersihan yang diawasi sendiri: agen dapat melangkah melalui lingkungan untuk mendeteksi dan menghapus tepi yang salah dari grafiknya. Gambar di bawah ini menggambarkan hasil dari proses ini. Sedangkan grafik yang padat ditunjukkan dengan warna merah banyak tepi yang salah, ketersebaran, dan pembersihan yang diawasi sendiri, ditampilkan dalam warna hijau, mengatasi kesalahan dalam metrik jarak yang dipelajari, yang mengarah ke tingkat keberhasilan 100%.

Kami melihat tren serupa dalam eksperimen dengan input visual. Di kedua ViZDoom [4] dan SafetyGym [5] – tugas navigasi labirin yang memerlukan perencanaan dari mentah images – Sparse Graphical Memory secara konsisten meningkatkan keberhasilan baseline metode termasuk SoRB [3] dan SPTM [2].

Selain mengandung lebih sedikit kesalahan, Sparse Graphical Memory juga menghasilkan rencana yang lebih optimal. Pada tugas navigasi labirin ViZDoom [4], kami menemukan SGM itu memerlukan langkah yang jauh lebih sedikit untuk mencapai tujuan akhir melalui kemudahan, media, dan tugas labirin sulit, yang berarti bahwa agen mengikuti jalur yang lebih pendek ke final tujuan.

Secara keseluruhan, kami menemukan bahwa agregasi status dengan konsistensi dua arah menghasilkan rencana yang secara substansial lebih kuat dibandingkan dengan yang tercanggih sebelumnya. Sementara menjanjikan, banyak pertanyaan terbuka dan tantangan tetap untuk menggabungkan klasik perencanaan dengan kontrol berbasis pembelajaran. Beberapa pertanyaan yang kami pikirkan about are – bagaimana kita bisa memperluas metode ini di luar navigasi ke manipulasi domain? Karena dunia ini tidak statis, bagaimana kita harus membuat grafik lebih dari perubahan lingkungan? Bagaimana konsistensi dua arah dapat digunakan di luar cakupan metode perencanaan berbasis grafis? Kami sangat senang dengan arah masa depan ini dan berharap temuan teoretis dan eksperimental kami terbukti bermanfaat bagi orang lain peneliti menyelidiki kontrol atas cakrawala waktu yang diperpanjang.

Referensi

  1. Emmons *, Jain *, Laskin dkk. Memori Grafis Jarang untuk Perencanaan Kuat . NeurIPS 2020.
  2. Savinov dkk. Memori Topologi Semi-parametrik untuk Navigasi . ICLR 2019.
  3. Eysenbach dkk. Pencarian di Replay Buffer: Bridging Planning and Reinforcement Learning . NeurIPS 2020.
  4. Wydmuch et al. Kompetisi ViZDoom: Bermain Doom dari Piksel . Transaksi IEEE pada Game, 2018.
  5. Ray et al. Benchmarking Eksplorasi Aman dalam Pembelajaran Penguatan Mendalam . Pracetak, 2019.

Read More

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments