Lifelong Planning A*
term_id: lifelong_planning_a
Category: application_paradigms
Definition
Lifelong Planning A* (LPA*) jest rozszerzeniem algorytmu wyszukiwania A*, zaprojektowanym dla środowisk, w których koszty zmieniają się w czasie. Zamiast restartować wyszukiwanie, LPA* utrzymuje kolejkę priorytetową i aktualizuje tylko te części drzewa wyszukiwania, które zostały zmienione, co znacznie przyspiesza proces.
Summary
Algorytm wyszukiwania ścieżki inkrementalnej, który efektywnie aktualizuje najkrótsze ścieżki w dynamicznych grafach bez konieczności przeliczania ich od zera po zmianie wag krawędzi.
Key Concepts
- Wyszukiwanie inkrementalne
- Wyznaczanie ścieżki
- Grafy dynamiczne
- Nawigacja robotów
Use Cases
- Trasy pojazdów autonomicznych w ruchu drogowym
- Nawigacja robotów w zmieniających się magazynach
- Ruch AI w grach strategicznych w czasie rzeczywistym