基于启发式算法的移动机器人全局路径规划系统设计.doc

摘要:本次毕业设计首先是对图搜索技术进行了详细地了解，但是其寻路的效果往往很差，搜索了大量不是最终路径的节点，浪费了很多时间和成本。所以基于此基础，学习了目前在寻路领域中最常用的启发式搜索算法，并且详细地介绍了一种智能性更高的A*算法，包括其原理和具体的搜索过程。深入学习并领会了其中心思想，即估价函数。然后提出了两种不同的估价函数，即曼哈顿距离公示和对角线距离公示，并且展示了相应的搜索路径。最后提出了能够考虑安全性的A*算法，并且成功地实现了路径的规划。

在编程程序中，移动机器人的全局路径用20*20的矩形方格来模拟，并且用不同的颜色方格代表不同的功能。编程程序分别展示了曼哈顿距离公式作为估价函数的搜索路径，对角线距离公式作为估价函数的搜索路径以及和障碍物保持一定距离的搜索路径。此外，还展示了相应的搜索路径和搜索时间。

关键词：图搜索；A星算法；移动机器人；全局路径规划

目录

摘要

Abstract

1.绪论-1

1.1研究背景和意义-1

1.2移动机器人的研究现状-1

1.3移动机器人的发展前景-2

1.4论文的研究工作和组织结构-2

1.4.1本文的研究工作-2

1.4.2本文的组织结构-3

2.搜索理论技术-4

2.1图搜索的理论介绍-4

2.2启发型搜索算法-4

2.2.1启发信息-5

2.2.2估价函数-5

2.3 A*算法-6

2.3.1 A*算法原理-6

2.3.2 A*算法的搜索过程-6

2.4本章小结-8

3.启发函数的优化-9

3.1估价函数的选取-9

3.1.1曼哈顿距离的介绍-9

3.1.2对角线距离的介绍-10

3.2基于安全性的估价函数-11

3.3本章小结-11

4.编程实验与结果分析-12

4.1编程平台简介-12

4.2编程操作说明-12

4.3标准A*算法的编程结果-14

4.3.1曼哈顿距离的编程结果-14

4.3.2对角线距离的编程结果-15

4.3.3考虑安全性的曼哈顿距离公式编程结果-16

4.3.4考虑安全性的对角线距离公式编程结果-17

4.3.5增大安全距离的曼哈顿距离公示编程结果-18

4.3.6增大安全距离的对角线公式编程结果-19

4.4本章小结-20

结    论-21

参 考 文 献-22

致    谢-23