黃梓軒

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

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

引言[1-2]

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

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

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

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

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

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

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

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

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

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

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

6結束語

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

參考文獻

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

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