Improving Dynamic Navigation Algorithms
Weiya Yue · OhioLink ETD Center (Ohio Library and Information Network) · 2013
Navigation algorithms for advanced autonomous vehicles, such as an unmanned automobile or airplane, require improved response times to complete numerous tasks that are still only imagined.Existing navigation algorithms tend to be incremental, do not take full advantage of accumulated information to compute a next move, and tend to be too eager in recomputing much information when a new optimal path must be found.The result is unnecessary per-round state recalculations that slow the algorithms considerably.The formalization of a general framework for dynamic planning algorithms, aimed at eliminating such recalculations by considering the relationship between optimal solutions between rounds, is proposed.The framework is based on our successful work which improved the speed of the well-known D*lite algorithm by up to eight times.The expected direct result of this research is to improve the performance of navigation algorithms in various terrains.As an example, the framework is applied to the Anytime D* algorithm, a variant of D*Lite, to get a new algorithm, called IAD*, which is an order of magnitude faster than Anytime D*.Moreover, the IAD* algorithm and the AWA* algorithm are combined to form another Anytime variant, and another new dynamic anytime algorithm, called DAWA*, the first dynamic anytime algorithm able to utilize time resource continuously.These improvements show the extensibility and robustness of the proposed framework.i