摘 要

移动机器人是机器人领域的一个重要分支，广泛应用于工业、农业、军事等领域。而路径规划问题又是移动机器人研究领域的重要问题。近些年兴起了一类新型的优化算法称路径规划算法，该算法迅速发展成为机器人领域和人工智能领域的研究热点之一。

本文主要研究在已知环境信息下应用人工神经网络对机器进行全局路径规划。首先将环境信息进行建模并存储相应的环境信息，再通过RBF神经网络输出的信息判断机器当前所在位置距障碍物的距离，以此为起点搜索机器下一可能行驶点并得到距离函数，将其比较大小再选取后续的路径。文中还简要介绍了BP神经网络及BP算法，k-means聚类算法以及最小二乘法。最后对该方法在Microsoft Excel 2013与Visio 2010中进行模拟应用仿真，并与内螺旋全局规划算法模拟退火神经网络算法从时间，转弯次数，区域重复率，路径长度等方面进行比较。实验结果说明神经网络对机器进行路径规划具有一定的价值。

关键词：BP算法；RBF神经网络；全局路径规划；k-means聚类

Abstract

Mobile robots are an important branch of the robotics field and are widely used in industrial, agricultural, military and other fields. Path planning is an important issue in the field of mobile robot research. In recent years, a new type of optimization algorithm called path planning algorithm has emerged, which has rapidly developed into one of the research hotspots in the field of robotics and artificial intelligence.

This paper mainly studies the application of artificial neural network to global path planning of machines under known environmental information. Firstly, the environmental information is modeled and the corresponding environmental information is stored, and then the information output by the RBF neural network is used to determine the distance of the current location of the machine from the obstacle, thereby searching for the next possible driving point of the machine and obtaining the distance function. The comparison size then selects the subsequent path. The paper also briefly introduces BP neural network and BP algorithm, k-means clustering algorithm and least squares method. Finally, the simulation application simulation of this method in Microsoft Excel 2013 and Visio 2010 is carried out, and compared with the inner spiral global programming algorithm simulated annealing neural network algorithm, the time, the number of turns, the regional repetition rate and the path length. The experimental results show that the neural network has certain value for path planning of machines.

Key Words：BP algorithm；RBF neural network；global path planning；k-means clustering

目 录

第1章 绪论 1

1.1 课题研究背景、目的和意义 1

1.2 路径规划的基本问题 1

1.3机器路径规划方法研究现状 1

1.3.2 国内研究现状 2

1.3.2 国内研究现状 2

1.4 本文研究内容 3

第2章 神经网络概述 4

2.1神经网络定义及发展 4

2.2神经网络分类 5

2.2.1前馈神经网络 5

2.2.2反馈神经网络 6

第3章 路径规划方法 7

3.1局部路径规划 7

3.1.1 神经网络在路径规划中的应用 7

3.2全局路径规划方法 12

3.2.1环境模型建立 12

3.2.2内螺旋法 16

3.2.3栅格法 17

3.2.4模拟退火神经网络法 17

3.3用RBF神经网络表示环境信息 20

3.3.1 两阶段学习算法 22

3.4路径选择 25

第4章 实验数据分析 26

4.1 RBF神经网络路径输出 26

4.2 内螺旋法路径输出 29

4.3 模拟退火神经网络路径输出 29

4.4 各路径输出方案比较 31

第5章 结论 32

参考文献 33

致 谢 35

第1章 绪论

1.1 课题研究背景、目的和意义

我国水环境状况不容乐观，污染程度严重，整治水质迫在眉睫。以长江流域水质为例，根据中华人民共和国环保部2015-2017这三年发布的中国环境状况公报可知I类水质断面从3.8%到2.7%再到2.2%；II类水质断面从55.0%到53.5%再到44.3%；III类水质断面从30.6%到26.1%再到38.0%；IV类水质断面从6.2%到9.6%再到10.2%，V类水质断面从1.2%到2.7%再到3.1%，劣V类断面水质断面从3.1%到3.5%再到2.2%。由上述数据可知尽管水污染治理已取得一定成效，我国水污染情况仍然不容乐观。

目前常用的水质治理基本路线为源头截污、水体治理、修复生态。其中水体治理包括清理河内垃圾、生物残骸，以及清除淤泥等，而打捞湖泊里的垃圾需要耗费大量资源，在打捞过程中还可能出现安全事故。为此，我们拟设计一个能在湖面上自动巡航的无人船，它可以在知道水域当前状况的前提下进行自动巡航并达到净化水质的目的,该方案可以代替人们进行高危、重复的工作，节省一定的人力资源，具有一定的经济效益。

1.2 路径规划的基本问题

路径规划是一个涉及到多学科的复杂问题，根据实际情况的不同需要考虑的问题也不一样。而不论在何种环境下实现机器人路径规划均需要考虑以下四个问题：

(1)如何从环境中获取有效信息，如障碍物信息等。

(2)如何利用传感器输出来获取当前所在位置。

(3)机器如何根据从环境中获得的信息以及其当前所处位置确定目标路径。

(4)如何产生合适的驱动信号使其运动在预定的轨迹上。

为解决这些问题，机器人需要具备以下四个相关技术：(1)传感技术；(2)自定位技术；(3)运动控制；(4)规划和决策^[1]。

1.3机器路径规划方法研究现状

路径规划近些年发展迅速已成为移动机器人领域研究热点问题。它可以实现自动遍历目标环境，并完成相应任务等功能。

按照对环境信息的已知程度可将路径规划分为全局路径规划与局部路径规划。当机器在已知环境中行驶时是全局路径规划，在局部未知或者完全未知的环境下行驶是局部路径规划^[2]。目前常用局部路径规划方法有人工势场法^[3]、遗传算法^[4-5]、蚁群算法^[6]等；全局路径规划有：单元分解法^[7]、栅格法^[8-9]以及神经网络^[10]等算法。

路径规划应用广泛，例如移动机器人、物流运输等方面，典型实际应用有扫雷机器人，矿藏探测机器人和清扫机器人^[11]。

1.3.1 国外研究现状

20世纪60年代末斯坦福研究院研制了移动机器人Shakey ^[12]。它是一个智能化的机器人,能够自主感知周围的环境，并对其所在环境建立数学模型执行任务,但它运算速度缓慢。此后科学家们一直致力于移动机器人的研究。移动机器人在各种环境下均有应用。美国机器人公司推出了吸尘器机器人，该机器人可以实现自动设计行进路线避开障碍，还可以在电量不足时自行驶向充电座进行补充充电等功能。日本举办的Robocup赛事是机器人领域的足球世界杯，在该比赛中来自各国的参赛机器人队伍 “互相竞争”角逐冠军。

Farhad SHAMSFAKHR等用反向传播算法训练逼近的前向神经网络对机器进行智能导航并躲避障碍，利用欧几里得距离核函数将将数据集降维到30，使得机器实行稳定，具有广泛性^[13]。Joon Seop Oh等提出以三角形单元映射表示的全区域覆盖和地图构建方法，使清洁机器人以比矩形单元映射表示更短的路径和更高的灵活性导航^[14]。Hoang Huu Viet等提出了一种基于左右交互运动和A *搜索算法（BA *）解决未知工作空间自动清洁机器人在线完全覆盖任务的新方法^[15]。Carmelo Di Franco等提出一种源自实际测量的能量模型，然后使用该模型实现覆盖路径规划算法，以降低能耗，并保证所需的图像分辨率^[16]。

1.3.2 国内研究现状

我国对机器人的研究较国外晚，但由于其良好的性能使其越来越受学者和国家的重视。近些年我国陆续研制出智能机器人。如中科院团队研发的智能移动机器CASIA-I、反恐防暴机器人、清华大学团队研发的智能车THMR等。

我国学者禹建丽等^[17]提出了一种基于神经网络的机器人路径规划算法,研究了在障碍物形状和位置环境已知情况下的全局路径规划算法。根据神经网络建立能量函数，根据路径点与障碍物之间的位置选择不同的运动方程。孙兵等^[18]提出了基于GBNN算法的多AUV全覆盖离散和集中编程，解决大水域单AUV全覆盖任务的问题。王栋等^[19]提出基于阿基米德螺线走法的全区域覆盖路径规划，在无障碍的类圆形区域具有较好的适用性。王智龙等^[20]提出采用现行路径记忆和基于动态地图的规划方案，实现让清洁机器人的运行轨迹遍布区域，同时能够避开障碍，减少运动轨迹的重复率。

1.4 本文研究内容

本文研究的主要内容是借助人工神经网络这一方法实现无人船的自动巡航路径规划方法研究。首先对目标环境建立模型，通过神经网络求解模型使无人船能自发寻找一条尽可能平滑的行驶路径且判断障碍物位置并自动避开障碍。无人船行驶路径、所耗时长应尽可能短；区域覆盖率应尽可能高。

第1章为绪论，主要介绍本文研究背景，以及路径规划的国内外研究现状。

第2章为神经网络概述，介绍了神经网络的定义、分类，以及它的发展历史。

第3章为路径规划方法的应用，介绍了神经网络在路径规划中的应用，BP神经网络的算法，环境模型的建立，以及内螺旋法，RBF神经网络路径规划，应用模拟退火和神经网络方法解决的全局路径规划。

第4章为实验数据的比较分析，从不同层面比较前文提到的三种全覆盖路径规划的实现程度。

第5章为总结，对全文进行总结，归纳了其中的成果与不足。

第2章 神经网络概述

2.1神经网络定义及发展

在细胞生命过程中，多数情况下，神经元是处于抑制状态，只有当其受到一定程度的刺激时神经元才会处于兴奋状态，此时信息通过突触传递给下一个神经元，从而激活下一个神经元的生物活动。

突触是树突与轴突相连的点，每个神经元都有许多树突却只有一个轴突。信号通过不同树突传入神经元，从而产生刺激，再通过轴突传递给树突进行周而复始得生命活动，神经元生命活动见图2.1。

图2.1 神经细胞生命活动

神经网络是由大量简单的神经元按照一定连接方式形成的智能仿生人工网络，它通过模拟神经元的生物活动进行工作，具有存储知识和联想记忆的特点。它还可以通过学习获得知识并可以通过存储的知识进行学习检验。神经网络发展至今已有60余年。我们可将其发展历史分为三个阶段，萌芽发展阶段，衰退阶段，复苏发展阶段。

首先是萌芽发展阶段：1943年科学家McCulloch和Pitts建立第一个神经元数学模型MP模型^[21]。该模型与神经元生命活动类似，只有当刺激达到一定强度才可以获得神经元输出。

第二阶段是衰退阶段，由于人工智能之父Minsky研究证明单层感知机神经网络无法解决异或问题。此后，神经网络的研究陷入了很长一段时间的低迷期。

第三阶段是复苏发展阶段，1982年著名的Hopfield神经网络解决了TSPNP问题,这一发现使得神经网络的研究开始快速发展。随后产生的BP神经网络学习算法，径向基神经网络（RBF）使神经网络走向实用阶段。后来随着计算机存储能力处理数据能力的提高，神经网络学习进入到了一个新高度，如图像识别，模式分类，其中图像识别的典型应用有人脸识别。

2.2神经网络分类

神经网络的种类很多，按照不同的分类标准可划分不同的神经网络。根据反馈方式不同可以分为两种，前馈神经网络和反馈神经网络，后者也可以称为递归神经网络，其中BP神经网络与Hopfield神经网络分别是前馈神经网络和反馈神经网络的主要代表。根据网络性能角度可分为连续型神经网络与离散型神经网络。当前神经网络在许多方面都取得良好的应用效果，如函数逼近，模式识别问题。人工神经网络基本结构见图2.2。

根据神经网络层数不同，前馈神经网络又可以分成单层前馈神经网络和多层前馈神经网络，如单层感知机就是单层前馈神经网络；多层感知机和BP网络均属于多层前馈神经网络^[22]，该网络具有一个或多个隐藏层。

2.2.1前馈神经网络

前馈神经网络就是将输入层信息一层一层向前依次传播给网络隐藏层及其输出层。其网络相同层之间的神经元之间彼此没有联系，不同层之间的神经元之间通过连接权值传递信息。

前馈神经网络模型选择的目标就是对于一个特定的学习任务，能够选择一个合适的网络。单个前馈神经网络因网络规模大小不同，输入层、输出层以及隐层节点数没有明确的选择界限，网络可能出现欠拟合或者过拟合的现象。为了提高网络性能，混合前馈神经网络应运而生，该网络可以通过综合利用单个前馈神经网络的优点具有更高的精度^[22]。

图2.2 人工神经网络基本结构

图2.2中f又称传输函数。根据网络应用情况的不同可以选择step函数，sgn函数，sigmiod函数linear函数，tanh函数等。相关函数图像如图2.3所示。

2.2.2反馈神经网络

反馈神经网络有反馈回路，它与前馈神经网络的区别在于反馈神经网络每个神经元之间可以将自身的输出作为输入反馈给同层其他神经元，也即神经元之间可以互相反馈信息，而前馈神经网络各层神经元之间并没有联系。典型的反馈神经网络有Hopfield神经网络与玻尔兹曼机，Hopfield神经网络典型结构如图2.4所示。

图2.3 神经网络常用传输函数

图2.4 Hopfield神经网络模型

第3章 路径规划方法

3.1局部路径规划

局部路径规划也可称点到点路径规划，是在已知起始点与目标点的基础上，利用从环境中动态获得到的信息自行规划出行驶路径。

3.1.1 神经网络在路径规划中的应用

神经网络（如图3.1所示）除了具有强大的学习能力还有良好的适应性能。该网络是由大量神经元连接成的复杂网络，通过调整内部节点之间连接关系来处理信息，当个别神经元出异常时，由于该神经元对神经网络整体影响很小，故不会影响整个网络的正常工作。

移动机器人的局部路径规划就是利用传感器获得外部环境信息并将从传感器处获得的信息作为网络输入通过神经网络迭代计算来获得网络输出，最后依据网络输出判断机器人应该采取的行动。

图3.1 神经网络数学模型

该模型的数学表达式为

(3-1)

式中x_i:输入端输入信号

b_j :神经元偏移量

n:输入信号数量

w_ji:连接权系数

y_j:第j个神经元的输出

f(.):传输函数

根据Kolrnogorov定理知一个含有一个输入层一个输出层一个隐藏层的三层BP网络可以以任意精度逼近非线性函数，通俗来讲也就是三层的BP网络可以解决函数逼近问题。BP网络隶属于前馈神经网络，每个网络层的神经元之间没有联系，不同网络层神经元之间互相联系。文中以三层BP神经网络为例，神经网络模型如图3.2所示，其中输入层有n个输入，隐层有m个输入，输出层有k个输出。

图3.2 BP神经网络模型

以上是毕业论文大纲或资料介绍，该课题完整毕业论文、开题报告、任务书、程序设计、图纸设计等资料请添加微信获取，微信号：bysjorg。

相关图片展示：