多移動機器人路徑規劃仿真平臺研究

摘要：多機器人路徑規劃仿真平臺(multi－robot path planning simulation platform)是通用的多機器人路徑規劃及協調與合作系統。該系統能將機器人狀態數據及時地以二維圖形方式顯示，并且能模擬現實工作環境，監測機器人動作，檢測機器人與環境物體間的碰撞，通過一系列仿真技術，使得原來必須用實際機器人作為對象的研究活動在一定程度上轉移到計算機中虛擬進行。比較詳細地描述了仿真平臺系統的設計原理、模型結構和運行方式，并討論了構成系統的關鍵技術特點。

關鍵詞：路徑規劃； 仿真； 面向對象技術； 多機器人

中圖分類號：TP24文獻標志碼：A

文章編號：1001－3695(2008)04－1020－03

在機器人應用領域中，由于操作任務日益復雜化及不確定性的不斷提高，對機器人系統的要求也越來越高。許多復雜的作業由單一機器人難以完成，需要多機器人相互協調與合作共同完成。這就導致了機器人的應用方式從部件式單元應用向系統式應用的方向發展[1]。為此，需要一個通用的多移動機器人路徑規劃仿真平臺來輔助研究，驗證算法的最優性、安全性、可達性。仿真平臺應能夠驗證系統單一算法的實施效果，而且在同一種工作環境下可以比較幾種不同設計算法的性能。目前通用的路徑規劃仿真系統很少，且大都停留在單機器人的路徑規劃仿真上，處理多機器人、多任務、動態環境的仿真系統較少，而且處理多機器人、多任務時做到并行處理以及較好的人機交互和動態調整是仿真平臺設計的難點。

本文討論的多機器人路徑規劃仿真平臺是一個基于C#語言及多線程技術開發的通用多機器人路徑規劃及協調與合作系統，為機器人仿真平臺系統的設計提供了很好的參考。

1路徑規劃問題概述

移動機器人路徑規劃問題是指在有障礙物的工作環境中，尋找一條恰當的從給定起點到終點的運動路徑，使移動機器人在運動過程中能安全無碰撞地繞過所有障礙物。可以按照已知和未知環境、靜態和動態環境將問題進行分類。

根據工作環境路徑規劃模型可分為兩種：a)基于模型的全局路徑規劃，作業環境的全部信息已知，又稱靜態或離線路徑規劃；b)基于傳感器的局部路徑規劃，作業環境信息全部未知或部分未知，又稱動態或在線路徑規劃。在已知的靜態環境中，一般采用一次性規劃即可得到一條可行路徑。對于未知或動態環境，由于先驗環境信息的不完全或不同時刻下環境信息不同，只能依靠實時探測到的環境信息經過多次重規劃來得到可行路徑。一般是首先更新實時探測的環境信息；然后基于已知環境信息設定子目標點，規劃一條局部的可行路徑，按照規劃出的局部可行路徑進行移動[2~7]。

2路徑規劃仿真平臺模型結構

為了解決多機器人、多任務、動態障礙物、人機交互等技術問題，系統依據以下原則進行設計：良好的算法擴充性、具備并行處理能力、在線修改參數、可視化顯示、實現人機交互等。系統采用model (模型)、view(視圖)、controller (控制)分離設計的MVC構架，具有良好的可擴展性和復用性，采用面向對象模型化技術（object modeling technique，OMT）對多機器人仿真系統進行分析，建立了仿真系統的對象模型、動態模型和功能模型[8]。

2．1平臺模型簡介

采用MVC架構的目的是增加代碼的重用率，減少數據表達、數據描述和應用操作的耦合度，使得系統可維護性、可修復性、可擴展性、靈活性以及封裝性提高。其中，各自的功能為：model抽象系統的應用功能、封裝系統的狀態、提供使用系統功能的方法和路徑、管理數據的存儲和一致性，當數據發生變化時通知相關部分；view抽象數據表達、表示針對用戶的數據、維護與model數據的一致性；controller抽象用戶和系統的事件語義映射，將用戶輸入翻譯為系統事件。

一個以MVC為架構的系統包含了很多設計模式，但是與MVC最為密切相關的是以下三種模式：observer、composite和strategy[8]。Observer模式是對象型模式，同時它也是行為型模式，它定義對象間的一對多的依賴關系。當一個對象的狀態發生改變時，所有與它有依賴關系的對象都得到通知并自動更新。當通過某一種方式改變了數據，那么其他的顯示都應能立即知道數據的改變并作相應的調整。Composite模式是對象型模式，同時它也是結構型模式，將對象組合成樹型結構以表示部分—整體層次結構。Composite使組合對象的使用和單個對象的使用具有一致性。本系統采用strategy模式。該模式定義一系列的算法，并將它們封裝起來，使它們可以互相替換，使得算法可以獨立于使用它的對象而變化。MVC將響應邏輯封裝在controller中，view使用controller來實現一個特定的響應策略。要實現不同的響應策略，還可以在運行時刻通過改變view的controller來改變view對用戶輸入的響應策略。系統用例圖如圖1所示。

2．2多機器人路徑規劃仿真平臺類圖

1）地圖類生成地圖對象，作為路徑規劃的環境模型，用一個動態二維數組存儲地圖信息，可以根據具體地圖的大小來決定此數組的大小。這是一個自定義的對象數組，每一個節點信息對象包含有節點坐標和節點類型兩個屬性。節點類型屬性用于記錄地圖上此坐標的節點信息，包括靜態障礙物、動態障礙物、機器人、可行點等，分別由不同的值表示。仿真系統通過可以讀取的BMP格式文件作為靜態地圖，每一個像素就是一個柵格節點，BMP文件可以任意編輯，因此仿真系統的靜態地圖建立是相當方便的。環境模型的另一個功能是用于顯示仿真動畫。由于動態數組信息中包括地圖信息、機器人、動態障礙物在內的各種信息，通過在不同時刻將數組中的節點信息顯示在界面上，就形成了仿真動畫[9]。

2）物體類包括機器人類和障礙物類。物體類是基類，標記當前坐標等基本信息。機器人的大小為一個柵格，即采用點狀機器人模型；對于非點狀機器人，可以通過擴展障礙物使機器人尺寸收縮為一個柵格大小。文獻[10]提出了一種基于客戶端/服務器結構的多機器人計算機仿真系統設計方案，基于二維平面模型來建立機器人模型、傳感器模型、環境模型；提供了配置傳感器參數功能、實時改變環境模型功能。在本系統中可以將每一個客戶端實例化為一個機器人，通過繼承父類并新添加自己屬性的方法，使不同機器人各自有不同的工作場景，各自按照規劃算法完成工作，并提供修改接口；在運行過程中改變參數，完成復雜的仿真，實現多機器人多任務的仿真。機器人類包括路徑規劃的起點和終點、視野半徑、步長、能否記憶標志等一些基本屬性。機器人類中有一個算法類的對象，機器人對象按照這個類的方法執行路徑規劃仿真。在機器人類中用動態二維數組記錄機器人獲知的地圖節點信息。這個數組中的元素對象類似于地圖類中的節點信息對象，但增加了其他屬性，用于記錄規劃路徑時的一些附加參數。機器人將這個數組作為柵格地圖來進行路徑規劃算法的計算，實現了記憶功能。環境感知記憶功能模擬了信息感知的功能，通過讀取環境地圖類中的數組信息并記錄下來；讀取的范圍根據機器人視野半徑屬性來決定，通過修改參數使機器人具有不同的感知能力。動態障礙物類定義了動態障礙物的模型，包括障礙物大小、當前坐標、移動步長、移動規律等屬性。動態障礙物模型與機器人模型有一定的相似性，它們都是根據地圖信息自主計算出本次移動路徑，進行移動之后再將移動過程記錄到地圖模型中用于顯示。它們之間的不同之處在于：首先，動態障礙物計算路徑是基于地圖數組，即它總是將所有地圖信息作為已知，因此它不需要環境感知模塊，而機器人則基于機器人范圍數組，其中可能只保存了部分地圖信息；其次，它計算路徑時的算法極為簡單，一般進行直線運動，遇到靜態障礙物則轉換方向，因此不需要獨立的算法模塊；最后，動態障礙物在計算路徑時無須考慮機器人的位置，而機器人在計算路徑時必須考慮動態障礙物的位置。物體類圖及地圖類圖如圖2所示。

3）算法類PathPlaningStrategy是一個抽象類，本身并不實現算法，而由子類實現路徑規劃算法；一個子類對應一種路徑規劃算法，每增加一個新的路徑規劃算法就需要添加一個新的繼承類。機器人類中定義了一個算法基類對象，仿真時實例化為一個算法子類，這樣就可以在不修改機器人類的基礎上，通過指定算法來完成某一個路徑規劃算法的仿真。文獻[11]中設計了一種不確定環境下移動機器人運動路徑的在線規劃算法，完成了在線規劃避障功能，可以將其算法封裝成一個算法類，在平臺上進行仿真。仿真算法函數基于數組中的柵格地圖信息規劃一條可行路徑，并將規劃后的路徑記錄于規劃路徑數組，因此數組和規劃路徑數組是算法的輸入/輸出接口。算法類的每一個繼承類應根據對應的路徑規劃算法給出這個函數的實現，將算法封裝在這個類函數中?；谏鲜龀绦蚪Y構和特點，用戶可以高效地對仿真系統進行新的路徑規劃算法的擴充。方法是繼承算法基類，生成一個新的算法類，然后將路徑規劃算法封裝在函數中，系統的其他部分無須改動。算法類圖如圖3所示。

2．3多機器人路徑規劃仿真平臺控制模塊

控制模塊完成機器人和障礙物的移動，并通過視圖顯示給用戶。根據規劃路徑中的信息和步長屬性來移動機器人，并將移動的過程記錄到地圖模型中；使動態障礙物能在地圖模型中根據事先規定的移動規律計算得到每一次的移動路徑，記錄在運動路徑數組中，移動動態障礙物。根據機器人實例化的不同規劃方法和C#語言的多態性，程序具有運行時識別的特性，在仿真過程中會自動調用用戶選擇的路徑規劃算法運行。

2．4仿真系統的運行方式及并行處理技術

通用路徑規劃仿真系統需要在動態或未知環境下進行路徑規劃，而在這些環境中進行路徑規劃必然要進行多次重規劃，因此仿真系統采用滾動運行方式。此方式同樣兼容靜態已知環境下的一次性路徑規劃。每次運行時，機器人首先感知視野半徑內的環境信息并記錄下來；然后根據記錄的信息進行局部路徑規劃；最后根據規劃的路徑移動機器人，并判斷是否已到達終點。如果沒有到達，則循環運行，同時還需要支持所有動態障礙物運動。

在系統仿真中會遇到并發處理的問題。由于計算機的串行運算特點，仿真步驟只能先后進行，這時就要用到多線程技術，每個機器人和障礙物都開啟一個線程并行運行，每個線程都有自己的內存空間。這樣有可能出現下述情況：機器人與動態障礙物的移動路徑中有相互沖突的節點，但是程序中兩個運行步驟的先后次序掩蓋了這一情況，這樣就會使研究者忽略一些算法中可能存在的缺陷。因此需要在程序中啟用多線程技術，實現對單個對象的互斥訪問，實現多個機器人的并行移動、并行尋找最優路徑。多線程中的一個重要問題是如何保護公共資源互斥訪問，這樣才會避免碰撞的發生。當機器人需要讀取共享信息時首先加鎖，加鎖成功則訪問；否則排隊等待，待此資源被其他使用者解鎖后再用。同樣，如果本機器人需要申請占用空間或準備移動到新的位置，則先行申請此空間，標注此空間被占用，然后解鎖這個訪問，其他機器人才可以訪問。這樣就解決了機器人路徑沖突的問題，避免碰撞發生。

3多機器人路徑規劃仿真平臺的實現

基于前述的多機器人路徑規劃仿真平臺的結構模型、類圖和程序流程，在Windows 2000操作系統上使用Visual C#開發工具實現了這一仿真系統。利用C#語言、Windows平臺提供的多線程、圖像處理等技術，實現了機器人的全局控制及并行處理。在這里給出兩個基于仿真系統的仿真實例。

圖4是一個有障礙物的地圖。環境設置為靜態未知，采用可視圖路徑規劃算法，分別設定不同的環境感知能力進行仿真，機器人都能找到路徑到達終點，完成了路徑規劃。對比結果顯示了環境感知能力強的機器人路徑規劃效果總體要好于感知能力差的。圖中情形b感知能力最弱，遇到障礙物時才會尋找新路徑；情形a和c均有較強的環境感知能力。因為環境未知，可能出現感知能力強的路徑不是最短的情況。例如圖中感知能力最強的a的實際路徑長度要大于c。在本系統中可以在同一個界面地圖中同時模擬不同參數或不同算法的路徑規劃仿真，使仿真結果更加直觀，在文獻[9]的基礎上更進了一步。

在圖5中為兩個機器人設定了相對的起始和終點坐標，環境為未知，機器人自動尋找路徑，行進速度不相同。在情形b和a表示的行進路徑上定會相遇，這時碰撞檢測機制應在相遇之前檢測到碰撞。如何檢測這個碰撞點是一個難點，因為個機器人都有自己的視野、自己的行進路徑。本系統利用多線程技術及鎖機制：

system.Threading.Thread OneRobot=new Thread(new ThreadStart(PathPlanBot));//創建一個機器人線程

oneRobot.Start();//機器人線程開始工作

……

//在每一個線程內需要公共資源時事先加鎖

system.Threading.Monitor.Enter(PicPlant);//資源可用時進入

pathPlan()；/*規劃路徑并作標志位，發現路徑上有點被占用則重規劃*/

system.Threading.Monitor.Exit(PicPlant); 

//使用完畢后解鎖，下一個申請者可以進入

每個機器人占用當前自己的位置和之后路徑上的幾個位置，根據速度參數計算出申請的位置數。如圖5中情形a和b 的路徑產生沖突，b作出了繞行，偏轉一個位置，之后直線前行到達目的地。本系統利用多線程及鎖機制，能夠有效地檢測到碰撞發生，并利用規劃算法避免碰撞。

4結束語

本仿真系統中算法設計獨立、擴充性好、仿真功能和交互能力強大，具有并行處理能力、在線修改參數和數據，可以進行可視化顯示；能夠很好地實現人機交互功能，極大地方便了路徑規劃算法的研究工作；可以驗證單一算法的實施效果；而且在同一種環境下可以比較幾種不同算法的性能。系統面向對象的結構特點以及并行處理能力，使它可以進一步用于分布式多移動機器人的路徑規劃仿真。在后繼開發過程中，可以引入一個通信模塊，完成分布式計算和多機協作的功能，支持網絡互連的分布式仿真。

參考文獻：

[1]王越超，談大龍.協作機器人學的研究現狀與發展[J].機器人，1998，20(1):69－75.

[2]ANN D. Automated guided vehicle system: an introduction[J]. Industrial Engineering， 1994(8):47－51.

[3]席裕庚，張純剛.一類動態不確定環境下機器人的滾動路徑規劃[J].自動化學報，2002，28(2):161－175.

[4]DIEGUEZ A R， SANZ R， LOPEZ J. Deliberative on－line local path planning for autonomous mobile robots[J]. Journal of Intelligent and Robotic Systems， 2003，37(1):1－19.

[5]KRUUSMAA M， WILLEMSON J. Covering the path space: a case base analysis for mobile robot path planning[J]. Knowledge－based Systems， 2003，16(5/6):235－242.

[6]KOENIG S， LIKHACHEV M.Improved fast replanning for robot navi－gation in unknown terrain[C]//Proc of IEEE International Con－ference on Robotics and Automation. Washington DC: IEEE Compu－ter Society， 2002:968－975.

[7]HAN W G， BAEK S M， KUC T Y. Genetic algorithm based path planning and dynamic obstacle avoidance of mobile robots[C]//Proc of IEEE International Conference on Computational Cybernetics and Simulation. Orlando:[s.n.]， 1997:2747－2751.

[8]GAMMA E， HELM R， JOHNSON R. Design pattern: elements of object－oriented software[M].北京:機械工業出版社， 2000.

[9]胡世亮，席裕庚.一種通用的移動機器人路徑規劃仿真系統[J]. 系統仿真學報， 2004，16(8):1714－1716，1720.

[10]王碩，張斌，譚民，等.多自主移動機器人計算機仿真系統的設計與實現[J].系統仿真學報，2002，14(2):225－228.

[11]李貽斌，周鳳余，李彩虹，等.移動機器人在線路徑規劃算法研究[J].系統工程與電子技術，2000，22(2):79－81.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”