logo资料库

基于蚁群算法的多机器人集中协调式路径规划.pdf

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：0.21M 资料格式：pdf 举报 版权申诉
第1页 / 共6页
第2页 / 共6页
第3页 / 共6页
第4页 / 共6页
第5页 / 共6页
第6页 / 共6页
资料共6页，全文预览结束
    机器人 技术应用 栏目主持：刘 远 江 基于蚁群算法的多机器人集中 协调式路径规划 o 吴 靓 1 何 清 华 1 , 2 黄 志 雄 1 , 2 邹 湘 伏 1 , 2 1 中南大学机电工程学院 2 湖南山河智能机械股份有限公司 [摘 要 ] 本文提出并建立了多机器人系统二维平面规划空间的有权图模型，在此基础上，采用 蚁群算法实现了多机器人系统的集中协调式路径规划。引入了通信网络技术的线路带宽利用率、网 络负载均衡等系统指标，衡量规划结果，指导规划进程，从而在协调个体行为的基础上实现系统目 标最优化。仿真实验表明该方法切实可行，协调性能优良。 [ 关 键 词 ] 路径规划，有权图模型，蚁群算法，路由选择 [Abstract] This paper systematically studied the path planning method by means presented and established of ACO (ant colony optimization).Firstly, this paper has a new model of environment of MMR, which is called Value-attached Network Model. Secondly, based on this new model, the ACO has been carried out in detail to resolv e the problem. Some parameters from communication-network technology are used fo r reference to scale the planning results and guide the process. Results of simul- ation shows this new method can be used to generate moving path in complex envi- ronment of MMR. [Key words] path planning ；value-attached network model ；ant colony optimizatio n (ACO)；routing 1、引言 算法解决多机器人二维平面路径规划问题。 路径规划问题是多机器人系统领域的核心研究 2、二维平面规划空间的有权图模型 问题之一，已有的方法有:C空间法、单元分解法、人 多机器人系统环境建模是其路径规划的基础， 工势场法、特权级法、交通规则法等。蚁群算法[6] 本文假设系统环境是二维平面，其中分布有各种物 是人们受到自然界中真实的蚁群集体行为的启发而 体和多个机器人。本文借鉴文献介绍的“多路径点 提出的一种基于种群的模拟进化算法。它属于随机 链接图建模”方法，对环境进行初步建模，再在 搜索算法，能通过蚂蚁群体中各个个体之间的相互 此基础上提出并建立了有权图模型。文献得到的模 作用，分布、并行地解决组合优化问题，该算法已 型连线比较繁杂，如图 1 所示。我们对该图做进一 经在相关领域得到应用[7，8，9]，正成为继遗传算法 步简化。在每个子空间面积重心设置一个节点，机 之后又一研究热点。 器人的起点和终点也设置成为一个节点，将各个相 路径规划问题本质是一“空间 - 时间”组合优 互间可见（即连线没有被物体所阻挡）的节点连 化问题，适合采用蚁群算法。本文将首次采用蚁群 接。两节点间的连线称为边。如果两边在非节点处 32
    机器人 技术应用 栏目主持：刘 远 江 相交，则将该交点设置为新的节点。由边相连接的 两节点称为相邻节点。一条边对应图1中的一段可直 达路径。每条边有两个参数，带宽和长度，分别对应 图1中一段可直达路径的宽度和距离。经过上述简化， 我们就得到如图2所示的网络图。对于图2除去障碍 物，并适当规整，将得到图3。我们称其为“有权图”， 相应的模型，称为“有权图模型”。 理论上说，所有二维平面规划空间都能通过以 上方法得到相应的有权图模型。我们将多机器人路 径规划问题转变为多机器人从有权图上源节点到目标 图 1 含有两台机器人的规划空间 及其多路径点链接图建模 图 2 多路径点链接图的简化 图3 有权图 节点的受约束的路由选择问题。接下来，我们建立 有权图模型的数学描述。 G=（V，L）表示该有权图，其中 V 是图 G 中所 有节点的集合，L是图G中所有边的集合，边的总数 为 K。对于图G 中一条有权边 l ， Ll ˛ ，用两个正实 数（C，E）来描述，C 表示该边的长度，E 表示该 Vsr , 边的带宽。r ,s 是图G中两相邻节点， rsl ˛ 。假设有 M 个机器人，R 为机 是 r，s 间的边， lrs 器人 i 的半径，机器人i 在任意边上占用的带宽为 Z i，Zi=2Ri（i = 1,2 …M），机器人i 需要从源节 L , 点 P i，到达目标节点 Q i。 我们继续定义一些指标来刻画系统： （1）边 l 带宽利用率 lh ：经过边l 的所有机器 人的带宽总和与边 l 带宽的比值。 h l = E - M 1 l = 1 i Z i r il (1) ilr ：机器人i 经过边i ，则 ilr =1，否则 ilr =0。 lh 越大，说明边l 利用得越充分，但从全局观 点分析，也说明该边代表的路径非常拥挤，将增大机 器人碰撞的概率，还说明该路径比较关键，多个机器 人将经过它，它容易成为系统瓶颈，如果该路径上发 生堵塞，造成系统崩溃可能性越大。 （2 ）网络负载均衡 2 ：衡量有权图网络的负 载分布的均匀程度。机器人在有权图的边上占用的 带宽称为网络负载。 2 等于图G中各边带宽利用率的 方差。令h 为 lh 的均值 2 d (3) h ) 2 带宽利用率和网络负载均衡都是通信网络中经常 使用的指标，网络负载均衡越小，说明负载分布越 均匀，系统瓶颈越少，系统鲁棒性越强，越健壮。 具体到多机器人路径规划问题， 2 也有类似意义， 33 h 1. h (2) l k = 1 l h ( l -= k = K = 1 i ˛ -
    机器人 技术应用 栏目主持：刘 远 江 2 越小说明多个机器人将尽量在不同路径上运动， 系统消耗的资源（即 S C ）尽可能少。 碰撞概率越小，由于路径堵塞而造成多机器人系统 以下将依次给出约束条件在有权图模型上的数学 崩溃的可能性越小，规划的路径的鲁棒性越强。 （3）机器人i 的耗时Ti：机器人i 从源节点 Pi 到达目标节点Qi 的时间。之所以采用Ti 是因为我们 描述 （1 ）多机器人无碰撞的充要条件：在任意时 刻t，在边 l 上的各个机器人的带宽总和小于或等于 认为它可以完全代替常用的单体机器人路径总长的指 边 l 的带宽，即： 标，而且信息量更大。例如，我们假设机器人速度恒 定，且机器人i 无停顿，那么Ti 正比于体机器人i 路 径总长。如果，机器人i 存在停顿、等待等时间组合 现象，则Ti 不仅包含机器人运行时间还包含等待时 E l M = 1 i Z i r il t )( (6) 其中 l 上，则 ilr ilr )(t )(t 的含义为：t 时刻，若机器人i 在边 = 1 ，否则 ilr )(t = 0 间。路径规划问题实质是“空间 - 时间”组合问 （2 ）满足每个机器人生命时限： iLT ‡ Ti （7） 如上所述，该条件实际涵盖了单体机器人对路 径总长的要求。 （3）多约束条件下的多机器人路径规划是NP问 题，在特殊情况下，虽然有解，但有些指标将相互冲 突，很难同时达到最优值。 2 与SC就是一对典型的冲 突指标， 2 越小表明规划结果具有良好的鲁棒性， 瓶颈越少，但付出的代价SC总长将增加。因此，系统 最优的结果只能是部分指标折衷后的非劣解。遵照以 上思想，我们可以构建一个代价函数： DJ = da 2 + b SC (8) 其中，a ，b 是常数，用于调整网络负载均衡 和占用的总资源SC影响代价函数的相对比重。从式 题，当空间资源短缺，依靠空间组合无法解决问题时， 某些情况下，可以通过时间组合间接复制空间资源从 而扩充空间资源，使问题得到解决，文献[11]具体体 现了该规律，文献[11]中安排部分机器人停顿，调整 机器人通过通道的次序，这就是时间组合。该规律说 明时间指标能够包含长度指标的信息，采用Ti 更能 刻画本质。 （4）机器人i 的生命时限 iLT ：机器人i 从源节 点Pi 到达目标节点Qi 的最大允许时间。 （5）系统总耗时 ST：所有机器人到达目标节 点的最长时间。ST用来衡量路径规划结果的时间效率。 = ST Max iTi ), ( = ,...2,1 M （4） （6 ）径总长度 SC ：所有机器人经过的所有边 的长度总和。 = K SC M = 1 l i 1 (5) （8）可见，当负载分布越均匀且总长度越小，该代价 r ilC l 函数DJ将越小。当有权图路径选择准则使两个指标不 SC越小，说明多机器人经过的总路径长度越小， 能同时为最优时，DJ实际是二者的折衷。因此，我们 也从另一方面说明规划效果越好。 至此，我们完成了环境建模工作。现在，我 们设定有权图路径选择的准则： 路径选择准则：在满足无碰撞和每个机器人生 命时限的前提下，使有权图的负载分布尽量均匀并且 34 将DJ最小作为衡量最佳路径选择的依据。 3、基于蚁群算法的路径规划 蚁群算法的基本表述与具体形式详见文献[6，12，13]， 本文不做赘述。如第二部分所述，多机器人路径规划 - ‡
    机器人 技术应用 栏目主持：刘 远 江 问题已经转变为有权图模型的受约束路由选择问题。 是与节点 r 相邻，但该只蚂蚁尚未经过的节点集 基于第二部分建立的有权图模型、路由选择准则和 约束条件，本文所提出的基于蚁群算法的有权图模 型路由选择方法简要描述如下： 取 N 组蚂蚁,每组包含 M 个不同种类的蚂蚁，每 类蚂蚁代表一个机器人。将一组 M 个蚂蚁分别放 到其所对应的机器人的源节点上,在满足机器人无 碰撞和生命时限要求前提下,依据信息强度随机选 择下一节点,使M个蚂蚁分别完成自己的路径选择 (若有一个蚂蚁在未到达终节点前死亡,则应用同 类的一个新蚂蚁代替该蚂蚁重新进行选路,直到有 一个该类的蚂蚁完成一次源到目的节点的完整路径 选择为止),然后,对该组蚂蚁中的每一类,都局部 调整其在G图中各边上的相应类型的信息强度。当 N组蚂蚁都完成路径选择并已局部调整其相应的信 息强度后,再对图G中每条边上的M类信息强度分别 进行全局调整。重复上述过程,直到最终得到各机 器人的收敛路径为止。 下面,我们具体描述实现上述路径选择的蚁群算 法。首先,我们规定在该算法中，对任何一个节点，每 一个蚂蚁只能经过一次。我们如下定义该算法中所需 要的三个准则（节点转移准则、信息强度PH局部调整 准则、信息强度PH全局调整准则）： （ 1 ） 一 个 第 i 类 蚂 蚁 在 节 点 r 处 选 择 下 一 个 节 点 s的 转 移 准 则 节点 S 由下面的式子确定： S = ，if { 1 q £ 0q S S 2 （9） 其中 S2 满足， = sriPH , ,( ) 2 max Ju˛ ri ),( uriPH ), ,( PH（i,r,s）代表第 i 类蚂蚁在边上积累的信 息强度。S2 随机从 J（i, r）中选取。J（i, r） 合。q为区间[0，1]上是服从均匀分布的随机变量，q0 0 是一个可指定常数， £ q 0 1 。q 相当于遗传算法 中的变异因子，避免了算法过早陷入局部优化，q0相 当于设置变异激烈程度的参数，q0越大，变异的可能 性越大，算法收敛速度越慢，调整其取值，能控制算 法的收敛速度。与文献[12]提出的转移概率准则相 比，该转移准则直接采用信息强度取代概率指标，简 化了路径能见度参数项，并引入了变异因子，避免陷 入局部优化。 （ 2 ） 信 息 强 度 P H 局 部 调 整 准 则 如果r,s是一个第i类蚂蚁在其所选路径上的相 邻两节点,则按下式调整其相应的信息强度,否则,信 息强度不做调整: PH(i,r,s)←(1-a0)·PH(i,r,s)+a0·cons0/DJ (10) 其中,0
    机器人 技术应用 栏目主持：刘 远 江 使各类蚂蚁寻找全局优化解。 长度为 2。多机器人系统有4 个机器人，每个占用的 在此基础上,本文的蚂蚁算法可归纳如下: 带宽都为 3 ，（如果 3 个机器人同时出现在同一路 对于每类蚂蚁,分别对其在图G中各边上的信息强 径，将发生碰撞）生命时限为 1 8 ，速度为 1 ，不 度PH(i,r,s)进行初始化; 允许等待（即允许机器人最多通过 9 条边，也就是 取一组蚂蚁(由M个不同种类的蚂蚁组成),将其 通常的单体机器人最长总路径限制）。四个机器人 中每一个都放到其所代表的机器人的源节点上; 的任务分别为：（1 ，2 0 ）、（2 0 ，1 ）、（4 ，1 令每个蚂蚁分别根据上述转移概率准则（9 ） 8 ）、（6 ，2 3 ），第一个数为机器人源节点，第 选取路径。若一个蚂蚁在未到达目的节点前发现此 二个数为机器人目的节点。 次路径已行不通,则其退回上一节点(时限减去所退 为使网络负载均衡和总路长对代价函数的影响 回的路径对应的生命时限),重新选择其他路径;若 均等，我们令α=20.0,β=4.7,以使式(8)中右边两 某一个蚂蚁未到达目的节点就已死亡,则应在初始 项所占比重大致相同。就蚂蚁算法而言,目前,该算 点重新发送一个同类的蚂蚁;若在某时刻某边上各 法中参数值的设定尚未有明显的数学表达式作为依 蚂蚁所占用的总带宽超过该边的带宽,即机器人发 据，一般都要根据具体应用，通过实验修正参数。但 生碰撞，该蚂蚁也要重新选择路径。（在程序中设置 大量实验表明，N应与M大致相当；q0与收敛速度相 坏节点判断和坏节点处理模块，集中解决上述问 关，前期该值应该比较大，保持算法前期的随机特 题。）当每个蚂蚁都成功地完成了一次其所对应的机 性，后期应该比较小，突现算法后期的内在学习特 器人的源与目的节点之间的完整路径选择后,利用 性；a1、cons1比a0、cons0要稍大，强化全局调整的 上述局部调整准则式（10）对每类蚂蚁的信息强度 力度；a0、a1、cons0、cons1的选取与网络本身有关， PH(i,r,s)分别进行局部调整； 取较大的值可以加快算法收敛速度，但也容易出现 另取一组蚂蚁,重复(2)、(3),直到N组蚂蚁都完 局 部 优 化 。 成各自的信息强度局部调整为止； 在该算例中，我们发现 N=6,q0=0.8，a0=0.1, 在这N组中,选取代价函数DJ最小的一组蚂蚁 a1=0.2,cons0=32.0,cons1=41.0, 经过大量实验， 所选择的路由结果,利用上述全局调整准则式（11） 和式（12），对其进行信息强度的全局调整； 重复(2)～(5),直到得到各机器人的收敛路径 （即找到的都是相同解）或指定次数循环结束为 止。 4 、仿真实验 由上可知，平面的多机器人路径规划问题都能 得到相应的有权图模型，作为算法仿真研究，我们可 以任意指定一个有权图，验证算法的可行性和有效 性。我们选择图4所示的模型。节点编号如图示。为 直观判断规划结果，该模型中，所有边的带宽为 7 图 4 有权图 36
    机器人 技术应用 栏目主持：刘 远 江 算法平均在370次循环内能达到收敛。其中的一次规 参 考 文 献 划结果如表1所示（蚁群算法有人工生命系统的突现 [1]TamioARAI, JunOTA .Motion Planning of Multiple 特性，当资源非常充裕时，每次规划结果都可能不同） Mobile Robots. IEEE/RSJ Int Confon Intelligent 表 1 规 划 结 果 机器人任务 蚁群算法的规划结果（机器人节点序列） （1 ，2 0 ） 1，11，16，18，20 （2 0 ，1 ） 20 ，18，13，8，6，1 （4 ，1 8 ） 4.7 10 ，14，17，18 （6 ，2 3 ） 6，9，11，21，22，23 从该规划结果我们可以看到，各个机器人走尽 Robots and Systems,1992:1761-1768084 [2]Hajime ASAMA,KoichiOZAKI,Kujirai.Functional Distribution Among Multiple Mobile Robot in An Autonomous and Decentralized RobotSystem.IEEE Int Confon Robotics and Automation,1991:1921-1926 [3]HiroshiNoborio,Hatsu-Cho.A Cooperative Path-Pl anning for Multiple Automata by Dynamic/Static Conversion .IEEE/RSJ Int Confon Intelligent Robots and Systems,1993:1955-1962 量不同的路径，使有权图模型的网络负载分布尽可能 [4]PaoloFiorini,ZviShiller.Motion Planning in Dynamic 均匀，每个机器人的路径尽可能的短，而且当与系统 Environments Using Velocity Obstacles.Int Jour 目标有冲突的情况下，机器人个体适当牺牲了自己的 of Robotics Re-search,1998,17(7),760-772 [5]孙茂相 ,周明等. 多移动机器人实时最优运动规划. 控 局部目标，例如机器人3的最短路径应该是节点序列 制与决策,1998,13(2):125-130 （4，7，8，13，18），但与第 2 个机器人的子节点 [6] 张纪会，高齐圣等.自适应蚁群算法.控制理论与应 序列（1 8 ，1 3 ，8 ）重复，增加了系统瓶颈，而 用,2000.2,Vol 17 No.1 且节点18也是机器人1的节点，碰撞的可能性很大， [7]DORIGOM, etal. The ant system :optimization by a colony of cooperating agents [J].IEEE TransSyst Man 非常危险，所以机器人 3 放弃了最短路径，牺牲了 Cybern,1996,26(2):29～41 个体目标。机器人2的路径规划结果也有类似特点。 以上结果表明本文方法是可行且有效的。 [8]DORIGOM,GAMBARDELLALM. Ant colony system:acoop- erative learning approach to the traveling sales man problem [J].IEEE Trans Evolutionary Computation, 5、结论 1997,1(1) 近年来多机器人路径规划问题受到国内外研究 [9]马良,蒋馥.多目标旅行售货员问题的蚂蚁算法求解. 系 机构的普遍关注，已有许多研究成果发表。本文 借助最新的蚁群算法和通信网络技术提出了一整 统工程理论方法应用,1999,Vol8,No.4 [10]周明,孙树栋等.基于遗传算法的多机器人集中协调式 路径规划.航空学报,2000.3,V21,N2:146-147 套新的解决方法，经仿真实验，验证了方法的可行 [11]顾国昌,李亚波.基于总体势减小的动态调度技术解决 性和有效性，为深入研究并最终解决多机器人路径 多机器人的路径规划. 机器人,2001.3,Vol23,No.2 规划问题进行了有意义的探索。本文提出的方法具 [12]ColorniA,DorigoM,ManiezzoV.Distributed optim- ization by ant colonies.Proc1st Europeanconf arti- 有优异的可构造性，为深入研究并最终解决多机器 ficial life.Pans,France:Elsevier,1991:134～142 人路径规划问题进行了有意义的探索。本文提出了 [13] ColorniA,DorigoM,ManiezzoV,TrubianM.BelgianJ. 的方法具有优异的可构造性。能方便的扩展到多机 Oper.REs.Statist.Comp.Sci,1994,34(1):39～53 [14] 李伟华、康继昌. 人工生命初探.计算机工程与设 器人多约束多目标路径规划领域，有潜在的广阔应 计,Vol 16,No2:60～64A. 用 前 景 。 37
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料