Block-Guided Theta* Path Planning Algorithm
Grid-based path planning is a widely discussed problem.Pre-existing algorithms always find paths with unrealistic looking(such as A*)or spend lots of effort expanding redundant vertices and thus causing time and memory waste(such as A*,A* with Post-Smoothing,Basic Theta* and Angle-Propagation Theta*).In this paper,we present Block-Guided Theta*,a variation of A* which expanding vertices in a more heuristic way.It significantly reduces the number of redundant vertex expansions and finds a even shorter path with less time and memory consumption.We compare Block-Guided Theta* with the former four existing algorithms,and although all these algorithms cant guarantee to find the real shortest path,we show experimentally that Block-Guided Theta* finds shorter path more quickly and memory economizing than other algorithms.
Path-planning Expanded Vertices Execution Time Memory Saving
Zi Yang Wensheng Yu
Shanghai Key Laboratory of Trustworthy Computing,East China Normal University,Shanghai 200062
国际会议
长沙
英文
3863-3868
2014-05-31（万方平台首次上网日期，不代表论文的发表时间）