可变环境下的快速全局路径规划

论文总字数：22603字

摘 要

路径规划是很多领域的研究热点，具有很高的科研和应用价值。本课题是基于热法的一个快速全局路径规划，热法是表面上一个热点随着时间向周围扩散热量，从中可以得到温度梯度，经过归一化处理得到单位向量场，最后用梯度和归一化所得向量场相同的函数计算出距离。我们需要给程序录入地图信息并对地图进行三角剖分，计算每个三角形中的梯度找出距离下降最快的方向。给定起始点和终点后根据三角形的梯度可以得到两点的最优路径和距离。热法可以通过设置不同的参数来调整规划的路径来满足一些实际中的要求，例如使路径尽量短或者尽量避开边界（墙壁）。通过录入不同的地图、设置不同的起始点和终点以及修改算法中的参数对规划的路径进行对比。实际中的的环境是可变的，所以我们也要考虑变化的环境。与传统路径规划不同的是，本课题旨在研究如何提高环境变化下的路径规划计算效率。

关键词：可变环境，路径规划，近似测地距离，热传导方程

Fast Global Path Planning In A Varying Environment

Abstrat

Path planning is a hot research topic in many fields, which is of high value in scientific research and application. We study the fast global path planning based on heat method in this work. Heat method describes that a hot source on the surface spread heat as time goes by, from which we can get the temperature gradient. And then we normalize the temperature gradient to get a unit vector field. Finally we calculate the distance with a function which has the same gradient as the unified temperature gradient. We need the boundary information of the map and then triangulate the boundary. the fastest decline of distance is found by computing the gradient of each triangle. With the given starting point and end point and finally, we can get the optimal path according to the gradients. Heat method can be used to set different parameters to adjust the planning path to meet some practical requirements, for example, make the path as short as possible, or try to avoid the boundary (wall). We also compare the path by inputting different maps, setting different starting points and endpoints, as well as modifying the parameters in the algorithm. The actual environment is changeable, so we should consider the change of the environment. Different from the traditional path planning, this paper aims to study how to improve the efficiency of path planning under environmental change.

Key Words: Variable Environment, Path Planning, Approximate Geodesic Distance,

Heat Equation

目 录

摘要………………………………………………………………………………………………Ⅰ

Abstract…………………………………………………………………………………………Ⅱ

第一章 绪论………………………………………………………………………………………1

1.1概述………………………………………………………………………………………1

1.1.1路径规划定义……………………………………………………………………1

1.1.2国内外研究现状…………………………………………………………………1

1.2全局路径规划算法……………………………………………………………………2

1.2.1可视图法…………………………………………………………………………2

1.2.2自由空间法………………………………………………………………………2

1.2.3栅格法……………………………………………………………………………2

1.2.4拓扑法……………………………………………………………………………3

1.2.5概率路径图法……………………………………………………………………3

1.2.6蚁群算法…………………………………………………………………………3

1.3 局部路径规划算法………………………………………………………………………3

1.3.1人工势场法………………………………………………………………………3

1.3.2模糊逻辑算法……………………………………………………………………4

1.3.3模拟退火算法……………………………………………………………………4

1.3.4遗传算法…………………………………………………………………………4

1.4本文内容简介……………………………………………………………………………5

1.5章末小结…………………………………………………………………………………5

第二章 热法………………………………………………………………………………………6

2.1介绍………………………………………………………………………………………6

2.2时间离散…………………………………………………………………………………7

2.3空间离散…………………………………………………………………………………7

2.3.1单一网格…………………………………………………………………………7

2.3.2多边形表面………………………………………………………………………8

2.3.3点云……………………………………………………………………………8

2.4边界条件和时间步长…………………………………………………………………9

2.5热法评价 ………………………………………………………………………………9

2.5.1性能……………………………………………………………………………9

2.5.2精度……………………………………………………………………………9

2.5.3稳定性…………………………………………………………………………10

2.6 章末小结………………………………………………………………………………10

第三章 软件实现…………………………………………………………………………………11

3.1简介……………………………………………………………………………………11

3.2算法流程………………………………………………………………………………11

3.2.1环境建模………………………………………………………………………11

3.2.2规划方法………………………………………………………………………12

3.2.3路径搜索策略…………………………………………………………………13

3.3实验结果………………………………………………………………………………14

3.3.1变化参数………………………………………………………………………15

3.3.2变化环境………………………………………………………………………15

3.3.3其他地图模型…………………………………………………………………16

3.4 影响因素………………………………………………………………………………17

3.5 章末小结………………………………………………………………………………17

第四章 总结与展望………………………………………………………………………………18

4.1 总结……………………………………………………………………………………18

4.2 展望……………………………………………………………………………………18

参考文献…………………………………………………………………………………………20

第一章 绪论

1.1概述

剩余内容已隐藏，请支付后下载全文，论文总字数：22603字