基于遺傳算法的多機器人聯(lián)盟形成 （外文翻譯）.rar
基于遺傳算法的多機器人聯(lián)盟形成 （外文翻譯）,基于遺傳算法的多機器人聯(lián)盟形成hui-yi liu, jin-feng chencomputer & information engineering college, hohai university nanjing, 210098,chinae-mail: hyliu@hhu.edu.cn,hhuchen@163.c...
該文檔為壓縮文件,包含的文件列表如下:
內(nèi)容介紹
原文檔由會員 wanli1988go 發(fā)布
基于遺傳算法的多機器人聯(lián)盟形成
HUI-YI LIU, JIN-FENG CHEN
Computer & Information Engineering College, Hohai University Nanjing, 210098,China
E-MAIL: hyliu@hhu.edu.cn,hhuchen@163.com
摘要：
在多機器人領(lǐng)域，聯(lián)盟形成是一個關(guān)鍵問題。單任務(wù)或多任務(wù)的多機器人協(xié)作，一般是通過找到聯(lián)盟的最高值或聯(lián)盟結(jié)構(gòu)的最大總聯(lián)盟值實現(xiàn)。傳統(tǒng)上，詳盡無遺的方法是用來獲得最優(yōu)的聯(lián)合或聯(lián)盟的結(jié)構(gòu)與巨大的消費量都在計算時間和通信開銷，而可能的結(jié)果，在搜索組合爆炸。本文中，MAS（多Agent系統(tǒng)）中Agent聯(lián)盟合作，是適用于多機器人系統(tǒng)與多機器人聯(lián)盟和聯(lián)盟結(jié)構(gòu)遺傳算法的形成，使得多機器人聯(lián)盟和聯(lián)盟結(jié)構(gòu)在執(zhí)行任務(wù)時通過尋找最優(yōu)解或可行的解決方案，以獲得盡可能最大聯(lián)盟值。
關(guān)鍵詞： 多機器人協(xié)作; Agent;聯(lián)盟形成; 遺傳算法
1 .緒論
在多機器人系統(tǒng)中，如果單一機器人不能或不能有效地完成一項特定任務(wù)，機器人形成一定的組合（如聯(lián)盟） ，以便完成這項工作并達到整體優(yōu)化 。由于不同成員的的數(shù)量和能力不同，不同的機器人聯(lián)盟在執(zhí)行任務(wù)時的效率和代價不同。優(yōu)先形成最佳機器人聯(lián)盟并合理分配任務(wù)，使得執(zhí)行任務(wù)時代價最小且效益最大。在多機器人系統(tǒng)中，機器人聯(lián)盟形成是一個優(yōu)化問題。與其他優(yōu)化問題一樣，聯(lián)盟形成問題也是一個優(yōu)化問題，與其他的優(yōu)化問題一樣，它需要在復(fù)雜而龐大的搜索空間中尋找最優(yōu)解或滿意解 。這種聯(lián)盟形成的策略是為任務(wù)分配尋找全局擇優(yōu)的方法。為了達到那個目的，任務(wù)分配過程巨細無遺地列舉了所有可能的聯(lián)盟，并試圖分配每一項任務(wù)，最終達到整體優(yōu)化。對于一個n個機器人的系統(tǒng)，所有可能的聯(lián)盟有 。當(dāng)n是比較大時，這種方法會消耗很多計算時間和通信開銷并有可能導(dǎo)致搜索組合爆炸。許多研究人員研究了如何降低復(fù)雜性的詳細方法。Shehory 介紹了一種常數(shù) K 來限制Agent聯(lián)盟中Agent的數(shù)量的方法，這種方法有效降低了Agent的數(shù)量，通信開銷與計算負荷，節(jié)省了形成聯(lián)盟的時間，并增加了聯(lián)盟效率。不過，在測定K和聯(lián)盟形成時也存在一些盲目性。Sinclair 和Billionnet 引入了低估計方法， 通過給定的限制的要求減少搜索空間，降低搜索樹。這兩種方法都對降低高代價求解最優(yōu)解時的復(fù)雜性做了很多工作，并且往往能得到次優(yōu)解。在本文中，Agent聯(lián)盟合作在MAS（多Agent系統(tǒng)）中適用于使用遺傳算法 解決機器人聯(lián)盟的多機器人系統(tǒng)。使用遺傳算法，一方面可以極大地減少尋找最優(yōu)解或可行解的開銷，另一方面它所找到的解(聯(lián)盟/聯(lián)盟結(jié)構(gòu))執(zhí)行任務(wù)時的開銷也比較小，能夠充分提高整個系統(tǒng)的效率。
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
摘要：
在多機器人領(lǐng)域，聯(lián)盟形成是一個關(guān)鍵問題。單任務(wù)或多任務(wù)的多機器人協(xié)作，一般是通過找到聯(lián)盟的最高值或聯(lián)盟結(jié)構(gòu)的最大總聯(lián)盟值實現(xiàn)。傳統(tǒng)上，詳盡無遺的方法是用來獲得最優(yōu)的聯(lián)合或聯(lián)盟的結(jié)構(gòu)與巨大的消費量都在計算時間和通信開銷，而可能的結(jié)果，在搜索組合爆炸。本文中，MAS（多Agent系統(tǒng)）中Agent聯(lián)盟合作，是適用于多機器人系統(tǒng)與多機器人聯(lián)盟和聯(lián)盟結(jié)構(gòu)遺傳算法的形成，使得多機器人聯(lián)盟和聯(lián)盟結(jié)構(gòu)在執(zhí)行任務(wù)時通過尋找最優(yōu)解或可行的解決方案，以獲得盡可能最大聯(lián)盟值。
關(guān)鍵詞： 多機器人協(xié)作; Agent;聯(lián)盟形成; 遺傳算法
1 .緒論
在多機器人系統(tǒng)中，如果單一機器人不能或不能有效地完成一項特定任務(wù)，機器人形成一定的組合（如聯(lián)盟） ，以便完成這項工作并達到整體優(yōu)化 。由于不同成員的的數(shù)量和能力不同，不同的機器人聯(lián)盟在執(zhí)行任務(wù)時的效率和代價不同。優(yōu)先形成最佳機器人聯(lián)盟并合理分配任務(wù)，使得執(zhí)行任務(wù)時代價最小且效益最大。在多機器人系統(tǒng)中，機器人聯(lián)盟形成是一個優(yōu)化問題。與其他優(yōu)化問題一樣，聯(lián)盟形成問題也是一個優(yōu)化問題，與其他的優(yōu)化問題一樣，它需要在復(fù)雜而龐大的搜索空間中尋找最優(yōu)解或滿意解 。這種聯(lián)盟形成的策略是為任務(wù)分配尋找全局擇優(yōu)的方法。為了達到那個目的，任務(wù)分配過程巨細無遺地列舉了所有可能的聯(lián)盟，并試圖分配每一項任務(wù)，最終達到整體優(yōu)化。對于一個n個機器人的系統(tǒng)，所有可能的聯(lián)盟有 。當(dāng)n是比較大時，這種方法會消耗很多計算時間和通信開銷并有可能導(dǎo)致搜索組合爆炸。許多研究人員研究了如何降低復(fù)雜性的詳細方法。Shehory 介紹了一種常數(shù) K 來限制Agent聯(lián)盟中Agent的數(shù)量的方法，這種方法有效降低了Agent的數(shù)量，通信開銷與計算負荷，節(jié)省了形成聯(lián)盟的時間，并增加了聯(lián)盟效率。不過，在測定K和聯(lián)盟形成時也存在一些盲目性。Sinclair 和Billionnet 引入了低估計方法， 通過給定的限制的要求減少搜索空間，降低搜索樹。這兩種方法都對降低高代價求解最優(yōu)解時的復(fù)雜性做了很多工作，并且往往能得到次優(yōu)解。在本文中，Agent聯(lián)盟合作在MAS（多Agent系統(tǒng)）中適用于使用遺傳算法 解決機器人聯(lián)盟的多機器人系統(tǒng)。使用遺傳算法，一方面可以極大地減少尋找最優(yōu)解或可行解的開銷，另一方面它所找到的解(聯(lián)盟/聯(lián)盟結(jié)構(gòu))執(zhí)行任務(wù)時的開銷也比較小，能夠充分提高整個系統(tǒng)的效率。
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
