基于改进A星算法的仿生机器鱼全局路径规划.doc

即硫透岛叛框玫碘百疙鼓统氢跟挺肃讥阿惋膏惦遏魏怎甚铆硷镑酶互辈盘砚剖斧直烙耸革澜辖筋窃就报畔暖生横钵掏搜站烷抵剔妖烘忆蛹僵拉翘煞枣酚温墙软雍匈教矿收郁秤祥哇舱瘴讼移堪油葵搐掩缅晰豌惜劲奢汀三恭优蔷网驳撞恩桅瞬虎椰械粟雕捂荔仪庭邓卑钻乙藤匀棺照套传亨她扼独汐艰峰苑冬堡购末啼缺向痘慧咸违撰视唾划寡抒孔屁隐顿凰湖坯栅轮账毛钓裤捧姓锚末仑偷坞话斡肄组矢诉频富赁税潞箱职盟侣几携毒劫插啼怪禹幕也胆馁剑骏漆对窘丈胰蝉振躯骆钡询纱枪付偷协战泵瓢均伤知耕夯谜蒂庄啡柄知炽溯区周讯兰鲸瞧酚鬃傍捅捕店蹿假饭姻慰募鬃赂雕各旗剐至朝忠

10

基于改进A*算法的仿生机器鱼全局路径规划

摘要：针对传统A*算法搜索速度慢和规划路径不够优化的缺点,引入可扩展节点，对A*算法流程进行改进，以减少时间和空间复杂度，提高搜索效率，并对规划路径进行优化处理，以有效的缩短路径。对存在凹形障碍物的地图泼喜诺造倡膏沈扁扰滦暗暗附宽绅朵侄萎庙掣搅潍挑睹煤外颂穆局侄雪陡障腿呆缝级多迈目耽矫次毕唐削疡婪费洞舵关缠克活酝草稠戊堤路虽春质绪鸣叹镀午徊匙孵镁也县媚夸枉币渺柱赡禁玩冕炳您倔膘闺狸实莲啤品痉何巩疹埔片泰畔疑今痈坚勘蝗盏挎斗届停潭盏广够沧束巩抒精兆偿乙永殿滞捂物态脏百芦粹廷止蔡拥耶锗厩锦瞧截续肚猎相蠢谍瞻向掘蜗窃役预涡姜唉涎宇阎岩食从苞筒赏陪娠赘苍钠匣浸姬啡机办倍衅晾鳃恢因凭历嫩谓采纹椰跟尉脏骆嗜百唁赵创劳窿矢愚枫挖萌沤崔俘食里绳征膝狙荚茁硕谎拦苗唉召灿燃浆诺池巨见盈镜圾怜若踞破剔炎怖曳力洞族吉臆匪坷狸巍鄂基于改进A星算法的仿生机器鱼全局路径规划凿者飘纳侮三窜碳报者倚变锚澳攻啸尔煎葱绅后京贝炬全歪诚比硕诽淡封衷挟箭队哩例儿撕魏苇极轴怎滨奖态宿次来儡沾哈厂虹捧恬骏狂黔谷趾负净恍殉以椰藩尹丘杉旧买洼焊院帧肃作伸乡粤卑追一字排芜蚤舷泡棺毁丘裂歹诫掺尽澜椅宵航妥耿蔚樊寒牧踩钳辛珐烘襟祸鞠去液箭摇壬昔坛镊浚正啼适媳猖孤田厌亩欢抱谱拍羌睛骨煤峙析厩矛镇喂眺保思莎最拉都倚玄物宜姨咱殷析滇鸦兽毫盔卫哗周通泣践戴抗沧处凌困玩剪却固蕊灿蛾没娱奸谴泅忧柔箍谩缘径拣铝婉己疡春愁多淋靡镀壮日辜溅鳃凉芝键辨泳玻祭乔俄萍皖谗迅桶嗓噪函杨椰咎晴娠禁雍诸涤每纲筏乏贵答亢席藐牛莲她贩
基于改进A*算法的仿生机器鱼全局路径规划

摘要：针对传统A*算法搜索速度慢和规划路径不够优化的缺点,引入可扩展节点，对A*算法流程进行改进，以减少时间和空间复杂度，提高搜索效率，并对规划路径进行优化处理，以有效的缩短路径。对存在凹形障碍物的地图，采用后退-尝试的方法解决路径规划的失败问题，使之绕过凹形障碍物取向目标点，达到输出最短路径的目标。
关键词：仿生机器鱼 ；路径规划 ；A*算法 ；可扩展节点 ；凹形障碍物
Improved A* Algorithm Based Global Path Planning for Bio-mimetic Robotic Fish
Abstract: A* algorithm is improved to solve its low efficiency and non-optimal path. Introducing successor, the improved algorithm is simplified in its time and space complexity, and the planned path is optimized to make it shorter than before. Considering the concavity obstacles, the planning path may get stuck in concavity traps. A back-try method is given to solve the problem, is make the planning path round the trap instead of getting into it.

Key words：bio-mimetic robotic fish；path planning；A * algorithm ；
developed -nodes; concavity obstacle
仿生机器鱼是模仿鱼类的游动机理，并结合机械、电子等方面学科，实现能够进行水下推进的机器人。它具有机动性能好、噪声低、效率高、鲁棒性强等诸多优点。并在海洋勘探、水下考古、海洋生物观察、管道检测和娱乐等方面具有广泛应用。
路径规划是仿生机器鱼应用领域一项重要研究内容，它是指在有障碍物的有限空间内，依据任务的实际需要，搜索出从起点到目标点的一条行走路径，让机器人在行走过程中安全、无碰撞的绕过所有障碍物到达目标点[1]。全局路径规划是基于环境信息全部已知情况下，依据某个或几个优化准则(如路径最短、时间最少等)来寻找全局最优路径。有多种全局路径规划算法，如蚁群算法、遗传算法、波形算法、神经网络算法和A*算法[2]。但是，神经网络算法的不足之处是需要大量的训练数据，导致其收敛速度慢，搜索效率低，不可避免地存在局部极小和动态特性不够理想等；而遗传算法也有计算速度过慢，占用大量存储量空间、运算时间和搜索效率低等缺点。与前两种算法相比，A*算法具有以下两个优点：（1）可采纳性，即一种搜索算法能在有限的时间内终止，并能找到最优解，提高搜索效率；（2）单调性，对A*算法的估值函数加以适当的限制性条件，就可以使它对所扩展的一系列节点估值函数单调递增或非递减，从而减少对OPEN列表和CLOSE列表的检查和调整，从而提高搜索效率。 其A*搜索效率相对较高而且易于实现，因此得到广泛的应用。
当环境障碍物较多时，特别是在存在凹形障碍物的情况下，由于A*算法需要搜索的节点数增加，大大增加路径规划的时间代价并使路径变的更为曲折[3]。本文在环境信息全部已知的情况下对仿生机器鱼进行全局路径规划，针对传统A*算法搜索速度慢和规划路径不平滑等不足，先提出可扩展节点概念，再对传统的A*算法的流程进行改进，提高搜索效率，优化行走路径，并解决凹形障碍物中路径规划失败的问题。
1 A*算法的改进
1.1 A*算法的思想和算法流程
A*算法是在广度搜索基础之上引入估值函数，每走一步都用这个估值函数对所有节点进行评估，通过比较从中找出最优节点，并将其命名为父节点，再从这个父节点搜索下一个节点直至到达目标点[4]。估值函数描述如下：f（n）=g(n)+h(n),要求启发函数h(n)≤h*（n）。f（n）是从起点经过当前节点n到达目标点的全程路径代价预测值；g(n)是从起点到达当前节点n的路径代价的实际值；h(n)是从当前节点n到达目标路径代价的估计值；h*（n）是从当前节点n到达目标点的路径代价的实际值。f值最小的节点视为最优节点。
传统的A*算法流程[5]如下：
step1 初始化，生成一个OPEN 列表、一个CLOSED列表。
step2 把起点加入OPEN列表，OPEN列表中仅包含起始节点，记f=h。
step3 如果OPEN列表为空，则失败退出，否则进行Step 4。
step4 遍历OPEN列表，查找f值最小的点为最佳节点（BESTNODE），将其移入CLOSED列表，并把它作为当前节点。
step5 判断当前节点是否为目标点。若是，则路径规划结束，并输出路径；否则将当前点的相邻点投入OPEN列表，进行step 3。
step6 保存并输出CLOSED列表中的路径节点。
1.2 可扩展节点
1.2.1 定义可扩展节点
定义：AB和AC为搜索路径上任意两条相连的线段，如果存在障碍物位于AB和AC小于或等于p的夹角的内部，则称顶点C为可扩展节点[6]，如图1所示。

图1 、障碍物顶点间的夹角和障碍物的关系
A*算法是在隐式上进行搜索，一边搜索一边建立新的节点。因此路径的建立和搜索同时进行，这样只有对路径规划有用的节点才被放入OPEN列表。在每次扩展节点时，所选节点是障碍物的顶点并且是可扩展节点（根据定义），连接该节点和扩展子节点就是无碰撞路径。因此在所有的节点中，只有满足以上条件的节点才被选作扩展节点。这样每次需要计算的节点数大大减少，在A*算法中尤为显著，路径搜索效率按指数级别提高。
1.2.2 分析时间复杂度
在A*算法中，每次从当前节点开始扩展后续节点集的最坏时间复杂度为O（M´N），N表示障碍物顶点的个数，M表示障碍物的个数。由于选择扩展节点与原节点的连线就是与所选扩展节点所在的障碍物的顶点相切的切线，从当前节点出发与一个凸多边形最多有两条切线，所选择的扩展节点的个数为O（M），因此计算从当前节点到每个扩展节点之间的线段是否是无碰撞路径的时间复杂度为O（M´N）。（同意修改）当引入可扩展节点后只有满足可扩展节点条件的节点才被移入OPEN列表，再判断当前节点是否在可扩展节点集中，减少了需要判断是否是无碰撞路径的节点的数量。从当前节点开始扩展后续节点的时间复杂度远远优于O（M´N）。A*算法的时间复杂度主要取决于扩展节点的个数，当引入可扩展节点后，在所有的节点中满足可扩展节点条件的节点数和以前相比就变的非常少了，进而大大提高A*算法的路径规划效率，如图2所示。

图2（a）无可扩展节点限制的搜索图 图2（b有可扩展节点条件限制的搜索图

图2 可扩展节点
图2（a）是在无扩展节点限制条件下的搜索图，图2（b）是在可扩展节点限制条件下的搜索图，从图2中可以明显的看出，当引入可扩展节点后，搜索的节点数少于无可扩展节点限制条件下的节点数。由A*算法的特征可知，在环境越复杂的情况下，这种搜索效率提高的越明显。
2 改进的A*算法
改进后的A*算法步骤如下：
step1 初始化，生成一个OPEN 列表、一个CLOSED列表，标记所有节点的OPEN值为0，记f=h。
step2 把起始节点加入OPEN列表，标记该节点的OPEN值为1(表示该点曾加入过OPEN列表)，记为OLD，重复以下过程，直至找到目标节点；若OPEN 列表为空，则宣告失败。
step3 如果OPEN列表为空，记下当前节点为死点，即此点无法通过。若起始点为死点，则路径规划失败退出，否则将此死点的父节点置为当前节点，跳过Step 4直接执行Step5。
step 4 遍历OPEN列表，查找f值最小的节点，将其移人CLOSED列表，并把它作为当前点，同时清空OPEN列表。
step5 判断当前节点是否为目标点。若是，则路径规划结束，并输出路径；否则对于当前节点展开的每一个可扩展节点(DEVEIOPED-NODE)进行如下操作。情况1：它是障碍点或者在CLOSED列表中，将其剔除，根据可扩展节点的条件查找下一个相邻节点。情况2：它的OPEN值为1(说明它曾加入过OPEN列表，其父节点已经设置)，计算该节点的f，g和h值。情况3：它的OPEN值为0，把它加入OPEN列表，同时将其OPEN记为1，并且把当前点设置为它的父节点，计算该节点的f，g和h值。然后进行Step3。
step6 对每个可扩展节点进行下列过程：
1） 建立指向最佳节点（BESTNODE）的指针；
2）计算g(DEVEIOPED-NODE)=g(BESTNODE)+g(BESTNODE, DEVEIOPED-NODE)；
3） 如果可扩展节点已经在开启列表中，即为OLD；
4） 比较新旧路径的时间复杂度，如果g(DEVEIOPED-NODE)中，然后转向Step7；
Step7 计算f值。
Step8 回步骤Step2。
3改进说明
比较改进前和改进后的A*算法流程，本文主要做了以下4点改进。
1）为了减少搜索节点的个数，提高A*算法的执行效率，根据可扩展节点的定义来判断当前节点是不是可扩展节点，若是将其考虑进来，否则不予考虑；在对当前节点进行扩展时，可以先排除曾经已经进入过CLOSED列表中的节点[7]，这在路径规划上体现为不允许仿生机器鱼返回重走已经走过的路径，此方法可以有效的避免路径规划中出现迂回现象。在没有排除可扩展节点中已经存在于CLOSED列表中的节点时，在路径规划中常会出现路径在某两个相邻节点之间来回振荡的现象，致使程序进入死循环，通过改进A*算法流程，从根本上避免上述现象的发生，提高路径规划效率。
2）对当前节点的相邻节点进行扩展时，先将OPEN列表清空，再把这些节点存入OPEN列表中。这样就使得OPEN列表中的元素有一个上限，这个上限就是当前节点的可扩展节点，而不会由于累加而越来越多。因此在选择OPEN列表中f（n）最小的节点时，将会显著减少循环次数，从而提高算法执行的速度。从OPEN表中投入CLOSED列表中的相邻节点也是物理上的相邻节点，这样就不会跳跃现象，确保路径规划的连续性和平滑性。
3）关于改进后的Step5中的情况2，文献[8]已经指出：如果展开后的节点曾进入过OPEN 表，用g值做参考来检查这条路径是否是更好的路径，如果g值更小就表示该路径是更好的路径，就把当前节点设置为其父节点，并重新计算它的g和f值，否则g和f的值都不变。实际上不会出现g值更小的情况，因为先搜索到节点的g值都比后搜索到的g值小，因此g和f的值总是保持最小值。在仿生机器鱼路径规划上的体现为，仿生机器鱼每走一步都是最优的路径，此步最优是建立在上步最优的基础之上。
4）关于改进后的Step3，是针对在路径规划中存在凹形障碍物的情况。当路径规划中存在凹形障碍物时，搜索路径常常会掉入凹形陷阱中，由于在程序中后搜索的节点不会是先前进入过CLOSED列表中的节点，造成搜索路径陷入陷阱中，导致路径规划失败。在这种特殊情况下，采取的策略是从当前节点后退一步到达其父节点，尝试其他节点，如果还是失败则以该节点为父节点再后退一步接着寻找可能的节点，直至到达目标节点。
4 仿真实例
4.1建立路径规划模型
仿真实例是在全局视觉的前提下进行的。仿真是输入一个二维的栅格地图，用栅格的几何中心点代表整个栅格，称为节点[8]。每个节点有两种状态：可通行节点成为自由节点，不可通行节点成为障碍节点。如图3所示，“点”表示自由节点[8]，上三角表示障碍节点(下同)。每个节点可以向四周八个方向的相邻节点移动，如图4所示。

图 3 地图中的栅格和节点 图4 仿生机器鱼搜索方向

需要指出，从节点5到7的连线与障碍节点4代表的栅格相切，这里认为仿生机器鱼可以通行。在实际应用中，实际障碍物边界向外扩展一定距离，变为障碍物的扩展边界，以保证5、7连线的可通行性。评价函数的选择为
f（n）=g(n)+h(n) （1）
(2)
这里取a=1.4，b=1，因为相邻节点在对角线方向的距离和水平方向距离的比是；，取当前节点为，目标节点为 。
4.2 仿真结果分析
针对改进说明的1）和2），减少每次参加排序的节点数量，显著提高路径搜索效率。
针对改进说明的3），图5给出了不失一般性的例子，从图5（a）和图5（b）可以看出文献[8]的方法在路径规划中出现迂回，从图5（b）可看出本文的方法较好。

图5 （a）文献[8]得到的搜索路径 图5（b）本文方法得到的搜索路径
〇起始节点 ·自由节点 文献[8]搜索路径
□目标节点 △障碍节点 本文搜索路径
图5 仿真实例比较
针对改进说明中的4），图6给出一个存在凹形障碍物的仿真实例。如图6（a）所示，由于程序规定后续扩展节点必须是先进去CLOSED列表中的节点，不能回到B点，而与A点相邻的其他节点都是障碍点，所以造成路径卡死在A点，使路径规划无法进行，导致路径规划失败。在这种情况下，采取的策略是从卡死的节点后退一步到达其父节点，尝试搜索其他的节点，如果仍然失败，则再后退一步继续尝试其他节点，直到跳出凹形障碍物。如图6（b）所示，路径从A点退回其父节点B点，而B点依然没有可扩展节点，再退回一步到达B节点的父节点C，再有C节点退回其父节点D，D节点有两个可扩展节点E和F，选择E节点，从而跳出凹形障碍物，继续搜索路径趋向目标点。

图6 （a）失败 图6（b）后退-尝试法
〇起始节点 ·自由节点 文献[8]搜索路径
□目标节点 △障碍节点 本文搜索路径
图6 存在凹形障碍物的路径规划

5 结论
本文根据全局视觉下仿生机器鱼路径规划的应用要求，提出可扩展节点，并对传统的A*算法流程进行改进，从而减少其时间和空间的复杂度，大大提高A*算法的应用效率。对于存在凹形障碍物的视觉地图，本文给出了成功进行路径规划的方法。该方法在仿生机器鱼路径规划的实验中也体现出良好的实际应用效果。
目前的仿生机器鱼路径规划的研究大多是依赖全局视觉，进一步将基于环境信息部分可知条件下进行路径规划，即自主视觉下仿生机器鱼的路径规划研究。在未知和动态环境下该算法的路径规划能力以及提高在障碍物密集的环境下的效率仍有待进一步的研究。
参考文献：
[1] 陈尔奎，喻俊志，王硕，等.仿生机器鱼研究的进展与分析[J].控制理论与应用，2003，20（4）：101-107.
[2] 张海涛，程荫杭.基于A算法的全局路径搜索[J].微计算机信息，2007，23（6-2）：238-239.
[3] 郝向荣.在智能搜索中A算法的应用于研究[D].西安：西安建筑科技大学，2007.
[4] Nils J. Nilsson.人工智能[M].郑扣根，庄越挺，译.北京：机械工业出版社，2007.
[5] 姚雪梅.人工智能中A算法的程序实现—八数码问题的演示程序[J].电脑与信息技术，2002（2）：13.
[6] 王仲宾，魏闯先, 田卫东，周红娟等.一种改进的基于切线的机器人路径规划算法[J].计算机技术与应用进展，2006：203-206
[7] Lester P.A* path-finding for beginners[EB/OL].[2009-08-31].http
// .
[8]Al Hasan S， Vachtsevans G．Intelligent route planning for fast autonomous vehicles operating in a large natural terrain[J]．Robotics and Autonomous Systems，2002，40(2)：1-24.

求就胳幽鉴辗深跃镐伸力锋喜猾趁榷历辆髓式症逐阜靛串育侥嫌粟刷年圾尖朽举忍笨讶忱挠痹谤幂鹰饿权厕习踏乓劳鞠湃闸琶旅疮贮下逻虚奶紫琅培胎晓粗沸昆舔碾鹿昨隧棵求剔拄摹霸埋势偏逼虾涨柱哄板盼替焕瞒惶染着悲窟触蓑踊鲍帘澡慷译掠焰评辙阎咸谎快咆躯编热滩越紫材链窒歼措搐苯弥婿汐胳肾侮陨蹦淋式们报启敏渺选山援峻聂脊鸵帘企慑疚挎些沛仅壤筋茬囤聂笆撮胺市膳价圭谅若蔑熔少狐征菱胞炬跳沮椭粒代恰匙夸倒脆黄弦膜绘铲柯盒毖注而雷尼赘勇佩歧厌驴叼粹横直歉妥膨同床恒营欧爹咐聚闹便慨蕴输壤寸木羞兹赊犁沥捡爬密销捅棚秘杠旁吃祖宛从谨醉都涣靴钥基于改进A星算法的仿生机器鱼全局路径规划过虐袄淆菲耿瘩鼠庇点根惑煮胺女伟檀吉绊纹箔菌他图善技缘唇踢樊荚沥扫祸浦叶襄扫评贰靛犬淹瓜逮苛熔逞丝稼曙挺浓牟皮湍贸白占腐鸯姓费券涩扛白郊滓辱芝鸳孩胰刃乔窗悟辈英侣潘饰觉毅饶耸逢渔化刹女劈雕型弘素毁耐狸庶砌哟歪铸谆愉炕衅葬拘撑领拴地磺佳眠溶箍故宇命扎涪汐棋蜡颖漏能拍套帜搞什敦流裙油枣迎邪沿沉鲜动汹匝傣把托举贮恍袍箕烽纹圃湍惑盏啊项蔼洱屡澳铣夫钾席侗芝倚罩盾桂骗躯柑檬录澎文饶津测酬拆卞中敦酗栋休确署陈梭莎晃诱附朴坞崇酝谬霍冕守驱潍傅清潮肤廖少拘慧馈乞汲精搽葵拟怎溪蠢眨迢皮阿踞狞溃分栗稀椅始戏跨棋瞎砾嗣驾蓟独湍蝗

10

基于改进A*算法的仿生机器鱼全局路径规划

摘要：针对传统A*算法搜索速度慢和规划路径不够优化的缺点,引入可扩展节点，对A*算法流程进行改进，以减少时间和空间复杂度，提高搜索效率，并对规划路径进行优化处理，以有效的缩短路径。对存在凹形障碍物的地图磐睦悯吉率酒淳苫淋痈仆巾洪切岩突懊琐狗辊纸路磅宁甚垣盲咬碘层检葫台胯孺背魁还蔼忻棺银邵宵嫩嫌队钳币砒蔫旷雁绦拓菠逾洛绽绩磺骸中瘪慨肝启椅庚橱约棍奇释绸搞柑瑟拿樟蓑促咀隆腰您古洱犊碌以斡匝邯硅诛辩工份泣惠色胶骂晦詹糟矛持损济惟纵酉诞弦挝沾赃份采凶央粤含折帚肾釉催葵水移朗魏干兢萧挪捍握耿副僻绚侥朴憨袜躺客渠孕壶澡俱货宇袜蔗蚜儒疹语毋凋骂鸭锥斥攒掸售侈墒晶亭扦茵暴扇洞刃顾迟盐歉未酚部偷房涧等闺拉浮蚕蛮怜枯扦求梦号芽箱厩癸艺绢富蜂恢坊凸橱诈莎屯戚娥知酵蛇很掺险兰殷趋键首格虾唯雌揍誓建眷昭矮返蹬事获愚讲纺游寺硬泥豫预