基于多智能體系統仿真的最短路徑規劃

唐 勇， 何東林， 朱新平

(1.成都大學 信息科學與工程學院， 四川 成都 610106；2.中國民航局第二研究所 科研開發中心， 四川 成都 610041；3.中國民用航空飛行學院 空中交通管理學院， 四川 廣漢 618307)

0 引 言

最短路徑規劃是圖論與網絡規劃中的經典問題，廣泛應用于基于地圖信息的交通導航、車輛調度管理、航線航路規劃、市政交通規劃以及網絡通信路由選擇等領域[1-4].對此，科研人員對最短路徑規劃問題進行了大量研究[5-7]，并提出了一系列最短路徑算法及各種改進算法，比如，A*算法、Dijkstra算法、Floyd算法、Bellman-Ford算法及SPFA算法等[8-12].總體來看，現有的最短路徑算法大多利用數學分析方法實現，但也存在解析參數過多或難以確定，甚至解析解不存在的情況.針對此問題，科研人員提出了系統仿真法對復雜系統進行求解，并取得了較好結果[13].基于此，本研究利用多智能體系統設計了最短路徑仿真算法，把有向圖中的節點與邊都建模成智能體，再設計機器人智能體，利用機器人智能體的自我復制和移動能力，讓機器人智能體沿著節點出邊對與該節點相連接的節點進行并行移動訪問，從而快速實現對有向圖節點的遍歷，采用系統仿真運行的方式直觀地獲取有向圖最短路徑.

1 問題描述

在具體應用中，實際的最短路徑問題通常轉換為權重有向圖.設權重有向圖，G=(V,E)，這里V為G中的頂點集合，E為G中的邊集合.設有向圖G的權重函數為w:E→R，即權重函數w把G中的每條邊映射為實數域中的數值，于是，某條路徑，p=〈v0,v1,…，vk〉，的長度可以用構成該路徑的全部邊的權重值相加得到，

(1)

因此，從節點a到節點b的最短路徑可以用最小權重函數進行表示，

(2)

邊的權重既可以是實際道路的幾何距離，也可以是其他度量單位，如時間、流量和成本等與路徑長度線性增加的量.

此外，最短路徑問題也可以分為指定結點間的最短路徑、單目的地最短路徑及所有節點間的最短路徑.指定節點間最短路徑，即計算給定的2個節點之間的最短距離；單目的地最短路徑，即計算所有節點到目的地節點的最短距離；所有節點間最短距離，即計算任意2個節點之間的最短距離.單目的地最短路徑和所有節點間最短路徑都可以歸結為指定節點間最短路徑的擴展.

本研究只研究指定節點間最短路徑，即：設有如圖1所示的有向圖，各條路段上的數字標明該條路段的長度(這里設路段權重數值都為正)，求從P1到P6的最短路徑.

圖1最短路徑有向圖模型

2 系統設計

2.1 系統結構設計

根據定義，多智能體系統中的每個智能體都具備獨立自主能力，每個智能體都選擇最有利于個體利益的策略.由于多智能體系統存在多個智能體，各個智能體在選擇最有利于自己的策略時必然產生沖突.對此，多智能體系統的目的是實現系統的整體利益最大化，此時就需要在各個智能體之間進行溝通和協調，讓個體利益服從整體利益.由此可見，智能體個體功能的設計和智能體之間的協調機制的確定是多智能體系統設計的關鍵.同時，根據不同的規劃目標選擇合適的系統結構是實現多智能體系統的重要保證.根據計算最短路徑的需求，本研究設計的層次型多智能體系統結構如圖2所示.

圖2層次型多智能體系統結構

圖2所示系統中，管理Agent負責多智能體系統的運行控制，是系統的關鍵智能體；節點Agent對應于有向圖中的節點；邊Agent對應于有向圖中的邊；機器人Agent是系統中的移動智能體，負責完成從起點到終點的運動；環境是多智能體系統的運行后臺，負責提供和管理系統運行的基礎功能，比如消息傳遞與智能體連接關系等；起點和終點節點對、有向圖均是系統的輸入信息，最短路徑是系統的輸出信息.

2.2 Agent設計

2.2.1 管理Agent.

管理Agent擔負系統的管理功能，負責整個多智能體系統運行控制，獲得路徑規劃結果.管理Agent在多智能體系統啟動時首先完成初始化工作，根據系統輸入的有向圖設置節點Agent和邊Agent，根據起點和終點產生第一個機器人Agent(初始機器人Agent)，并放入起點對應的節點Agent(初始節點Agent).同時，對各種Agent的相互協作提供運行管理支持，輸出最短路徑.

2.2.2 節點Agent.

節點Agent對應于有向圖的節點，是供機器人Agent進行自我復制和邊斷開操作的環境.節點Agent具有名稱和出入邊屬性.其中，名稱即是節點Agent的編號，可對節點身份進行標識；出入邊屬性標識了該節點Agent的出邊和入邊數量以及與邊Agent的關聯關系等.

2.2.3 邊Agent.

邊Agent對應于有向圖中的邊，邊Agent具有時間屬性、方向屬性及節點關聯屬性等.時間屬性對應于有向圖中的權重，指明了機器人Agent通過該條邊所花費的時間；方向屬性指明了機器人Agent在邊Agent上的運動方向；節點關聯屬性指明了邊Agent與節點的關聯關系，即有向圖中節點間的連接情況.

2.2.4 機器人Agent.

機器人Agent具有節點間移動能力、自我復制能力、邊斷開能力及歷史節點屬性.機器人Agent會沿著某個節點Agent出邊的方向移動到其下個節點Agent，移動的時間等于邊的權重值.

如果節點Agent有不止一條出邊，則機器人Agent能自我復制出多個機器人，即讓該節點Agent的每條出邊都由機器人Agent占據.機器人Agent只有在到達節點Agent且該節點Agent有不止一條出邊才立即進行自我復制.若節點Agent有n條出邊且n>1，則自我復制的數量為(n-1).如果節點Agent有多條入邊，機器人Agent到達該節點后只留下它曾走過的入邊，而把其他入邊都斷開(確保任何節點至多被訪問一次).歷史節點屬性記錄該機器人已通過的節點，以便最后輸出路徑.一旦有機器人Agent到達終點，便完成最短路徑計算過程.該機器人Agent走過的路徑即是從起點到終點的最短路徑，則系統輸出最短路徑，結束多智能體系統運行.

2.3 多智能體系統運行過程

最短路徑多智能體系統運行過程是機器人Agent通過在邊Agent上的移動和自我復制實現對節點Agent遍歷最終獲得最短路徑的過程，具體為：系統運行開始后，第一個機器人Agent出現在起始節點Agent處，根據起始節點出邊數量決定是否自我復制，并沿著出邊Agent移動到相鄰節點Agent；當有機器人Agent移動到目的地節點Agent，系統就完成了對有向圖中最短路徑的計算，停止系統遍歷，輸出機器人Agent走過的節點即得到最短路徑.

在系統運行過程中需注意的是：第一個機器人Agent根據系統提供的有向圖、起點及終點/節點選擇活動初始點；機器人Agent只在邊Agent上移動才耗費時間，耗費的時間等于邊的權重，通過節點Agent和自我復制不會耗費時間；由于機器人Agent對節點Agent入邊的斷開能力，保證了任何節點最多被訪問一次而不會出現環路.

3 算法測試

3.1 算法測試

本研究選擇Anylogic 8.2作為開發平臺，進行最短路徑規劃多智能體系統開發.Anylogic是目前最專業的多Agent系統(Multi-agent system,MAS)開發工具，也是目前最成功的MAS系統商業開發平臺.Anylogic提供了各種Agent控件及多智能體系統需要的通信交互等功能，讓開發者把主要精力用于設計算法的實現上，有效降低了多智能體系統的開發難度.

本研究以圖1所示的有向圖對最短路徑多智能體系統進行算法測試：設P1為源節點，P6為目的地節點，求P1到P6間的最短距離.

最短路徑規劃多智能體系統的運行初始界面如圖3所示，圖4～圖6中缺失的邊即是系統運行過程中被機器人Agent到達節點Agent后斷開的入邊Agent.邊Agent被斷開后，在其上運動的機器人Agent會一并消失.圖4中，由于從P2來的機器人Agent先到達P6，因此(P3，P5)邊被斷開.圖5中，從P2來的機器人Agent先到達P4，于是(P3，P4)邊被斷開.圖6中，從P5來的機器人Agent先到達P6，于是(P4，P6)邊被斷開.由于P6是終點，系統便停止運行，輸出最短路徑為P=〈P1,P2,P5,P6〉，最短路徑長度為15.本研究通過最短路徑規劃多智能體系統，讓最短路由計算過程完全可視化，通過系統仿真的形式獲得了指定節點對之間的最短路徑，形象直觀展示了整個系統的運行過程.

圖3 MAS最短路徑啟動界面

圖4邊(P3，P5)被斷開

圖5邊(P3，P4)被斷開

圖6機器人Agent到達節點P6，邊(P4，P6)被斷開，仿真結束

3.2 算法復雜度

假設有向圖共有E條邊，由于每條邊最多有一個機器人Agent通過，所以機器人Agent的最大復制次數為E.每次復制機器人時，算法需要把它走過的節點添加到新復制的機器人歷史節點屬性中，最大添加次數為V.因此，最短路徑多智能體系統的算法復雜度不超過O(VE)，此與Bellman-Ford算法復雜度相同[11].

4 結 語

本研究利用多智能體系統實現了單源最短路徑計算，不同于傳統的最短路徑算法，本研究算法通過Agent的移動、復制和相互協同實現對有向圖節點的遍歷，快速找出了從源點到目的地的最短路徑.本研究把邊的權重轉換為機器人Agent通過該條邊所花費的時間，利用Anylogic進行系統開發，通過機器人Agent在有向圖中的移動直觀展示了系統尋找最短路徑的過程，使得整個運行過程直觀可視.同時，本研究通過多智能體系統中各種智能體功能、屬性和協調等的定義和設置，使得任何邊最多被訪問一次，有效控制了算法復雜度不超過O(VE).需說明的是，由于機器人Agent的運動時間不能為負數(或者移動速度不能為負)，因此本研究算法不能對包含負值權重的有向圖求最短路徑.