唐 勇， 何東林， 朱新平

(1.成都大學(xué) 信息科學(xué)與工程學(xué)院， 四川 成都 610106；2.中國(guó)民航局第二研究所 科研開發(fā)中心， 四川 成都 610041；3.中國(guó)民用航空飛行學(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].對(duì)此，科研人員對(duì)最短路徑規(guī)劃問題進(jìn)行了大量研究[5-7]，并提出了一系列最短路徑算法及各種改進(jìn)算法，比如，A*算法、Dijkstra算法、Floyd算法、Bellman-Ford算法及SPFA算法等[8-12].總體來看，現(xiàn)有的最短路徑算法大多利用數(shù)學(xué)分析方法實(shí)現(xiàn)，但也存在解析參數(shù)過多或難以確定，甚至解析解不存在的情況.針對(duì)此問題，科研人員提出了系統(tǒng)仿真法對(duì)復(fù)雜系統(tǒng)進(jìn)行求解，并取得了較好結(jié)果[13].基于此，本研究利用多智能體系統(tǒng)設(shè)計(jì)了最短路徑仿真算法，把有向圖中的節(jié)點(diǎn)與邊都建模成智能體，再設(shè)計(jì)機(jī)器人智能體，利用機(jī)器人智能體的自我復(fù)制和移動(dòng)能力，讓機(jī)器人智能體沿著節(jié)點(diǎn)出邊對(duì)與該節(jié)點(diǎn)相連接的節(jié)點(diǎn)進(jìn)行并行移動(dòng)訪問，從而快速實(shí)現(xiàn)對(duì)有向圖節(jié)點(diǎn)的遍歷，采用系統(tǒng)仿真運(yùn)行的方式直觀地獲取有向圖最短路徑.

1 問題描述

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

(1)

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

(2)

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

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

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

圖1最短路徑有向圖模型

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

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

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

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

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

2.2 Agent設(shè)計(jì)

2.2.1 管理Agent.

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

2.2.2 節(jié)點(diǎn)Agent.

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

2.2.3 邊Agent.

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

2.2.4 機(jī)器人Agent.

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

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

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

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

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

3 算法測(cè)試

3.1 算法測(cè)試

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

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

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

圖3 MAS最短路徑啟動(dòng)界面

圖4邊(P3，P5)被斷開

圖5邊(P3，P4)被斷開

圖6機(jī)器人Agent到達(dá)節(jié)點(diǎn)P6，邊(P4，P6)被斷開，仿真結(jié)束

3.2 算法復(fù)雜度

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

4 結(jié) 語(yǔ)

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