基于多Agent系統(tǒng)的動(dòng)態(tài)任務(wù)分配研究.pdf

1、動(dòng)態(tài)任務(wù)分配就是將合適的任務(wù)實(shí)時(shí)地分配給合適的成員，以充分利用系統(tǒng)的資源，提高任務(wù)的完成績效。它通常包含再分配型和新任務(wù)型兩類：再分配型的動(dòng)態(tài)任務(wù)分配是封閉系統(tǒng)中的一類典型問題，目前已有成熟的技術(shù)方法，如動(dòng)態(tài)負(fù)載平衡和各種優(yōu)化算法等。新任務(wù)型的動(dòng)態(tài)分配，是當(dāng)今以分布式、開放性、智能化和社會(huì)性為特征的復(fù)雜系統(tǒng)運(yùn)作中的重要問題，這些系統(tǒng)成員異構(gòu)所帶來的復(fù)雜性以及系統(tǒng)內(nèi)外環(huán)境變化所產(chǎn)生的不確定性等都給這類動(dòng)態(tài)任務(wù)分配問題的求解帶來了困難。多A

2、gent系統(tǒng)(MAS)思想的出現(xiàn)，為解決這類新任務(wù)型的動(dòng)態(tài)任務(wù)分配問題提供了新的途徑?；贛AS研究復(fù)雜系統(tǒng)不僅可以有效地揭示復(fù)雜系統(tǒng)的運(yùn)作特征，而且可以借鑒MAS研究的理論成果和方法技術(shù)，解決復(fù)雜系統(tǒng)運(yùn)作中用傳統(tǒng)方法難以求解的問題。此外，現(xiàn)實(shí)需求驅(qū)動(dòng)下的研究成果又可以進(jìn)一步地豐富MAS理論，指導(dǎo)更為廣泛的復(fù)雜系統(tǒng)運(yùn)作。因此，基于MAS的動(dòng)態(tài)任務(wù)分配問題研究具有重要意義。 基于MAS研究動(dòng)態(tài)任務(wù)分配問題的基本思路是：選取MAS作

3、為復(fù)雜系統(tǒng)的研究模型，借鑒現(xiàn)有任務(wù)分配理論的研究成果和技術(shù)方法，圍繞任務(wù)分解、集中式運(yùn)作環(huán)境的任務(wù)分配以及分布式運(yùn)作環(huán)境的任務(wù)分配展開討論。在形式化分析任務(wù)和Agent能力特征的基礎(chǔ)上，提出基于MAS任務(wù)分解的原則和方法步驟；針對(duì)集中式運(yùn)作環(huán)境，建立基于馬爾可夫決策過程(MDP)的動(dòng)態(tài)任務(wù)分配模型，用來指導(dǎo)任務(wù)分配方案的優(yōu)化；針對(duì)分布式?jīng)Q策環(huán)境，建立基于擴(kuò)展合同網(wǎng)的任務(wù)分配模型，通過任務(wù)分配運(yùn)作框架和流程的描述，規(guī)范化基于擴(kuò)展合同網(wǎng)(E

4、CNP)動(dòng)態(tài)任務(wù)分配的過程。 基于MAS的任務(wù)分解是研究復(fù)雜系統(tǒng)任務(wù)分配的前期準(zhǔn)備。一般地，復(fù)雜系統(tǒng)中被分配的任務(wù)可區(qū)分為簡(jiǎn)單任務(wù)和復(fù)雜任務(wù)。簡(jiǎn)單任務(wù)可直接分配給單個(gè)Agent獨(dú)立完成；復(fù)雜任務(wù)通常轉(zhuǎn)化為簡(jiǎn)單任務(wù)后再分配。在對(duì)簡(jiǎn)單任務(wù)和Agent能力特征建模的基礎(chǔ)上，我們提出了基于MAS任務(wù)分解所遵循的6項(xiàng)原則和5個(gè)關(guān)鍵步驟?；贛AS 的任務(wù)分解不僅可以為復(fù)雜問題的求解提供指導(dǎo)，而且也向規(guī)范化的任務(wù)分解邁進(jìn)了一步。 集

5、中和分布是復(fù)雜系統(tǒng)運(yùn)作的兩類重要模式。對(duì)于集中式動(dòng)態(tài)任務(wù)分配問題，根據(jù)系統(tǒng)運(yùn)作收益最大化的目標(biāo)、環(huán)境的不確定性和動(dòng)態(tài)任務(wù)分配序列決策的要求，我們構(gòu)建了相應(yīng)的馬爾可夫決策過程模型，并證明了該模型在狀態(tài)空間和行動(dòng)空間有限時(shí)存在最優(yōu)解，討論了模型求解的迭代算法。仿真實(shí)驗(yàn)表明基于MDP的動(dòng)態(tài)任務(wù)分配因考慮了系統(tǒng)的長遠(yuǎn)收益，雖然在某些決策時(shí)點(diǎn)做出的決策不是即時(shí)最優(yōu)的，但系統(tǒng)長期運(yùn)作的期望總收益則優(yōu)于即時(shí)最優(yōu)分配方案。因此，基于MDP的動(dòng)態(tài)任務(wù)分配

6、模型適用于解決長期運(yùn)作的小規(guī)模系統(tǒng)中的動(dòng)態(tài)任務(wù)分配問題。 對(duì)于分布式動(dòng)態(tài)任務(wù)分配問題，在建立擴(kuò)展合同網(wǎng)理論的基礎(chǔ)上，通過描述基于MAS動(dòng)態(tài)任務(wù)分配問題的兩級(jí)框架，提出了基于擴(kuò)展合同網(wǎng)求解動(dòng)態(tài)任務(wù)分配的基本思想，規(guī)范化了從招標(biāo)準(zhǔn)備、招標(biāo)、投標(biāo)到揭標(biāo)的運(yùn)作流程。基于擴(kuò)展合同網(wǎng)動(dòng)態(tài)任務(wù)分配的基本思想包括：基于任務(wù)熟人信任度的招標(biāo)策略，基于自適應(yīng)的投標(biāo)策略和基于模糊綜合評(píng)判的評(píng)標(biāo)策略；以及基于時(shí)限的聯(lián)合承諾協(xié)議和基于KQML的通信規(guī)范等