Lifelong Planning A*
term_id: lifelong_planning_a
Category: application_paradigms
Definition
Lifelong Planning A* (LPA*) er en udvidelse af A*-søgealgoritmen designet til miljøer, hvor omkostninger ændrer sig over tid. I stedet for at genstarte søgningen, opretholder LPA* en prioritetskø og opdaterer
Summary
En inkrementel sti-finding-algoritme, der effektivt opdaterer korteste veje i dynamiske grafer uden at genberegne fra bunden efter ændringer i kantvægte.
Key Concepts
- Inkrementel søgning
- Sti-finding
- Dynamiske grafer
- Robotnavigation
Use Cases
- Ruteplanlægning for autonome køretøjer i trafik
- Robotnavigation i skiftende lagermiljøer
- Bevægelse af AI i realtids-strategispil
Related Terms
- a_star (en bredt anvendt algoritme til at finde den korteste vej mellem to punkter i en graf)
- d_star (en algoritme til sti-finding i dynamiske miljøer)
- inkrementel søgning (en søgemetode, der genbruger tidligere beregninger ved små ændringer)
- sti-planlægning (processen med at finde en sekvens af trin fra start til mål)