基于遗传算法的多机器人联盟形成 （外文翻译）.rar
基于遗传算法的多机器人联盟形成 （外文翻译）,基于遗传算法的多机器人联盟形成hui-yi liu, jin-feng chencomputer & information engineering college, hohai university nanjing, 210098,chinae-mail: hyliu@hhu.edu.cn,hhuchen@163.c...
该文档为压缩文件,包含的文件列表如下:
内容介绍
原文档由会员 wanli1988go 发布
基于遗传算法的多机器人联盟形成
HUI-YI LIU, JIN-FENG CHEN
Computer & Information Engineering College, Hohai University Nanjing, 210098,China
E-MAIL: hyliu@hhu.edu.cn,hhuchen@163.com
摘要：
在多机器人领域，联盟形成是一个关键问题。单任务或多任务的多机器人协作，一般是通过找到联盟的最高值或联盟结构的最大总联盟值实现。传统上，详尽无遗的方法是用来获得最优的联合或联盟的结构与巨大的消费量都在计算时间和通信开销，而可能的结果，在搜索组合爆炸。本文中，MAS（多Agent系统）中Agent联盟合作，是适用于多机器人系统与多机器人联盟和联盟结构遗传算法的形成，使得多机器人联盟和联盟结构在执行任务时通过寻找最优解或可行的解决方案，以获得尽可能最大联盟值。
关键词： 多机器人协作; Agent;联盟形成; 遗传算法
1 .绪论
在多机器人系统中，如果单一机器人不能或不能有效地完成一项特定任务，机器人形成一定的组合（如联盟） ，以便完成这项工作并达到整体优化 。由于不同成员的的数量和能力不同，不同的机器人联盟在执行任务时的效率和代价不同。优先形成最佳机器人联盟并合理分配任务，使得执行任务时代价最小且效益最大。在多机器人系统中，机器人联盟形成是一个优化问题。与其他优化问题一样，联盟形成问题也是一个优化问题，与其他的优化问题一样，它需要在复杂而庞大的搜索空间中寻找最优解或满意解 。这种联盟形成的策略是为任务分配寻找全局择优的方法。为了达到那个目的，任务分配过程巨细无遗地列举了所有可能的联盟，并试图分配每一项任务，最终达到整体优化。对于一个n个机器人的系统，所有可能的联盟有 。当n是比较大时，这种方法会消耗很多计算时间和通信开销并有可能导致搜索组合爆炸。许多研究人员研究了如何降低复杂性的详细方法。Shehory 介绍了一种常数 K 来限制Agent联盟中Agent的数量的方法，这种方法有效降低了Agent的数量，通信开销与计算负荷，节省了形成联盟的时间，并增加了联盟效率。不过，在测定K和联盟形成时也存在一些盲目性。Sinclair 和Billionnet 引入了低估计方法， 通过给定的限制的要求减少搜索空间，降低搜索树。这两种方法都对降低高代价求解最优解时的复杂性做了很多工作，并且往往能得到次优解。在本文中，Agent联盟合作在MAS（多Agent系统）中适用于使用遗传算法 解决机器人联盟的多机器人系统。使用遗传算法，一方面可以极大地减少寻找最优解或可行解的开销，另一方面它所找到的解(联盟/联盟结构)执行任务时的开销也比较小，能够充分提高整个系统的效率。
Abstract:
Coalition formation is a key problem in multi-robot
cooperation. The formation of multi-robot cooperation for
single or multi-task is settled via finding the coalition
maximum value or the coalition structure with the largest
total coalition value. Traditionally, exhaustive method is used
to get the optimal coalition or coalition structure with huge
consumption in both computation time and communication
overhead, which possibly results in search combination
explosion. In this paper, agent coalition cooperation in MAS
(Multi-Agent System) is applied in multi-robot system with
genetic algorithm for the formation of multi-robot coalition
and coalition structure in order to gain the possible maximum
coalition value during task execution through finding the
optimal solution or feasible solution for multi-robot coalition
and coalition structure.
Keywords:
Multi-robot Cooperation; Agent; Coalition Formation;
Genetic Algorithm
1.ntroduction
If a single robot can not or not effectively complete a
given task in multi-robot systems, robots form a certain
combination (such as coalition) to complete it and reach
global optimization[1]. Different robot coalitions execute
tasks at different efficiency and cost due to the different
number and ability of their members. It is a priority to form
a best robot coalition and assign the task reasonably with
maximum benefit at lest cost during task execution in
multi-robot cooperation.
In multi-robot systems, the formation of robot
coalition is an optimization problem. The same with other
optimization ones, it requires the optimal or satisfying
solution in a complex and large searching space [2,3]. The
strategy for the coalition formation is looking for a global
optimization plan for task assignment. To reach that, the
HUI-YI LIU, JIN-FENG CHEN
Computer & Information Engineering College, Hohai University Nanjing, 210098,China
E-MAIL: hyliu@hhu.edu.cn,hhuchen@163.com
摘要：
在多机器人领域，联盟形成是一个关键问题。单任务或多任务的多机器人协作，一般是通过找到联盟的最高值或联盟结构的最大总联盟值实现。传统上，详尽无遗的方法是用来获得最优的联合或联盟的结构与巨大的消费量都在计算时间和通信开销，而可能的结果，在搜索组合爆炸。本文中，MAS（多Agent系统）中Agent联盟合作，是适用于多机器人系统与多机器人联盟和联盟结构遗传算法的形成，使得多机器人联盟和联盟结构在执行任务时通过寻找最优解或可行的解决方案，以获得尽可能最大联盟值。
关键词： 多机器人协作; Agent;联盟形成; 遗传算法
1 .绪论
在多机器人系统中，如果单一机器人不能或不能有效地完成一项特定任务，机器人形成一定的组合（如联盟） ，以便完成这项工作并达到整体优化 。由于不同成员的的数量和能力不同，不同的机器人联盟在执行任务时的效率和代价不同。优先形成最佳机器人联盟并合理分配任务，使得执行任务时代价最小且效益最大。在多机器人系统中，机器人联盟形成是一个优化问题。与其他优化问题一样，联盟形成问题也是一个优化问题，与其他的优化问题一样，它需要在复杂而庞大的搜索空间中寻找最优解或满意解 。这种联盟形成的策略是为任务分配寻找全局择优的方法。为了达到那个目的，任务分配过程巨细无遗地列举了所有可能的联盟，并试图分配每一项任务，最终达到整体优化。对于一个n个机器人的系统，所有可能的联盟有 。当n是比较大时，这种方法会消耗很多计算时间和通信开销并有可能导致搜索组合爆炸。许多研究人员研究了如何降低复杂性的详细方法。Shehory 介绍了一种常数 K 来限制Agent联盟中Agent的数量的方法，这种方法有效降低了Agent的数量，通信开销与计算负荷，节省了形成联盟的时间，并增加了联盟效率。不过，在测定K和联盟形成时也存在一些盲目性。Sinclair 和Billionnet 引入了低估计方法， 通过给定的限制的要求减少搜索空间，降低搜索树。这两种方法都对降低高代价求解最优解时的复杂性做了很多工作，并且往往能得到次优解。在本文中，Agent联盟合作在MAS（多Agent系统）中适用于使用遗传算法 解决机器人联盟的多机器人系统。使用遗传算法，一方面可以极大地减少寻找最优解或可行解的开销，另一方面它所找到的解(联盟/联盟结构)执行任务时的开销也比较小，能够充分提高整个系统的效率。
Abstract:
Coalition formation is a key problem in multi-robot
cooperation. The formation of multi-robot cooperation for
single or multi-task is settled via finding the coalition
maximum value or the coalition structure with the largest
total coalition value. Traditionally, exhaustive method is used
to get the optimal coalition or coalition structure with huge
consumption in both computation time and communication
overhead, which possibly results in search combination
explosion. In this paper, agent coalition cooperation in MAS
(Multi-Agent System) is applied in multi-robot system with
genetic algorithm for the formation of multi-robot coalition
and coalition structure in order to gain the possible maximum
coalition value during task execution through finding the
optimal solution or feasible solution for multi-robot coalition
and coalition structure.
Keywords:
Multi-robot Cooperation; Agent; Coalition Formation;
Genetic Algorithm
1.ntroduction
If a single robot can not or not effectively complete a
given task in multi-robot systems, robots form a certain
combination (such as coalition) to complete it and reach
global optimization[1]. Different robot coalitions execute
tasks at different efficiency and cost due to the different
number and ability of their members. It is a priority to form
a best robot coalition and assign the task reasonably with
maximum benefit at lest cost during task execution in
multi-robot cooperation.
In multi-robot systems, the formation of robot
coalition is an optimization problem. The same with other
optimization ones, it requires the optimal or satisfying
solution in a complex and large searching space [2,3]. The
strategy for the coalition formation is looking for a global
optimization plan for task assignment. To reach that, the
