Apa perbedaan antara algoritma pathfinding mutakhir untuk mengubah grafik (D *, D * -Lite, LPA *, dll) berbeda?

Banyak algoritma pencarian jalur telah dikembangkan dalam beberapa tahun terakhir yang dapat menghitung jalur terbaik dalam menanggapi perubahan grafik jauh lebih cepat daripada A * - apa sajakah itu, dan bagaimana perbedaannya? Apakah mereka untuk situasi yang berbeda, atau melakukan beberapa yang lain usang?

Inilah yang saya dapat temukan sejauh ini:

• D * (1994)
• Berfokus D * (1995)
• DynamicSWSF-FP (1996)
• LPA (1997)
• LPA * / Incremental A * (2001)
• D * Lite (2002)
• SetA * (2002)
• HPA * (2004)
• Anytime D * (2005)
• PRA * (2005)
• Field D * (2007)
• Theta * (2007)
• HAA * (2008)
• GAA * (2008)
• BELAJAR (2009)
• BDDD * (2009 - Saya tidak dapat mengakses makalah ini: |)
• Incremental Phi * (2009)
• GFRA * (2010)
• MTD * -Lite (2010)
• Tree-AA * (2011)

Saya tidak yakin yang mana dari ini berlaku untuk masalah spesifik saya - saya akan membaca semuanya jika perlu, tetapi itu akan menghemat banyak waktu jika seseorang dapat menulis ringkasan.

Masalah spesifik saya: Saya punya kisi dengan permulaan, akhir, dan beberapa dinding. Saat ini saya menggunakan A * untuk menemukan jalur terbaik dari awal hingga akhir.

Pengguna kemudian akan memindahkan satu dinding , dan saya harus menghitung ulang seluruh jalan lagi. Langkah "pindah-dinding / menghitung ulang-jalan" terjadi berkali-kali berturut-turut, jadi saya mencari algoritma yang akan dapat dengan cepat menghitung ulang jalur terbaik tanpa harus menjalankan iterasi penuh A *.

Meskipun, saya tidak perlu mencari perubahan ke A * - itu bisa menjadi algoritma yang sepenuhnya terpisah.

Jadi, saya membaca sekilas kertas-kertas itu, dan inilah yang saya kilaukan. Jika ada orang yang lebih berpengetahuan dalam masalah ini, perbaiki saya jika saya salah (atau tambahkan jawaban Anda sendiri, dan sebagai gantinya saya akan menerimanya!) .

Tautan ke setiap makalah dapat ditemukan di pos-pertanyaan di atas.

• Perhitungan ulang sederhana
  • D * (alias Dynamic A * ) (1994): Pada awalnya, D * berjalan sangat mirip dengan A *, menemukan jalur terbaik dari awal hingga selesai dengan sangat cepat. Namun, ketika unit bergerak dari awal ke akhir, jika grafik berubah, D * dapat dengan cepat menghitung ulang jalur terbaik dari posisi unit itu ke selesai, jauh lebih cepat daripada hanya menjalankan A * dari posisi unit itu lagi. D *, bagaimanapun, memiliki reputasi sebagai sangat kompleks, dan telah sepenuhnya ditinggalkan oleh D * -Lite yang lebih sederhana.
  • Focused D * (1995): Peningkatan ke D * untuk membuatnya lebih cepat / "lebih realtime." Saya tidak dapat menemukan perbandingan untuk D * -Lite, tetapi mengingat bahwa ini lebih tua dan D * -Lite lebih banyak dibicarakan, saya berasumsi bahwa D * -Lite entah bagaimana lebih baik.
  • DynamicSWSF-FP (1996): Menyimpan jarak dari setiap node ke node selesai. Memiliki pengaturan awal yang besar untuk menghitung semua jarak. Setelah perubahan pada grafik, itu hanya dapat memperbarui node yang jaraknya telah berubah. Tidak terkait dengan A * dan D *. Berguna ketika Anda ingin menemukan jarak dari beberapa node ke finish setelah setiap perubahan; jika tidak, LPA * atau D * -Lite biasanya lebih bermanfaat.
  • LPA * / Incremental A * (2001): LPA * (Lifelong Planning A *) , juga dikenal sebagai Incremental A * (dan kadang-kadang, membingungkan, sebagai "LPA," meskipun tidak ada hubungannya dengan algoritma lain bernama LPA) adalah kombinasi DynamicSWSF-FP dan A *. Pada putaran pertama, persis sama dengan A *. Namun, setelah perubahan kecil pada grafik, pencarian selanjutnya dari pasangan awal / akhir yang sama dapat menggunakan informasi dari proses sebelumnya untuk secara drastis mengurangi jumlah node yang perlu diperiksa, dibandingkan dengan A *. Ini persis masalah saya, jadi sepertinya LPA * akan cocok untuk saya. LPA * berbeda dari D * karena selalu menemukan jalur terbaik dari awal yang sama ke akhir yang sama; itu tidak digunakan ketika titik awal bergerak(seperti unit yang bergerak di sepanjang jalur terbaik awal) . Namun...
  • D * -Lite (2002): Algoritma ini menggunakan LPA * untuk meniru D *; yaitu, ia menggunakan LPA * untuk menemukan jalur terbaik baru untuk suatu unit saat bergerak di sepanjang jalur terbaik awal dan grafik berubah. D * -Lite dianggap jauh lebih sederhana daripada D *, dan karena selalu berjalan setidaknya secepat D *, D * telah sepenuhnya usang. Jadi, tidak pernah ada alasan untuk menggunakan D *; gunakan D * -Lite sebagai gantinya.
• Gerakan sudut manapun
  • Field D * (2007): Varian D * -Lite yang tidak membatasi pergerakan ke grid; yaitu jalur terbaik dapat membuat unit bergerak sepanjang sudut, tidak hanya 45- (atau 90-) derajat antara titik-titik grid. Digunakan oleh NASA untuk menemukan jalan bagi penemu Mars.
  • Theta * (2007): Varian A * yang memberikan jalur yang lebih baik (lebih pendek) daripada Field D *. Namun, karena didasarkan pada A * daripada D * -Lite, itu tidak memiliki kemampuan perencanaan ulang yang cepat yang dilakukan Field D *. Lihat juga .
  • Incremental Phi * (2009): Yang terbaik dari kedua dunia. Versi Theta * yang bersifat inkremental (alias memperbolehkan replanning cepat)
• Memindahkan Poin Target
  • GAA * (2008): GAA * (Generalized Adaptive A *) adalah varian A * yang menangani titik target yang bergerak. Ini adalah generalisasi dari algoritma yang bahkan lebih awal yang disebut "Moving Target Adaptive A *"
  • GRFA * (2010): GFRA * (Generalized Fringe-Retrieving A *) muncul (?) Menjadi generalisasi GAA * ke grafik arbitrer (mis. Tidak terbatas pada 2D) menggunakan teknik dari algoritma lain yang disebut FRA *.
  • MTD * -Lite (2010): MTD * -Lite (Moving Target D * -Lite) adalah "perpanjangan dari D * Lite yang menggunakan prinsip di balik Generalized Fringe-Retrieving A *" untuk melakukan pencarian target-gerakan yang cepat.
  • Tree-AA * (2011): (???) Tampak sebagai algoritma untuk mencari medan yang tidak diketahui, tetapi didasarkan pada Adaptive A *, seperti semua algoritma lainnya di bagian ini, jadi saya taruh di sini. Tidak yakin bagaimana perbandingannya dengan yang lain di bagian ini.
• Cepat / Kurang optimal
  • Anytime D * (2005): Ini adalah varian "Anytime" dari D * -Lite, dilakukan dengan menggabungkan D * -Lite dengan algoritma yang disebut Anytime Repairing A * . Algoritme "Kapan saja" adalah algoritma yang dapat berjalan di bawah batasan waktu apa pun - ia akan menemukan jalur yang sangat suboptimal dengan sangat cepat untuk memulai, kemudian memperbaiki jalur itu semakin banyak waktu diberikan.
  • HPA * (2004): HPA * (Hierarchical Path-Finding A *) adalah untuk pencarian-jalan sejumlah besar unit pada grafik besar, seperti dalam video game RTS (strategi waktu sebenarnya) . Mereka semua akan memiliki lokasi awal yang berbeda, dan lokasi akhir yang berpotensi berbeda. HPA * memecah grafik menjadi hierarki untuk menemukan jalur "hampir-optimal" dengan cepat untuk semua unit ini jauh lebih cepat daripada menjalankan A * pada masing-masing unit secara individual. Lihat juga
  • PRA * (2005): Dari apa yang saya pahami, PRA * (Partial Refinement A *) memecahkan masalah yang sama dengan HPA *, tetapi dengan cara yang berbeda. Keduanya memiliki "karakteristik kinerja yang serupa."
  • HAA * (2008): HAA * (Hierarchical Annotated A *) adalah generalisasi HPA * yang memungkinkan untuk melintasi terbatas beberapa unit di beberapa medan (mis. Jalur kecil yang dapat dilalui beberapa unit tetapi yang lebih besar tidak dapat dilalui; atau lubang yang hanya bisa dilintasi unit terbang; dll.)
• Lainnya / Tidak Diketahui
  • LPA (1997): LPA (Loop-free path-finding algorithm) tampaknya merupakan algoritma-perutean yang hanya sedikit terkait dengan masalah yang diselesaikan oleh algoritma lain di sini. Saya hanya menyebutkannya karena makalah ini membingungkan (dan salah) direferensikan di beberapa tempat di Internet sebagai makalah yang memperkenalkan LPA *, padahal tidak.
  • LEARCH (2009): LEARCH adalah kombinasi dari algoritma pembelajaran mesin, yang digunakan untuk mengajari robot cara menemukan jalur yang hampir optimal secara mandiri. Penulis menyarankan untuk mengkombinasikan LEARCH dengan Field D * untuk hasil yang lebih baik.
  • BDDD * (2009): ??? Saya tidak dapat mengakses kertas.
  • SetA * (2002): ??? Ini, rupanya, varian A * yang mencari model "binary decision diagram" (BDD) dari grafik? Mereka mengklaim bahwa itu menjalankan "beberapa urutan besarnya lebih cepat dari A *" dalam beberapa kasus. Namun, jika saya mengerti dengan benar, kasus-kasus tersebut adalah ketika setiap node pada grafik memiliki banyak sisi?

Mengingat semua ini, tampaknya LPA * paling cocok untuk masalah saya.

Ada peringatan besar ketika menggunakan D *, D * -Lite, atau salah satu algoritma tambahan dalam kategori ini (dan perlu dicatat bahwa peringatan ini jarang disebutkan dalam literatur). Jenis algoritma ini menggunakan pencarian terbalik. Yaitu, mereka menghitung biaya keluar dari simpul tujuan, seperti riak yang menyebar keluar. Ketika biaya tepi berubah (misalnya Anda menambah atau menghapus dinding dalam contoh Anda) mereka semua memiliki berbagai strategi yang efisien untuk hanya memperbarui subset dari node yang dieksplorasi (alias 'dikunjungi') yang dipengaruhi oleh perubahan.

Peringatan besar adalah bahwa lokasi perubahan ini sehubungan dengan lokasi tujuan membuat perbedaan besar pada efisiensi algoritma. Saya menunjukkan dalam berbagai makalah dan tesis saya bahwa sangat mungkin untuk kinerja kasus terburuk dari salah satu algoritma inkremental ini menjadi lebih buruk daripada membuang semua informasi dan mulai lagi dengan sesuatu yang non-incremental seperti A * biasa.

Ketika informasi biaya yang diubah dekat dengan batas depan pencarian yang diperluas (wilayah 'yang dikunjungi'), beberapa jalur harus diubah, dan pembaruan tambahannya cepat. Contoh terkait adalah robot seluler dengan sensor yang melekat pada tubuhnya. Sensor hanya melihat dunia di dekat robot, dan karenanya perubahan ada di wilayah ini. Wilayah ini adalah titik awal pencarian, bukan tujuan, sehingga semuanya berjalan dengan baik dan algoritme sangat efisien untuk memperbarui jalur optimal untuk memperbaiki perubahan.

Ketika informasi biaya yang diubah dekat dengan tujuan pencarian (atau skenario Anda melihat lokasi perubahan tujuan, bukan hanya permulaan), algoritma ini mengalami pelambatan bencana. Dalam skenario ini, hampir semua informasi yang disimpan perlu diperbarui, karena wilayah yang diubah sangat dekat dengan tujuan sehingga hampir semua jalur pra-perhitungan melewati perubahan dan harus dievaluasi kembali. Karena overhead menyimpan informasi tambahan dan perhitungan untuk melakukan pembaruan tambahan, evaluasi ulang pada skala ini lebih lambat daripada awal yang baru.

Karena skenario contoh Anda muncul untuk membiarkan pengguna memindahkan setiap dinding yang mereka inginkan, Anda akan mengalami masalah ini jika Anda menggunakan D *, D * -Lite, LPA *, dll. Kinerja waktu algoritma Anda akan bervariasi, tergantung pada pengguna memasukkan. Secara umum, "ini adalah hal yang buruk" ...

Sebagai contoh, kelompok Alonzo Kelly di CMU memiliki program fantastis bernama PerceptOR yang mencoba menggabungkan robot darat dengan robot udara, yang semuanya berbagi informasi persepsi secara real-time. Ketika mereka mencoba menggunakan helikopter untuk memberikan pembaruan biaya waktu-nyata ke sistem perencanaan kendaraan darat, mereka menemukan masalah ini karena helikopter dapat terbang di depan kendaraan darat, melihat perubahan biaya yang lebih dekat ke tujuan, dan dengan demikian memperlambat algoritma mereka. Apakah mereka membahas pengamatan yang menarik ini? Tidak. Pada akhirnya, yang terbaik yang mereka kelola adalah memiliki helikopter yang terbang tepat di atas kendaraan darat - menjadikannya tiang sensor termahal di dunia. Tentu, saya picik. Tapi itu masalah besar yang tidak ingin dibicarakan orang - dan mereka harus,

Hanya ada beberapa makalah yang membahas hal ini, kebanyakan oleh saya. Dari makalah yang ditulis oleh penulis atau siswa dari penulis makalah asli yang tercantum dalam pertanyaan ini, saya hanya bisa memikirkan satu yang benar-benar menyebutkan masalah ini. Likhachev dan Ferguson menyarankan untuk mencoba memperkirakan skala pembaruan yang diperlukan, dan menyiram informasi yang tersimpan jika pembaruan tambahan diperkirakan akan memakan waktu lebih lama daripada awal yang baru. Ini adalah solusi yang cukup masuk akal, tetapi ada juga yang lain. PhD saya menggeneralisasi pendekatan yang serupa di berbagai masalah komputasi dan semakin melampaui ruang lingkup pertanyaan ini, namun Anda dapat menemukan referensi yang bermanfaat karena memiliki tinjauan menyeluruh tentang sebagian besar algoritma ini dan banyak lagi. Lihat http://db.acfr.usyd.edu.au/download.php/Allen2011_Thesis.pdf?id=2364 untuk detail.

Gagasan utamanya adalah menggunakan algoritme inkremental, yang dapat memanfaatkan perhitungan sebelumnya ketika rute awal yang dihitung diblokir. Ini sering diselidiki dalam konteks robot, navigasi, dan perencanaan.

Koenig & Likkachev, Perencanaan ulang cepat untuk Navigasi di Medan yang Tidak Diketahui, Transaksi IEEE pada Robotika, Vol. 21, No. 3, Juni 2005 memperkenalkan D * Lite. Tampaknya aman untuk mengatakan bahwa D * sudah usang dalam arti bahwa D * Lite selalu secepat D *. Selain itu, D * rumit, sulit dipahami, dianalisis, dan diperluas. Gambar 9 memberikan pseudocode untuk D * Lite, dan Tabel 1 menunjukkan hasil eksperimen dengan D * Lite dibandingkan dengan BFS, Backward A *, Forward A *, DynamicSWSF-P dan D *.

Saya tidak tahu algoritma terbaru yang Anda daftarkan (Kapan saja D *, Bidang D *, PELAJARI). Baru-baru ini saya melihat robot yang menggunakan D * Lite untuk perencanaan di lingkungan dengan pejalan kaki acak di dalamnya. Dalam hal ini, saya tidak berpikir D * Lite sudah usang sama sekali. Untuk masalah praktis Anda, saya kira tidak ada salahnya mencoba cara teknik yang biasa: mengambil beberapa pendekatan, dan jika tidak sesuai dengan kebutuhan Anda, coba sesuatu yang lain (lebih kompleks).

Saya ingin menambahkan sesuatu tentang pohon acak yang dieksplorasi dengan cepat, atau RRT. Ide dasarnya memiliki diskusi yang baik di seluruh internet, tetapi mungkin aman untuk memulai dengan tautan dari halaman Wikipedia dan dengan tulisan asli Kuffner dan LaValle tentang topik tersebut.

Fitur terpenting RRT adalah mereka dapat menangani ruang bernilai nyata dari dimensi yang sangat tinggi tanpa tersedak. Mereka dapat menangani dinamika, tidak optimal tetapi probabilistically lengkap (dijamin akan berhasil jika mungkin karena waktu komputasi pergi hingga tak terbatas), dan mampu menangani target bergerak. Ada beberapa ekstensi yang memungkinkannya bekerja di ruang non-statis, yang terbaik terlihat sebagai pekerjaan RRT Multipartit yang saya tautkan di bawah ini.

• http://en.wikipedia.org/wiki/Rapidly_exploring_random_tree
• http://swing.adm.ri.cmu.edu/pub_files/pub4/zucker_matthew_2007_1/zucker_matthew_2007_1.pdf

Struktur data yang disebut jarak oracle menangani masalah seperti itu. Namun, sebagian besar hasil penelitian hanya untuk grafik statis .

Jika grafik adalah kisi-kisi (dan karenanya planar), beberapa struktur data dinamis ada (tidak jelas apakah konstanta cukup kecil untuk aplikasi yang dimaksud):

Jalur terpendek yang tepat:

Jittat Fakcharoenphol, Satish Rao: Grafik planar, tepi bobot negatif, jalur terpendek, dan waktu linear dekat. J. Comput. Syst. Sci. 72 (5): 868-889 (2006)

Perkiraan jalur terpendek:

Philip N. Klein, Sairam Subramanian: Skema Pendekatan Sepenuhnya Dinamis untuk Jalur Terpendek dalam Grafik Planar. Algorithmica 22 (3): 235-249 (1998)

Ittai Abraham, Shiri Chechik, Cyril Gavoille: Peramalan perkiraan dinamis sepenuhnya untuk grafik planar melalui label jarak terlarang-set. STOC 2012: 1199-1218

Di sekolah saya berkecimpung dengan optimasi koloni semut . Dalam beberapa teks itu disebut-sebut sebagai solusi untuk terus mengubah grafik, merute jaringan, dll. Ini bukan solusi rekayasa, tetapi adaptasi dari bagaimana semut menavigasi rintangan dengan menyebarkan feromon untuk menandai jalur yang baik dan buruk. Saya tidak tahu apakah itu bekerja untuk masalah Anda, tetapi saya pikir itu sudut pandang yang menarik.