《基于SOM神经网络的多机器人任务分配问题.docx》由会员分享，可在线阅读，更多相关《基于SOM神经网络的多机器人任务分配问题.docx（15页珍藏版）》请在金锄头文库上搜索。
1、多机器人任务分解与分配问题研究绪论移动机器人是国际机器人学术界研究和关注的热点问题，随着机器人应用领域的不断拓广，单个机器人在各个方面很难满足人们的需求，研究和使用多个机器人组成一个系统，通过协商和合作完成某些复杂任务，成为一种新的趋势，并日益引起国内外研究学者的关注。特别是近二十年来，随着计算机技术、机器人技术、人工智能理论以及相关领域技术的不断成熟和发展，使得多机器人系统领域的研究从理论到实践都取得了丰富的成果。基于多机器人系统的诸多优点，其在军事、工农业生产、空间搜索、医学、交通控制、服务行业等领域具有良好的应用前景，并且已经得到一定的实际应用。如在航天领域中，利用机器人群体进行卫星和空
2、间站的内外维护以及星球搜索；在医学领域，利用大量微机器人进入肠道、胃、血管等人体狭窄部位进行检查、发现和修补病变；在工业领域中，多机器人系统在一些危险、恶劣环境下代替人自主地完成一些复杂作业；在军事领域，无人侦察机甚至无人作战飞机、无人潜艇、无人战车、排雷机器人、巡航导弹等智能武器已经开始在战场上出现，甚至发挥着重要作用。多机器人系统任务分配作为移动机器人的研究一个重要领域，其任务是在具有障碍物的环境中，按照一定的评价标准，寻找一条从起始点到达目标点的安全、高效的免碰撞的运行路径。本文通过对移动机器人最优路径的研究与规划，实现以最短的路径或时间对给定区域的侦察与扫描，使我军在作战方面拥有更多的
3、主动权是本课程设计最主要的目的。因此，本课程的研究和实现在今后的作战方面具有很强的适用性。本课题的研究对象选为多机器人协作执行搜索任务，该任务是由多个机器人协作完成任务的，在这个工作进行过程中，可以涉及到多机器人在任务级的合作与协调、多机器人简单的编队及多机器人分布式控制系统的设计等典型问题，具有很重要的理论研究价值。而且，此背景中的规则不像机器人足球中的约束性那么强，比较容易建立模型，也有利于研究工作的进行。在实际应用中，世界各国的战争方式正趋于多样化。随着高科技的应用，在战场上越来越多的机器人得到了应用，无人驾驶飞机、坦克等已经在实际中被使用。利用多机器人合作与协调进行海上巡逻、目标追踪及
4、环境侦察，具有重要的现实和长远意义。由于多机器人系统受到越来越多的关注，近几年已经有相关算法可以有效通过其内部对目标位置进行划分，然后控制使机器人以最短路径移动到目标位置。但大多数算法是在静态的环境中对任务进行分解和分配，例如，图像匹配算法，单纯的网络算法，分布式拍卖算法，蚁群算法，机器人的基本算法，和动态禁忌搜索算法。这些算法主要关注任务的分解和分配而不考虑机器人的移动问题。其结果导致机器人只能在其目标点给定后开始移动，不能达到动态的效果。此外，这些方法不适用于移动目标点。Starke等提出了使用流体自发形成模式原则，流体加热和冷却在其表面可以生成卷或六角模式的算法。获取自我行为的模式构成原
5、理其关键思想是构建一个合适的动态系统，在此系统中被识别的机器人系统可以动态变化。该算法可执行二维或三维空间中自主移动机器人到目标任务的分配。然而，它不适用于复杂情况，例如多数机器人被分配到同一个目标位置以及一个机器人需连续到达多个目标。此外，该方法不能够用于处理可移动目标。受到生物系统自发引起许多复杂模式在同质细胞中出现的启发，Shen等提出了称为“数字荷尔蒙模型”的模型，通过将一个机器人假设为一个细胞，自发组织形成一个全局多机器人系统。它适用于一些搜索或监控给定区域和建筑物的任务，自主修复全局模式的漏洞，通过绕道避免陷阱。为了搜索和锁定目标任务，该算法不能处理包含多个目标和动态目标的情况，如
6、果有两个目标和四个机器人，所有的机器人靠近一个目标，而远离另一个，结果将导致一个目标吸引所有的四个机器人到达而另一目标没有机器人到达。因此，该算法没有充分考虑机器人之间的竞争与合作。无人驾驶飞行器(无人机)任务分配的研究中也有相似的问题，它要求分配一群无人机到几个目标位置同时要躲避威胁。无人机通常只侦察或搜索静态区域。Beard等提出了一个解决合作与竞争的方法，通过将全局问题分解成子问题，包括目标任务、路径规划、协调无人机截获、轨迹的生成与遵循。首先，通过泰森多边形图法的方法形成一个全局地图，描述了飞机位置、目标位置、威胁点位置和可能减少这种威胁的路径。基于泰森多边形图法，以每台飞机到每个目标
7、距离中等、所遇威胁中等等成本来计算最好的路径。然后每台飞机被分配到一个目标，将目标的团队路径长度最小化了，最小限度地减少团队的曝光威胁，实现了到达目标位置飞机数量的最大化，被访问目标的最多化，之后，再考虑目标被拦截时的协调时间，每辆飞机到其各自目标的路径将被规划好。最后，再用这个路径来控制每辆飞机的速度。当其它一些动态威胁出现后，再重新规划飞机的路径，以避免动态威胁。这是一个端到端的解决方案，着重于几个不同的方面，比如通过泰森多边形图法构建地图、使用博弈论进行目标管理，拦截管理和轨迹生成等。该解决方案不关注移动目标、动态威胁和飞机的动态性，比如添加新的飞机或某些飞机突然出现故障。由于泰森多边形
8、图法的限制，该方法不适用于动态环境下的无人机任务分配。其他的研究主要集中在小群机器人的优先级控制，通常先将一项任务分成多个子任务，通过机器人之间的竞争以及少量的合作完成任务。Miyata等提出了一种处理在一个未知的静态环境下由一群机器人将一个物体从一个地点运输到另一个地点运输问题的方法。这种方法着重于如何将运输任务分配成许多子任务和如何将子任务分配给不同的机器人。子任务可能包括搜索工作区，识别需要被移动的对象，移走活动障碍，处理一个对象。此任务分配的定义侧重于不同的子任务和这些子任务优先级。该方法仅适合静态环境下的小群机器人。U.chibe等提出了另一种将任务分配给一群机器人的方法，这种方法需
9、提前为任务设计模型，然后动态的将模型分配每台机器人。该方法解决了模型选择的冲突问题，它适合于小群机器人完成可以分为子任务的任务，如由几个机器人运输物体等。Brandt等提出了另一个多机器人系统任务分配问题，并提出了一个解决该问题的算法，该方法侧重于通过承包商进行不同任务的创建，然后选择不同兴趣的招包者，招包者与承包单位协商得到最大效益。招包者之间更多的是竞争以及少量的合作。虽然有些可以处理动态环境的方法，但是，为了动态环境而更改算法，这将有可能导致系统稳定性变差或增加额外的成本。尽管提出了许多用于机器人系统的神经网络(neural network, NN)方法，但大多数只适用于处理单个机器人系
10、统或完全已知环境的情况。基于自组织映射SOM（Self-Organizing Feature Map）神经网络算法用于解决多机器人系统任务分配问题，其侧重解决静态或动态环境下存在大量机器人和目标的情况。由于算法的自组织性能，该算法对不确定的动态环境是稳定的、鲁棒的、合适的。在该算法中，机器人运动规划与任务分配相结合，因此一旦给定全局任务机器人便开始运动。这群移动机器人可以自动安排整个任务，无论环境何时改变，比如一些机器人出故障，一些新的机器人或任务被添加至全局任务时，或某些任务暂时取消时，都能动态地调整所有机器人的运动。基本任务和思想论述1 基本任务描述本文要解决的任务分配问题要求多个机器人从
11、起始点出发，以最短的路径（或时间）完成对所有目标点的侦察，同时满足安全性等方面的约束，该问题可以看成是一个约束性很强的组合优化问题。在多机器人系统中，主要的挑战是在执行一个任务时多机器人之间的协调与合作。在本文中，假设有一群可自主移动机器人和目标点随机的分布在有界区域R中，如图1所示。图1包含多机器人和目标的工作区域R每一个目标需要一定数量的机器人在那个位置来完成一项任务，目标是以最小或接近最小的总成本动态分配一组机器人到每一目标附近。对每个机器人而言，成本评估是其从初始位置到最终位置的距离。总成本定义为每台机器人成本的总和。当每个目标所需数量机器人到达时，该任务便完成。在图1中，点代表移动机
12、器人的初始位置，方块代表目标位置。此外，假定机器人是具有基本导航避障和位置识别功能的相同移动机人。本文的多机器人系统任务分配不仅强调预期数量的机器人到每一个目标位置的分配，而且也强调机器人从它们的初始位置到目标位置总的移动距离，而目标点既可以静止又可以运动。2 基本思想的提出和解决方法受到中枢神经系统普遍存在的皮质地图的启发，Kohonen首先在1980年提出SOM算法，随后得到扩展。它的理论基础是：在哺乳动物的大脑中存在一段有序的处理单元，每个部分用于特定的任务，每组神经元感应特定类型的输入信号。术语“秩序”通常指其空间排列。这些单元由那些在产生某些有意义的组织过程中可变的参数来决定。因为它
13、的普遍适用性和易处理性，该算法很快便成为一个有用的工具并且应用于许多现实世界的问题。SOM神经网络方法基于结合竞争学习原理和拓扑神经元的结构，这些相邻神经元有类似权重向量的倾向。该模型着重于在合理的时间内实现多机器人之间的协调，强调降低总成本和每台机器人工作量的平衡。假设在一个工作区R中随机分布有K台机器人和M个目标。给定的适用于多机器人系统SOM神经网络模型如图2所示。wkiywkix输出层输入层图2基于SOM算法的神经元模型该模型有两个层次的神经元。第一层是包括两个神经元(,)的输入层，这代表二维工作区第i个目标点的笛卡尔坐标。所有目标的坐标构成输入数据集。第二层是包括KM个神经元(，)的
14、输出层，这代表K个机器人的坐标和规划路径。在此，对每台机器人M个神经元形成一组。每一个输出层的神经元是与输入层的神经元完全连接。输出神经元与输入神经元的连接强度是由一个二维权向量，k=1，2，K；m=1，2，M给出的，每台机器人的M个神经元权重向量随着机器人的初始坐标位置而初始化。引入K组输出神经元的原因是在每台机器人工作量平衡的条件下记录K台机器人的动态轨迹。当完成任务分配的过程时，M个目标吸引来自KM个输出神经元的M个神经元为K台机器人形成k条路径。每台机器人有自己从初始位置通过几个目标的路径。所有的M个目标都将被访问。K组中M个神经元序列是机器人路径规划的客观条件。在自组织网络中，神经元
15、有获得包含输入向量空间特性的权重向量的倾向。在一开始，网络由权重向量，k=1，2，K；m=1，2，M初始化，这是机器人的初始位置。在每次迭代后，目标坐标随着输入数据集随机的在网络中给出。在每次迭代中，所有的目标以一个随机的顺序给出，然后将目标一个接一个的输入到网络，直到输入最后的目标。这种数据集以随机顺序的输入策略影响该算法的鲁棒性，减少其对初始工作空间结构和输入数据集序列的依赖。其程序流程如图3所示。图3基于SOM算法任务分配程序流程图在神经网络初始化后，目标位置一个接一个的输入到网络。在一次迭代中以一个给定的目标作为输入涉及三个步骤：首先是找到获胜者；其次是决定与获胜者相邻的神经元；最后是
16、修改获胜者及其相邻神经元的权重，这三个步骤是重复执行直到所有的权重不再变化，如此机器人根据权重的变化一步一步的移动到目标，当所有的目标均已达到任务便完成。对于一个作为输入的给定目标，输出神经元竞争成为赢家根据指定的标准，其中表明从第k组输出神经元而来的第m个神经元是获胜者，如图3-4所示，是在一次迭代中还没有成为赢家的一系列神经元，加权距离，表示欧几里得距离，k=1，2，K；m=1，2，M，从第k组输出神经元而来的第m个神经元的坐标，参数P控制的每台机器人工作负载的平均分配，是第k台机器人的路径长度，k=1，2，K；V是机器人路径的平均长度。获胜者不仅是对输入数据有最小距离的神经元，也是输出神经元中拥有较低工作负载的神经元。为了限制一个神经元在每次迭代中不止一次是获胜者，为每一个神经元定义一个抑制指数。这种策略把冠军神经元从未来的竞争中剔除，而为其他神
