Algorytm A* świadomy kierunku i samoadaptacyjny z heurystyką PPO do planowania tras UAV w inteligentnym mieście

Inteligentniejsze trasy dla miejskich dronów

Wyobraź sobie flotę małych dronów dostawczych przemierzających przestrzeń między drapaczami chmur, dostarczających leki, przesyłki lub materiały ratunkowe w zatłoczonym mieście. Aby latać bezpiecznie i szybko, każdy dron musi nieustannie decydować, w którą stronę lecieć. W artykule przedstawiono nową metodę, która pozwala dronom znajdować lepsze trasy w zatłoczonych, trójwymiarowych przestrzeniach miejskich — trasy krótsze, płynniejsze i bardziej niezawodne niż przy użyciu tradycyjnych metod.

Dlaczego znalezienie dobrej trasy jest tak trudne

Dla drona wybór trasy to więcej niż narysowanie prostej linii od punktu A do punktu B. Musi on omijać budynki, drzewa i strefy zakazu lotu, jednocześnie respektując ograniczenia dotyczące zakrętów i wysokości. Klasyczne metody planowania trasy, takie jak dobrze znany algorytm A*, sprawdzają się na prostych mapach, ale mają problemy w realistycznych, trójwymiarowych środowiskach miejskich. Często rozważają zbyt wiele możliwych następnych kroków, marnując moc obliczeniową, i mogą generować zygzakowate trasy dłuższe niż konieczne lub nawet zawodzić, gdy otoczenie jest bardzo zatłoczone. W miarę jak inteligentne miasta stają się coraz bardziej złożone, te słabości stanowią poważne ograniczenie dla bezpiecznego i efektywnego ruchu powietrznego.

Ulepszenie klasycznego narzędzia z uwzględnieniem kierunku

Autorzy bazują na algorytmie A* i proponują jego rozszerzoną wersję nazwaną DASA* (Direction‑Aware and Self‑Adaptive A*). Zamiast bezmyślnie przeszukiwać wszystkie kierunki wokół drona, DASA* zwraca uwagę na położenie celu. Klasyfikuje pobliskie kandydatów na pozycje w trzy warstwy: te głównie przed dronem w kierunku celu, te boczne oraz mały zestaw za nim, które mogą pomóc w wydostaniu się z martwych punktów. Prosty detektor zastoju obserwuje oznaki „zakleszczenia” wyszukiwania i automatycznie rozszerza obszar poszukiwań z wąskiego stożka przedniego do pełniejszego sąsiedztwa, gdy jest to potrzebne. To przemyślane, w stronę celu ukierunkowane rozszerzanie zmniejsza zbędne eksploracje, jednocześnie gwarantując, że prawidłowa trasa zostanie znaleziona, jeśli istnieje.

Dopasowanie do zatłoczonych i otwartych przestrzeni

Kolejną kluczową cechą DASA* jest to, że dostosowuje „krok” w zależności od otoczenia. Gdy dron znajduje się daleko od przeszkód, algorytm stosuje większe kroki, szybko pokrywając otwartą przestrzeń. W miarę zbliżania się do budynków lub innych zagrożeń przechodzi na mniejsze kroki, co pozwala na precyzyjne manewrowanie w wąskich przejściach. Ta zmienna „skala” pozwala planistowi poruszać się szybko tam, gdzie jest bezpiecznie, i zwalniać tylko tam, gdzie liczy się dokładność. Po znalezieniu surowej trasy następuje etap korekcji, który usuwa niepotrzebne punkty przelotowe i dopasowuje gładką krzywą przez pozostałe istotne punkty. Efektem jest trasa, która nie tylko unika kolizji, ale także przypomina naturalną ścieżkę lotu wybraną przez doświadczonego pilota, z mniejszą liczbą nagłych skrętów.

Nauczenie algorytmu patrzenia w przód

Tradycyjny A* opiera się na prostych wzorach odległości do oceny, jak daleko każda pozycja jest od celu. DASA* zastępuje tę heurystykę wyuczonym przewodnikiem opartym na Proximal Policy Optimization (PPO), nowoczesnej technice uczenia przez wzmacnianie. W środowisku treningowym wirtualny agent wielokrotnie ćwiczy poruszanie się w kierunku celu w przestrzeni 3D, mierząc odległości, różnice wysokości i informacje o kierunku. Sieć neuronowa stopniowo uczy się, jak obiecujące są poszczególne sytuacje i po treningu służy jako moduł „intuicji” w DASA*. Ta wyuczona heurystyka kieruje wyszukiwaniem bardziej bezpośrednio ku dobrym rozwiązaniom, zwłaszcza w złożonych układach, gdzie prosta odległość w linii prostej bywa myląca.

Jak dobrze działa w wirtualnych miastach

Badacze przetestowali DASA* w wielu symulowanych scenariuszach 3D wypełnionych budynkami w kształcie pudeł i cylindrycznymi przeszkodami imitującymi rzeczywiste struktury miejskie. Porównali go z klasycznym A* i kilkoma popularnymi alternatywami, w tym ulepszonymi wersjami szybkiego eksplorowania drzew (RRT), rojami cząstek, ewolucją różnicową oraz inną odmianą A* nazwaną Theta*. W wielu testach DASA* konsekwentnie znajdował krótsze trasy, rozszerzał znacznie mniej kandydatów i działał znacznie szybciej — często 10 do 50 razy szybciej niż standardowy A*. Utrzymywał również perfekcyjny lub niemal perfekcyjny wskaźnik sukcesu nawet w gęstych, labiryntowych środowiskach, podczas gdy niektóre konkurencyjne metody częściej zawodziły lub generowały długie, kręte objazdy.

Co to oznacza w codziennym życiu

Mówiąc prosto, DASA* daje latającym robotom lepsze wyczucie kierunku i ocenę sytuacji. Koncentrując się na obiecujących kierunkach, dostosowując poziom szczegółowości do lokalnego otoczenia, wykorzystując wyuczone poczucie bliskości sukcesu i wygładzając końcową trasę, przekształca surowe dane mapy w ścieżki lotu efektywne, płynne i praktyczne. Jeśli podejście to zostanie przyjęte w systemach rzeczywistych, może pomóc przyszłym inteligentnym miastom zarządzać dostawami dronów, inspekcjami i reakcjami ratunkowymi bezpieczniej i bardziej niezawodnie, nawet gdy niebo stanie się bardziej zatłoczone, a środowiska jeszcze bardziej złożone.

Cytowanie: Zhang, X., Tan, L. & Chai, J. Direction aware and self-adaptive A* algorithm with PPO heuristic for UAV path planning of smart city. Sci Rep 16, 6174 (2026). https://doi.org/10.1038/s41598-026-36066-4

Słowa kluczowe: planowanie tras UAV, drony w inteligentnym mieście, algorytm A*, autonomiczna nawigacja, planowanie ruchu robota