论文研究-水下机器人软件可靠性及故障诊断方法研究.pdf

所需积分/C币:6 2019-09-08 12:16:34 572KB .PDF

依据真实蚂蚁具有自动分流功能这一研究成果,提出了一种全新的基于异类蚂蚁算法的机器人路径滚动规划算法。算法引入分流蚁,以选择信息素较少的路径行走,从而增强了搜索多样性。为加快收敛,结合模拟退火思想动态调节分流蚁的个数。仿真实验表明,即使在复杂的未知环境下,利用该算法也可以规划出一条全局优化路径。
高冒:异类和群蚂蚁机器人滚动规划算法 2011,47(8)247 到达该栅格,从而解决了路径死锁问题。约東3是为使搜索过 [1/T, (nrn, (g 程远离最不可能产生较优解的空间,减少劣质解的产生。 ∈taba (8 1()L(g]) 3.2算法步骤 g∈PS 算法将两个蚂蚁家族的各m个蚂蚁(均含ma个分流蚁)将/加入禁忌表 tabu e 分别放置在P()和gm,其屮蚂蚁家族1的m个蚂蚁以P(t) 步骤6局部信息素更新。 为出发点,以g。为目标;蚂蚁家族2的m个蚂蚁则相反,两个 用叁数1~表示信息消逝程度,每一只蚂蚁选择完一个节 蚂蚁家族相向搜索,从而协作完成规划工作。对于两个蚂蚁点后按式(9进行局部信息更新: 家族中的每一个蚂蚁,以当前节点为中心,按一定策略选择并 r(m+1)=(1-p)(n)+p△r 行走到下一可行节点。由于两个蚂蚁家族除了采用的启发两 当蚂蚁k走过边 数、出发点不同外,算法完全相同。为了减少变量的下标,以 △ (9) 下以蚂蚁家族1的搜索算法为例进行说明,并将表示蚂蚁家族 0否则 1的所有下标省略。 ∑ 根据以上思路和定义,基丁异类蚁群算法的机器人滚动 规划步骤描述如下: 当z1(+1)<乙m时,令,(m+1)=m,式中Q1为常数,m 步骤1产生任意的起点3mcm和终点gm并对有关参数是设定的最小值;d是蚂蚁k已走过边的边长,可由式(2)计 进行初始化。 算。w是蚂蚁k在本次搜索中已走过的边数;1是k在本次搜 步骤2将gm目标点映射到Rb视野域Riew边界内作索中到当前时刻为止已走过的路程(边的累加总长)。 为局部子日标g;其中局部子日标g映射算法如下 步骤7k,k=1,2,…,m,选择完第j个节点后,按定义8 在时划Rob的视野域为Riew(PA(),若有(P)g)=定义的条件,检杳两族蚂蚁中的听有蚂蚁是否已有蚂蚁相遇 r-6,则取g=gm,此时即为g与g相同;否则令若有,则转步骤8;否则,令行,返步骤5开始选择下一个节点 d(P())=r-6且满足mind(gmg)。其中,r为Rob的直到有蚂蚁相遇或所有节点选择完毕,若重复多次仍无蚂蚁 视野域Re的半径,o为Rob的行走步长。 相遇,则可以判断起点与终点间无可行通道。 步槳3Rob在当前位置P(ω)进行环境探测,识别出障碍 步骤8当两族中的两只蚂蚁或多只蚂蚁满足定义8的相 物Sb,和NFS。 遇条件时,将相遇蚂蚁所走通道连接,并用式(3)计算其路程 步骤4将m只蚂蚁(其中包含ma个分流蚁)放置在出发并保存最短路程Lm(Lkmn- minL) 点PR(),并设置到禁忌表tbm中(k=1,2,…,m)。令(O)= 将本次搜索得到的Lkm与已得到的历史最优长度L比 (τo为常数)。设置迭代计数器n=0,最大代数为MAx 较,若有Lm<L则用Lm替换L4,并记忆最佳通道的节点 步骤5(1)常规蚂蚁以当前节点∈F为中心,按式集合 (5)或式(6)选择并行走到下一节点g,且有g,∈ FSkBR(g), 步骤9全局信息素更新。 本次搜索相遇并完成通道连接后,将本次搜索最短通道 g还tbk。节点选择算法如下: 上的信息素按式(10)调整 = arg max([t, (n)I'n,(g≤ (5) (1-a.+a△ 式中j(∈C),蚂蚁k所选g的节点序号,在此省略了上标k △τ (10) S为由式(6)决定的随变量;q为随机数(0<≤1);qo为初始化 △ if i e global-best-tour 时给定的阈值;n(g)为由定义7给出的启发信息;B是在边e otl 上残留信息的重要程度,Pm)为在n代蚂蚁k由节点转移到式中,a为全局信息素挥发系数:L为本次搜索最佳通道 节点j的概率,,j∈C。 的长度;纩∈ global-best- tour表示蚂蚁k所走的边j属于最 q和9是为了防止出现停滞而设的随机搜索策略所需参佳通道 数,以增加搜索的多样性。当q>q时,计算FPS个节点的转 步骤10当分流蚂蚁的个数不为零时,依据公式(4)减少 移概率p,并根据赌轮盘规则选择节点j 分流蚂蚁的个数;令迭代次数n加1,若不等于MAX,则清空禁 忌表,重复上述搜索过程,直到nMAX为止。最终记忆的最 p(m)= Lt, (n)I n, (g) ∑[zaOn(g j tabu (6)佳通道即为规划出的最优路径 步骤11机器人沿着规划出的局部最优路径向g-前进 将加入禁忌表lbuk。 一。若g≠g。,Rωb沿局部最优路径向g前进一步并 (2)分流蚁vk,以当前节点g∈FS为中心,按式(7)或式(8)返回步骤2,否则Rob按照局部最优路径直接走向g 选择并行走到下一节点g,且有g∈ FSKBR(g),g,∈tbu4。 =gmin(n)n(g)}fq≤4 (7) 仿真实验 else 本文实验环境:机器配置为CPU赛扬2.66GHz,内存为 SS由式(8)计算,其他参数同上。 512MB,编译工具VC++60。 2482011,47(18) Computer Engineering and Applications计算机工程与应用 在不影响总体结果的前提下,假设机器人的视野域为10x 表1算法对比表 10的方形,运行参数设定如下:蚂蚁数为20,ma-5,B=2,a Ga ACO-grid RRT-grid本文的算法 0.1,=0.1,MAX=50。对于图3所示的复杂地形,黑色表示 环境要求 全局已知全局已知全局已知全局已知局部已知 N/A85.491650006120061200 障碍格,图3所示为用本文算法得到的从8m到右下角gm获得可行解比例(%)01090 100 100 的一条路径。为了说明算法的有效性,图4给出了环境随机生平均消耗时间s大于3001071 41.7 2.992 1.653 成时规划出的全局路径。 为了进一步说明算法有效性,用文献的实验环境进行5结论 了测试,结果如图5所示。其中红色是本文算法,黑线是文献 本文算法是受真实蚂蚁的觅食行为、滚动规划等思想的 [门算法的路径,虚线是基本蚂蚁算法的路径η 启发,并与解决实际问题相结合得出的算法。算法中Rob总 是以最终目标点的方向为前进目标,其特点是利用gat来引 导机器人,规划岀局部路径,此路径是全局的一种引导趋势 从而使其不仅能避碰,而且可以使所走路径全局最优或较 优。实验表明:只要有可行通道客观存在,既使在异常复杂的 地形环境,也能迅速找到一·条优化路径。计算机仿真实验取 得了非常好的效果。 图3实验结果图4环境随机生成图5对比实验图 时的全局路径 参考文献: 图6、图7、图8给出了实验过程中的分解子过程,其中粗[11张纯刚,席裕庚全局环境未知时基于滚动窗口的机器人路径规 线内表示Rob视野域范围。图6给出了Rob在起点时的部分 划中国科学:E辑,2001,31(1):51-58 视野域以及规划出来的局部优化路径;图7和图8分别表示Rob[2] Ferguson D, Stentz A. Anytime RRTs[C],Proceedings of the200 从起点前进一步、七步后再次规划出的局部路径。从图可以 IEFF International Conference on Intelligent robots and Systems 看出,Rob仅沿每次规划出的局部路径走一步,但它构成了全 October9-15,2006:5369-5375 局的一种引导趋势,从而使得不仅能避碰而且可以使得所走朱庆保全局知环境下多机器人运动蚂蚁导航算法门软件学 路径全局最优或较优。 报,2006,19(9):1890-1898 [4]朱庆保复杂环境下的机器人路径规划蚂蚁算法[].自动化学报 2006,32(4):586-593 [5] Ilsiao Y, Chuang C, Chien C C Ant colony optimization for best path planning[c]/ proceedings of Int Symp on Communications and Information Technologies, Japan, 2004: 109-113 [6] Dussutour A, Fourcassie V, Helbing D, et al. Optimal traffic orga 图6第一个局部路径图7第二个局部路径图8第八个局部路径 nization in ants under crowded conditions[J]. Nature, 2004, 428 为了进一步验证算法的收敛性能,在文献8]中给出的栅(门刘徐迅曹阳除晓伟基于移动机器人路径规划的鼠群算法门控 格规模为30×30的环境下,用本文算法和在全局已知条件下, 制与决策,2008,23(9):1060-1064 对经典的A*算法GA算法、ACO算法以及文献8中的算法进8国海涛,朱庆保,徐守江基于栅格法的机器人路径规划快速搜索 行了对比。性能对比结果如表1所示。 随机树算法南京师范大学学报:工程技术版,2007,7(2):58-61 (上接236页) 17-25 究仍然是在维平面结构上进行的,如何将其推广到三维Toy[5]黄德双生物信息学中的智能计算理论与方法研究M合肥:中国 模型中,进而能够较好地预测三维结构,将是接下来的工作。 科学技术大学出版社,2006 [6 Eberhart R C, Kennedy J. A new optimizer using particle swarm 参考文献 theory[C]//Proc of the International SyInposiuIn Onl Micromachine [I Anfinsen C B Principles that govern the folding of protein chains[J] and Human Science. Piscataway: IEEE Service Center, 1995: 39-43 Scince,1973,181(4096):223-227 7]何庆元,韩传久带有扰动项的改进粒子群算法计算机工程与 [2 Dill K ATheory for the folding and Stability of Globular Pro 应用,2007,43(7):8486 teins J. Biochemistry, 1985, 24: 1501-1512 [3] Stillinger F H, Gordon T h, Hirshfeld CL. Toy model for protein8]陈国初,俞金变邻域宽度的爬山微粒群优化算法及其应用门J化 folding[]. Physical Review, 1993, 48(2): 1469-1477 工学报,2005,56(10):1928-1931 [4] Rainer K, Thomas D Improving genetic algorithms for protein fold- [9] Mount D WBioinformatics: sequence and genome Analysis[M] ing simulation by systematic crossover[J].BioSystems, 1999, 50(5) [S.l. ] Cold Spring Harbor Laboratory Press, 2001

...展开详情
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐