Jakie są najnowocześniejsze algorytmy wyszukiwania ścieżek na ciągłej mapie Ziemi?

14

Załóżmy, że mam gdzieś na fiordach Norwegii autonomiczny statek powierzchniowy zasilany energią słoneczną, wyposażony w całkiem nowy zestaw map, odbiornik GPS i nie ma możliwości przesyłania szczegółowych poleceń ode mnie. Statek ten musi dotrzeć na wyspę Hainan w najwcześniejszym możliwym momencie.

  • Jakie są deterministyczne algorytmy wyszukiwania trasy morskiej na kuli ziemskiej?
  • Jaki jest ich czas i złożoność pamięci?

  • Czy mogę na przykład użyć A * po przekształceniu mapy globu w diagram z połączonymi wielokątami (tj. Triangulacja Delaunaya na kuli / elipsoidzie) i jakie są inne możliwe podejścia?

Odpowiedzi najlepiej powinny zawierać odniesienia do artykułów z omówieniem wyżej wymienionych pytań.

Jak zauważył Rob Lang , algorytmy muszą spełniać zwykłe kryteria: w przypadku braku ograniczeń czasowych prowadzić do najkrótszej ścieżki między dowolnymi dwoma punktami na oceanach i morzach Ziemi lub wskazywać inaczej niepowodzenie w znalezieniu ścieżki.

Są tutaj interesujące podtematy (handel czasem / pamięcią przed obliczeniami do obliczeń online, zapewnianie nieco nieoptymalnych tras przed upływem terminu itp.), Ale są one pomocnicze w stosunku do głównego problemu.

Łowca jeleni
źródło
1
@JDong - nawigacja naziemna podąża ogólnie po trasach / drogach, dlatego A * występuje naturalnie. Użyłbym gotowego wykresu.
Deer Hunter
1
Ach, przegapiłem kluczową część twojego pytania: „ciągłe”. W takim przypadku być może pola wektorowe lub potencjalne mogą być obiecujące.
JDong
1
@RobLang - pytanie edytowane.
Deer Hunter
1
W przypadku trasy morskiej należy uwzględnić w obliczeniach poziomy morza, wiatr i przepływ wody. O jakim statku mówimy? OpenSeaMap zapewnia kilka linii żeglugowych. Gdybyś mógł skorzystać z tych A * działałoby. Myślę też, że to pytanie jest zbyt szerokie dla tej wersji beta.
PiTheNumber
1
Myślę, że to pytanie jest w porządku, jeśli tylko prosi o najlepsze algorytmy dynamicznego wyszukiwania ścieżek dla dzisiejszych ciągłych przestrzeni. Mogę spróbować odpowiedzieć na to później dzisiaj po kilku badaniach.
JDong

Odpowiedzi:

7

Wymóg deterministyczny nie jest aż tak ograniczający. To po prostu sugeruje, że twój pojazd jest pewny, w jakim jest stanie. Mówiąc to, prawdopodobnie będziesz chciał zaplanować ścieżki w taki sposób, abyś mógł omijać przeszkody. Najlepszy sposób, w jaki to widziałem, to planowanie na podstawie próbkowania. Steven LaValle napisał centralne źródło naukowe na ten temat: Algorytmy planowania .

Algorytm RRT * należy do planistów, których opisuje. Algorytm ten generuje drzewo przestrzeni stanów z losowymi próbkami i kilkoma heurystykami, aby zapewnić wykonalność (np. Unikanie przeszkód) i optymalizację. Szczegółowe informacje na temat RRT * można znaleźć w książce LaValle lub na stronie internetowej Sertaca Karamana . Czas asymptotyczny i charakterystyka pamięci są opisane jako O (nlogn) do przetworzenia, a O (n) dla zapytań. Algorytm jest liniowy, O (n), również w złożoności przestrzeni.

jdmartin86
źródło
Wybrano na referencje. Rozważy zaakceptowanie po przeczytaniu książki LaValle i sprawdzeniu rzeczy RRT *. Dzięki!
Deer Hunter
4

Do dalszych rozważań, potencjalne pola są interesującym, niedrogim wyborem do wyszukiwania ścieżek. Umieścisz silny ładunek w miejscu docelowym, a ostatecznie agent dotrze do opłaty. Bardziej techniczny artykuł International Foundation for Autonomous Agents and Multiagent Systems.

Pola wektorowe są również bardzo tanim rozwiązaniem, ale częściej wykorzystywane do wyszukiwania ścieżek z wieloma agentami . Pola wektorowe są jednak bardzo dobre dla otwartych przestrzeni. Żadna z powyższych metod nie gwarantuje jednak najkrótszej ścieżki, poświęcając optymalne ścieżki dla lepszej dynamicznej odpowiedzi.

Silne są również podejścia łączone, takie jak wcześniejsze użycie A * do generowania punktów trasy i użycie pól wektorowych do przejścia do każdego punktu. Zapewni to prawdopodobnie znacznie bardziej optymalne zachowanie w skali makro.

Miej to na uwadze, jeśli zdobędziesz armię robotów pływających.

JDong
źródło