基于A*搜索算法的改良算法介绍
[TOC]
项目实践中使用 Hybrid A*算法(关于图搜索算法的介绍博文)搜索粗轨迹的时候, 由于搜索过程太耗费资源加上很多时候不需要每时每刻进行搜索. 因此需要决定什么时候才会 replan, 提升效率. 本篇文章为调查的总结. 该系列算法都是对 A* 的改进, 都是出自 Likhachebv Maxim 教授或者 Sven Koenig 教授的研究成果.
如果对 A* 搜索改进算法感谢的同学也可以关注这两位大牛的主页, 里面有很多教程以及研究结果, 演示软件等.
Likhachebv Maxim 教授的主页 :http://www.cs.cmu.edu/~maxim/
Sven Koenig 教授的主页: http://idm-lab.org/project-a.html
Likhachebv Maxim 教授研究室还研发出了开源的 SBPL C++ 算法库. 支持在ROS中使用, 不仅包含执行代码,还 包括可视化与 debug 的功能.
SBPL 的代码库, ROS wiki. 支持的搜索算法: ARA*, Anytime D*, ANA*, R* , Multi-Heuristic A*.
回到本文内容, 共介绍了 anytime 类: ARA* (Anytime Repairing A*), Incremental类: LPA* (Lifelong Planning A*),FSA*(Fringe-Saving A*),D* Lite.
