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

黃梓軒

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

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

引言[1-2]

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

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

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

2多智能體規(guī)劃的非標準性適應(yīng)方法

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

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

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

4基于預(yù)計算知識的多智能體目標分配規(guī)劃

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

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

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

6結(jié)束語

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

參考文獻

[1] 蔡自興，蒙祖強.人工智能基礎(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.