多Agent系統(tǒng)任務(wù)分配的市場機(jī)制研究.pdf

1、任務(wù)/資源分配是計算機(jī)科學(xué)領(lǐng)域一個重要的研究問題，多Agent系統(tǒng)的特點決定了其任務(wù)分配與傳統(tǒng)的任務(wù)分配有很大的不同。本文利用機(jī)制設(shè)計的方法研究集中式和分布式多Agent系統(tǒng)任務(wù)分配問題，更具體地，本文考慮一類特殊的多Agent系統(tǒng)：系統(tǒng)中提供資源的理性Agent供給能力是有限的，且具有較復(fù)雜的成本結(jié)構(gòu)。
　　 本文介紹了機(jī)制設(shè)計的基本理論，重點研究了兩類基于市場的任務(wù)分配機(jī)制--VCG機(jī)制和CDA機(jī)制。VCG機(jī)制可以求出最優(yōu)解

2、，但只能用于求解集中式多Agent系統(tǒng)任務(wù)分配問題；CDA機(jī)制是分布式的，但無法保證最優(yōu)解。
　　 本文首先剖析了一個改進(jìn)的VCG機(jī)制，其支付由效用轉(zhuǎn)移和懲罰兩部分構(gòu)成，懲罰方案不僅保證了該VCG機(jī)制的激勵相容特性，也對無法確定自身容量的Agent具有魯棒性，該VCG機(jī)制的最優(yōu)解可由中心在偽多項式時間內(nèi)求得，本文用其求解了集中式多Agent系統(tǒng)的最優(yōu)分配。
　　 對于分布式多Agent系統(tǒng)任務(wù)分配問題的求解，本文考慮多單

3、元CDA機(jī)制，買者和賣者分別連續(xù)地向系統(tǒng)提交報價及其需求量和供給容量，當(dāng)買賣方的價格匹配時，即買者的出價高于賣者的要價，且賣方的需求能一次性滿足時，匹配的買賣方即成功進(jìn)行一次交易，隨后市場出清一次。CDA機(jī)制通過買賣方的交互實現(xiàn)系統(tǒng)任務(wù)/資源的分配，并且是激勵相容的。為讓系統(tǒng)中Agent更加理性地參與市場交互，本文提出了ZIP2策略，借助一個簡單的機(jī)器學(xué)習(xí)算法，讓Agent根據(jù)市場歷史信息預(yù)測將來市場環(huán)境，并不斷調(diào)整自己的利潤率，以保證

4、其市場競爭力。實驗表明，對“無政府”的分布式多Agent系統(tǒng)資源分配問題的求解，該ZIP2-CDA機(jī)制是有效的，且其求解效率高于采用零智能策略實現(xiàn)的CDA機(jī)制。
　　 在此基礎(chǔ)上，本文探討了市場機(jī)制在傳感器網(wǎng)絡(luò)環(huán)境的應(yīng)用，分析了傳感器網(wǎng)絡(luò)任務(wù)分配問題，其優(yōu)化目標(biāo)就是在滿足網(wǎng)絡(luò)中探測任務(wù)需求和各傳感器節(jié)點電量約束的前提下，最小化整個網(wǎng)絡(luò)消耗的電量。并用擴(kuò)展的VCG機(jī)制和ZIP2-CDA機(jī)制求解了該網(wǎng)絡(luò)環(huán)境下的任務(wù)分配問題。在用ZI