Jak zbudować „AI ruchu”?

Projekt, nad którym teraz pracuję, charakteryzuje się dużym „ruchem” w sensie samochodów poruszających się po drogach, samolotów poruszających się po płycie postojowej itp.

Obecnie dostępne ścieżki są wstępnie obliczane, więc węzły są generowane automatycznie dla skrzyżowań, które same są połączone krawędziami. Kiedy postać / agent odradza się w świecie, zaczyna się w pewnym węźle i znajduje ścieżkę do węzła docelowego za pomocą prostego algorytmu A *. Agent podąża ścieżką i ostatecznie dociera do celu. Jak dotąd żaden problem.

Teraz muszę umożliwić agentom unikanie kolizji i obsługę złożonych sytuacji na drodze. Ponieważ jestem nowy w dziedzinie sztucznej inteligencji, przejrzałem kilka artykułów / artykułów na temat zachowań kierowniczych, ale stwierdziłem, że są one zbyt niskie. Mój problem nie polega na faktycznym unikaniu kolizji (co w tym przypadku jest dość proste, ponieważ agenci podążają ściśle określonymi ścieżkami), ale na sytuacjach, w których jeden agent opuszcza ślepą uliczkę, podczas gdy inny chce wejść dokładnie w to samo. Lub dwóch agentów spotykających się na wąskim gardle, które pozwala na przejście tylko jednego agenta na raz, ale obaj muszą go przepuścić (zgodnie z optymalną trasą wcześniej ustaloną) i muszą znaleźć sposób, aby drugi przeszedł pierwszy. Zasadniczo głównym aspektem problemu byłoby przewidywanie ruchu ulicznego w celu uniknięcia martwych blokad.

Trudno to opisać, ale myślę, że rozumiesz. Czy masz dla mnie jakieś zalecenia, od czego zacząć? Jakieś dokumenty, przykładowe projekty lub podobne rzeczy, które mogłyby mnie zacząć?

Doceniam twoją pomoc!

Jest tak wiele sposobów rozwiązania tego problemu, z którymi trudno byłoby mi udzielić przyzwoitej i kompleksowej odpowiedzi. Ale oto kilka punktów projektowania na wysokim poziomie.

• Budujesz tutaj symulację agenta. Wyszukiwanie ścieżki jest po prostu jednym wejściem do systemu - agent ma cel, a znalezienie ścieżki jest tylko sposobem na osiągnięcie tego celu. Właściwie, myśląc o tym realnie, agent ma dwa cele: najważniejszym celem kierowcy jest „nie upaść”, a po drugie „dostać się tam, gdzie chcę jechać”.

• Wasze systemy powinny opierać się na paralelach ze świata rzeczywistego. Powodem, dla którego większość dróg ma dwa lub więcej pasów ruchu, jest to, że dzięki temu systemowi łatwiej jest zorganizować ruch, nikt nie musi dużo myśleć. W scenariuszu z jednym pasem kierowcy muszą rozwiązać różne problemy:

  wykrywanie - rozpoznanie, że ty i nadjeżdżający samochód rozbije się, chyba że się unikniesz

  reakcja - spowolnienie i wejście w fazę negocjacji.

  negocjacje - jeden z kierowców musi przejąć inicjatywę, drugi musi ustąpić. Zasady podejmowania takich decyzji są niejasne, ale zasadniczo chcesz czegoś, w którym jeden kierowca arbitralnie (lub na podstawie heurystyki na temat liczby samochodów jadących w innym kierunku) decyduje się przyjąć priorytet. Np. A ma pierwszeństwo w czasie 1, B widzi, że A ma pierwszeństwo i daje (ustępując z drogi i zatrzymując się). Jeśli zarówno A, jak i B próbują uzyskać pierwszeństwo, powinny się zatrzymać, poczekać losowo (lub zasygnalizować sobie nawzajem) i spróbować ponownie. W końcu jedno ulegnie drugiemu.

  Piękno tej implementacji polega na tym, że unika ona potrzeby utrzymywania sztucznych kolejek lub innych fałszywych konstrukcji. Negocjacje odbywają się w kategoriach rzeczywistych wyobrażeń - gdy obie strony znajdą się w fazie negocjacji, każdy znaczący ruch do przodu jest łatwo wykrywany jako próba nadania priorytetu. Powinien także odpowiednio reagować na użytkownika, który najprawdopodobniej nie będzie przestrzegał dobrych zasad jazdy.

• Załóż najgorsze. Nawet w idealnym systemie mogą pojawić się dziwne sytuacje, a twoi aktorzy powinni działać rozsądnie. Jest to tym bardziej prawdopodobne, że gracz może ingerować (sztucznie blokować obszary itp.) Często zatrzymanie jest jedyną sensowną reakcją (blokada!) Obracanie się w miejscu lub oczywiście bycie w stanie zepsutym jest awarią AI. Całkowite zaprzestanie jest przynajmniej możliwe w realnych warunkach.

  Im bardziej modelujesz sztuczną inteligencję swojego aktora na prostej logice świata rzeczywistego, tym łatwiej będzie stworzyć przekonującą sztuczną inteligencję. Prawdziwi ludzie nie zatrzymują się ani nie oscylują w przód iw tył, jeśli nie mogą osiągnąć celu. Jeśli jedyna droga do miejsca docelowego AI jest zablokowana, powinni ją rozpoznać i wybrać odpowiedź (zatrzymać się całkowicie, poddać się i pojechać do domu, poddać się i pojechać gdzie indziej).

• Zachowaj warstwy, aby uzyskać to, czego chcesz. Pamiętaj, że 1. celem jest nie upaść. Dlatego logika unikania (kierowania) powinna zawsze dominować w działaniach kierowcy. Nałóż na to logikę kierunkową pochodzącą ze znajdowania ścieżki („Chcę skręcić w prawo na następnym skrzyżowaniu”). Warstwa na wierzchu od czasu do czasu ponownej oceny ścieżek, z logiką wyższego poziomu („wolę iść naprzód, ale jeśli nie mogę zrobić postępu, pozwól na nową ścieżkę, która wymaga zawracania”).

• Szukanie ścieżki pochodzi z pamięci, ale świadomość sytuacyjna opiera się na percepcji. Nie staraj się, aby Twoi agenci byli idealni. Znają drogę z domu do biura, więc wiedzą, co zrobić. Ale nie wiedzą, że ulica oddalona o 2 mile jest zablokowana. Nie staraj się, aby twoi agenci opracowali idealną ścieżkę, ponieważ nie ma żadnej - nawet jeśli zacznie się idealnie, inne czynniki mogą zablokować jej ścieżkę. Agenci powinni jedynie zaplanować kilka ulic przed nimi, dokąd idą.

• Jakość informacji Twoje zachowania powinny być proste, ale aby to osiągnąć, potrzebujesz dobrej funkcjonalności zapytań. Musisz umieć zadawać pytania otoczenia: „czy nadjeżdżający samochód zajmuje mój pas?”, „Ile samochodów nadjeżdża?”, „Czy są jakieś samochody za mną”, „czy mogę zawrócić” .

Widząc straszne niepowodzenia w wydanych grach, mam kilka sugestii:

1) O ile nie ma uzasadnionego powodu, aby zrobić dwa pasy ruchu i dla celów sztucznej inteligencji ustawić je jako priorytetowe dla normalnego kierunku przepływu - zezwól na podróż na dwa odcinki, ale jeśli coś idzie w drugą stronę, facet po niewłaściwej stronie drogi zawsze ulega temu.

2) Jakaś logika, która odwija ​​korki, jeśli się pojawią. Widziałem sytuacje, w których obsługa korków dotyczyła tylko pojazdów, które próbowały na siebie wpaść, ale całkowicie zawiodły, gdy skonfrontowano je ze wzorem -> -> <- <-. Przypominam sobie jedną mapę, która była na to podatna - był to punkt pośredni, który miał utrudnić atak na bazę AI, ale prędzej czy później pojawią się dwaj zbieracze zasobów, gdy grupa atakująca wyrusza i to wszystko. Jednostki będące w kontakcie obracały się wokół, próbując znaleźć drogę, ale nie miały żadnych legalnych ruchów. Nie cofnął się i nie stwierdził, że jakaś inna jednostka musiała się najpierw ruszyć, dlatego AI nie podjęła żadnych użytecznych działań, dopóki blokada drogi nie została usunięta. (Możesz obserwować, jak stykające się jednostki obracają się wokół i nic więcej nie robią.)

Wierzę, że można to rozwiązać, każąc utkniętej jednostce powiedzieć sąsiednim jednostkom, aby zejść im z drogi - rozprzestrzeniałoby się to, aż dotrze do unieruchomionej jednostki, która może się wycofać. Musiałoby to obejmować jakąś logikę, aby trzymać je z dala, dopóki problem nie zostanie rozwiązany.

Pamiętaj, że po prostu szukanie alternatywnej ścieżki jest często złą odpowiedzią. Widziałem tego rodzaju sytuacje na żywo - jednostka A zauważa, że ​​B blokuje drogę do przodu, więc zawraca, aby wybrać inną trasę. To blokuje drogę dla B, który zawraca - teraz droga jest odblokowana, więc obaj zawracają. W każdym zakręcie naprzemiennie poruszają się do przodu i do tyłu.

Ta sama gra widziałem inną wersję, również z powodu mgły wojny. W punkcie pośrednim znajdowała się jednostka wroga. Podczas automatycznego poruszania się, odnajdywanie ścieżek nie będzie walczyć, chyba że zostanie faktycznie skierowane na wrogą jednostkę. Poruszałby się do przodu i widziałby, że droga jest zablokowana. Następnie cofnął się, nie widział już blokady i znów ruszyłby do przodu. Powtarzaj, dopóki człowiek nie zorientuje się, że nie dotrze tam, gdzie powinien.

Nie mam zbyt dużego doświadczenia z symulacjami ruchu, ale przychodzi mi na myśl kilka rzeczy.

Po pierwsze, aby przede wszystkim uniknąć wąskich gardeł, miałbym dwa pasy ruchu, które pozwolą pojazdom poruszać się w przeciwnych kierunkach. na tej samej „drodze”.

Po drugie, w przypadku kolizji, które mogą się zdarzyć, powinieneś mieć zachowanie kierowania unikaniem kolizji, aby zapobiec masywnemu gromadzeniu się. Zachowania sterujące mogą być na niskim poziomie, ale są bardzo przydatne w tworzeniu realistycznie wyglądających zachowań wschodzących.

Jeśli nie chcesz mieć więcej niż jednego pasa, musisz zapisać więcej informacji na wykresie. Na przykład, jeśli A jest środkiem na drodze (reprezentowane krawędzi wykresu) i agenta B jest na tej samej drodze poruszającego się w kierunku przeciwnym do A potem będzie Collide / impas / cokolwiek masz kodowane do czynienia z tego zachowania.

Jeśli jednak agent A jest na drodze, może zażądać prawa własności do tej drogi. Posiadanie drogi oznaczałoby, że żaden inny agent nie może podróżować wzdłuż tej krawędzi (możesz to zrobić po prostu zmieniając koszt krawędzi na ogromną liczbę, aby upewnić się, że A * nie wybiera drogi podczas obliczania ścieżki). Następnie, gdy agent A jest wolny od tej drogi, traci własność.

Szczerze mówiąc, jest to hackerskie rozwiązanie, którego nie lubię i większość symulacji ruchu drogowego (jeśli nie wszystkie?), Które widziałem, używają podejścia wielopasmowego.

Powiedziałeś, że przejrzałeś kilka artykułów na temat zachowania kierownicy, chociaż na wszelki wypadek, czy przejrzałeś następny?

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

Jeśli nie, może dostarczyć ci odpowiedzi, ponieważ obejmuje niektóre z wymienionych przez ciebie problemów, na przykład problem wąskiego gardła (kolejkowanie).

Myślę, że musisz zaimplementować algorytm znajdowania ścieżki.

Podziel mapę na możliwie małe części (powiedzmy kwadraty), ale tylko w miejscach, w których ruch może się odbywać. Następnie określisz, gdzie jest pojazd i dokąd zmierza, i znajdziesz ścieżkę, być może najkrótszą lub najbardziej bezpośrednią. Ścieżka będzie układem kwadratów na każdym kroku do miejsca przeznaczenia. To, czego chciałbyś wtedy, to obliczenie nie tylko bieżącej pozycji wszystkich pojazdów, ale także przyszłych pozycji pojazdów dla kilku kroków w przyszłości. Jeśli dwa pojazdy będą w przyszłości na tym samym placu, musisz zmienić prędkość jednego lub obu z nich.

* (Gwiazda) jest bardzo prostym algorytmem znajdowania ścieżek, który prawdopodobnie łatwo po prostu przetłumaczyć kod psuedo z wikipedii na wybrany język i będzie działał: http://en.wikipedia.org/wiki/A*_search_algorithm

Kiedy wdrożyłem Enemy Nations, mój ostatni awaria polegał na tym, że jeśli pojazd utknął przez ponad 2 sekundy, przeskoczyłem go do przodu na swojej drodze. Więc kiedy utknęli, jednostka w zasadzie została przetransportowana. Nikt nigdy nie narzekał, więc myślę, że kilka razy to się zdarzyło, nikt nie patrzył i nie widział tego.