基于帶權(quán)與或樹和AOE-網(wǎng)的多智能體動(dòng)態(tài)任務(wù)規(guī)劃研究.pdf

1、多智能體系統(tǒng)中的任務(wù)規(guī)劃是近年來研究的熱點(diǎn)之一。機(jī)器人救援仿真系統(tǒng)是一個(gè)典型的異構(gòu)多智能體系統(tǒng),為在動(dòng)態(tài)復(fù)雜場(chǎng)景下快速、高效規(guī)劃救援任務(wù),提高救援效率,將災(zāi)難損失降到最低,本文引入帶權(quán)與或樹和AOE-網(wǎng),提出一種高效的動(dòng)態(tài)任務(wù)規(guī)劃方法,主要包括層次任務(wù)分解、計(jì)劃一致協(xié)調(diào)、動(dòng)態(tài)調(diào)整和沖突消除協(xié)調(diào)這幾個(gè)相互關(guān)聯(lián)且又緊密結(jié)合的過程。
　　 針對(duì)任務(wù)的復(fù)雜性和時(shí)序約束問題,提出一種時(shí)序約束的帶權(quán)與或樹任務(wù)分解層次規(guī)劃,帶權(quán)與或樹描述了復(fù)

2、雜任務(wù)與其子任務(wù)之間的層次關(guān)系以及任務(wù)的與或特性；與或樹中葉子結(jié)點(diǎn)通過添加權(quán)值來描述其相應(yīng)簡(jiǎn)單任務(wù)的執(zhí)行時(shí)間；在帶權(quán)與或樹的基礎(chǔ)上,增加輔助線來限定任務(wù)結(jié)點(diǎn)之間的時(shí)序約束,得出時(shí)序約束的帶權(quán)與或樹任務(wù)分解結(jié)構(gòu)模型,進(jìn)行層次任務(wù)規(guī)劃。
　　 針對(duì)在任務(wù)分解后各智能體在執(zhí)行子任務(wù)計(jì)劃中難以達(dá)成一致的問題,提出將帶權(quán)與或樹轉(zhuǎn)化為AOE-網(wǎng)的任務(wù)規(guī)劃。在采用時(shí)序約束的帶權(quán)與或樹結(jié)構(gòu)對(duì)復(fù)雜任務(wù)進(jìn)行分解的基礎(chǔ)上,首先基于結(jié)點(diǎn)的最小執(zhí)行權(quán)值對(duì)

3、帶權(quán)與或樹進(jìn)行修剪,舍棄部分或子結(jié)點(diǎn),以減少不必要或子任務(wù)的執(zhí)行；然后將時(shí)序約束的帶權(quán)與或樹轉(zhuǎn)化為AOE-網(wǎng),通過AOE-網(wǎng)的關(guān)鍵路徑算法,得出各子任務(wù)的最早發(fā)生時(shí)間,基于最早發(fā)生時(shí)間,計(jì)算各子任務(wù)的開始執(zhí)行時(shí)間和結(jié)束時(shí)間,使總?cè)蝿?wù)的完成時(shí)間最短,達(dá)到計(jì)劃一致協(xié)調(diào)。
　　 針對(duì)在計(jì)劃一致協(xié)調(diào)過程中,智能體執(zhí)行任務(wù)時(shí)產(chǎn)生的沖突和動(dòng)態(tài)變化所引起的任務(wù)延遲或中斷問題,提出基于任務(wù)轉(zhuǎn)包和動(dòng)態(tài)再分解的動(dòng)態(tài)任務(wù)規(guī)劃。當(dāng)智能體的某個(gè)子任務(wù)產(chǎn)生

4、中斷時(shí),便將此任務(wù)轉(zhuǎn)包給其他智能體或?qū)⒋巳蝿?wù)再分解成多個(gè)簡(jiǎn)單子任務(wù),形成新的帶權(quán)與或樹,以滿足智能體執(zhí)行任務(wù)的可行性；再將新的帶權(quán)與或樹轉(zhuǎn)化為AOE-網(wǎng),使整個(gè)任務(wù)能夠繼續(xù)保持計(jì)劃一致協(xié)調(diào),滿足任務(wù)規(guī)劃的動(dòng)態(tài)實(shí)時(shí)性,達(dá)到?jīng)_突消除和動(dòng)態(tài)調(diào)整協(xié)調(diào)。
　　 通過開發(fā)“動(dòng)態(tài)任務(wù)規(guī)劃仿真系統(tǒng)”,驗(yàn)證了所提出的動(dòng)態(tài)任務(wù)規(guī)劃方法的可用性和有效性,并應(yīng)用到中南大學(xué)機(jī)器人仿真隊(duì)CSU_Yunlu中,并在2009年中國機(jī)器人公開賽上獲得亞軍,驗(yàn)證了