Path planning in dynamic environments is an important research field for the continuous development of autonomous mobile robots. Dynamic environments contain unknown static and moving obstacles, which require the robot to find a collision-free path and avoid obstacles in real-time with low computational effort. Several nature-inspired, evolutionary computation algorithms have been developed for this cause, such as the simulated annealing algorithm. There are also more conventional graph search algorithms for path planning, and developments of those such as the D* Lite algorithm, which is suited for dynamic environments. This paper aims to compare the performance of the D* Lite algorithm with the simulated annealing algorithm in five different simulated dynamic environments with varying amount of static and moving obstacles. The metrics studied were computation time and path length. It was found that the D* Lite algorithm performed generally better, consistently generating slightly shorter paths, and often requiring less computation time. The simulated annealing algorithm parameters can be tuned to perform quite efficiently, requiring less computation time than D* Lite in some cases, while still generating path lengths close to D* Lite. A significant difference between the algorithms was the amount of variation in the results, where simulated annealing was more spread out. D* Lite performed more consistently with regard to both path length and computation time, without the risk of generating a path far from optimal solution.

Vägplanering i dynamiska miljöer är ett viktigt forskningsområde för den kontinuerliga utvecklingen av autonoma mobila robotar. Dynamiska miljöer innehåller okända statiska och rörliga hinder, vilket kräver att roboten hittar en kollisionsfri väg och undviker hinder i realtid med låg beräkningsinsats. Flera naturinspirerade, evolutionära-beräkningsalgoritmer har utvecklats för detta ändamål, såsom simulated annealing. Det finns också mer konventionella grafsökningsalgoritmer för vägplanering, och utvecklingar av dessa, såsom D* Lite-algoritmen som är anpassad för dynamiska miljöer. Denna artikel syftar till att jämföra prestanda hos D* Lite och simulated annealing i fem olika simulerade dynamiska miljöer med varierande mängd statiska och dynamiska hinder. Beräkningstid och väglängd uppmättes. Det konstaterades att D* Lite-algoritmen generellt sett presterade bättre, genom att konsekvent generera något kortare vägar och ofta kräva mindre beräkningstid. För simulated annealing kan algoritmens parametrar finjusteras för att prestera ganska effektivt, med användning av mindre beräkningstid i vissa fall, samtidigt som den fortfarande genererar väglängder nära D* Lite. En signifikant skillnad mellan algoritmerna var mängden variation i resultaten, där simulated annealing hade mer spridning. D* Lite presterade mer konsekvent med avseende på både väglängd och beräkningstid, utan risk för att generera en väg långt från en optimal lösning.