Bagaimana cara membangun "traffic AI"?

Sebuah proyek yang sedang saya kerjakan sekarang menampilkan banyak "lalu lintas" dalam arti mobil bergerak di sepanjang jalan, pesawat bergerak di sekitar celemek, dll.

Sampai sekarang jalur yang tersedia sudah dihitung, sehingga node dihasilkan secara otomatis untuk penyeberangan yang mereka sendiri saling terhubung oleh tepi. Ketika sebuah karakter / agen memunculkan ke dunia itu dimulai pada beberapa node dan menemukan jalan ke target node dengan hanya menggunakan algoritma A *. Agen mengikuti jalan dan akhirnya mencapai tujuannya. Tidak masalah sejauh ini.

Sekarang saya perlu mengaktifkan agen untuk menghindari tabrakan dan untuk menangani situasi lalu lintas yang kompleks. Karena saya baru di bidang AI saya mencari beberapa makalah / artikel tentang perilaku kemudi tetapi menemukan mereka terlalu rendah. Masalah saya kurang terdiri dari penghindaran tabrakan yang sebenarnya (yang agak sederhana dalam kasus ini karena agen mengikuti jalur yang ditetapkan secara ketat) tetapi dari situasi seperti satu agen meninggalkan jalan buntu sementara yang lain ingin memasukkan yang persis sama. Atau dua agen bertemu di sebuah bottleneck yang hanya memungkinkan satu agen untuk lulus pada satu waktu tetapi keduanya harus melewati itu (sesuai dengan rute optimal yang ditemukan sebelumnya) dan mereka perlu menemukan cara untuk membiarkan yang lain melewati terlebih dahulu. Jadi pada dasarnya aspek utama dari masalah ini adalah memprediksi pergerakan lalu lintas untuk menghindari jalan buntu.

Sulit dijelaskan, tapi saya kira Anda mengerti maksud saya. Apakah Anda memiliki rekomendasi untuk saya di mana harus mulai mencari? Adakah makalah, proyek sampel, atau hal serupa yang dapat membantu saya memulai?

Saya menghargai bantuan Anda!

Ada banyak cara untuk mengatasi masalah ini, saya berjuang untuk memberikan jawaban yang layak dan komprehensif di sini. Tapi di sini ada beberapa poin desain tingkat tinggi.

• Anda sedang membuat simulasi agen di sini. Pathfinding hanyalah satu input ke dalam sistem - agen memiliki tujuan, dan pencarian jalur hanyalah cara untuk mencapai tujuan tersebut. Sebenarnya, memikirkannya secara riil agen memiliki dua tujuan: tujuan utama pengemudi adalah "jangan tabrak", yang kedua adalah "dapatkan tujuan yang ingin saya tuju".

• Sistem Anda harus dibangun di atas paralel dunia nyata. Alasan mengapa sebagian besar jalan memiliki dua lajur atau lebih adalah karena lebih mudah mengatur lalu lintas dengan sistem itu, tidak ada yang harus berpikir banyak. Dalam skenario jalur tunggal, pengemudi harus memilah berbagai masalah:

  deteksi - mengenali bahwa Anda dan mobil yang melaju akan jatuh kecuali Anda saling menghindari

  reaksi - melambat dan memasuki fase negosiasi.

  negosiasi - salah satu pendorong harus memimpin, yang lain harus menyerah. Aturan untuk cara memutuskan ini tidak jelas, tetapi pada dasarnya Anda menginginkan sesuatu di mana satu pengemudi secara sewenang-wenang (atau berdasarkan heuristik tentang berapa banyak mobil yang datang ke arah lain) memutuskan untuk mengambil prioritas. Misalnya A mengambil prioritas pada waktu 1, B melihat A mengambil prioritas, dan menghasilkan (dengan bergerak keluar dari jalan dan berhenti). Jika A dan B mencoba mengambil prioritas, keduanya harus berhenti, tunggu beberapa waktu secara acak (atau saling memberi sinyal) dan coba lagi. Akhirnya satu akan menghasilkan yang lain.

  Keindahan dari implementasi ini adalah bahwa ia menghindari kebutuhan untuk mempertahankan antrian buatan atau konstruksi palsu lainnya. Negosiasi dilakukan dalam hal persepsi dunia nyata - setelah kedua pihak berada dalam fase negosiasi, setiap gerak maju yang signifikan mudah dideteksi sebagai upaya untuk mengambil prioritas. Ini juga harus bereaksi dengan tepat kepada pengguna, yang kemungkinan besar tidak akan mematuhi aturan mengemudi yang baik.

• Anggaplah yang terburuk. Bahkan dalam sistem yang sempurna, situasi aneh dapat muncul, dan aktor Anda harus bertindak bijaksana. Ini bahkan lebih mungkin jika pemain dapat ikut campur (secara artifisial memblokir area, dll.) Seringkali, berhenti sama sekali adalah satu-satunya respons yang masuk akal (kemacetan!) Berputar di tempat atau jelas berada dalam kondisi rusak adalah kegagalan AI. Berhenti sama sekali setidaknya masuk akal dari segi dunia nyata.

  Semakin dekat Anda membuat model AI aktor Anda pada logika dunia nyata yang sederhana, semakin mudah untuk membuat AI yang meyakinkan. Orang sungguhan tidak berhenti atau berosilasi bolak-balik jika mereka tidak dapat mencapai tujuan mereka. Jika satu-satunya jalan ke tujuan AI diblokir, mereka harus mengenalinya dan memilih respons (berhenti sama sekali, menyerah dan pulang, menyerah dan mengemudi di tempat lain).

• Lapisan perilaku untuk mendapatkan apa yang Anda inginkan. Ingat, tujuan pertama bukanlah untuk mogok. Jadi logika avoidance (steering) harus selalu mendominasi aksi pengemudi. Lapisan di atas itu logika directional yang berasal dari path-finding ('Saya ingin mengambil hak di persimpangan berikutnya'). Lapisan di atas itu evaluasi sesekali jalan, dengan logika tingkat yang lebih tinggi ('lebih suka untuk maju, tetapi jika saya tidak dapat membuat kemajuan, izinkan jalur baru yang melibatkan putar-U').

• Menemukan jalan berasal dari ingatan, tetapi kesadaran situasional didasarkan pada persepsi. Jangan mencoba membuat agen Anda sempurna. Mereka tahu jalan dari rumah ke kantor, jadi mereka tahu jalan mana yang harus diambil. Tetapi mereka tidak tahu bahwa jalan 2 mil jauhnya diblokir. Jangan mencoba membuat agen Anda memplot jalur yang sempurna, karena tidak ada - bahkan jika itu dimulai dengan sempurna, faktor-faktor lain mungkin menghalangi jalan mereka. Agen seharusnya hanya perlu merencanakan beberapa jalan di depan ke mana mereka pergi.

• Kualitas informasi. Perilaku Anda harus sederhana, tetapi untuk mencapai itu Anda memerlukan fungsionalitas permintaan yang baik. Anda harus dapat mengajukan pertanyaan tentang lingkungan Anda seperti "apakah mobil yang akan datang itu menempati jalur saya?", "Berapa banyak mobil yang melaju?", "Apakah ada mobil di belakang saya", "bisakah saya melakukan putar balik" .

Setelah melihat beberapa kegagalan yang mengerikan dalam game yang dirilis, saya punya beberapa saran:

1) Kecuali ada alasan yang kuat untuk membuat dua lajur dan untuk tujuan AI membuat mereka memiliki prioritas untuk arah aliran yang normal - ijinkan perjalanan dua arah tetapi jika ada sesuatu yang terjadi sebaliknya pria di sisi jalan yang salah selalu hasil untuk itu.

2) Semacam logika untuk menghilangkan kemacetan jika terjadi. Saya telah menyaksikan situasi di mana penanganan kemacetan hanya berlaku untuk kendaraan yang mencoba saling bertemu tetapi sama sekali gagal ketika dihadapkan dengan pola -> -> <- <. Saya ingat satu peta yang rentan terhadap ini - itu adalah chokepoint yang dimaksudkan untuk membuat pangkalan AI lebih sulit untuk diserang tetapi cepat atau lambat dua pemanen sumber daya akan masuk ketika sebuah kelompok serangan sedang menuju keluar dan itu adalah itu. Unit-unit yang berhubungan akan berputar mencoba menemukan rute keluar tetapi mereka tidak memiliki langkah hukum. Itu tidak mundur dan mengetahui bahwa beberapa unit lain harus bergerak terlebih dahulu, dan dengan demikian AI tidak mengambil tindakan yang berguna sampai penghalang jalan dilepaskan. (Anda dapat menonton unit-unit yang bersentuhan berputar dan tidak ada yang melakukan apa pun.)

Saya percaya ini bisa diselesaikan dengan membuat unit macet memberitahu unit tetangga untuk keluar dari jalan - ini akan menyebar sampai mencapai unit unstuck yang bisa mundur. Ini harus melibatkan semacam logika untuk menjauhkan mereka sampai masalahnya selesai.

Perhatikan bahwa hanya mencari jalur alternatif seringkali merupakan jawaban yang buruk. Saya telah menyaksikan situasi livelock semacam itu - unit A mencatat bahwa B menghalangi jalan di depan sehingga berbalik untuk menggunakan rute yang berbeda. Ini sekarang memblokir jalan untuk B yang berbalik - sekarang jalan tidak diblokir sehingga keduanya berbalik lagi. Setiap belokan mereka bergantian antara bergerak maju dan bergerak mundur.

Game yang sama saya telah melihat versi yang berbeda, juga karena kabut perang. Ada unit musuh di chokepoint. Pada auto-move, pathfinding tidak akan bertempur kecuali benar-benar ditargetkan pada unit musuh. Itu akan bergerak maju dan melihat jalan terhalang. Kemudian bergerak mundur, tidak bisa lagi melihat pemblokir dan itu akan bergerak maju lagi. Ulangi sampai manusia menyadari itu tidak sampai ke tempat seharusnya.

Saya tidak terlalu berpengalaman dengan simulasi lalu lintas, tetapi beberapa hal muncul dalam pikiran.

Pertama, untuk mencegah kemacetan di tempat pertama saya akan memiliki dua jalur yang memungkinkan kendaraan untuk melakukan perjalanan di arah yang berlawanan. di "jalan" yang sama.

Kedua, untuk tabrakan yang mungkin terjadi, Anda harus memiliki perilaku kemudi tabrakan menghindari untuk mencegah tumpukan besar. Perilaku kemudi mungkin level rendah, tetapi mereka sangat berguna dalam menciptakan perilaku yang tampak realistis.

Jika Anda tidak ingin memiliki lebih dari satu jalur, Anda harus menyimpan lebih banyak informasi dalam grafik. Misalnya, jika agen A berada di jalan (digambarkan sebagai tepi grafik) dan agen B berada di jalan yang sama bergerak dalam arah yang berlawanan dengan A maka mereka akan bertabrakan / jalan buntu / apa pun yang Anda kodekan untuk menangani perilaku ini.

Namun, jika agen A ada di jalan, itu bisa meminta kepemilikan jalan itu. Memiliki jalan berarti bahwa tidak ada agen lain yang dapat melakukan perjalanan di sepanjang tepi itu (Anda bisa melakukan ini cukup dengan mengubah biaya tepi menjadi sejumlah besar untuk memastikan A * tidak memilih jalan ketika menghitung jalan). Kemudian ketika agen A bebas dari jalan itu ia melepaskan kepemilikan.

Jujur, ini solusi hacky yang saya tidak terlalu sukai dan sebagian besar simulasi lalu lintas (jika tidak semua?) Yang saya lihat menggunakan pendekatan multi-jalur.

Anda bilang Anda mencari beberapa artikel tentang perilaku kemudi, meskipun untuk berjaga-jaga, apakah Anda sudah mencari yang berikut?

http://www.red3d.com/cwr/steer/

Jika tidak, ini mungkin memberi Anda beberapa jawaban, karena mencakup beberapa masalah yang Anda beri nama, misalnya masalah bottleneck (Antrian).

Saya pikir apa yang perlu Anda lakukan adalah menerapkan algoritma pencarian jalur.

Pisahkan peta Anda menjadi bagian-bagian kecil yang Anda bisa (katakanlah kotak) tetapi hanya untuk tempat yang valid untuk lalu lintas yang akan bepergian. Anda kemudian akan menentukan di mana kendaraan itu dan di mana ia pergi dan menemukan jalan, terpendek atau paling langsung mungkin. Jalan akan menjadi array kotak, setiap langkah menuju ke tujuan. Apa yang Anda inginkan adalah menghitung tidak hanya posisi saat ini dari semua kendaraan tetapi posisi kendaraan di masa depan untuk beberapa langkah di masa depan. Jika dua kendaraan akan berada di alun-alun yang sama di masa depan maka Anda perlu mengubah kecepatan satu atau keduanya.

A * (Bintang) adalah algoritme pencarian jalur yang sangat sederhana yang mungkin Anda bisa dengan mudah menerjemahkan kode psuedo di wikipedia ke dalam bahasa pilihan Anda dan itu akan berfungsi: http://en.wikipedia.org/wiki/A*_search_algorithm

Ketika saya mengimplementasikan Enemy Nations, kemunduran terakhir saya adalah jika sebuah kendaraan macet selama lebih dari 2 detik, saya melompat maju di jalurnya. Jadi ketika mereka macet, sebuah unit pada dasarnya diangkut. Tidak ada yang pernah mengeluh jadi saya pikir beberapa kali itu terjadi tidak ada yang menonton dan tidak melihatnya.