Bagaimana Algoritma Pathfinding Umum Dibandingkan Dengan Proses Manusia

Ini mungkin berbatasan dengan ilmu kognitif komputasi, tapi saya ingin tahu bagaimana proses yang diikuti oleh algoritma pathfinding umum (seperti A * ) dibandingkan dengan proses yang digunakan manusia dalam situasi pathfinding yang berbeda (diberi informasi yang sama). Apakah proses ini serupa?

Manusia cenderung memilih tidak sepenuhnya optimal, tetapi mendekati solusi terpendek. Jadi, Anda harus melihat algoritma fuzzy (perkiraan), bukan pada A *.

Algoritma terdekat dengan pemikiran manusia yang saya sadari adalah hierarki Contaction yang setara dengan algoritma pemangkasan Reach . Ketika saya perlu menemukan jalur antara A dan B di peta, saya melakukan tinjauan singkat, dengan mempertimbangkan apakah ada persimpangan sungai atau sesuatu yang lain dan mencari beberapa cara umum dan kemudian menambahkan rincian yang dapat mempersingkat jalur.

Di sini Anda sejumlah pertimbangan. Dua yang pertama diambil dari PhD luar biasa oleh Andreas Junghanns (sekarang kembali ke Industri di Berlin, Jerman dan dengan senang hati menghitung dia di antara teman-teman saya :)):

Pencarian Pertama - Breadth : Jika Anda hanya berdiri di depan furnitur dan sesuatu yang berharga (katakanlah koin, atau cincin) jatuh dan pergi di bawah furnitur, sehingga Anda tidak dapat melihatnya, maka Anda melambaikan tangan sedikit mulai dari titik di mana Anda melihat objek menghilang. Jika Anda tidak menemukannya, Anda melangkah lebih jauh dan melanjutkan dengan cara ini sampai Anda menemukannya atau Anda kehilangan kesabaran. Itulah pencarian pertama yang luasnya dalam aksi: pertama, Anda mempertimbangkan semua lokasi yang tidak diketahui pada kedalaman 1, kemudian pada kedalaman 2 dan seterusnya.

Pencarian Kedalaman-Pertama : ketika mencari sesuatu yang jaraknya dekat dengan lingkungan Anda, Anda tidak pernah memilih algoritma yang disebutkan di atas dan alih-alih Anda berkomitmen pada suatu arah. Contohnya adalah Cristobal Colon berkomitmen ke barat ketika mencari rute ke India. Yah, dia salah tapi kita tahu itu sekarang. Bayangkan Colon mencoba pencarian pertama yang luas dan bergerak di sepanjang spiral dari Burgos di mana kontrak antara Reyes Católicos dan Colon ditandatangani. Sebaliknya dia menunjuk ke arah yang diberikan tanpa pernah mundur.

Contoh lain dari salah satu profesor saya di Universitas (José Cuena, yang sudah meninggal) mengenai pencarian dua arah : insinyur, ketika membangun terowongan di pegunungan dimulai dari kedua ujung secara bersamaan dan berakhir ketika mereka bertemu di suatu tempat di tengah. Alasannya sederhana, jika mereka memulai hanya dari satu ujung, sangat mungkin bahwa akan ada penyimpangan besar di ujung lainnya. Mulai dari kedua ujungnya secara bersamaan meminimalkan penyimpangan di titik pertemuan.

$^*$

• Daftar terbuka hanyalah daftar kemungkinan terbuka yang menunggu untuk dipertimbangkan. Semua manusia melakukan ini meskipun kita tidak sebaik komputer mengingat hal-hal.
• Daftar tertutup hanya berfungsi untuk menghindari penalaran melingkar atau melanjutkan penalaran dari titik yang telah kita bahas sebelumnya. Ini terjadi jika Anda beralasan dengan suara keras dan Anda mengulangi sesuatu. Kemudian, seseorang akan menyadari dan akan segera memberi tahu Anda "hai, Anda sudah mengatakan itu sebelumnya"

Pertanyaan yang sangat menarik, entah bagaimana, ditanggapi oleh orang lain adalah apakah manusia dapat menjalankan algoritma apa pun dan (bahkan lebih menarik dari sudut pandang saya) apakah algoritma ini (atau, secara umum, cara kita membangun Kecerdasan Buatan) meniru prosedur kecerdasan alami kita.

Sudahkah Anda menyaksikan seorang anak belajar menavigasi sebuah ruangan? Anda harus memberi tahu mereka, "Pergi berkeliling meja. SEKITAR ".

Perencanaan jalur manusia adalah tas heuristik, sebagian bawaan dan sebagian dipelajari. Lookahead mungkin diperbaiki ke sejumlah kecil, tentu bukan rekursi umum seperti A *.