基於共識的委員會來協調多代理人系統 - 智能電網和無人機群的兩個應用案例研究

Consensus Based Committee Coordination for Multi-agent Systems -- Two Case-studies of Application on Smart Grid and UAVs

余琬瑜(WAN-YU YU)

指導教授 ： 蘇豐文

國立清華大學/電機資訊學院/資訊系統與應用研究所/博士(2021年)

摘要

多代理人系統透過擬人化的協調並達到共識是一個具有挑戰的研究方向。近年來在很多不同的領域都有不同的應用與發展。例如，智能機器人、智慧型電網架構、自動控制及軍事領域等，信息系統的複雜性和動態性不斷增加，需要設備自己做出決策以滿足其設計目標。我們整合了多代理人系統社會化的概念提出委員會的架構，並透過訊息的溝通及提案的分享，在考量多個限制條件下，加入了共識決策的方法，並將架構及決策方法以模擬的方式分別驗證在智慧型電網的復電模型及無人機群的自主動態任務分配及避障的路徑規劃，驗證結果顯示了所提出的方法比傳統方法更有效地達成共識。
在這項研究中，我們基於委員會的演算法中也導入了具有Redun-skip方式的容錯機制，以增強多代理人系統的強健性。如此可避免軟體代理人在執行過程中因某些原因造成的錯誤導致系統失效，我們提出的方法中已包含的容錯機制可以容許在有限數量的代理人失效時，系統仍然可以持續工作。我們將此方法驗證於電力恢復系統，以評估在電力恢復系統中代理人在不同程度的故障下系統性能下降的程度。模擬結果證明，Redun-Skip機制可以在不增加硬體成本的情況下，提高了基於代理人機制的電力服務恢復系統的穩定性及強健性。
在配電系統服務恢復問題中，電力系統拓撲中的開關被模擬為智能代理人並組織為配電系統中的電力委員會。這種方法的優點是:委員會本身具備解決問題的能力，可以透過與相鄰委員會的協調，以達成滿足配電系統服務恢復問題的全局目標的協議，而無需依賴須預先具備足夠訊息的傳統集中式優化演算法。本研究中所提出的協調演算法有助於分散式電力委員會中的開關代理人在檢測到錯誤時同時主動採取故障隔離後，並可以同時在許多提出的服務恢復解決方案中達成共識。我們也在尋找解決方案時也同時考慮了電壓偏差下降的問題。本研究中以兩個不同配電系統架構的案例，模擬了協調方法的演算法如何在許多提議的局部候選解決方案中識別最佳電力恢復問題的解決方案。
在另一個多無人機系統的應用中，無人機技術近年來得到迅速的發展，應用範圍廣泛。然而，協調一組自主無人機在未知和不斷變化的環境中完成任務一直是個具有挑戰性和復雜性的問題。我們修改了基於共識的拍賣算法，使其可以在無人機之間動態進行任務分配，從而可以靈活地找到到達目標的路徑，同時可以在避免碰撞的狀況下保持群飛的隊形。我們提出了核心演算法並根據經驗模擬了許多場景，以說明所提出的框架是如何工作的。具體而言，我們模擬了無人機如何在某些目標可能會在飛行任務期間出現和消失的動態情況下重新進行任務分配並可以尋找到到達目標的動態路徑。
應用於上述兩個不同領域的模擬結果都表明，我們所提出的基於委員會的多代理方法比以前的方法具有更好的效能及穩健性。最後我們還提出了一些具有挑戰性的問題作為未來的研究。

關鍵字

多代理人系統 ； 分散式系統 ； 容錯機制 ； 協調及共識 ； 能源系統 ； 復電問題 ； 智慧型代理人 ； 機群 ； 自動路徑規劃 ； 任務分配

並列摘要

Consensus in Multi-Agent System (MAS) coordination is a challenge research topic. The consensus of MAS had been widely applied and developed in many fields such as intelligent robots, smart grid structures, autonomous control and military operations. In real word applications, agents need to make operation decision to fulfill their design functions in a complex and dynamic information environment. In this research, we proposed an idea of "committee-based structure" based on the imitating human socialization concept. Under the committee-based structure, members can exchange information and proposed solutions to reach a consensus under the constraints. We tested the proposed method to the cases of restoration of smart grid power system and the task allocation with obstacle-avoid path planning among UAVs.
In this research, the fault tolerance mechanism is embedded in our committee-base algorithm with Redun-skip scheme to enhance the robustness of the MAS. In which they can avoid the agents failure for some reasons during the executing processes. Even when a limited number of agents failure, the proposed fault tolerance mechanism can still make the system work persistently. This method is used for simulation evaluation of the power restoration system to reveal how the performance of the system degrades under different degrees of failure of the commission agent in the power restoration system. The simulation results show that the Redun-Skip mechanism improves the stability of the MAS committee-based power service restoration system without increasing any hardware costs.
In distribution system service restoration problems, switches in the power topology are modeled as intelligent agents and organized as local power committees in a distribution system. The advantage of this approach is to utilize the solving ability of a local committee of agents who could coordinate with neighboring committees to achieve an agreement that satisfies the global objective of the power distribution system service restoration problems without relying on a pre-determined centralized optimization algorithm as traditional approaches. The proposed coordination method helps switches in the distributed local power committees to reach a consensus among many proposed service restoration solutions after faults are detected and isolated. We also take the voltage deviation into consideration in the search of solutions. Two examples of different power distribution system are presented to demonstrate how the algorithms of the coordination method can identify the best restoration solution among many proposed local candidate solutions.
In the application of UAVs, the UAV technology has recently been developed rapidly in a wide variety of applications. However, coordinating a team of autonomous UAVs to complete missions in an unknown and changing environment has been a challenging and complicated task. We modify Consensus-Based Auction Algorithm (CBAA) so that it can dynamically reallocate tasks among UAVs that can flexibly find a path to reach multiple dynamic targets while avoiding unexpected obstacles and staying close as a group as possible simultaneously. We propose the core algorithms and simulate with many scenarios empirically to illustrate how the proposed framework works. Specifically, we show that how UAVs could reallocate the tasks among each other in finding dynamically changing paths while certain targets may appear and disappear during the flight mission.
The simulation results applied in the above two different fields both show that the proposed committee-based multi-agent approach yields better performance than the previous methods. We also discuss some challenging problems as future work.

並列關鍵字

Multi-agent System ； Distribution System ； Fault Tolerance ； Power System ； Power Restoration ； Intelligent Agent ； Coordination ； Consensus ； Multi-UAV ； Path Planning ； Task Allocation

參考文獻

[1] Mordor Intelligence. INTERNET OF THINGS (IOT) MARKET - GROWTH, TRENDS, COVID-19 IMPACT, AND FORECASTS (2021 - 2026). Mordor Intel- ligence Pvt Ltd, 2021.

[2] Gerhard Weiss. Multiagent systems: a modern approach to distributed artificial intelligence. MIT press, 1999.

[3] Michael J Wooldridge and Nicholas R Jennings. Intelligent agents: Theory and practice. The knowledge engineering review, 10(2):115–152, 1995.

[4] Hyacinth S Nwana et al. Software agents: An overview. Knowledge engineering review, 11(3):205–244, 1996.

[5] B. W. Schermer. Software agents, surveillance, and the right to privacy: a legislative framework for agent-enabled surveillance. Leiden University Press, 2007.