Jak dostosować algorytmy wyszukiwania ścieżki do ograniczonego ruchu?


10

Wyobraź sobie ruch podobny do samochodu, w którym byty nie mogą włączyć dziesięciocentówki. Powiedzmy, ze względu na dyskusję, że przy dużej prędkości mogą obracać się o 90 stopni na sekundę. W wielu przypadkach zmieniłoby to optymalną ścieżkę, a tym samym wyszukiwanie ścieżki. Może nawet sprawić, że „zwykłe” ścieżki będą całkowicie niemożliwe do przejścia.

Czy istnieją jakieś algorytmy wyszukiwania ścieżki lub algorytmy planowania ruchu, które mogą o tym pamiętać, czy też istnieją proste sposoby dostosowania popularnych?


czy wyszukiwanie ścieżek obejmowałoby również dane prędkości? na przykład, przejdź z A do B przy X km / h (lub mph), czy byłaby to stała prędkość? także 90 stopni na sekundę przy niskich prędkościach może być bardzo zamkniętym zakrętem, prawdopodobnie nawet fizycznie niemożliwym. (chyba że wszystkie koła obracają się xD)
Brian H.,

@BrianH. Dlatego powiedziałem „z prędkością”. W rozsądnych okolicznościach obowiązywałyby minimalne i maksymalne progi. Ale idealnie byłoby, gdyby algorytm szukał „idealnej” ścieżki, która może obejmować zmiany prędkości.
Weckar E.

Uważam to za bardzo interesujące pytanie, dostałem ode mnie +1, nie mogę się doczekać, aby zobaczyć jakieś fajne odpowiedzi :)
Brian H.,


Uważałbym to za jakąś niewidzialną ścianę. Ponadto większość algorytmów finansowania ścieżki ma „wagę” dla każdej ścieżki (na przykład chodzenie po wodzie jest wolniejsze niż chodzenie po lądzie), dzięki czemu można dodać dodatkową wagę do ścieżki, która jest trudniejsza do uzyskania. Wszystko to można poznać tylko na podstawie prędkości i kierunku samochodu.
the_lotus

Odpowiedzi:


10

Witamy w cudownym świecie niehonomicznego planowania ruchu. Polecam to zrobić za pomocą planera ścieżki siatki kratowej . Inne alternatywy obejmują kinodynamiczną RRT i optymalizację trajektorii . Systemy niehonomiczne obejmują samochody, łodzie, monocykle lub cokolwiek, w którym pojazd nie może jechać w dowolnym kierunku. Planowanie tych systemów jest znacznie trudniejsze niż systemy holonomiczne i do ~ 2000 roku znajdowało się na krawędzi badań akademickich. Obecnie istnieje wiele algorytmów do wyboru, z których działa przyzwoicie.

wprowadź opis zdjęcia tutaj

Oto jak to działa.

Stan

Konfiguracja twojego samochodu q jest w rzeczywistości stanem 3D zawierającym pozycję x, y i jego orientację t . Węzły w algorytmie A * są w rzeczywistości wektorami 3D.

class Node
{
    // The position and orientation of the car.
    float x, y, theta;
}

działania

A co z krawędziami?

To nieco trudniejsze, ponieważ twój samochód może faktycznie wybrać nieskończoną liczbę sposobów obracania koła. Tak, możemy zrobić to dostępne do planowania sieci kratowej poprzez ograniczenie liczby działań samochód może podjąć w celu dyskretnego zbioru, A . Dla uproszczenia załóżmy, że samochód nie przyspiesza, ale może natychmiast zmienić prędkość. W naszym przypadku A może wyglądać następująco:

class Action
{
    // The direction of the steering wheel.
    float wheelDirection;

    // The speed to go at in m/s.
    float speed;

    // The time that it takes to complete an action in seconds.
    float dt;
}

Teraz możemy stworzyć dyskretny zestaw działań, które samochód może podjąć w dowolnym momencie. Na przykład twarde prawe naciśnięcie gazu do końca przez 0,5 sekundy wyglądałoby tak:

Action turnRight;
turnRight.speed = 1;
turnRight.wheelDirection = 1;
turnRight.dt = 0.5;

Włączenie cofania i cofanie samochodu wyglądałoby następująco:

Action reverse;
reverse.speed = -1;
reverse.wheelDirection = 0;
reverse.dt = 0.5;

Twoja lista działań wyglądałaby następująco:

List<Action> actions = { turnRight, turnLeft, goStraight, reverse ...}

Potrzebny jest także sposób zdefiniowania, w jaki sposób działanie podjęte w węźle powoduje powstanie nowego węzła. Nazywa się to dynamiką naprzód systemu.

// These forward dynamics are for a dubin's car that can change its
// course instantaneously.
Node forwardIntegrate(Node start, Action action) 
{
    // the speed of the car in theta, x and y.
    float thetaDot = action.wheelDirection * TURNING_RADIUS;

    // the discrete timestep in seconds that we integrate at.
    float timestep = 0.001;

    float x = start.x;
    float y = start.y;
    float theta = start.theta;

    // Discrete Euler integration over the length of the action.
    for (float t = 0; t < action.dt; t += timestep)
    {
       theta += timestep * thetaDot;
       float xDot = action.speed * cos(theta);
       float yDot = action.speed * sin(theta);
       x += timestep * xDot;
       y += timestep * yDot;
    }

    return Node(x, y, theta);
}

Dyskretne komórki siatki

Teraz, aby zbudować siatkę kratową, wszystko, co musimy zrobić, to hash stany samochodu w dyskretne komórki siatki. To zamienia je w odrębne węzły, po których może następować A *. Jest to bardzo ważne, ponieważ w przeciwnym razie A * nie miałby możliwości dowiedzenia się, czy dwa stany samochodu są takie same, aby je porównać. Przez mieszanie z wartościami całkowitymi komórek siatki staje się to trywialne.

GridCell hashNode(Node node)
{
    GridCell cell;
    cell.x = round(node.x / X_RESOLUTION);
    cell.y = round(node.y / Y_RESOLUTION);
    cell.theta = round(node.theta / THETA_RESOLUTION);
    return cell; 
}

Teraz możemy zrobić plan A *, w którym GridCells są węzłami, Działania są krawędziami między węzłami, a Start i Cel są wyrażone w postaci GridCells. Heurystyka między dwoma komórkami siatki to odległość w xiy plus odległość kątowa w theta.

Podążając ścieżką

Teraz, gdy mamy ścieżkę pod względem GridCells i akcji między nimi, możemy napisać obserwatora ścieżki dla samochodu. Ponieważ komórki siatki są dyskretne, samochód przeskakuje między komórkami. Będziemy musieli wygładzić ruch samochodu wzdłuż ścieżki. Jeśli gra korzysta z silnika fizyki, można to osiągnąć, pisząc kontroler kierowania, który stara się utrzymywać samochód jak najbliżej ścieżki. W przeciwnym razie możesz animować ścieżkę za pomocą krzywych Beziera lub po prostu uśredniając kilka najbliższych punktów na ścieżce.


Znakomity post (a nawet krótki! Robię coś podobnego do łodzi - śliska :-). Oto jest więcej miejsca,
Stormwind,

4

Większość algorytmów wyszukiwania ścieżek działa na dowolnym wykresie bez ograniczenia geometrii.

Musisz więc dodać orientację samochodu do każdego badanego węzła i ograniczyć, które węzły są faktycznie połączone.


Problem polega na tym, że samochód może odwiedzić ten sam węzeł zbliżający się z różnych kierunków, co nakłada różne ograniczenia na połączenia, z których można przejść.
Weckar E.,

6
@WeckarE. Ale samochód nie odwiedza tego samego węzła. Odwiedza 2 węzły, które mają tę samą lokalizację, ale inną orientację
maniak zapadkowy

3
@WeckarE. Traktuj je jak dwa osobne węzły. Wykres fizyczny i wykres logiczny nie muszą być dokładnie takie same.
BlueRaja - Danny Pflughoeft

1

Moje myśli nigdy ich nie testowały!

  1. Uruchom A * od początku do miejsca docelowego, zwróć ścieżkę.
  2. Pętlę przez ścieżkę, po wykryciu zakrętu, użyj Bezier algorytmu (lub dowolnego podobnego), który wykorzystuje bieżącą prędkość poszukiwaczy do przewidzenia węzłów, które utworzą płynny zakręt. Upewnij się, że próbuje wrócić do najbliższego węzła-ścieżki.
  3. Jeśli skręt można wykonać, świetnie, jeśli nie, powtarzaj z mniejszą prędkością, co daje ostrzejszy zakręt.
  4. Po utworzeniu prawidłowej ścieżki, wróć nią, dostosowując prędkość poszukiwacza przed wykonaniem zwrotu, aby zwolnił do właściwej prędkości przed rozpoczęciem zwrotu.
  5. Jeśli nie można w ogóle wykonać tury, ponownie uruchom całą sprawę. Upewnij się tylko, że wszystkie obsługiwane węzły kolei, których nie można wykonać, znajdują się na zamkniętej liście, aby zostały zignorowane. Możesz zacząć od momentu rozpoczęcia tury, abyś mógł pominąć udaną część ścieżki, jednak w niektórych przypadkach może to skutkować mniej niż optymalną ścieżką.

Powinieneś być w stanie to zrobić bez konieczności wcześniejszego ukończenia ścieżki, ergo: obsługa zwrotów podczas A *, które prawdopodobnie będą znacznie lepiej zoptymalizowane, ale może również okazać się problematyczne i usterkowe, naprawdę nie wiedziałbym i niestety nie mam czasu, aby sam to przetestować.

Znalezienie drogi


0

Jeśli twój agent ma pełną kontrolę nad samochodem, zrób to na odwrót. Najpierw podłącz linię od początku do końca, a następnie ustal, z jaką prędkością możesz nawigować na każdym zakręcie, podobnie jak w odpowiedzi Dennisa.

Nie rysuj jednak krzywych Beziera ze stałych punktów. Aby zminimalizować utratę prędkości, musisz przesunąć całą linię, więc zacznij od wstawienia dodatkowych węzłów w mniej więcej równej odległości, a następnie przejdź do minimalizacji energii lub podobnych strategii. Aby uzyskać szczegółowe informacje, musisz przyjrzeć się generowaniu linii AI w grach wyścigowych (najlepiej sim lub semi-sim).

Po uruchomieniu systemu linii AI uruchom wyszukiwanie A * i dla każdej ścieżki przejdź przynajmniej o jeden róg do przodu, a następnie oblicz linię AI, która daje oszacowanie czasu. To byłaby twoja funkcja kosztów.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.