基于SOM神经网络的多机器人任务分配问题文档格式.docx

1、然而,它不适用于复杂情 况,例如多数机器人被分配到同一个目标位置以及一个机器人需连续到达多个目 标。此外,该方法不能够用于处理可移动目标。受到生物系统自发引起许多复杂模式在同质细胞中出现的启发, Shen 等提出 了称为“数字荷尔蒙模型”的模型,通过将一个机器人假设为一个细胞,自发组 织形成一个全局多机器人系统。它适用于一些搜索或监控给定区域和建筑物的任 务,自主修复全局模式的漏洞,通过绕道避免陷阱。为了搜索和锁定目标任务, 该算法不能处理包含多个目标和动态目标的情况, 如果有两个目标和四个机器人, 所有的机器人靠近一个目标,而远离另一个,结果将导致一个目标吸引所有的四 个机器人到达而另一目标

2、没有机器人到达。因此,该算法没有充分考虑机器人之 间的竞争与合作。无人驾驶飞行器 （无人机 任务分配的研究中也有相似的问题,它要求分配一 群无人机到几个目标位置同时要躲避威胁。无人机通常只侦察或搜索静态区域。 Beard 等提出了一个解决合作与竞争的方法,通过将全局问题分解成子问题,包 括目标任务、路径规划、协调无人机截获、轨迹的生成与遵循。首先,通过泰森 多边形图法的方法形成一个全局地图,描述了飞机位置、目标位置、威胁点位置和可能减少这种威胁的路径。基于泰森多边形图法,以每台飞机到每个目标距离 中等、 所遇威胁中等等成本来计算最好的路径。 然后每台飞机被分配到一个目标, 将目标的团队路径长度

3、最小化了,最小限度地减少团队的曝光威胁,实现了到达 目标位置飞机数量的最大化,被访问目标的最多化,之后,再考虑目标被拦截时 的协调时间,每辆飞机到其各自目标的路径将被规划好。最后,再用这个路径来 控制每辆飞机的速度。当其它一些动态威胁出现后,再重新规划飞机的路径,以 避免动态威胁。这是一个端到端的解决方案,着重于几个不同的方面,比如通过 泰森多边形图法构建地图、使用博弈论进行目标管理,拦截管理和轨迹生成等。 该解决方案不关注移动目标、动态威胁和飞机的动态性,比如添加新的飞机或某 些飞机突然出现故障。由于泰森多边形图法的限制,该方法不适用于动态环境下 的无人机任务分配。其他的研究主要集中在小群机

4、器人的优先级控制,通常先将一项任务分成多 个子任务,通过机器人之间的竞争以及少量的合作完成任务。 Miyata 等提出了一 种处理在一个未知的静态环境下由一群机器人将一个物体从一个地点运输到另一 个地点运输问题的方法。这种方法着重于如何将运输任务分配成许多子任务和如 何将子任务分配给不同的机器人。子任务可能包括搜索工作区,识别需要被移动 的对象,移走活动障碍,处理一个对象。此任务分配的定义侧重于不同的子任务 和这些子任务优先级。该方法仅适合静态环境下的小群机器人。U.chibe 等提出了另一种将任务分配给一群机器人的方法, 这种方法需提前为 任务设计模型,然后动态的将模型分配每台机器人。该方法

5、解决了模型选择的冲 突问题,它适合于小群机器人完成可以分为子任务的任务,如由几个机器人运输 物体等。Brandt 等提出了另一个多机器人系统任务分配问题,并提出了一个解决该问 题的算法,该方法侧重于通过承包商进行不同任务的创建,然后选择不同兴趣的 招包者,招包者与承包单位协商得到最大效益。招包者之间更多的是竞争以及少 量的合作。虽然有些可以处理动态环境的方法,但是,为了动态环境而更改算法,这将 有可能导致系统稳定性变差或增加额外的成本。尽管提出了许多用于机器人系统 的神经网络 （neural network, NN 方法,但大多数只适用于处理单个机器人系统或完全已知环境的情况。基于自组织映射

6、SOM （Self-Organizing Feature Map神经网络算法用于解决 多机器人系统任务分配问题,其侧重解决静态或动态环境下存在大量机器人和目 标的情况。由于算法的自组织性能,该算法对不确定的动态环境是稳定的、鲁棒 的、合适的。在该算法中,机器人运动规划与任务分配相结合,因此一旦给定全 局任务机器人便开始运动。这群移动机器人可以自动安排整个任务,无论环境何 时改变,比如一些机器人出故障,一些新的机器人或任务被添加至全局任务时, 或某些任务暂时取消时,都能动态地调整所有机器人的运动。基本任务和思想论述1 基本任务描述本文要解决的任务分配问题要求多个机器人从起始点出发, 以最短的路径

7、 （或 时间完成对所有目标点的侦察,同时满足安全性等方面的约束,该问题可以看 成是一个约束性很强的组合优化问题。在多机器人系统中,主要的挑战是在执行 一个任务时多机器人之间的协调与合作。在本文中,假设有一群可自主移动机器 人和目标点随机的分布在有界区域 R 中,如图 1所示。 图 1 包含多机器人和目标的工作区域 R每一个目标需要一定数量的机器人在那个位置来完成一项任务,目标是以最 小或接近最小的总成本动态分配一组机器人到每一目标附近。 对每个机器人而言, 0246810121416X /mY /m成本评估是其从初始位置到最终位置的距离。总成本定义为每台机器人成本的总 和。当每个目标所需数量机

8、器人到达时,该任务便完成。在图 1中,点代表移动 机器人的初始位置,方块代表目标位置。此外,假定机器人是具有基本导航避障 和位置识别功能的相同移动机人。本文的多机器人系统任务分配不仅强调预期数 量的机器人到每一个目标位置的分配,而且也强调机器人从它们的初始位置到目 标位置总的移动距离,而目标点既可以静止又可以运动。2 基本思想的提出和解决方法受到中枢神经系统普遍存在的皮质地图的启发, Kohonen 首先在 1980年提出 SOM 算法,随后得到扩展。 它的理论基础是:在哺乳动物的大脑中存在一段有序 的处理单元,每个部分用于特定的任务,每组神经元感应特定类型的输入信号。 术语“秩序”通常指其空

9、间排列。这些单元由那些在产生某些有意义的组织过程中可变的参数来决定。因为它 的普遍适用性和易处理性,该算法很快便成为一个有用的工具并且应用于许多现 实世界的问题。 SOM 神经网络方法基于结合竞争学习原理和拓扑神经元的结构, 这些相邻神经元有类似权重向量的倾向。该模型着重于在合理的时间内实现多机器人之间的协调,强调降低总成本和 每台机器人工作量的平衡。假设在一个工作区 R 中随机分布有 K 台机器人和 M 个目标。给定的适用于多机器人系统 SOM 神经网络模型如图 2所示。图 2 基于 SOM 算法的神经元模型该模型有两个层次的神经元。第一层是包括两个神经元 （i x , i y 的输入层,这

10、 代表二维工作区第 i 个目标点的笛卡尔坐标 i T 。 所有目标的坐标构成输入数据集。 第二层是包括 KM 个神经元 （11R M R 1, 21R M R 2, , 1M R MM R 的输出层,这代表 K 个机器人的坐标和规划路径。 在此, 对每台机器人 M 个神经元形成一组。 每一个输出层的神经元是与输入层的神经元完全连接。输出神经元与输入神经元 的连接强度是由一个二维权向量 , km y km x km w w R , k =1, 2, , K ; m =1, 2, , M 给出的, 每台机器人的 M 个神经元权重向量随着机器人的初始坐标位置而初始 化。 引入 K 组输出神经元的原因

11、是在每台机器人工作量平衡的条件下记录 K 台机 器人的动态轨迹。当完成任务分配的过程时, M 个目标吸引来自 KM 个输出神经 元的 M 个神经元为 K 台机器人形成 k 条路径。 每台机器人有自己从初始位置通过 几个目标的路径。所有的 M 个目标都将被访问。 K 组中 M 个神经元序列是机器 人路径规划的客观条件。在自组织网络中,神经元有获得包含输入向量空间特性的权重向量的倾向。 在一开始,网络由权重向量 , km y km x w w , k =1, 2, , K ; m =1, 2, , M 初始 化,这是机器人的初始位置。在每次迭代后,目标坐标随着输入数据集随机的在 网络中给出。在每次

12、迭代中,所有的目标以一个随机的顺序给出,然后将目标一 个接一个的输入到网络,直到输入最后的目标。这种数据集以随机顺序的输入策 略影响该算法的鲁棒性,减少其对初始工作空间结构和输入数据集序列的依赖。 其程序流程如图 3所示。图 3 基于 SOM 算法任务分配程序流程图在神经网络初始化后,目标位置一个接一个的输入到网络。在一次迭代中以一个给定的目标作为输入涉及三个步骤:首先是找到获胜者;其次是决定与获胜 者相邻的神经元;最后是修改获胜者及其相邻神经元的权重,这三个步骤是重复 执行直到所有的权重不再变化,如此机器人根据权重的变化一步一步的移动到目 标,当所有的目标均已达到任务便完成。对于一个作为输入

13、的给定目标,输出神经元竞争成为赢家根据指定的标准, ; ,., 1; ,., 1, min, =m k and M m K k M i D N N ikm m k其中 , m k N N 表明从第 k 组输出神经元而来的第 m 个神经元是获胜者,如图 3-4所 示 , 是 在 一 次 迭 代 中 还 没 有 成 为 赢 家 的 一 系 列 神 经 元 , 加 权 距 离 1（P R T D km i ikm +-=, 22 （ （kmy i kmx i km i w y w x R -+-=-表示欧几里得距离, , km y km x km w w R =, k =1, 2, , K ; m

14、=1, 2, , M ,从第 k 组输出神经元而来 的第 m 个神经元的坐标,参数 P 控制的每台机器人工作负载的平均分配, VV L P k +-=1, k L 是第 k 台机器人的路径长度, k =1, 2, , K ; V 是机器人路径的 平均长度。获胜者不仅是对输入数据有最小距离的神经元,也是输出神经元中拥 有较低工作负载的神经元。 为了限制一个神经元在每次迭代中不止一次是获胜者, 为每一个神经元定义一个抑制指数 。这种策略把冠军神经元从未来的竞争中剔 除,而为其他神经元提供更多的获胜机会。当获胜者被选择后,下一步就是设计近邻函数,决定下一次的获胜者。近邻 函数决定了输入获胜者和近邻神

15、经元目标位置的影响 （吸引力强度 。获胜者的吸 引力是最高的, 越靠近获胜者的神经元吸引力越小, 对非近邻的神经元没有影响。 近邻函数 f 定义为:22（ （, 0j d G t j j eif d r f d G otherwise-= （1j d =m N j -是第 j 个神经元与获胜者的距离。表示绝对值, r 是一个表明 相邻范围的常数。 函数 0 1（ （G t G t -=是一个非线性函数, t 是迭代次数, 是决定计算时间的变化率, 越小, 计算时间越长。 越小, 机器人的总路径就越短。在获胜者和它相邻的神经元选定后,下一步是将获胜者和它近邻的神经元移 动到输入位置目标,而其他神

16、经元保持不动。更新规则定义为:-+=+otherwiset R t T G d f t R t T t R km i j km i km , （ （ , （ （ D D , （ 1（min ikm （2 是学习速率 ,是一个小常数, min D 是任意两个神经元之间的最短距离, min D 的引入可明显降低算法计算时间。很明显,权重的修改不仅取决于获胜者和它相 邻的神经元以及输入目标神经元之间的初始距离,但取决于附近近邻函数和网络 学习速率。图 4 获胜神经元 23R 及其邻居神经元 22R ,点代表机器人图 4表示机器人路径规划的一次实例, 方格代表作为输入神经元的目标位置。 图 4（a展示

17、了机器人位置和一个随机选择的目标 （如 i T 作为输入。 图 4（b显示了根 据获胜规则选择获胜神经元,获胜者是距离输入 i T 最近的。图 4（c显示了根据近 邻选择规则选择获胜者的近邻神经元, 这个例子中 22R 是 坐落在获胜者附近的唯一 近邻神经元。 图 4（d显示获胜者和它的近邻根据规则在运动。 两个神经元 23R 和 22R 通过改变权重向量和向目标移动一小段距离,而其它则保持不动。获胜者比其近 邻移动的距离大。越接近获胜神经元,移动距离就越大。然后循环返回图 4（a又把另一个随机选择的目标作为输入 , 重复 （a-（d,直到所有的目标通过机器人。复杂情况分析为了进一步说明了多机

18、器人系统任务分配算法的有效性,在这一节中研究四 个不同的案例,包括静态环境下的任意数量的机器人和目标。1 机器人与目标数量相同该算法首先应用于比较简单的情况,机器人和目标的数量相同。图 3-5的四 个时间示例说明了一个多机器人系统的自组织行为随时间变化的过程。初始状态 是图 5（a所示, 在图中方格代表目标点的位置, 点代表机器人位置。 在工作空间, 有 10个随机分布的目标和 10个随机分布的移动机器人。 在 5次和 20次迭代后显 示单个机器人逐渐移动到目标点,如图 5（b和 5（c所示。最后,当每个机器人到 达一个目标点时出现一个稳定状态,如图 5（d所示。（a初始位置 （b5次迭代（c

19、20次迭代 （d最终位置图 5 机器人与目标数量相同的静态环境,点代表机器人,方框代表目标点051015X/mY /m 051015X/mY /m 05X/mY /m由于目标位置随着每次迭代以输入数据集的形式随机的进入网络,因此不同 的机器人其运动轨迹不相同,但所有的结果是合理的。在工作区中使用完全相同 的初始目标和机器人的位置,两次不同的随机输入目标 T 的数据结果在图 6中显 示,方块代表目标,点代表机器人,线代表机器人到达目标的实时路径。这些数 据显示多机器人系统自组织性的动态过程,与传统的多机器人多任务路径规划方 法不同,该方法中任务分配和路径规划是分开处理的。（a实验结果 1（b实验

20、结果 2图 6目标位置输入次序不同时的实验结果,点代表机器人,方框代表目标点该方法集成了机器人和机器人运动规划的任务要求,机器人在它们的目的地确定之前便可以开始移动。2 机器人与目标数量未知该算法被应用于机器人和目标的数量是随机给出的情况。机器人和目标的初 始位置也随机给出。为了简化测试,我们假设机器人或目标的数量选择的范围为 1到 100。我们进行了 200次实验。每一次,该算法可以在大约 0.2秒在 10分钟 经过 160次迭代找到一个解决方案。例如,结果从图 7所示 4条轨迹可看出,点 表示机器人,方块表示目标:（a 有 30个目标和 3机器人; （b 3目标和 30机器 人; （c 5

21、0个目标和 60个机器人; （d 100个目标和 10个机器人。图 7目标和机器人数量随机给定时的实验结果,点代表机器人,方框代表目标点 显然,该方法能够处理机器人的数量小于目标数量的情况。例如,在一个工 作区如果有 10台机器人和 12个目标,首先, 12个目标会通过竞争的方法吸引机器人。一些机器人实现快速到达目标,而另一些将会是缓慢的。当任一机器人到达目标,它便成为空闲的,可以追寻下一个目标。图 8显示了机器人在这种情况 下的轨迹, R 1在他到达目标 T 1后继续寻找目标 T 2, R 2在他到达目标 T 3后继续寻 找目标 T 4, R 3在他到达目标 T 5后继续寻找目标 T 2,

22、当 R 1到达 T 2时 R 3将会停止。图 8 机器人数量小于目标数量,点代表机器人,方框代表目标点机器人之间的竞争和自组织特性是有意义的,允许多机器人系统自主的完成 任务分配。3 多机器人合作该算法也可以处理常规方法不能处理的一些复杂情况,例如多个机器人同时 到达一个目标点来完成某项任务,如图 9所示。图 9 机器人数量多于目标数量在图 9所示的情况下,目标 T 1需要 2个机器人, T 2需要 1个机器人, T 3需 要 2个机器人, T 4需要 3个机器人。 在一开始, 机器人 R 1和 R 9都移动到目标 T 1,而 R 2移动到 T 2。几个步骤之后,机器人 R 1和 R 2移动到

23、目标 T 1,由于该方法的 自组织特性, 机器人 R 9停止运动。 因为 R 10距离任何目标都比较远, 所以它不动。 显然,对于多机器人系统该方法可以自动的完成任务分配。4 机器人失效该方法具有很强的适用性。 它可以成功的完成传统方法不能处理的突发事件, 自组织特性允许过程中环境的突然变化,例如,机器人在运动过程中出现故障。 图 10显示了这种情况。开始一段时间,机器人 R 1移动到,机器人 R 2远离 T 1移 动,向 T 2运动,机器人 R 4移动至 T 3,机器人 R 5远离 T 3移动至 T 4等。假设一段 时间后, 机器人 R 1和 R 4出现故障, 如图 10所示。 在这种情况下

24、, R 2返回至 T 1, R 5返回至 T 3。最后,由于该方法的自组织特性,每一个目标至少都会有一个机器 人到达。图 10 某些机器人出现故障讨论与分析一个系统对参数变化的敏感性是提议或评估一个模型需重要考虑的因素。一 个可接受的模型应该对它的参数变化具有很强的适应性。该模型对参数的变化不 是很敏感,这样生成的路径不会因一个参数的小幅度变化而大幅改变。为了分析 参数的敏感性,该方法进行了许多参数变化的测试。结果表明,学习速率 在区 域 0.05, 0.1不是很敏感。 参数 在区域 0.1, 0.4的范围内不是很敏感。 参数 在范围 0.01, 0.1不是很敏感。实验还表明,迭代次数主要依赖

25、于 的变化率。当 初 始化时为 0.03时,所需的迭代次数只有 160。此外,该算法的收敛速度远远快于 其他算法。该方法能够控制一群移动机器人在几个不同的位置实现多个任务。它结合了 机器人和机器人运动规划的任务要求, 这些在传统方法中通常被分开处理。 因此, 一旦总任务给定机器人便可开始移动。机器人导航可以动态调整机器人的运动以 保证每个目标位置将有预期数量的机器人到达。该模型将机器人、 环境、 目标作为在机器人运动时可随意改变的自组织系统。 它可以从图 2所显然系统的结构模型被解释。机器人可作为输出层的神经元。在 没有影响整个系统的情况下,神经元的数量在程序中可以改变。因此,本文提出 的方法

26、可以处理不确定性因素,例如当一些机器人出故障或一些机器人被添加。 此外,环境中的目标看作输入层神经元。在没有影响整个系统的情况下,输入神 经元的数量在程序中可以改变, 因此, 该方法有能力应对不断变化的环境, 比如, 目标可移动或添加新目标,传统方法不能处理此类情况。此外, 该方法可以扩展到其他问题, 如旅行商问题 （TSP是一个典型的任务分 配问题,在一个静态的工作区只有一个机器人和许多的目标。 TSP 的扩展算法可 以在我们之前的工作中找到,这比传统方法快了许多。一种基于 SOM 神经网络算法用于复杂环境下多机器人系统的任务分配,它 涉及定义初始神经网络的权重、选择获胜者的规则、更新权重的

27、规则和近邻函数 的规则等,与一个自组织过程相比,该方法具有几个很好的特性和优点。该模型 将多机器人系统的目标分配和运动规划结合在一起,使机器人在它们的目标在给 定之前便可开始移动。该算法能处理某种情况下的突发状况,例如,某些机器人 出现故障或增加新的任务至全局任务等。此外,它还可以处理复杂情况,例如分 配多个机器人到目标位置或机器人少于目标数量等。此外,它还有应对不断变化 环境的能力,比如移动目标。总结机器学习是人工智能的主要研究领域之一,具有重要的实际应用价值。多机 器人系统任务分配是多机器人系统研究领域的一个重要的基础问题,体现了多机器人系统的优越性和必要性。本章介绍了 SOM 神经网络算法应用于多机器人系 统的任务分配问题研究,阐述了设计思路的提出,以及它如何应用于多机器人系 统的任务分配,最后介绍了该算法用于复杂任务条件的情况。