本文为美国马里兰大学（作者：MatthewDavid Solomon）的硕士论文，共95页。

无人机经常在部分或完全未知的环境中飞行。当无人机穿越环境并检测到新的障碍物时，路径的快速重新规划对于避免碰撞至关重要。本文提出了一种新的分层D* Lite（HD*）算法，该算法将增量D* Lite算法与一种新的分层路径规划方法相结合，能够快速地重新规划路径，实现实时操作。与当前的分层规划算法不同，HD*在规划新路径之前不需要进行地图更正。定向成本比例因子、路径平滑和Catmull-Rom样条用于确保生成的路径是可行的，但HD*牺牲了实时性能的最佳特性，其计算时间和路径质量取决于地图大小、障碍物密度、传感器范围以及对规划时间的限制。对用于测试的最复杂场景，HD*在35毫秒内找到了10%的最佳路径。

Unmanned aerial vehicles (UAVs) frequentlyoperate in partially or entirely unknown environments. As the vehicle traversesthe environment and detects new obstacles, rapid path replanning is essentialto avoid collisions. This thesis presents a new algorithm called HierarchicalD* Lite (HD*), which combines the incremental algorithm D* Lite with a novelhierarchical path planning approach to replan paths sufficiently fast forreal-time operation. Unlike current hierarchical planning algorithms, HD* doesnot require map corrections before planning a new path. Directional cost scalefactors, path smoothing, and Catmull-Rom splines are used to ensure theresulting paths are feasible. HD* sacrifices optimality for real-timeperformance. Its computation time and path quality are dependent on the mapsize, obstacle density, sensor range, and any restrictions on planning time.For the most complex scenarios tested, HD* found paths within 10% of optimal inunder 35 milliseconds.

1 引言

2 项目背景

3 已有算法回顾

4 将算法扩展到三维场景

5 提升路径质量的方法

6 提升算法性能的途径

7 实验结果

8 未来研究工作展望与结论

附录A HD*算法伪码

更多精彩文章请关注公众号：