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

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

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

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

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

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

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