基于限定Delaunay三角剖分的移动机器人路径规划

摘要

本文对移动机器人路径规划算法的研究状况进行了归纳总结,指出了各算法的性能差异和优缺点。全面阐述了路径规划中常用的启发式搜索算法,重点介绍了A*、D*、D*Lite和LRTA*这四种基本的启发式搜索算法。设计了启发式搜索算法仿真平台,并在此平台下对以上四种算法进行了分析,评价其搜索思想,比较其优缺点。 接着,本文阐述了基于限定Delaunay三角剖分的移动机器人路径规划算法。该算法首先用限定Delaunay三角剖分把环境三角化,然后将A*和D*Lite路径搜索算法扩展到了三角形环境中,分别用于静态和动态环境中搜索路径。为了克服三角形形状不规则所造成的非最优路径,充分考虑到了相邻三角形的几何位置关系和机器人当前位置和目标点的几何位置关系,设计了搜索节点构造规则,该方法能够保证搜索到一条最优或近似最优的无碰撞路径。本文还提出了一种动态三角剖分方法,该方法能够满足动态搜索算法的需要,保证大部分搜索节点可以重新利用,而且还可以快速重新剖分环境。与传统的栅格法相比,本文所述的算法属于精确单元分解法,能够完全表达外界环境,环境包含的搜索节点数要少,需要更少的存储数据空间。而且本文所述算法找到的是一条从起点到目标点的“通道”,便于应用运动控制算法。理论分析证明了本算法的正确性和完整性,仿真实验表明了本算法的有效性和最优性。 最后,本文将离散的三角形环境空间当作离散系统,机器人的速度的连续变化当作连续系统,构造一个统一框架,即混杂系统。路径规划算法用于在三角化的环境中找到一个最优的三角形序列,运动控制算法用于操纵机器人在最优的三角形序列中安全、最优、平滑地从起点运动到目标点,将两者结合组成三角仿射混杂系统。

目录

文摘

英文文摘

声明

第1章绪论

1.1课题研究意义

1.2移动机器人路径规划算法研究综述

1.2.1路图法

1.2.2单元分解法

1.2.3势场法

1.2.4智能化路径规划方法

1.3文章主要内容

1.3.1本文的研究思路

1.3.2文章的结构安排

第2章启发式路径搜索算法的仿真与分析

2.1启发式路径搜索算法综述

2.2算法简介

2.2.1 A*算法

2.2.2 D*算法

2.2.3 O*Lite算法

2.2.4 LRTA*算法

2.3算法仿真与分析

2.3.1仿真软件设计

2.3.2 A*与D*、D*Lite的比较分析

2.3.3 D*与D*Lite的比较分析

2.3.4 LRTA*与A*、D*、D*Lite的比较分析

2.4本章小结

第3章基于限定Delaunay三角剖分的路径规划算法

3.1 Delaunay三角剖分

3.1.1 Delaunay三角剖分简介

3.1.2限定Delaunay三角剖分

3.2构造搜索节点

3.3静态搜索

3.4动态搜索

3.4.1动态环境下的Delaunay三角剖分

3.4.2增量启发式搜索算法

3.5算法分析与证明

3.5.1算法最优性分析

3.5.2算法证明

3.6仿真实验

3.7本章小结

第4章基于三角仿射混杂系统的运动控制算法

4.1混杂系统简介

4.2三角仿射混杂系统运动控制算法

4.2.1混杂系统建模

4.2.2运动控制算法

4.3仿真实验

4.4本章小结

结论

参考文献

攻读硕士学位期间发表的学术论文

致谢