کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
380841 | 1437460 | 2013 | 11 صفحه PDF | دانلود رایگان |
This paper introduces a novel variant of the A⁎ path planning algorithm, which we call Light-assisted A⁎ (or LA⁎ for short). The LA⁎ algorithm expands less nodes than A⁎ during the search process, especially in scenarios where there are complex-shaped obstacles in the path between the start and goal nodes. This is achieved using the concept of (virtual) light which identifies and demotes dead-end paths blocked by obstacles, thus ensuring that the search stays focused on promising paths. Three path planning problems are used to test the performance of LA⁎. These include path finding in a grid cluttered by randomly placed obstacles, robot navigation in a map containing multiple solid walls, and finally mazes. The results of these experiments show that LA⁎ can achieve orders of magnitude improvement in performance over A⁎. In addition, LA⁎ results in near-optimal solutions that are very close to the optimal path obtained by the conventional A⁎ algorithm.
Journal: Engineering Applications of Artificial Intelligence - Volume 26, Issue 2, February 2013, Pages 888–898