多移動(dòng)機(jī)器人任務(wù)分配的市場(chǎng)方法研究.pdf

1、人類可以借助多移動(dòng)機(jī)器人系統(tǒng)執(zhí)行工農(nóng)業(yè)生產(chǎn)、軍事國(guó)防和科學(xué)研究等領(lǐng)域中許多單調(diào)、繁重、復(fù)雜或危險(xiǎn)的任務(wù),實(shí)現(xiàn)降低人類勞動(dòng)強(qiáng)度、提高工作效率、避免人員傷亡以及擴(kuò)展人類活動(dòng)空間等目的。任務(wù)分配是有效利用多移動(dòng)機(jī)器人系統(tǒng)資源以充分發(fā)揮系統(tǒng)效能優(yōu)勢(shì)的重要基礎(chǔ),其重要性程度隨系統(tǒng)成員的功能差異性和任務(wù)的結(jié)構(gòu)復(fù)雜性的增加而增加。最優(yōu)任務(wù)分配是最大化多移動(dòng)機(jī)器人系統(tǒng)效能的前提條件,但在大多數(shù)情況下最優(yōu)任務(wù)分配算法的計(jì)算復(fù)雜度隨問(wèn)題規(guī)模的指數(shù)級(jí)增長(zhǎng),當(dāng)

2、任務(wù)分配問(wèn)題存在顯著的動(dòng)態(tài)不確定性時(shí)多移動(dòng)機(jī)器人系統(tǒng)實(shí)現(xiàn)最優(yōu)任務(wù)分配將愈加困難,在可接受的時(shí)間內(nèi)實(shí)現(xiàn)最優(yōu)分配的任務(wù)規(guī)模非常有限。
　　 基于市場(chǎng)交易機(jī)制的任務(wù)分配方法是一種具有良好魯棒性、靈活性和可擴(kuò)展性的任務(wù)分配方法,其最大優(yōu)勢(shì)在于適合動(dòng)態(tài)不確定性環(huán)境下多移動(dòng)機(jī)器人系統(tǒng)中各機(jī)器人分布地通過(guò)最大化個(gè)體效能實(shí)現(xiàn)最大化系統(tǒng)總效能的目的。本文研究多移動(dòng)機(jī)器人系統(tǒng)協(xié)作任務(wù)的分布式市場(chǎng)分配方法,分別對(duì)多移動(dòng)機(jī)器人系統(tǒng)的松散耦合任務(wù)分配、緊

3、密耦合任務(wù)分配以及動(dòng)態(tài)任務(wù)的重分配的市場(chǎng)方法進(jìn)行研究,目的在于探索基于市場(chǎng)機(jī)制協(xié)調(diào)的多移動(dòng)機(jī)器人系統(tǒng)提高分布式任務(wù)分配最優(yōu)性和動(dòng)態(tài)任務(wù)重分配效率的新方法。
　　 (1)本文通過(guò)引入代價(jià)標(biāo)示圖方法可以比較直觀地描述移動(dòng)機(jī)器人依次執(zhí)行多個(gè)任務(wù)所消耗的移動(dòng)代價(jià)、操作代價(jià)以及完成任務(wù)的回報(bào)等指標(biāo)值。通過(guò)引入能力向量可以簡(jiǎn)潔地描述機(jī)器人能力的類型和大小,也便于描述不同機(jī)器人的能力異構(gòu)性和機(jī)器人對(duì)應(yīng)用任務(wù)能力需求的滿足性。
　　 (

4、2)分布式協(xié)調(diào)的多移動(dòng)機(jī)器人系統(tǒng)中各機(jī)器人的協(xié)作行為具有顯著的并發(fā)性,若系統(tǒng)不支持不同任務(wù)管理者并發(fā)協(xié)商任務(wù)分配,則全局任務(wù)分配的最優(yōu)性和實(shí)時(shí)性會(huì)受到制約。給出了一種基于并發(fā)合同網(wǎng)協(xié)議的任務(wù)管理者招標(biāo)和任務(wù)投標(biāo)者投標(biāo)的算法框架,并提出一種基于動(dòng)態(tài)鄰居集合的任務(wù)招標(biāo)對(duì)象選擇方法。并發(fā)的協(xié)商方法有利于提高任務(wù)分配的最優(yōu)性,也利于減少實(shí)現(xiàn)任務(wù)分配消耗的協(xié)商時(shí)間。
　　 (3)針對(duì)松散耦合任務(wù)分配提出了一種基于序貫單項(xiàng)任務(wù)拍賣和任務(wù)分組

5、分配的分布式任務(wù)分配方法。任務(wù)分配過(guò)程被劃分成兩個(gè)階段,第一個(gè)階段采用序貫單項(xiàng)任務(wù)拍賣過(guò)程確定每個(gè)機(jī)器人對(duì)每個(gè)任務(wù)的投標(biāo)值,第二個(gè)階段采用多個(gè)移動(dòng)吸引子根據(jù)第一個(gè)階段獲得的投標(biāo)值確定任務(wù)的分組,任務(wù)管理者根據(jù)分組結(jié)果確定任務(wù)的最終分配。新的方法可以顯著提高任務(wù)分配的最優(yōu)性,但增加的任務(wù)管理者的計(jì)算代價(jià)僅僅是O(m3),通訊代價(jià)的增加量是O(n),其中m是任務(wù)數(shù)量,n是參與任務(wù)分配的機(jī)器人數(shù)量。
　　 (4)需要多個(gè)機(jī)器人緊密協(xié)調(diào)

6、的緊密耦合任務(wù)的分配可以劃分成兩個(gè)層次的分配,第一個(gè)層次的分配是指將需要多個(gè)機(jī)器人緊密協(xié)調(diào)執(zhí)行的多個(gè)單機(jī)器人任務(wù)作為一個(gè)整體分配給某個(gè)機(jī)器人群組執(zhí)行,第二個(gè)層次的分配是指將若干個(gè)存在嚴(yán)格的空間或時(shí)間約束性的單機(jī)器人任務(wù)分配給同一群組內(nèi)不同的機(jī)器人執(zhí)行。第一個(gè)層次的分配問(wèn)題主要是為給定任務(wù)尋找最優(yōu)的機(jī)器人聯(lián)盟問(wèn)題,第二個(gè)層次的分配問(wèn)題主要是解決協(xié)作機(jī)器人執(zhí)行任務(wù)的時(shí)序約束性問(wèn)題。本文針對(duì)第一個(gè)層次的分配問(wèn)題提出了一種基于二進(jìn)制粒子群優(yōu)化技