Delaunay三角网格-栅格地图下移动机器人路径规划方法

摘要

本发明公开一种Delaunay三角网格‑栅格地图下移动机器人路径规划方法，首先采用栅格法和Delaunay三角网格剖分法建立地图模型，将连续的可行域离散为三角网格和正方形栅格的结合，用Delaunay三角网格‑栅格地图的节点集合建立赋权有向循环图，然后根据赋权有向循环图用Dijkstra搜索算法搜索从起始点到终点的所有目标点，最后采用启发式算法提取目标点中的关键路标，得到机器人的最终路径。本发明方法能够根据机器人所处运行环境的障碍物位置的不同，找到规划的机器人的无碰撞移动路径，与实际更相符。

说明书

技术领域

本发明涉及路径规划领域，尤其涉及一种Delaunay三角网格-栅格地图下移动机器人路径规划方法。

背景技术

机器人路径规划是机器人研究的一个重要领域，也是机器人技术的重要组成部分。尽管智能机器人技术已经广泛的应用到各种领域，但是在路径规划和地图构建等方面仍然存在着难以攻克的难题。针对智能机器人在实施探测任务时，在实际复杂地形行驶中，实现从起始点到终点之间的最优路径，并减少其工作代价。

为此本发明给出一种Delaunay三角网格-栅格地图下移动机器人路径规划方法，为得到最优的无碰撞路径，建立的Delaunay三角网格-栅格地图模型，让其能够无碰撞地通过长而窄的通道，与实际情况更相符，为移动机器人逃脱各种障碍，规划最优路径提供了一种新思路。

发明内容

本发明的目的在于提供一种Delaunay三角网格-栅格地图下移动机器人路径规划方法，用于实现从起始点到终点之间的最优路径，并减少其工作代价。

为了达成上述目的，本发明的解决方案是：

Delaunay三角网格-栅格地图下移动机器人路径规划方法，包括以下步骤(1)～(6)：

步骤(1)：设机器人工作区域为D，D为一个L1*L2的二维平面空间，根据平面空间中障碍物的分布情况，将平面空间分为可行域和不可行域，障碍物为随机分布，个数为K个；

步骤(2)：按照步骤(1)中地图规模及各障碍物的分布情况，用栅格法将平面空间划分为规则的栅格地图，并将栅格地图划分为障碍物栅格与可行域栅格；

步骤(3)：基于步骤(2)中所建的栅格地图，使用Delaunay三角网格剖分法，以障碍物为三角形顶点，建立Delaunay三角网格-栅格地图，将所建地图中的节点及三角网格-栅格剖分所得的单元进行编号，并将节点编号转为节点坐标；

步骤(4)：利用步骤(3)中所建的Delaunay三角网格-栅格地图，对三角网格-栅格剖分所得的单元进行组装，将单元矩阵元素按照Delaunay三角网格-栅格地图中的节点的编号放到整体节点关联矩阵中，用Delaunay三角网格-栅格地图的节点集合建立赋权有向循环图；并将节点分为Delaunay三角网格地图节点和有障碍物的栅格地图节点；

步骤(5)：根据步骤(4)中的赋权有向循环图，确定任意初始位姿点E

步骤(6)：根据步骤(5)中算法搜索得到的目标点，采用启发式算法提取目标点中的关键路标U

2、本发明的Delaunay三角网格-栅格地图下移动机器人路径规划方法，所述步骤(2)、(3)中用栅格法及Delaunay三角网格剖分法将连续的可行域离散为正方形网格和三角网格组合体，其中，三角形剖分的地图用节点矩阵及单元连接矩阵表示，记剖分后的可行域有b个节点和f个单元，第i个节点P

3、本发明的Delaunay三角网格-栅格地图下移动机器人路径规划方法，所述步骤(4)将单元矩阵元素按照相关节点的编号放到整体节点关联矩阵中，基于三角网格建立赋权有向循环图，需要对各个单元进行组装，组装过程就是将单元矩阵元素按照相关节点的编号置放到整体节点关联矩阵中。由于只有在同一单元中相关联的节点才会在整体关联矩阵相应的行及列中出现，则在整体矩阵中，必然会存在大量的零矩阵，故整体矩阵为稀疏矩阵。由单元连接矩阵，构造节点关联矩阵T与S，T＝[t

4、本发明的Delaunay三角网格-栅格地图下移动机器人路径规划方法，所述步骤(5)中从权利要求1中步骤(4)得到的Delaunay三角网格地图节点和有障碍物的栅格地图节点，作为关键性路标。所述步骤(6)中使用启发式函数，在关键性路标中得到一条最优路径。

附图说明

图1为Delaunay三角网格-栅格地图下移动机器人路径规划方法流程图。

图2为Delaunay三角网格-栅格地图下移动机器人路径规划结果

具体实施方式

下面结合附图对本发明的技术方案进行进一步说明：

本发明提供Delaunay三角网格-栅格地图下移动机器人路径规划方法，其总体思路为：

首先采用栅格法和Delaunay三角网格剖分法建立地图模型，将连续的可行域离散为三角网格和正方形栅格的结合，用Delaunay三角网格-栅格地图的节点集合建立赋权有向循环图，然后根据赋权有向循环图用Dijkstra搜索算法搜索从起始点到终点的所有目标点，最后采用启发式算法提取目标点中的关键路标，得到机器人的最终路径。本发明方法能够根据机器人所处运行环境的障碍物位置的不同，找到规划的机器人的无碰撞移动路径，与实际更相符。

如图1所示，本发明的Delaunay三角网格-栅格地图下移动机器人路径规划方法，具体实施包括以下步骤(1)～(6)：

步骤(1)：设机器人工作区域为D，D为一个L1*L2的二维平面空间，根据平面空间中障碍物的分布情况，将平面空间分为可行域和不可行域，障碍物为随机分布，个数为K个；

步骤(2)：按照步骤(1)中地图规模及各障碍物的分布情况，用栅格法将平面空间划分为规则的栅格地图，并将栅格地图划分为障碍物栅格与可行域栅格；

步骤(3)：基于步骤(2)中所建的栅格地图，使用Delaunay三角网格剖分法，以障碍物为三角形顶点，建立Delaunay三角网格-栅格地图，将所建地图中的节点及三角网格-栅格剖分所得的单元进行编号，并将节点编号转为节点坐标；

步骤(4)：利用步骤(3)中所建的Delaunay三角网格-栅格地图，对三角网格-栅格剖分所得的单元进行组装，将单元矩阵元素按照Delaunay三角网格-栅格地图中的节点的编号放到整体节点关联矩阵中，用Delaunay三角网格-栅格地图的节点集合建立赋权有向循环图；并将节点分为Delaunay三角网格地图节点和有障碍物的栅格地图节点；

步骤(5)：根据步骤(4)中的赋权有向循环图，确定任意初始位姿点E

步骤(6)：根据步骤(5)中算法搜索得到的目标点，采用启发式算法提取目标点中的关键路标U

以上实施例仅为说明本发明的技术思想，不能以此限定本发明的保护范围，凡是按照本发明提出的技术思想，在技术方案基础上所做的任何改动，均落入本发明保护范围之内。