车辆导航系统的核心是路径规划算法，路径规划算法分静态路径规划（Static Path Planning， SPP）算法和动态路径规划（Dynamic Path Planning， DPP）算法，SPP的不足是不能对实时变化交通信息做出快速响应，而DPP则可以利用路网中实时更新的交通信息及时地为驾驶者提供更佳的导航路线。本文在研究了静态路径规划中用到的一些算法后，如A*算法，继而分析动态路径规划的一些思想，在此基础上分析D*Lite算法可以改进的地方，并给出优化后的算法程序。利用10×10、50×50、100×100三种规模的模拟路网做对比实验，实验表明优化后的D*Lite算法在速度上有了较大提高。

D* Lite并不基于原始的D*或有焦点的D*，而是实现相同的行为。它更容易理解，可以用更少的代码行实现，因此被称为“D* Lite”。就表现而言，它和专注的D*一样好，甚至更好。D* Lite基于终身计划A*，由科尼格和利哈乔夫在几年前推出。

D * -Lite类 该软件是D * -Lite算法的实现，如[Koenig，2002]中所述。 这是非优化版本，如本文图5所述。 在下面的第3节中说明了对该算法所做的一些小改进。 该资源是根据GNU通用公共许可证版本3（2007年6月29日发布）发布的，该版本可在以下获得： ： 请注意，这是一个早期版本，该软件仍然存在一些小错误。 运行dstar测试程序： 您需要先安装OpenGL / GLUT库，然后才能运行。 但是您不需要他们在自己的程序中使用Dstar类。 $ tar -xzf dstar.tgz $ cd dstar $ make $ ./dstar 指令 [q / Q]-退出 [r / R]-重新计划 [a / A]-切换自动重新计划 [c / C]-清除（重新启动） 鼠标左键-使单元格不可遍历（成本-1） 鼠标中键-将目标移至单元格 右键单击-将开始移至单元

采用D*Lite算法规划出的路径并不平滑,且预规路径与障碍物均十分接近.除此之外,在动态环境下时,由D*Lite算法重规划得到的路径也离障碍物距离很近,十分容易发生碰撞.针对此问题,引入懒惰视线算法与距离变换相结合的方法改进D*Lite算法.首先,对地图进行距离变换,并引入距离值的启发式代价,使得距离障碍物较远的节点优先被选择.然后,在扩展节点时引入视线算法,增加本地父亲节点和远程父亲节点的概念,使得路径不局限于八邻域扩展,从而进化为任意角度路径规划算法;最后,在遇到未知障碍物时进行局部距离变换,结合启发距离值信息进行重规划,使得重规划得到的路径远离突现的障碍物.仿真实验表明,在不同环境下规划所得到的路径均十分平滑与安全.

DStarLite_Unity2019.3.4项目 链表+ 堆.rar