探討多智能體技術(shù)在規(guī)劃中的應(yīng)用

黃梓軒

摘 要 人工智能中的多智能體技術(shù)正被應(yīng)用于許多領(lǐng)域，多智能體技術(shù)與經(jīng)典規(guī)劃方法集成所產(chǎn)生的多智能體規(guī)劃具有巨大的潛力。本文概括性地介紹多智能體技術(shù)在規(guī)劃中的一些應(yīng)用進(jìn)展。

關(guān)鍵詞 多智能體;規(guī)劃;兩段算法;非標(biāo)準(zhǔn)性適應(yīng);目標(biāo)分配規(guī)劃;傳感器網(wǎng)絡(luò)

引言[1-2]

多智能體系統(tǒng)（Multi-Agent Systems）正被應(yīng)用于許多領(lǐng)域。具有巨大潛力的一個(gè)新研究領(lǐng)域是將多智能體系統(tǒng)與經(jīng)典規(guī)劃方法集成在一起，產(chǎn)生了多智能體規(guī)劃（Multi-Agent Planning，MAP）這一子領(lǐng)域。

1多智能體規(guī)劃的兩段算法[2]

多智能體規(guī)劃（MAP）研究由多個(gè)合作智能體組成的規(guī)劃系統(tǒng)，這些系統(tǒng)基于長期目標(biāo)進(jìn)行推理，每個(gè)智能體保持其知識(shí)的私有性。近期以來，研究人員已經(jīng)設(shè)計(jì)了一些新的MAP技術(shù)來提供有效的解決方案。大多數(shù)方法采用修正的規(guī)劃器來擴(kuò)展分布式搜索，并通過規(guī)劃器進(jìn)行公共信息交換。這些方法有兩個(gè)缺點(diǎn)：它們依賴于規(guī)劃器;而且需要高昂的通信成本。Daniel Borrajo和Susana Fernández提出了一種兩段算法，每個(gè)智能體的搜索過程是單獨(dú)規(guī)劃的，不發(fā)生通信，MAP系統(tǒng)的任務(wù)收集不依賴于系統(tǒng)規(guī)劃器。兩段算法的第一階段——分布式方法，首先將每個(gè)公共目標(biāo)分配給每個(gè)智能體的子集，每個(gè)智能體通過接收前任智能體的規(guī)劃、目標(biāo)和狀態(tài)來迭代地解決問題，通過復(fù)用前任智能體的規(guī)劃生成新規(guī)劃之后，他們與后任智能體共享新規(guī)劃和一些模糊的私有信息;兩段算法的第二階段——集中式方法，每個(gè)智能體生成問題的模糊版本，以保護(hù)其信息的私有性，然后將其提交給MAP系統(tǒng)執(zhí)行集中任務(wù)的規(guī)劃器。他們所提出的方法是有效的，優(yōu)于其他最先進(jìn)的方法。

2多智能體規(guī)劃的非標(biāo)準(zhǔn)性適應(yīng)方法

在做決策的過程中，智能體希望遵從理想的行為或標(biāo)準(zhǔn)，但在現(xiàn)實(shí)中難以得到滿足。Luca Gasparini等專家研究了如何規(guī)避該問題的多智能體設(shè)計(jì)方法，他們選擇集體策略以避免智能體因違反標(biāo)準(zhǔn)而出現(xiàn)失敗的狀況。他們通過違背職責(zé)的義務(wù)和違反的嚴(yán)重程度對(duì)多智能體系統(tǒng)的規(guī)范需求進(jìn)行建模，基于分散的部分可觀馬爾可夫決策過程（POMDPs），使用定性獎(jiǎng)勵(lì)函數(shù)來捕獲遵從性的級(jí)別（n-Dec-POMDPs），提出了一種新的多智能體規(guī)劃機(jī)制。通過實(shí)證分析，該新機(jī)制產(chǎn)生的集體策略與通過現(xiàn)有方法產(chǎn)生的策略一樣好，但執(zhí)行時(shí)間大大縮短。

3基于復(fù)用的規(guī)劃合并多智能體規(guī)劃

在多智能體規(guī)劃MAP中，最大的挑戰(zhàn)之一是如何處理每個(gè)智能體行為之間的交互問題。Nerea Luis和Susana Fernandez等專家提出了基于復(fù)用的規(guī)劃合并算法（Plan Merging by Reuse，PMR），每個(gè)智能體自動(dòng)調(diào)整其行為以適應(yīng)交互級(jí)別。給定一個(gè)MAP規(guī)劃任務(wù)，PMR將目標(biāo)分配給特定的智能體，被選擇的智能體解決各自的規(guī)劃任務(wù)，然后將規(guī)劃結(jié)果進(jìn)行合并。由于合并的規(guī)劃并不總是有效的，所以PMR通過復(fù)用來執(zhí)行規(guī)劃以生成有效的規(guī)劃。Nerea Luis和Susana Fernandez等人還提出了一種隨機(jī)規(guī)劃復(fù)用方法（RRPT-PLAN），該方法組合了規(guī)劃復(fù)用、 標(biāo)準(zhǔn)搜索和抽樣。他們進(jìn)行了大量的實(shí)驗(yàn)，以分析PMR的性能與最新的多智能體規(guī)劃技術(shù)的關(guān)系。

4基于預(yù)計(jì)算知識(shí)的多智能體目標(biāo)分配規(guī)劃

許多真實(shí)的機(jī)器人場(chǎng)景需要執(zhí)行任務(wù)規(guī)劃來決定行動(dòng)方案。傳統(tǒng)的集中式規(guī)劃方法必須在搜索空間內(nèi)找到一個(gè)解決方案，其中包含所有可能的機(jī)器人和目標(biāo)組合，這會(huì)導(dǎo)致效率低下的解決方案。多智能體規(guī)劃（MAP）為有效地解決這類任務(wù)提供了一種新的途徑。現(xiàn)有的MAP方法將問題分解，以減少規(guī)劃工作量，即將目標(biāo)在智能體之間劃分，但當(dāng)智能體和目標(biāo)的數(shù)量增加時(shí)，這些技術(shù)不能擴(kuò)展，而且，在許多大的MAP真實(shí)場(chǎng)景中，目標(biāo)可能不是每個(gè)智能體都能達(dá)到，所以它有一個(gè)相關(guān)的計(jì)算成本。Nerea Luis和Tiago Pereira等研究者將機(jī)器人技術(shù)和規(guī)劃技術(shù)結(jié)合起來，采用“行動(dòng)多智能體方法（AMs）”，以減少和促進(jìn)目標(biāo)分配過程的計(jì)算。AMs可以確定每個(gè)智能體的行動(dòng)邊界，因此可以提取特定的信息，以了解每個(gè)智能體可以實(shí)現(xiàn)哪些目標(biāo)，以及廉價(jià)地估計(jì)使用每個(gè)智能體來實(shí)現(xiàn)每個(gè)目標(biāo)的成本。實(shí)驗(yàn)表明，當(dāng)AMs提取的信息被提供給多智能體規(guī)劃算法時(shí)，目標(biāo)分配過程要快得多，并大大加快了規(guī)劃進(jìn)程。實(shí)驗(yàn)同時(shí)也表明，AMs方法大大優(yōu)于傳統(tǒng)的集中式規(guī)劃方法。

5大型傳感器網(wǎng)絡(luò)多移動(dòng)智能體行程規(guī)劃

傳感器網(wǎng)絡(luò)通常是網(wǎng)絡(luò)物理系統(tǒng)的一部分。大型傳感器網(wǎng)絡(luò)通常涉及大數(shù)據(jù)采集和數(shù)據(jù)融合。在無線傳感器網(wǎng)絡(luò)（WSN）實(shí)現(xiàn)數(shù)據(jù)融合和能量平衡方面，智能體技術(shù)引起了人們的廣泛關(guān)注。現(xiàn)有的多智能體行程算法在實(shí)踐中要么耗時(shí)，要么過于復(fù)雜。Bo Liu和 Jiuxin Cao等人通過構(gòu)造WSN節(jié)點(diǎn)生成樹，為多智能體行程問題設(shè)計(jì)了一種路由行程規(guī)劃方案。第一步，他們構(gòu)造了一個(gè)多智能體分布式WSN模型（DWSN）和能量消耗模型;第二步，他們提出了一種新的路由行程算法DMAIP，該算法為智能體把所有傳感器節(jié)點(diǎn)分組為多個(gè)行程路線，并將DMAIP進(jìn)行了擴(kuò)展，設(shè)計(jì)了DMAIP-E，避免了DMAIP中的長距離傳輸。評(píng)估結(jié)果表明，他們提出的路由行程規(guī)劃方案在生命周期和能耗方面優(yōu)于現(xiàn)有的WSN數(shù)據(jù)收集方案。

6結(jié)束語

人工智能、規(guī)劃及相關(guān)領(lǐng)域的科研人員在多智能體規(guī)劃的兩段算法、多智能體規(guī)劃的非標(biāo)準(zhǔn)性適應(yīng)方法、基于復(fù)用的規(guī)劃合并多智能體規(guī)劃、基于預(yù)計(jì)算知識(shí)的多智能體目標(biāo)分配規(guī)劃以及大型傳感器網(wǎng)絡(luò)多移動(dòng)智能體行程規(guī)劃等方面進(jìn)行了開拓性研究。

參考文獻(xiàn)

[1] 蔡自興，蒙祖強(qiáng).人工智能基礎(chǔ)（3版）[M].北京：高等教育出版社，2016：202.

[2] Daniel Borrajo.Susana Fernández： Effificient approaches for multi-agent planning[J]. Knowl Inf Syst，2019，（58）：425–479.