发布时间 : 星期二 文章机器人路径规划演示平台设计更新完毕开始阅读7efab99de53a580217fcfe01
山东建筑大学毕业论文
学模型。网络依赖于复杂的系统，通过调整内部之间的联系，以实现节能的目的和完成信息处理。
优点：人工神经网络算法研究始于20世纪40年代，是在现代生物学研究人脑结构和功能成果的基础上提出来的。它作为一个高度并行的分布式系统，能较好地模拟人的形象思维，具有大规模并行协同处理能力、较强的容错能力、联想能力和较强的学习能力。该方法具有鲁棒性强等优点，在智能自主移动机器人路径规划中的应用已显示出其优越性。
缺点：神经网络中的权值设定比较困难。 2.5.2 人工神经网络算法理论基础
在人工神经网络路径规划算法中设计了一个检测器，它实际上是一个神经网络分类器。利用检测器在路径规划的过程中始终检测着路径点的位置(x,y)，由神经网络分类器判断该点是否在障碍物内即是否与障碍物相碰并将检测结果返回系统神经网络分类器就是在路径点到一个障碍物的罚函数的神经网络中间层和顶层结点的激发函数取为阶跃函数8则中间层的每个结点是决定该结点是否满足它的限定条件，若满足，则输出1，否则输出为0，若所有中间点均满足则顶层输出为1，它表示该点在障碍物内8若中间点检测出其中至少有一个不满足限制条件，顶层输出便为0，它表示该点在障碍物外。系统根据检测器返回的信息选择路径点的动态运动方程，若路径点在障碍物内则按动态运动方程（2.11）、（2.12）移动。若路径点在障碍物之外，则按动态方程（2.13）移动。即若路径点在障碍物外或障碍物内的路径点一旦移出了障碍物就仅按减少路径长的方向移动，不再向远离障碍物的方向移动，从而使路径能快速收敛到无碰的最短路径。
下面给出改进的快速神经网络最短路径规划算法，在此作了3点假设：障碍物是多边形围成的平面图形或者是圆形的平面图形；机器人为圆形点机器人，计算时障碍物的尺寸按机器人的半径作了适当拓展；障碍物为静止的。
步骤1：输入出发点P(x1,y2)，及目标点P(xN,yN)的坐标，对于t=0，初始路径一般取为出发点到目标点的直线上均匀分布的点列,当x1?xN时有公式(2.11)：
xi?x1?i?xN?x1???N?1?
yi?(yxN?y1)(i?(i?2,?3,?,N1?x?)N?x?1?x1)y （2.11）
- 16 -
山东建筑大学毕业论文
步骤2：对于路径点P(xi,yi),i?2,3,?,N?1用检测器检测是否在障碍物内。 步骤3：① 若P(xi,yi)在障碍物内8则按下列运动方程移动。 方程(2.12)为：
xi???1(2?(l2x?ix???1ix1?)ik?c?f((I))(?f?Hm((IHm)ik)?xm))K??kOiM
k?1m?1yi???1(2?l(2yi?yi?1?yi?1)?k?c?f((I))(?f?Hm((IHm)ik)?ym))K? (2.12)
?kOiMk?1m?1方程(2.13)为：
xi???1(?2l(2?ix??i?x1?x?1)i(H(Ii?))(Px))i ? （2.13）
yi???1(?2l(2??1?y?1)iy?iyi?cf?((OIi)?)?fH?cf?((OIi)?)?fH(H(Ii?))(Qiy))其中方程(2.12)用于P(xi,yi)位于多边形的障碍物内的情况，方程(2.13)用于P(xi,yi)位于圆心在(P,Q)的圆形障碍物内的情况。
② P(xi,yi)若在障碍物之外，则按运动方程(2.14)移动：
xi???2(2?xi1) (2.14) ?yi???2(2y?i?yi?1?yi1)?i??
x?1xi步骤4：重复执行步骤2，步骤3直到路径收敛。
这里，整条路径总能量函数的定义与原算法相同，一个点到一个障碍物的罚函数的神经网络结构的中间层第m个结点的输出改为：
OHm?f中间层第m个结点的激发函数改为:
fHm(x)?
Hm(IH m ) (2.15)
11?e?x?THmTHm(t)??mlog(1?t) (2.16)
其中?m是相应于障碍物每一条边的初始温度，即可以根据障碍物的形状设定各边的不同的
- 17 -
山东建筑大学毕业论文
初始温度，这样对于一些不对称图形可避免其罚函数曲面形成一边倒的情况，从而避免路径规划收敛到局部极小值。 当障碍物是圆形的平面图形时不等式的个数取为一，即中间层只有一个结点，且输入为
22?(ix?O)?(? 2Q IH?R ) (2.17) iy其中R为圆形障碍物的半径，（P,Q）为圆形障碍物的圆心。 2.6 蚁群算法 2.6.1 蚁群算法概述
目标：机器人在有障碍物的工作环境中工作时，通过两组蚂蚁相向搜索，优化寻找出一条从给定起始点到终止点的较优的运动路径，使机器人在运动过程中能安全、无碰撞地绕过所有的障碍物，且所走路径最短。
方法：用两组蚂蚁分别以机器人出发点和目标点为出发点，按照一定的概率搜索算法相向搜索。本课题要研究这一概率搜索算法及其编程实现，并用C语言给出仿真结果。
原理 生物学的研究表明：虽然单个蚂蚁的能力非常有限，但多个蚂蚁构成的群体具有找到蚁穴与食物之间最短路径的能力。这种能力是靠其在所经过的路径上留下的一种挥发性分泌物，即信息素(pheromone)来实现的。蚂蚁在路径上前进时会根据前边走过的蚂蚁所留下的信息素选择其要走的路径，其选择一条路径的概率与该路经上分泌物的强度成正比。因此，由大量蚂蚁组成的群体的集体行为实际上构成一种学习信息的正反馈现象：某一条路径走过的蚂蚁越多，后面的蚂蚁选择该路径的可能性就越大。蚂蚁的个体之间通过这种信息的交流寻求通向食物的最短路径。 2.6.2 蚁群算法理论基础
算法分析
步骤1：在屏幕上画一个10*10的栅格，格子的号码从1到100，栅格障碍物的号码随机生成（设有20个障碍物），并按照生成的号码在图中用阴影表示。
步骤2：设定起点和终点的位置：begin=5,end=99。因为障碍物是随机生成的，所以设定的起点和终点有可能与障碍物的号码冲突。为了避免出现这样的情况，需用另外的函数来检测，如果设定的起点或者终点恰好就是随机生成的障碍物时，就要再重新设定起点和
- 18 -
山东建筑大学毕业论文
终点的方格号码。为了便于后续距离的计算，将终点end转换为横纵坐标：横坐标endx=(end-1)/Y+1；纵坐标endy=(end-1)%Y+1。
步骤3：初始化。将每两个方格之间的信息素初始化为一个很小的常数值：
hormone[i][j]=hormone[j][i]=0.5;起点和终点处均放置一定数量的蚂蚁（本程序中分别放两只），并将它们固定地分配到起点和终点地四周（一个方格放一只）。对于每一只蚂蚁，将它们所在的方格号码加到禁忌表中。
步骤 4：下一步要走的方格的选择。每只蚂蚁在自己领接的（8个）非障碍物的格子中（c[i][k]!=0）选择下一步要走的方格。同样运用ACS算法中选择结点的方法：
?j?argmax?hormoneij(t)?f2?,如果temp1?q0???j?tabuk?? (2.18) ??hormone(t)f?kij2??,j?tabuk,否则?pij???hormoneik(t)??f2(t)???k?tabuk?q0也是初始设定的参数，temp1是一个0到1之间的随机数。如果temp1按照最大信息素选择j，
??否则计算转移概率，按赌轮盘规则选择j，同时将j加入到禁忌表中。
f2是当前点转移到方格j的启发函数。如果是起点的蚂蚁，它的启发函数就是它领接的
各点到终点的距离的倒数，f2?1/dij。终点的蚂蚁就恰好相反。
设x,y分别表示将要走的点的横纵坐标，距离
dij?(x?endx)2?(y?endy)2 (2.19)
步骤5：信息素局部更新。每只蚂蚁走完一步后，用下式更新该边上的信息素。
?Q1?， sumtaok??lk??0，当蚂蚁k走过方格i,j时否则 (2.20)
lk是蚂蚁k从起点到当前方格所走过的路径长度。
步骤6：计算距离看是否有两只蚂蚁可以相遇。
当有从起点和终点出发的两只蚂蚁相遇时，一次搜索过程结束，将这两只蚂蚁所走过的路径相加，就得到了一次循环中从起点到终点得最佳路径。对每两只蚂蚁i，j:
用x0,y0记录蚂蚁i在t时刻所在方格的横坐标和纵坐标，有
/ Y 1 x0??tab?u??i??t?1? (2.21)
- 19 -