基于三角网追踪的机器人路径规划

摘要

基于Voronoi图的路径规划方法计算复杂度高，安全性差，本文提出一种基于三角网追踪解决机器人路径规划的方法，通过三角网的值点追踪策略结合Dijkatra算法生成一条机器人最优路径。该方法无需随障碍物的移动而重构三角网格，可根据障碍物的大小选取特征值对路径进行优化。仿真结果表明，该方法有效地降低了计算复杂度，提高了路径的安全性。 按每个障碍物横切面的外接圆将障碍物量化为半径不同的圆，圆心放入点集，利用Delaunay三角剖分法生成三角网。在三角网格中，依据每条边上两顶点的特征值确定一个值点。三角网的值点追踪就是按照某种算法寻找一条路径，能够经过包括起始点在内的所有边上的值点。 值点追踪线进入网格时应正确选择初始边，一种方法以距离起始点最近的值点所在的边作为初始边，如果有两值点距离初始点相等且最近，优先考虑距离初始点较近的一条边作为初始边。另一种方法使用传统的动态规划方法进行初始边的选择，此方法可解决两个值点距离初始点相等且初始点距离值点所在的两条边亦相等的情况。 追踪线进入网格后，应选择网格的另两条边上的值点作为出口。追踪下一个值点的方法有两种：一种方法是为了较为准确的确定一条机器人行走的稳定路径，采用传统的Dijkstra算法。另一种方法是在精度要求不高的条件下，取另外两条边上的值点中距离目标点较近的一个作为下一个要追踪的值点。 实验结果表明，基于三角网追踪的机器人路径规划算法在保证拐角点数目的同时，降低了算法的计算复杂度，提高了路径规划的安全性，满足实时路径规划的需求。

目录

文摘

英文文摘

声明

第一章绪论

1.1引言

1.2课题的提出、目的及意义

1.3国内外研究现状

1.4研究目标和主要研究内容

1.5论文的组织结构

第二章机器人路径规划

2.1引言

2.2机器人路径规划概述

2.2.1路径规划问题的描述

2.2.2路径规划的分类及特点

2.3机器人路径规划的基本问题

2.3.1世界空间到位姿空间中的转换

2.3.2位姿空间的计算方法

2.3.3物体信息的获取和表示

2.3.4搜索方法

2.3.5路径规划中的碰撞检测

2.4传统路径规划方法

2.4.1可视图法

2.4.2自由空间法

2.4.3栅格解耦法

2.4.4人工势场法

2.5智能路径规划方法

2.5.1模糊逻辑法

2.5.2神经网络法

2.5.3人工蚁群法

2.5.4遗传算法

2.6本章小结

第三章基于Voronoi图的机器人路径规划

3.1引言

3.2 Voronoi图的生成方法概述

3.3 Voronoi图的广泛应用性

3.4 Voronoi图和平面点集的三角剖分

3.4.1基本定义

3.4.2平面点集的Voronoi图生成方法

3.4.3平面点集上的三角剖分

3.5 Voronoi图法机器人路径规划策略

3.5.1基于Voronoi图理论的环境建模

3.5.2机器人运行环境预处理

3.5.3基于Voronoi图的机器人路径规划仿真

3.5.4 Dijkstra最短路径搜索算法

3.6本章小结

第四章基于三角网追踪的机器人路径规划

4.1引言

4.2 Delaunay方法基本原理

4.2.1 Voronoi图与Delaunay三角网(Delaunay Triangulation)的基本概念

4.2.2 Delaunay三角网的重要性质

4.3 Delauany三角网生成算法

4.3.1分治算法

4.3.2逐点插入法

4.3.3三角网生长法

4.4三角网值点追踪

4.5基于三角网追踪的机器人路径规划

4.5.1算法思路

4.5.2算法描述

4.5.3算法优点

4.5.4基于三角网追踪的机器人路径规划仿真

4.6本章小结

第五章基于三角网追踪的机器人路径规划的实现

5.1数据结构

5.2实验环境

5.3实验流程图

5.3.1基于Voronoi图的机器人路径规划方法流程图

5.3.2基于三角网追踪的机器人路径规划方法流程图

5.4实验对比分析

5.4本章小结

第六章总结与展望

参考文献

攻读硕士学位期间取得的学术成果

致谢