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

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。
基于改进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)<g(OLD), 则重新定义OLD的父辈节点为最佳节点, 记下较小代价g(OLD), 并修正f(OLD)值;
5) 若得到OLD节点的时间复杂度较低或相同, 立即停止修正;
6) 若后继的可扩展节点( DEVEIOPED-NODE) 不在开启列表( OPEN) 中, 则看其是否在关闭列表( CLOSED) 中;
7) 若后继节点( DEVEIOPED-NODE) 在关闭列表( CLOSED) 中, 则转向Step3;
8) 若后继的可扩展节点( DEVEIOPED-NODE) 既不在开启列表( OPEN) 中, 也不在关闭列表( CLOSED) 中, 则把它放入开启列表( OPEN) 中, 然后转向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].控制理论与应用, , 20( 4) : 101-107.
[2] 张海涛, 程荫杭.基于A算法的全局路径搜索[J].微计算机信息, , 23( 6-2) : 238-239.
[3] 郝向荣.在智能搜索中A算法的应用于研究[D].西安: 西安建筑科技大学, .
[4] Nils J. Nilsson.人工智能[M].郑扣根, 庄越挺, 译.北京: 机械工业出版社, .
[5] 姚雪梅.人工智能中A算法的程序实现—八数码问题的演示程序[J].电脑与信息技术, ( 2) : 1-3.
[6] 王仲宾, 魏闯先, 田卫东, 周红娟等.一种改进的基于切线的机器人路径规划算法[J].计算机技术与应用进展, : 203-206
[7] Lester P.A* path-finding for beginners[EB/OL].[ -08-31].http
//.net .
[8]Al Hasan S, Vachtsevans G．Intelligent route planning for fast autonomous vehicles operating in a large natural terrain[J]．Robotics and Autonomous Systems, , 40(2): 1-24.