探討多智能體技術在規劃中的應用

黃梓軒

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

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

引言[1-2]

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

1多智能體規劃的兩段算法[2]

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

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

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

3基于復用的規劃合并多智能體規劃

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

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

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

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

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

6結束語

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

參考文獻

[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.