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

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.

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.

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.