基于SOM神经网络的多机器人任务分配问题文档格式.docx
《基于SOM神经网络的多机器人任务分配问题文档格式.docx》由会员分享，可在线阅读，更多相关《基于SOM神经网络的多机器人任务分配问题文档格式.docx（16页珍藏版）》请在冰点文库上搜索。
然而,它不适用于复杂情况,例如多数机器人被分配到同一个目标位置以及一个机器人需连续到达多个目标。
此外,该方法不能够用于处理可移动目标。
受到生物系统自发引起许多复杂模式在同质细胞中出现的启发,Shen等提出了称为“数字荷尔蒙模型”的模型,通过将一个机器人假设为一个细胞,自发组织形成一个全局多机器人系统。
它适用于一些搜索或监控给定区域和建筑物的任务,自主修复全局模式的漏洞,通过绕道避免陷阱。
为了搜索和锁定目标任务,该算法不能处理包含多个目标和动态目标的情况,如果有两个目标和四个机器人,所有的机器人靠近一个目标,而远离另一个,结果将导致一个目标吸引所有的四个机器人到达而另一目标没有机器人到达。
因此,该算法没有充分考虑机器人之间的竞争与合作。
无人驾驶飞行器（无人机任务分配的研究中也有相似的问题,它要求分配一群无人机到几个目标位置同时要躲避威胁。
无人机通常只侦察或搜索静态区域。
Beard等提出了一个解决合作与竞争的方法,通过将全局问题分解成子问题,包括目标任务、路径规划、协调无人机截获、轨迹的生成与遵循。
首先,通过泰森多边形图法的方法形成一个全局地图,描述了飞机位置、目标位置、威胁点位置
和可能减少这种威胁的路径。
基于泰森多边形图法,以每台飞机到每个目标距离中等、所遇威胁中等等成本来计算最好的路径。
然后每台飞机被分配到一个目标,将目标的团队路径长度最小化了,最小限度地减少团队的曝光威胁,实现了到达目标位置飞机数量的最大化,被访问目标的最多化,之后,再考虑目标被拦截时的协调时间,每辆飞机到其各自目标的路径将被规划好。
最后,再用这个路径来控制每辆飞机的速度。
当其它一些动态威胁出现后,再重新规划飞机的路径,以避免动态威胁。
这是一个端到端的解决方案,着重于几个不同的方面,比如通过泰森多边形图法构建地图、使用博弈论进行目标管理,拦截管理和轨迹生成等。
该解决方案不关注移动目标、动态威胁和飞机的动态性,比如添加新的飞机或某些飞机突然出现故障。
由于泰森多边形图法的限制,该方法不适用于动态环境下的无人机任务分配。
其他的研究主要集中在小群机器人的优先级控制,通常先将一项任务分成多个子任务,通过机器人之间的竞争以及少量的合作完成任务。
Miyata等提出了一种处理在一个未知的静态环境下由一群机器人将一个物体从一个地点运输到另一个地点运输问题的方法。
这种方法着重于如何将运输任务分配成许多子任务和如何将子任务分配给不同的机器人。
子任务可能包括搜索工作区,识别需要被移动的对象,移走活动障碍,处理一个对象。
此任务分配的定义侧重于不同的子任务和这些子任务优先级。
该方法仅适合静态环境下的小群机器人。
U.chibe等提出了另一种将任务分配给一群机器人的方法,这种方法需提前为任务设计模型,然后动态的将模型分配每台机器人。
该方法解决了模型选择的冲突问题,它适合于小群机器人完成可以分为子任务的任务,如由几个机器人运输物体等。
Brandt等提出了另一个多机器人系统任务分配问题,并提出了一个解决该问题的算法,该方法侧重于通过承包商进行不同任务的创建,然后选择不同兴趣的招包者,招包者与承包单位协商得到最大效益。
招包者之间更多的是竞争以及少量的合作。
虽然有些可以处理动态环境的方法,但是,为了动态环境而更改算法,这将有可能导致系统稳定性变差或增加额外的成本。
尽管提出了许多用于机器人系统的神经网络（neuralnetwork,NN方法,但大多数只适用于处理单个机器人系统或
完全已知环境的情况。
基于自组织映射SOM（Self-OrganizingFeatureMap神经网络算法用于解决多机器人系统任务分配问题,其侧重解决静态或动态环境下存在大量机器人和目标的情况。
由于算法的自组织性能,该算法对不确定的动态环境是稳定的、鲁棒的、合适的。
在该算法中,机器人运动规划与任务分配相结合,因此一旦给定全局任务机器人便开始运动。
这群移动机器人可以自动安排整个任务,无论环境何时改变,比如一些机器人出故障,一些新的机器人或任务被添加至全局任务时,或某些任务暂时取消时,都能动态地调整所有机器人的运动。
基本任务和思想论述
1基本任务描述
本文要解决的任务分配问题要求多个机器人从起始点出发,以最短的路径（或时间完成对所有目标点的侦察,同时满足安全性等方面的约束,该问题可以看成是一个约束性很强的组合优化问题。
在多机器人系统中,主要的挑战是在执行一个任务时多机器人之间的协调与合作。
在本文中,假设有一群可自主移动机器人和目标点随机的分布在有界区域R中,如图1所示。
图1包含多机器人和目标的工作区域R
每一个目标需要一定数量的机器人在那个位置来完成一项任务,目标是以最小或接近最小的总成本动态分配一组机器人到每一目标附近。
对每个机器人而言,02468
10121416
X/mY/m
成本评估是其从初始位置到最终位置的距离。
总成本定义为每台机器人成本的总和。
当每个目标所需数量机器人到达时,该任务便完成。
在图1中,点代表移动机器人的初始位置,方块代表目标位置。
此外,假定机器人是具有基本导航避障和位置识别功能的相同移动机人。
本文的多机器人系统任务分配不仅强调预期数量的机器人到每一个目标位置的分配,而且也强调机器人从它们的初始位置到目标位置总的移动距离,而目标点既可以静止又可以运动。
2基本思想的提出和解决方法
受到中枢神经系统普遍存在的皮质地图的启发,Kohonen首先在1980年提出SOM算法,随后得到扩展。
它的理论基础是:
在哺乳动物的大脑中存在一段有序的处理单元,每个部分用于特定的任务,每组神经元感应特定类型的输入信号。
术语“秩序”通常指其空间排列。
这些单元由那些在产生某些有意义的组织过程中可变的参数来决定。
因为它的普遍适用性和易处理性,该算法很快便成为一个有用的工具并且应用于许多现实世界的问题。
SOM神经网络方法基于结合竞争学习原理和拓扑神经元的结构,这些相邻神经元有类似权重向量的倾向。
该模型着重于在合理的时间内实现多机器人之间的协调,强调降低总成本和每台机器人工作量的平衡。
假设在一个工作区R中随机分布有K台机器人和M个目标。
给定的适用于多机器人系统SOM神经网络模型如图2所示。
图2基于SOM算法的神经元模型
该模型有两个层次的神经元。
第一层是包括两个神经元（ix,iy的输入层,这代表二维工作区第i个目标点的笛卡尔坐标iT。
所有目标的坐标构成输入数据集。
第二层是包括KM个神经元（11R…MR1,21R…MR2,…,1MR…MMR的输出层,
这代表K个机器人的坐标和规划路径。
在此,对每台机器人M个神经元形成一组。
每一个输出层的神经元是与输入层的神经元完全连接。
输出神经元与输入神经元的连接强度是由一个二维权向量},{kmykmxkmwwR,k=1,2,…,K;
m=1,2,…,M给出的,每台机器人的M个神经元权重向量随着机器人的初始坐标位置而初始化。
引入K组输出神经元的原因是在每台机器人工作量平衡的条件下记录K台机器人的动态轨迹。
当完成任务分配的过程时,M个目标吸引来自KM个输出神经元的M个神经元为K台机器人形成k条路径。
每台机器人有自己从初始位置通过几个目标的路径。
所有的M个目标都将被访问。
K组中M个神经元序列是机器人路径规划的客观条件。
在自组织网络中,神经元有获得包含输入向量空间特性的权重向量的倾向。
在一开始,网络由权重向量},{kmykmxww,k=1,2,…,K;
m=1,2,…,M初始化,这是机器人的初始位置。
在每次迭代后,目标坐标随着输入数据集随机的在网络中给出。
在每次迭代中,所有的目标以一个随机的顺序给出,然后将目标一个接一个的输入到网络,直到输入最后的目标。
这种数据集以随机顺序的输入策略影响该算法的鲁棒性,减少其对初始工作空间结构和输入数据集序列的依赖。
其程序流程如图3所示。
图3基于SOM算法任务分配程序流程图
在神经网络初始化后,目标位置一个接一个的输入到网络。
在一次迭代中以
一个给定的目标作为输入涉及三个步骤:
首先是找到获胜者;
其次是决定与获胜者相邻的神经元;
最后是修改获胜者及其相邻神经元的权重,这三个步骤是重复执行直到所有的权重不再变化,如此机器人根据权重的变化一步一步的移动到目标,当所有的目标均已达到任务便完成。
对于一个作为输入的给定目标,输出神经元竞争成为赢家根据指定的标准,
}},{;
...,1;
...,1,min{],[Ω∈===⇐mkandMmKkMiDNNikmmk
其中],[mkNN表明从第k组输出神经元而来的第m个神经元是获胜者,如图3-4所示,Ω是在一次迭代中还没有成为赢家的一系列神经元,加权距离1（PRTDkmiikm+-=,22（（kmyikmxikmiwywxR-+-=-表示欧几里得距离,},{kmykmxkmwwR=,k=1,2,…,K;
m=1,2,…,M,从第k组输出神经元而来的第m个神经元的坐标,参数P控制的每台机器人工作负载的平均分配,V
VLPk+-=1,kL是第k台机器人的路径长度,k=1,2,…,K;
V是机器人路径的平均长度。
获胜者不仅是对输入数据有最小距离的神经元,也是输出神经元中拥有较低工作负载的神经元。
为了限制一个神经元在每次迭代中不止一次是获胜者,为每一个神经元定义一个抑制指数θ。
这种策略把冠军神经元从未来的竞争中剔除,而为其他神经元提供更多的获胜机会。
当获胜者被选择后,下一步就是设计近邻函数,决定下一次的获胜者。
近邻函数决定了输入获胜者和近邻神经元目标位置的影响（吸引力强度。
获胜者的吸引力是最高的,越靠近获胜者的神经元吸引力越小,对非近邻的神经元没有影响。
近邻函数f定义为:
22（（,0jdGtjje
ifdrfdGotherwise
-⎧⎪<
=⎨⎪⎩（1
jd=mNj-是第j个神经元与获胜者的距离。
表示绝对值,r是一个表明相邻范围的常数。
函数01（（GtGtα-=是一个非线性函数,t是迭代次数,α是决
定计算时间的变化率,α越小,计算时间越长。
α越小,机器人的总路径就越短。
在获胜者和它相邻的神经元选定后,下一步是将获胜者和它近邻的神经元移动到输入位置目标,而其他神经元保持不动。
更新规则定义为:
⎩⎨⎧-⨯+<
=+otherwise
tRtTGdftRtTtRkmijkmikm,（（（,（（DD,（1（minikmβη（2β是学习速率,
η是一个小常数,minD是任意两个神经元之间的最短距离,minD的引入可明显降低算法计算时间。
很明显,权重的修改不仅取决于获胜者和它相邻的神经元以及输入目标神经元之间的初始距离,但取决于附近近邻函数和网络学习速率。
图4获胜神经元23R及其邻居神经元22R,点代表机器人
图4表示机器人路径规划的一次实例,方格代表作为输入神经元的目标位置。
图4（a展示了机器人位置和一个随机选择的目标（如iT作为输入。
图4（b显示了根据获胜规则选择获胜神经元,获胜者是距离输入iT最近的。
图4（c显示了根据近邻选择规则选择获胜者的近邻神经元,这个例子中22R是坐落在获胜者附近的唯一近邻神经元。
图4（d显示获胜者和它的近邻根据规则在运动。
两个神经元23R和22R通过改变权重向量和向目标移动一小段距离,而其它则保持不动。
获胜者比其近邻移动的距离大。
越接近获胜神经元,移动距离就越大。
然后循环返回图4（a
又
把另一个随机选择的目标作为输入,重复（a-（d,直到所有的目标通过机器人。
复杂情况分析
为了进一步说明了多机器人系统任务分配算法的有效性,在这一节中研究四个不同的案例,包括静态环境下的任意数量的机器人和目标。
1机器人与目标数量相同
该算法首先应用于比较简单的情况,机器人和目标的数量相同。
图3-5的四个时间示例说明了一个多机器人系统的自组织行为随时间变化的过程。
初始状态是图5（a所示,在图中方格代表目标点的位置,点代表机器人位置。
在工作空间,有10个随机分布的目标和10个随机分布的移动机器人。
在5次和20次迭代后显示单个机器人逐渐移动到目标点,如图5（b和5（c所示。
最后,当每个机器人到达一个目标点时出现一个稳定状态,如图5（d所示。
（a初始位置（b5次迭代
（c20次迭代（d最终位置
图5机器人与目标数量相同的静态环境,点代表机器人,方框代表目标点
05
1015
X/mY/m051015
X/mY/m05
X/mY/m
由于目标位置随着每次迭代以输入数据集的形式随机的进入网络,因此不同的机器人其运动轨迹不相同,但所有的结果是合理的。
在工作区中使用完全相同的初始目标和机器人的位置,两次不同的随机输入目标T的数据结果在图6中显示,方块代表目标,点代表机器人,线代表机器人到达目标的实时路径。
这些数据显示多机器人系统自组织性的动态过程,与传统的多机器人多任务路径规划方法不同,该方法中任务分配和路径规划是分开处理的。
（a实验结果1
（b实验结果2
图6目标位置输入次序不同时的实验结果,点代表机器人,方框代表目标点
该方法集成了机器人和机器人运动规划的任务要求,机器人在它们的目的地
确定之前便可以开始移动。
2机器人与目标数量未知
该算法被应用于机器人和目标的数量是随机给出的情况。
机器人和目标的初始位置也随机给出。
为了简化测试,我们假设机器人或目标的数量选择的范围为1到100。
我们进行了200次实验。
每一次,该算法可以在大约0.2秒在10分钟经过160次迭代找到一个解决方案。
例如,结果从图7所示4条轨迹可看出,点表示机器人,方块表示目标:
（a有30个目标和3机器人;
（b3目标和30机器人;
（c50个目标和60个机器人;
（d100个目标和10个机器人。
图7目标和机器人数量随机给定时的实验结果,点代表机器人,方框代表目标点显然,该方法能够处理机器人的数量小于目标数量的情况。
例如,在一个工作区如果有10台机器人和12个目标,首先,12个目标会通过竞争的方法吸引机
器人。
一些机器人实现快速到达目标,而另一些将会是缓慢的。
当任一机器人到
达目标,它便成为空闲的,可以追寻下一个目标。
图8显示了机器人在这种情况下的轨迹,R1在他到达目标T1后继续寻找目标T2,R2在他到达目标T3后继续寻找目标T4,R3在他到达目标T5后继续寻找目标T2,当R1到达T2时R3将会停止。
图8机器人数量小于目标数量,点代表机器人,方框代表目标点
机器人之间的竞争和自组织特性是有意义的,允许多机器人系统自主的完成任务分配。
3多机器人合作
该算法也可以处理常规方法不能处理的一些复杂情况,例如多个机器人同时到达一个目标点来完成某项任务,如图9所示。
图9机器人数量多于目标数量
在图9所示的情况下,目标T1需要2个机器人,T2需要1个机器人,T3需要2个机器人,T4需要3个机器人。
在一开始,机器人R1和R9都移动到目标T1
而R2移动到T2。
几个步骤之后,机器人R1和R2移动到目标T1,由于该方法的自组织特性,机器人R9停止运动。
因为R10距离任何目标都比较远,所以它不动。
显然,对于多机器人系统该方法可以自动的完成任务分配。
4机器人失效
该方法具有很强的适用性。
它可以成功的完成传统方法不能处理的突发事件,自组织特性允许过程中环境的突然变化,例如,机器人在运动过程中出现故障。
图10显示了这种情况。
开始一段时间,机器人R1移动到,机器人R2远离T1移动,向T2运动,机器人R4移动至T3,机器人R5远离T3移动至T4等。
假设一段时间后,机器人R1和R4出现故障,如图10所示。
在这种情况下,R2返回至T1,R5返回至T3。
最后,由于该方法的自组织特性,每一个目标至少都会有一个机器人到达。
图10某些机器人出现故障
讨论与分析
一个系统对参数变化的敏感性是提议或评估一个模型需重要考虑的因素。
一个可接受的模型应该对它的参数变化具有很强的适应性。
该模型对参数的变化不是很敏感,这样生成的路径不会因一个参数的小幅度变化而大幅改变。
为了分析参数的敏感性,该方法进行了许多参数变化的测试。
结果表明,学习速率β在区域[0.05,0.1]不是很敏感。
参数η在区域[0.1,0.4]的范围内不是很敏感。
参数θ
在范
围[0.01,0.1]不是很敏感。
实验还表明,迭代次数主要依赖于α的变化率。
当α初始化时为0.03时,所需的迭代次数只有160。
此外,该算法的收敛速度远远快于其他算法。
该方法能够控制一群移动机器人在几个不同的位置实现多个任务。
它结合了机器人和机器人运动规划的任务要求,这些在传统方法中通常被分开处理。
因此,一旦总任务给定机器人便可开始移动。
机器人导航可以动态调整机器人的运动以保证每个目标位置将有预期数量的机器人到达。
该模型将机器人、环境、目标作为在机器人运动时可随意改变的自组织系统。
它可以从图2所显然系统的结构模型被解释。
机器人可作为输出层的神经元。
在没有影响整个系统的情况下,神经元的数量在程序中可以改变。
因此,本文提出的方法可以处理不确定性因素,例如当一些机器人出故障或一些机器人被添加。
此外,环境中的目标看作输入层神经元。
在没有影响整个系统的情况下,输入神经元的数量在程序中可以改变,因此,该方法有能力应对不断变化的环境,比如,目标可移动或添加新目标,传统方法不能处理此类情况。
此外,该方法可以扩展到其他问题,如旅行商问题（TSP是一个典型的任务分配问题,在一个静态的工作区只有一个机器人和许多的目标。
TSP的扩展算法可以在我们之前的工作中找到,这比传统方法快了许多。
一种基于SOM神经网络算法用于复杂环境下多机器人系统的任务分配,它涉及定义初始神经网络的权重、选择获胜者的规则、更新权重的规则和近邻函数的规则等,与一个自组织过程相比,该方法具有几个很好的特性和优点。
该模型将多机器人系统的目标分配和运动规划结合在一起,使机器人在它们的目标在给定之前便可开始移动。
该算法能处理某种情况下的突发状况,例如,某些机器人出现故障或增加新的任务至全局任务等。
此外,它还可以处理复杂情况,例如分配多个机器人到目标位置或机器人少于目标数量等。
此外,它还有应对不断变化环境的能力,比如移动目标。
总结
机器学习是人工智能的主要研究领域之一,具有重要的实际应用价值。
多机器人系统任务分配是多机器人系统研究领域的一个重要的基础问题,体现了多机
器人系统的优越性和必要性。
本章介绍了SOM神经网络算法应用于多机器人系统的任务分配问题研究,阐述了设计思路的提出,以及它如何应用于多机器人系统的任务分配,最后介绍了该算法用于复杂任务条件的情况。
升级会员 