基于多智能體系統(tǒng)仿真的最短路徑規(guī)劃

唐 勇， 何東林， 朱新平

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

0 引 言

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

1 問題描述

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

(1)

因此，從節(jié)點a到節(jié)點b的最短路徑可以用最小權(quán)重函數(shù)進行表示，

(2)

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

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

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

圖1最短路徑有向圖模型

2 系統(tǒng)設(shè)計

2.1 系統(tǒng)結(jié)構(gòu)設(shè)計

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

圖2層次型多智能體系統(tǒng)結(jié)構(gòu)

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

2.2 Agent設(shè)計

2.2.1 管理Agent.

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

2.2.2 節(jié)點Agent.

節(jié)點Agent對應(yīng)于有向圖的節(jié)點，是供機器人Agent進行自我復(fù)制和邊斷開操作的環(huán)境.節(jié)點Agent具有名稱和出入邊屬性.其中，名稱即是節(jié)點Agent的編號，可對節(jié)點身份進行標識；出入邊屬性標識了該節(jié)點Agent的出邊和入邊數(shù)量以及與邊Agent的關(guān)聯(lián)關(guān)系等.

2.2.3 邊Agent.

邊Agent對應(yīng)于有向圖中的邊，邊Agent具有時間屬性、方向?qū)傩约肮?jié)點關(guān)聯(lián)屬性等.時間屬性對應(yīng)于有向圖中的權(quán)重，指明了機器人Agent通過該條邊所花費的時間；方向?qū)傩灾该髁藱C器人Agent在邊Agent上的運動方向；節(jié)點關(guān)聯(lián)屬性指明了邊Agent與節(jié)點的關(guān)聯(lián)關(guān)系，即有向圖中節(jié)點間的連接情況.

2.2.4 機器人Agent.

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

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

2.3 多智能體系統(tǒng)運行過程

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

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

3 算法測試

3.1 算法測試

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

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

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

圖3 MAS最短路徑啟動界面

圖4邊(P3，P5)被斷開

圖5邊(P3，P4)被斷開

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

3.2 算法復(fù)雜度

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

4 結(jié) 語

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