复杂三维环境中的路径规划方法(翻译)

《复杂三维环境中的路径规划方法(翻译)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、复杂三维环境中的路径规划方法晏飞刘一莎肖继忠摘要：本文介绍了在复杂环境中的无人机（UAV）三维路径规划算法。在该算法中，环境是由八叉树算法分为体素。为了满足UAV的安全要求，自由空间被自由体素，其具有足够的空间余量为UAV穿过表示。边界框数组在整个三维空间来评价自由体素连通创建。概率路线图方法（PRM）由边界框阵列中随机抽样改进，以确保路线节点的在3D空间中的更有效的分配。根据连接评估，路线图是用来通过使用A*算法来规划的可行路径。实验结果表明，该算法在复杂的3D环境有效。关键词：3D路径规划，复杂的环境中，无人机（UAV），概率路线图法（PR

2、M），八叉树1引言近年，无人机（UAV）正被越来越多地用于许多领域，如消防[1]，救灾难度太大或危险的任务[2]，搜救[3]，目标跟踪[4]，以及面向空间的应用[5]。对于这些应用，所述UAV应计划在其工作空间中的非碰撞路径的能力。路径规划的中心问题是根据一些规定诸如能源，时间和安全性，以产生从初始点到目标点与障碍物的环境中的无冲突路径和优化路径[6]。规划算法已经开发几十年。在[7]中，波前算法被用作路径规划三维正态分布变换（3D-NDT）地图。这个算法是直观的，易于实现，但它会无法找到在复杂环境中的最佳路径。在另一方面，A*（见[8-10]

3、）是找到一个给定的起始节点到目的节点的最低成本路径最佳优先启发式搜索算法。不幸的是，随着工作空间变得越来越大，所花费的时间以指数寻找最优路径的增加[5]。路线图通常适用于帮助这些启发式搜索算法，这往往是在配置空间表示。各种路线图的方法已被用于如能见度线[11]，虚拟力[9]，迅速-探索随机树木[12，13]和概率路线图方法（PRM）[14]。路径规划将在3D环境中，这是特别是在复杂的环境中的一大挑战来进行。通常用于高维配置空间的方法是基于基于采样的方法，包括在PRM[15,16]和它的变体。PRM有两个阶段：一个学习阶段和一个查询相[15]。在

4、学习阶段，一个数据结构被称为路线图被构造为给定的场景。该路线图是一个无向图R(N,E)。N为一组节点，这是随机无冲突配置空间采样点。有前途的节点对被选择在图表和一个本地筹办被用于尝试这种安排有边缘连接。如果它们可以被连接，则该边缘加到大肠杆菌好的图形ř应覆盖自由空间很好。在查询阶段中，路径通常是由路径查询诸如Dijkstra算法或A*找到。基本PRM的瓶颈在于它在寻找通过狭窄的通道路径很麻烦。使太少节点被放置在狭窄的通道，这是由于在自由空间中的随机抽样的节点。一个解决方案是增加接近障碍物边界[17，18]的配置。虽然这种方法增加取样狭窄的通道

5、节点的概率，在狭窄的通道以外的许多节点不改善路线图的连通性帮助。Hsu等人[19，20]提出一种混合策略：桥试验在狭窄的通道施加增加采样密度，它也使用了在开放的自由空间均匀的采样策略。在文献[21]中，作者用一个慵懒的显著边缘算法在尚未导航区域来放置新样本改善慵懒的概率路径规划。在这些方法中，环境的障碍是由几何模型呈现。但在实践中，实际的实验环境不能由几何模型描述。对于复杂的3D场景，最流行的表示是三维点群[22-27]或体素[28，29]。当使用基本PRM或变种以上这些3D表示所提到的，碰撞检查是因为障碍物（点或体素），数量庞大沉重的计算负担

6、。为了解决这个问题，细胞分解是一种可以把自由空间到子空间的好选择。该方法是由伯格和奥维马斯[30]为指导采样向现场最有趣的地区分离大开放的区域[31]。提出了完整的运动计划，结合近似细胞分解与PRM混合的方法。但在这些方法，碰撞检查用于获得路线图构成的无碰撞的本地路径也复杂3D环境的一个大问题。在本文中，我们提出了基于三维复杂环境下的无人机路径规划PRM方法的算法。环境可以通过激光扫描仪捕获的3D点云来表示。然而，从激光扫描器的原始数据为任何路径规划算法实时实现望而却步巨大。因此我们使用八叉树算法来划分作业空间成体素，这是环境的3D网格表示。以

7、提取用于UAV导航自由空间，我们记录期间八叉树生成过程的中心点和自由体素尺寸。路径规划的最小自由体素的尺寸被设定为比UAV的物理尺寸较大，以确保它能够通过通路安全。最终路径连接自由体素的序列。为了应对窄通道问题，环境等分为称为边界框几个子区域。从我们以前的论文[32]不同，则节点随机从游离体素中的每个边界框根据自由和占用的体素的体积比采样。游离体素的连通性的评价在每个边界框进行。那么局部规划将搜索边界框节点无碰撞路径。为了使路线图覆盖整个可用空间，则加入另外的边界框重叠相邻边界框在相邻的区域中的局部路线图的连接评估。最后，我们使用A*方法从开始

8、搜索素在路线图的目标体素路径。我们已经实现了该算法在实际户外环境中，由3D点云表示。在本文的其余部分安排如下：第二节介绍了复杂的3D环境表示。第3节介