基于神经网络的多机器人任务配问题.docx

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