多移動機器人任務(wù)分配的市場方法研究.pdf

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

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

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

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

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

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