动态环境中的无人机路径规划研究

摘要

路径规划是无人机自主任务规划的关键技术之一。好的路径规划方法可以降低无人机任务油耗、提高无人机生存能力。本文以无人机为研究对象，采用基于采样的方法，研究了动态环境中的无人机路径规划问题。本文的研究工作和创新点简述如下：
　　1．针对环境建模提出了一种对不同类型障碍物分别处理的方法。基于采样的方法采用基本构型近似表示环境中的障碍物，而地形障碍采用基本构型近似表示会丢失大量的信息。为了更好的表示环境信息，将地形障碍与其他障碍物分开处理，用基本构型近似表示障碍物，而直接采用栅格法表示地形信息，然后采用基于采样的方法对环境信息进行综合。
　　2.为了提高概率地图法在含有窄通道的环境中的效率，提出了一种改进的路线图构造方法。好的采样策略可以用较少的采样点完成对自由空间的覆盖并能很好的描述其连通性，目前的采样策略需要补充采样来达到联通窄通道的目的。为了提高采样效率，在分析已有各种算法优缺点的基础上，通过引入人工势场法的思想，提出了一种改进的概率地图法，使得算法对不同的环境都能具有较好的适应能力。仿真研究表明，改进算法能够在窄通道中得到足够的采样点，对不同的环境具有更强的适应性。
　　3．对于蚁群算法在概率地图中的应用，引入了一种新的启发信息，并对信息素的更新机制进行了改进。在蚁群算法的基础上，将方向信息作为启发信息引入蚁群算法，并采用基于排序的信息素更新机制，使蚂蚁更倾向于搜索目标所在的方向。仿真结果表明，新的启发信息能够极大的提高算法的搜索效率。其次，修改了蚁群算法的信息素更新规则，使其可以同时优化多个目标。最后，通过引入Pareto解集，播撒不同种类的信息素，使蚁群算法可以同时优化路径长度和威胁大小两个目标，并能得到一组非支配解，有利于决策者选择合适的路径。
　　4．对D*Lite算法在概率地图中的应用，引入了无人机约束，改进了信息更新机制，修改了距离和启发函数计算方法。D* Lite算法得到的路径没有考虑无人机的约束，可能会不满足无人机可飞的要求，因此在D* Lit e算法搜索可行节点过程中加入了无人机的约束，去除了不满足约束的节点。部分突发威胁没有出现在无人机的当前路径上，对无人机没有影响，这种情况下不需要重新规划路径，因此对D* Lit e算法作了改进，将不必要的信息更新延迟到需要时进行。为了避免得到的路径在不同高度间频繁切换，增大了算法距离公式和启发函数公式中高度的权重。仿真结果表明，改进的D* Lite算法得到的路径可以满足无人机约束要求，搜索到的路径更平滑，避免了飞机高度的频繁切换。
　　5．提出了一种改进的快速随机搜索树方法。针对含有窄通道环境中的搜索树构建问题，通过引入采样点的移动，将落在障碍物上的采样点移动到窄通道中，提高了路径搜索效率。为了实现突发威胁情况下的快速重规划，将快速随机搜索树方法和D* Lite算法相结合。通过利用搜索树构建中得到的信息，D*Lite算法可以快速生成替代路径。仿真结果表明，改进的快速随机搜索树方法可以用更少的采样点搜索到路径，当出现突发威胁时能更快的得到替代路径。
　　6．对于动态环境中的路径规划问题，提出了一种引入时间轴的方法。为了表示运动障碍物在所有时刻的可能位置，在构型空间基础上引入时间轴，将构型空间扩展为构型-时间空间。然后提出了两种构型-时间空间中的路径规划方法：直接在构型-时间空间中采样然后构建路线图并进行路径生成的直接搜索法，和先在构型空间中构建路线图然后在构型-时间空间中搜索的两步法，解决了包含动态障碍物的环境中的最短路径问题和给定到达时间条件下的路径规划问题。在路径生成阶段，提出了一种改进的蚁群算法，通过对蚂蚁的引导使蚂蚁在初始搜索路径时更有针对性。仿真结果表明，构型-时间空间可以解决动态环境的表示问题，改进蚁群算法可以更快的收敛到全局最优解。
　　7．针对动态环境中的路径重规划问题，将快速随机搜索树方法应用到构型-时间空间中，并作了改进。在构建搜索树时，动态添加采样点时间维坐标，并保存计算得到的路径段结果，动态规划时引入排序机制并利用已有的路径段快速构建搜索树，提高了算法在动态规划中的效率。仿真结果表明，在出现突发移动威胁后动态快速搜索随机树算法可以更快的找到替代路径。

目录

封面

中文摘要

英文摘要

目录

第一章 绪论

1.1无人机路径规划研究背景及意义

1.2 路径规划研究现状

1.3 PRM方法研究现状

1.4 RRT方法研究现状

1.5 动态环境中的路径规划研究现状

1.6 本文研究内容及章节安排

1.7 本章小结

第二章 环境建模与碰撞检测

2.1 凸多边形障碍物

2.2 圆形障碍物

2.3 凸多面体障碍物

2.4 球体障碍物

2.5 圆柱体障碍物

2.6 圆锥体障碍物

2.7 地形障碍

2.8 本章小结

第三章 概率地图法及其改进

3.1 采样源研究

3.2 采样策略

3.3 本章小结

第四章 蚁群算法

4.1 概述

4.2 蚁群算法的基本思想

4.3 蚁群算法模型

4.4常用改进蚁群算法

4.5 一种引入方向信息的蚁群算法

4.6 多目标蚁群算法

4.7 一种多路径蚁群算法

4.8 本章小结

第五章 D*Lite算法

5.1 D*Lite算法

5.2 一种改进的D*Lite算法

5.3 本章小结

第六章 快速随机搜索树方法及其改进

6.1 RRT算法

6.2 RRT*算法

6.3 一种改进的RRT*算法

6.4 双树RRT*算法

6.5 一种三维环境中的RRT*算法

6.6 结论

第七章 动态环境中的路径规划

7.1 CT空间

7.2 直接CT空间搜索法

7.3 两步法

7.4 未知动态环境中的路径规划

7.5障碍物部分已知的路径规划

7.6 本章小结

第八章 基于RRT*算法的动态路径规划

8.1 规划环境模型

8.2 一种动态RRT*算法

8.3 目标移动情况下的路径规划

8.4 一种基于RRT*算法的四维路径规划方法

8.5 本章小结

第九章 总结与展望

9.1 本文工作总结

9.2 研究工作展望

参考文献

致谢

攻读博士学位期间发表的学术论文和参加科研情况

声明