緒論：寫作既是個人情感的抒發，也是對學術真理的探索，歡迎閱讀由發表云整理的11篇路徑規劃典型算法范文，希望它們能為您的寫作提供參考和啟發。

篇（1）

交通運輸的現代化使人們享受便利的同時，也面臨道路擁堵、事故頻發等問}。近年來，智能交通系統越來越受到人們的重視，它涉及到交通領域諸多方面，如最優路徑選擇、車輛路徑規劃、動態車輛調度、交通流量控制等。其中一個重要的應用是一類典型的以數學理論為基礎的組合優化問題，而蟻群算法具有內在的搜索機制及正反饋性，適合求解一系列的組合優化問題。

1 蟻群算法描述

蟻群算法源于20世紀90年代初意大利學者M.Dorigo首次提出的螞蟻系統。它是基于種群的啟發式放生進化系統，是通過對蟻群覓食過程中其行為的研究而得出的一種算法。主要思路是螞蟻借助自己路徑尋優的能力可以找到巢穴與食物之間最短的途徑。在尋找過程中主要依靠的是每個螞蟻在行進過程中留下的揮發性分泌物――信息素，依靠信息素，蟻群的螞蟻之間可以相互合作，相互配合，因此形成的正反饋可以使每只螞蟻找到所有路徑中最短的路徑。

螞蟻a從節點j移動至k的轉移概率可以從式（1）中獲取：

（1）

（2）

（3）

2 蟻群算法的應用優勢

蟻群算法，又名螞蟻算法，螞蟻可以利用信息素的濃度大小從而尋找到覓食的最優路徑。該算法的優點可以總結為：

2.1 并行分布式計算

每個螞蟻都是獨立的個體，在覓食過程中屬于多起點同時啟動，互不影響，從根本上分析該過程屬于分布式的多Agent系統，整體蟻群最終任務的順利完成不會由于某些個體的缺陷而受到影響。該算法具有真實可用性，并且可用于解決對單目標的優化或者對多目標的優化等重要問題。此外，螞蟻算法還可進行并行計算。

2.2 魯棒性

蟻群算法的最終結果與螞蟻最初選擇的路徑無太大關系，在利用人工仿真螞蟻進行問題求解過程中，不需要對其進行人工的修整。把問題簡單化，可以和其他算法相互結合求解最優問題。

2.3 自組織性

蟻群算法組織指令的來源為系統內部，它不受外界環境的干擾，因此該算法具有自組織性。

2.4 正反饋性

螞蟻對于最優路徑的選擇主要依靠路徑上信息素濃度的多少，信息素的堆積是正反饋的過程，路徑上信息素的含量越多則該路徑被選擇的幾率就會越大，正反饋的作用是使整體能夠更快的尋找到最優途徑，正反饋在蟻群算法中處于重要地位。

2.5 易于實現

它是一種啟發示算法，其計算復雜性為，整個算法的空間復雜度是：。

3 蟻群算法在智能交通領域的應用空間

蟻群算法在解決組合優化問題方面有著明顯的優勢，從而在智能交通領域也有著廣泛的應用空間。

3.1 車輛路徑導航

根據行車人員的需要，根據對實時路況信息的統計，系統可以智能的為其推薦最優路徑，節省時間，節省資源。

3.2 動態車輛調度

當客戶需要調度中心為其進行車輛服務時，調度中心要考慮到客戶的情況，要考慮到效率的問題，要考慮到行車路線、行駛時間等問題。蟻群算法便可迅速得到合理的解決方案，使客戶和調度中心均可受益。

3.3 車輛路徑規劃

面對多個客戶不同的要求時，配送中心要根據實際情況進行車輛的配送，通過蟻群算法系統獲取整體的最優路線，根據路線規劃，及時進行車輛出發以滿足客戶要求，同時充分利用了道路資源和車輛資源。

3.4 公共交通智能化調度

利用先進的技術手段、大型數據庫技術等動態地獲取實時交通信息，實現對車輛的實時監控和調度，最終建立集運營指揮調度、綜合業務通信及信息服務等為一體的智能化管理系統。

3.5 交通流量控制

通過蟻群算法簡化復雜的道路交通網絡，盡量使交通流量在各個道路上分布均勻，避免因流量過大而造成車輛的阻塞。及時了解交通流量情況，緩解了交通擁擠，降低了交通事故的發生率。

參考文獻

[1]M.Dorigo，V.Maniezzo，A.Colom.Ant System：Optimization by a colony of cooperating agents.IEEE trans on SMC，1996，26（01）：28-41

[2]Eric BONABEAUB， Marco DORIGO，Guy THERAULAZ.AWARM intelligence： from natural to artificial systems[M].New York：Oxford University Press，1999

[3]楊海.蟻群算法及其在智能交通中的應用[D].濟南：山東師范大學，2008：14-18

作者簡介

白曉（1979-），女。工學碩士學位。現供職于廈門軟件職業技術學院軟件工程系。主要研究方向為軟件工程、智能算法。

篇（2）

當前，智能電網的發展在一定程度上帶動了電網技術的發展，并且成為了電網技術發展的重要方向。實際上，智能電網的重要組成部分在于智能配電網，智能配電網的主要特征為擁有完備的自愈能力，同時還能夠最大程度的減少電網故障給用戶帶來的影響。而配電網故障的恢復是智能配電網自愈功能實現的重要過程，配電網故障恢復問題主要指配電網發生故障以后，在故障定位與故障隔離的基礎之上，應用一定的故障恢復策略對其進行操作，從而確保供電的平穩與正常。

一、對最佳路徑的分析

配電網故障區域恢復供電的最佳路徑事實上是在故障情況下的配電網絡重構。主要的目的在于，能夠快速的將非故障區域供電恢復，與此同時，還能夠有效的滿足線路負載容量的要求以及線損最小等各個方面的條件。現階段，在配網自動化領域中研究最多的在于怎樣能夠快速的實現故障隔離以及快速的恢復費故障區域的供電技術方法，因此，在恢復路徑的最優化選擇方面出現了較多的研究。

一般而言，配電網故障區域恢復供電的路徑為多目標最佳路徑問題，現階段在最佳路徑問題的研究上較多的便是城市交通網絡中的最短路徑問題的研究。由于問題解決的思路存在著極大的不同點，因此最短路徑問題能夠被分為單元最短路徑算法與基于啟發式搜索最短路徑算法[1]。這與鄧群，孫才新，周駁仍凇恫捎枚態規劃技術實現配電網恢復供電》一文中的觀點極為相似。其中，單元最短路徑算法主要體現在幾個方面，即：

第一，在GIS空間查詢語言方面的最短路徑。該職工路徑的研究方法在當前還停留在理論研究方面，例如在MAX中定義了一套空間查詢語言，該套語言對其完備性給予了相關證明，同時通過舉證的方式，對范圍查詢與時態查詢等進行了應用分析。

雖然，對于GIS空間發展研究GeoSQL為一種有效的處理最短路徑的手段，但是GIS受到數據庫技術發展的制約與影響，導致實際的應用領域和背景的不同，使其和商用之間還有很長的一段距離。

第二，在功能模塊思想路徑方面，需要按照不同的分類方法實施，而單元最短路徑問題的算法能夠被分為很多種，例如神經網絡法與基于人工智能的啟發式搜索算法等，對于不同的背景應用需求和具體軟件應用的環境，各種算法在空間的復雜程度與時間的復雜程度等都有明顯的體現[2]，這與李振坤，周偉杰，錢嘯等在《有源配電網孤島恢復供電及黑啟動策略研究》一文中有著相似的觀點。并且各種算法在故障恢復方法中各具特色。

另外，啟發式搜索最短路徑算法也是一種有效的手段。基于啟發式方向策略最短路徑算法，其中包括空間有效方向的可控參數法，該方法能夠有效的調節相關系數，在有效方向上路徑無效的時候，能夠確保得到有效的路徑。

二、最佳路徑的選擇方法分析

事實上，配電網故障區域恢復供電的最佳路徑并不是簡單的路徑問題，而是多目標最佳路徑問題。為此，在研究配電網非故障區域恢復供電的最佳路徑過程中，需要對其展開綜合的分析。

首先，在多目標分析方面，通常在選擇配電網非故障區域恢復供電最佳路徑的時候，最為重視的目標為：

第一，在恢復供電路徑的過程中，饋線負荷不能過載，同時，還需要確保恢復區域的電壓質量能夠與實際規定的標準要求相吻合。當供電質量可靠性最高的時候，那么恢復的時間將會很短[3]；這與鄧昆英，汪鳳嬌，饒杰等在《智能配電網有功自治互動建模研究》一文中的觀點極為相似。另外，供電過程中，線損最低，證明開關拉合的次數最少，同時現場的操作點也會最少。

第二，在動態規劃技術恢復供電的最短路徑方面需要明確，動態規劃主要是運籌學的一個分支，它是求解決策過程的最優的數學方式。早在很久以前，就已經有研究人員對多階段過程轉化問題轉化為一系列的單階段問題，并且逐一進行求解，這標志著解決這類過程優化問題的新方法的創立，即動態規劃技術。

本文主要將一典型的復雜配電網絡作為研究例子，該連通系包括10個電源點，8個分支點，同時聯絡開關有16個。將其加入到配網潮流方向和典型的運動方式中，將聯絡開關和電源點作為定點，那么可以將其分為26個定點。盡管從數量上頂點比較多，但是由于存在著較為復雜的網絡關系，使得該問題成為一個極為簡單的最短路徑問題[4]。這與楊建在《配電網無功補償系統的關鍵技術研究》一文中的觀點有著相似之處。加之恢復路徑主要指費故障區域相關的聯絡開關與相應路由，為此我們可以將其理解為從不同電源點出發到各個聯絡開關的最短路徑問題，這樣一來，故障恢復工作的實施便簡單的多。

總結

本文主要從兩個方面左手，共同分析了采用動態規劃技術實現配電網恢復供電的方法與效果，一方面著手于最佳路徑的分析，另一方面著手于最佳路徑的選擇方法。從這兩個方面可以看出，利用動態規劃技術去實現配電網恢復供電是一種可行的方法。但是，受到歷史原因的影響，我國城市配電網絡還缺少標準的規范要求，導致配電網常常出現一些事故。因此，恢復配電網供電已經成為當務之急。隨著科技的發展，智能配電網已經被廣泛的應用在供電方面，這為平穩供電提供了一定的保障，同時也為恢復配電網故障供電創建了良好的環境與條件等。

參考文獻

[1]鄧群，孫才新，周駁.采用動態規劃技術實現配電網恢復供電[J].重慶大學學報（自然科學版），2006，29（3）：40-44.

[2]李振坤，周偉杰，錢嘯等.有源配電網孤島恢復供電及黑啟動策略研究[J].電工技術學報，2015，30（21）：67-75.

[3]鄧昆英，汪鳳嬌，饒杰等.智能配電網有功自治互動建模研究[J].機電工程技術，2014，（2）：4-7.

篇（3）

為了減輕交通壓力，人們越來越關心交通系統的智能化進程。智能交通系統主要的研究方向之一就是動態路徑誘導系統，它可根據外出的人們的需求，為駕駛員提供最新的路況信息和最佳路徑選擇，以此避免交通擁堵現象的發生，從而優化交通狀況，最終使交通時時地保持一個合理的動態分配。目前，最優路徑選擇的方法有很多，但是真正需要解決大型問題時，計算機需要搜索的選擇范圍太大，傳統的動態算法基本上無法處理。1995年，神經動態規劃算法被提出，該算法把復雜的問題分成若干子問題，這些子問題被拆分后更容易解決，使計算過程大幅簡化，且更容易被計算機處理。采用這種方法，可準確、快速、實時、穩定地選擇出最優路徑，值得推廣。

1 神經動態規劃概述與核心思想

在解決多階段決策問題時，動態規劃大致思想為：將非常繁瑣的原始問題分解為若干個階段，這些階段看似不相關，卻是相互聯系的子階段，在找到上一階段的解決方法以后才能處理下一個階段，依次求出每個階段的解，最后得到全局最佳的解。多階段決策問題具備很強的順序性，同時每個階段所使用的解決方法也是隨著階段的變化而變化，所以“動態”意義就得以體現。其中交通網中最佳路徑的求解就是典型的多階段決策問題。

在路徑優化中，動態規劃是一種非常經典的計算方法，但在處理實際問題的時，我們肯定會遇到缺少一個完整信息或者維數災等一系列問題，所以，引進神經網絡對動態規劃具有較大的解決實際問題的意義。神經動態規劃如圖1所示。

2 基于神經動態規劃算法的最優路徑實現

（1）將原來的問題分解成很多個小問題，即子階段，并且找到每個子階段的最優解決辦法。求解多級問題的步驟為：根據每個問題的特點，劃分子階段。在劃分子階段時，必須按照一定的規則，比如根據執行決策的時間、空間的順序等。本文用x來表示子階段變量。

（2）求解狀態和狀態變量。每個子階段具體的起始位置可以依靠自然狀態來指導，其中客觀條件階段性數目的狀態是自然狀態中的一種，它傳達每個子階段的關鍵信息，此外，一組或者無后效性的變量同樣可以用來表示狀態變量。本文用Hx來表示第x級的狀態變量。

（3）求解原問題決策變量和集合。從目前階段到下一個階段狀態選擇時，決策者需要做出恰當的決策，決策變量的范圍稱為集合。本文用Dx表示決策集合，用Ux表示決策變量。

（4）研究狀態轉移的方程。假設狀態轉移方程是：Hx+1=Tx（Hx，Ux）。次方程式中Tx不定，根據具體問題才能確定，如果Hx確定，一旦變量Ux確定，那么第x+1階段狀態變量（Hx+1）也將確定。

（5）研究指標函數。因為n和vi的遞進性和可分離性，所以很容易找到指標函數n和vi之間的關系，顯然，指標函數的求解也相對簡單化。

（6）動態規劃函數的基本方程。邊界條件為；

，第x-m階的最優動態規劃函數是。

3 仿真結果

將上述模型，在Matlab仿真軟件上進行模擬仿真，分解原始問題并確定各個子階段的最佳方案，將這個問題用網格的形式如圖2進行表示：A為起始地點，E為目標地點，從起始地點到目標終點有很多路徑，假設經過每個節點需要一定的運輸成本，在Matlab仿真軟件上進行仿真后依據動態規則算法的要求，設定好相應的算法模型以及相應的計算公式，這樣便可以找到最優路徑。

由圖2可以非常清楚的看出，成本最低的路線為：或者或者，成本都是110。仿真結果可以看出神經動態規劃算法具有較多優點：得到清晰運算結果；很容易找到全局的最優路徑；可以找到一組完善的解，有利進一步的分析。

4 結語

我們在使用神經動態規劃算法來探索最優路徑的時候，具有很多優勢，首先其具有穩定、可靠的步驟，過程并不復雜，但是給予我們的結果十分清晰明確，且適用于現實生活。使用這種動態規劃算法解決復雜的問題時，可以非常容易找到解決方案，而且效率很高。當然，該算法也有一定的局限，但只要我們不斷地改進完善，日后繼續研究神經動態規劃算法，相信一定可以攻克更多的局限，能夠使其更好地被應用。

參考文獻

[1]謬慧芬，邵小兵.動態規劃算法的原理及應用[J].中國科技信息，2006（23）：32.

[2]楊琰，廖偉志，李文敬，楊文，李杰.基于Petri網的顧及轉向延誤的最優路徑算法[J].計算機工程與設計，2013（10）.

作者簡介

篇（4）

關鍵詞：多機器人；路徑規劃；強化學習；評判準則

Abstract:This paper analyzed and concluded the main method and current research of the path planning research for multirobot.Then discussed the criterion of path planning research for multirobot based large of literature.Meanwhile，it expounded the bottleneck of the path planning research for multirobot，forecasted the future development of multirobot path planning.

Key words:multirobot；path planning;reinforcement learning;evaluating criteria 

近年來，分布式人工智能(DAI)成為人工智能研究的一個重要分支。DAI研究大致可以分為DPS（distributed problem solving）和MAS（multiagent system）兩個方面。一些從事機器人學的研究人員受多智能體系統研究的啟發，將智能體概念應用于多機器人系統的研究中，將單個機器人視做一個能獨立執行特定任務的智能體，并把這種多機器人系統稱為多智能體機器人系統（MARS）。因此，本文中多機器人系統等同于多智能體機器人系統。目前，多機器人系統已經成為學術界研究的熱點，而路徑規劃研究又是其核心部分。

機器人路徑規劃問題可以建模為一個帶約束的優化問題，其包括地理環境信息建模、路徑規劃、定位和避障等任務，它是移動機器人導航與控制的基礎。單個移動機器人路徑規劃研究一直是機器人研究的重點，且已經有許多成果[1~3]，例如在靜態環境中常見的有連接圖法、可視圖法、切線圖法、Voronoi圖法、自由空間法、柵格法、拓撲法、鏈接圖法、DempsterShafer證據理論建圖等；動態環境中常見的有粒子群算法、免疫算法、遺傳算法、神經網絡、蟻群算法、模擬退火算法、人工勢場法等。然而，多機器人路徑規劃研究比單個機器人路徑規劃要復雜得多，必須考慮多機器人系統中機器人之間的避碰機制、機器人之間的相互協作機制、通信機制等問題。

1 多機器人路徑規劃方法

單個機器人的路徑規劃是找出從起始點至終點的一條最短無碰路徑。多個機器人的路徑規劃側重考慮整個系統的最優路徑，如系統的總耗時間最少路徑或是系統總路徑最短等。從目前國內外的研究來看，在規劃多機器人路徑時，更多考慮的是多機器人之間的協調和合作式的路徑規劃。

目前國內外多機器人路徑規劃研究方法分為傳統方法、智能優化方法和其他方法三大類。其中傳統方法主要有基于圖論的方法（如可視圖法、自由空間法、柵格法、Voronoi圖法以及人工勢場方法等）；智能優化方法主要有遺傳算法、蟻群算法、免疫算法、神經網絡、強化學習等；其他方法主要有動態規劃、最優控制算法、模糊控制等。它們中的大部分都是從單個機器人路徑規劃方法擴展而來的。

1）傳統方法 多機器人路徑規劃傳統方法的特點主要體現在基于圖論的基礎上。方法一般都是先將環境構建成一個圖，然后再從圖中尋找最優的路徑。其優點是比較簡單，比較容易實現；缺點是得到的路徑有可能不是最優路徑，而是次優路徑。薄喜柱等人[4]提出的一種新路徑規劃方法的基本思想就是基于柵格類的環境表示和障礙地圖的。而人工勢場方法的基本思想是將移動機器人在環境中的運動視為一種虛擬人工受力場中的運動。障礙物對移動機器人產生斥力，目標點產生引力，引力和斥力周圍由一定的算法產生相應的勢，機器人在勢場中受到抽象力作用，抽象力使得機器人繞過障礙物。其優點是適合未知環境下的規劃，不會出現維數爆炸問題；但是人工勢場法也容易陷入局部最小，并且存在丟失解的部分有用信息的可能。顧國昌等人[5]提出了引用總體勢減小的動態調度技術的多機器人路徑規劃，較好地解決了這個問題。

2）智能優化方法 多機器人路徑規劃的智能優化方（算）法是隨著近年來智能計算發展而產生的一些新方法。其相對于傳統方法更加智能化，且日益成為國內外研究的重點。

遺傳算法是近年來計算智能研究的熱點，作為一種基于群體進化的概率優化方法，適用于處理傳統搜索算法難以解決的復雜和非線性問題，如多機器的路徑規劃問題。在路徑規劃中，其基本思想是先用鏈接圖法把環境地圖構建成一個路徑節點鏈接網，將路徑個體表達為路徑中一系列中途節點，并轉換為二進制串；然后進行遺傳操作（如選擇、交叉、復制、變異），經過N次進化，輸出當前的最優個體即機器人的最優路徑。遺傳算法的缺點是運算速度不快，進化眾多的規劃要占據很大的存儲空間和運算時間；優點是有效避免了局部極小值問題，且計算量較小。 

孫樹棟等人[6，7]在這方面較早地展開了研究，提出的基于集中協調思想的一種混合遺傳算法來規劃多機器人路徑方法較好地解決了避障問題。但不足的是該方法必須建立環境地圖，在環境未知情況下的規劃沒有得到很好的解決；且規劃只能保證找到一個比較滿意的解，在求解全局最優解時仍有局限。

文獻[8]中提出的一種基于定長十進編碼方法有效降低了遺傳算法的編碼難度，克服了已有的變長編碼機制及定長二進制編碼機制需特殊遺傳操作算子和特殊解碼的缺陷， 使得算法更加簡單有效。

智能計算的另一種常見的方法——蟻群算法屬于隨機搜索的仿生算法。其基本思想是模擬螞蟻群體的覓食運動過程來實現尋優，通過螞蟻群體中各個體之間的相互作用，分布、并行地解決組合優化問題。該算法同樣比較適合解決多機器人的路徑規劃問題。

朱慶保[9]提出了在全局未知環境下多機器人運動螞蟻導航算法。該方法將全局目標點映射到機器人視野域邊界附近作為局部導航子目標，再由兩組螞蟻相互協作完成機器人視野域內局部最優路徑的搜索，然后在此基礎上進行與其他機器人的碰撞預測與避碰規劃。因此，機器人的前進路徑不斷被動態修改，從而在每條局部優化路徑引導下，使機器人沿一條全局優化的路徑到達目標點。但其不足是在動態不確定的環境中路徑規劃時間開銷劇增，而且機器人缺乏必要的學習，以至于整個機器人系統路徑難以是最優路徑。

強化學習[10，11] (又稱再激勵學習)是一種重要的機器學習方法。它是一種智能體從環境狀態到行為映射的學習，使得行為從環境中獲得積累獎賞值最大。其原理如圖1所示。

強化學習算法一般包含了兩個步驟：a）從當前學習循環的值函數確定新的行為策略；b）在新的行為策略指導下，通過所獲得的瞬時獎懲值對該策略進行評估。學習循環過程如下所示，直到值函數和策略收斂:

v0π1v1π2…v*π*v*

目前比較常見的強化學習方法有：Monte Carlo方法、動態規劃方法、TD（時間差分）方法。其中TD算法包含Sarsa算法、Q學習算法以及Dyna-Q算法等。其Q值函數迭代公式分別為

TD（0）策略： V(si)V(si)+α[γi+1+γV(si+1)-V(si)]

Sarsa算法： Q(st，at)Q(st，at)+α[γt+1+γQ(st+1，at.+1)-Q(st，at)]Qs′學習算法： Qπ(s，a)=∑Pαss′[Rass′+γVπ(s′)]

近年來，基于強化學習的路徑規劃日益成為國內外學者研究的熱點。M. J. Mataric[12]首次把強化學習引入到多機器人環境中。而基于強化學習的多機器人路徑規劃的優點主要體現在：無須建立精確的環境模型，簡化了智能體的編程；無須構建環境地圖；強化學習可以把路徑規劃、避碰、避障、協作等問題統一解決。

張芳等人[13]提出了基于再激勵協調避障路徑規劃方法，把再勵函數設計為基于行為分解的無模型非均勻結構，新的再勵函數結構使得學習速度得以提高且有較好的魯棒性。同時，證明了在路徑規劃中，機器人的趨向目標和避障行為密切相關，對反映各基本行為的再勵函數取加權和來表示總的再勵函數要優于取直接和的表示方式，也反映了再勵函數設計得合理與否及其確切程度將影響再勵學習的收斂速度。王醒策等人[14]在動態編隊的強化學習算法方面展開了研究。宋一然[15]則提出了分段再勵函數的強化學習方法進行路徑規劃。其缺點是學習次數較多、效率不高，當機器人數目增加時，它有可能面臨維數災難的困難。所以，基于強化學習的路徑規劃在多機器人環境下的學習將變得比較困難，需要對傳統的強化學習加以優化，如基于人工神經網絡的強化學習[16]等。

3)其他方法 除了以上國內外幾種比較常見且研究較多的方法外，還有唐振民等人[17]提出的基于動態規劃思想的多機器人路徑規劃，把運籌學中的動態規劃思想與Dijkstra算法引入到多機器人的路徑規劃中，用動態規劃的基本思想來解決圖論中的費用流問題和路徑規劃中的層級動態聯盟問題。其選擇距離鄰近法作為聯盟參考依據。一個機器人的鄰居是指在地理位置上分布在這個機器人周圍的其他機器人；與該機器人最近鄰的機器人為第一層鄰居，第一層鄰居的鄰居為該機器人的第二層鄰居， 依此類推。那么層級越高（即越近)的鄰居，它滿足協作要求的可能性越大。動態規劃算法實質上是一種以空間換時間的技術，它在實現的過程中，必須存儲產生過程中的各種狀態，其空間復雜度要大于其他算法，故動態規劃方法比較適合多機器人的全局路徑規劃。

孫茂相等人[18]提出了最優控制與智能決策相結合的多移動機器人路徑規劃方法。其首先構造一個以各機器人最優運動狀態數據庫為核心的實時專家系統， 在離線狀態下完成; 然后各機器人在此專家系統的支持下， 以最優規劃策略為基礎， 采用速度遷移算法， 自主決定其控制。該方法擁有較好的穩定性與復雜度。焦立男等人[19]提出的基于局部傳感和通信的多機器人運動規劃框架較好地解決了多機器人路徑規劃在局部在線規劃的系統框架問題。沈捷等人[20]提出了保持隊形的多移動機器人路徑規劃。以基于行為的導航算法為基礎，把機器人隊列的運動過程劃分為正常運動、避障和恢復隊形三個階段。在避障階段，引入虛擬機器人使隊形保持部分完整;當隊形被嚴重打亂時，規劃機器人的局部目標位姿使隊列快速恢復隊形。其算法重點為避障機器人進入避障狀態，暫時脫離隊列，并以虛擬機器人代替避障機器人。

2 多機器人避碰和避障

避障和避碰是多機器人路徑規劃研究中需要考慮的重點問題之一。避障和避碰主要討論的內容有防止碰撞；沖突消解、避免擁塞；如何避免死鎖。在路徑規劃中常見的多機器人避障方法[21]有主從控制法、動態優先法（建立在機器人之間的通信協商上）、交通規則法、速率調整法，以及障礙物膨脹法、基于人工勢場的方法等。

目前國內外對于多機器人避障展開的研究還不是很多，比較典型的有徐潼等人[22]以Th.Fraichard的思想為基礎，擴充并完善了路徑/速度分解方案來協調多機器人，設立集中管理agent進行整體規劃，為每個機器人規劃路徑；并根據優先級規則對運動特征進行分布式規劃以避免機器人間的沖突。周明等人[23]提出分布式智能避撞規劃系統，將原來比較復雜的大系統轉換為相對簡單的子系統問題，由各智能機器人依據任務要求和環境變化， 獨立調整自身運動狀態，完成任務的分布式智能決策體系結構。任炏等人[24]提出了基于過程獎賞和優先掃除的強化學習多機器人系統的沖突消解方法。該算法能夠顯著減少沖突，避免死鎖，提高了系統整體性能。歐錦軍等人[25]提出了通過調整機器人的運動速度實現多機器人避碰，將避碰問題轉換為高維線性空間的優化問題， 并進一步將其轉換為線性方程的求解。該方法的缺點是系統的復雜度較高、計算量太大。

人工勢場方法的特點是計算簡潔、實時性強、便于數學描述，且適合于多自由度機器人環境，但容易產生抖動和陷入局部極小。為了克服其缺點，景興建等人[26]提出了人工協調場的方法，在傳統排斥力場中增加一個協調力，并將吸引力、排斥力和協調力與局部環境下機器人的運動狀態和運動要求結合起來，有效地保證機器人的安全性，提高機器人在復雜動態環境下行為決策的準確性和魯棒性。

3 多機器人協作和協調機制

多機器人間的運動協調[27~31]是多機器人路徑規劃的關鍵，也是多機器人與單機器人路徑規劃相區別的根本所在。多機器人系統在復雜動態實時環境下，由于受到時間、資源及任務要求的約束，需要在有限時間、資源的情況下進行資源分配、任務調配、沖突解決等協調合作問題，而機器人間的協調與協作，能夠大大地提高整個系統的效率和魯棒性，成為系統完成控制或解決任務的關鍵。

目前已有的協調方式分為集中式、分布式和混合式三種。在集中式協調中，集中規劃器詳細地規劃出每個機器人的動作，通常的做法是將多個機器人看做一個多自由度的機器人進行規劃；而分布式協調規劃中，機器人之間進行合作，將一個任務分成多個子任務，根據各自的特點完成不同的子任務，從而共同完成總任務；混合式協調是集中式和分布式混合在一起的形式。

多機器人間典型的協調方法[32]有合同網協議[33]、黑板模型、結果共享的協同方法、市場機制。近年來強化學習在多機器人協作方面也得到很好的應用，陳雪江[32]在基于強化學習的多機器人協作方面展開了研究，提出了多智能體協作的兩層強化學習方法來求解在多智能體完全協作、有通信情況下的協作問題。其主要通過在單個智能體中構筑兩層強化學習單元來實現：第一層強化學習單元負責學習智能體的聯合任務協作策略；第二層強化學習單元負責學習在本智能體看來是最有效的行動策略。陳偉等人[34]提出基于多目標決策理論的多機器人協調方法；通過對環境的拓撲建模，從基于行為的機器人學角度出發，對任務進行分解并設計目標行為，以多目標行為決策理論作為決策支持，從而達到多機器人運動協調的目的。

4 多機器人路徑規劃方(算)法的判優準則

通常評價機器人路徑規劃方(算)法的標準文獻[35]有正確性、時間/空間復雜度、并行性、可靠性、擴展性、魯棒性和學習。而多機器人的路徑規劃除了以上一些衡量標準之外，還需要考慮整個系統的最優化以及機器人間的協調性。

1)正確性 是分析算法的最基本的原則之一。一般來說算法的正確性是指:在給定有效的輸入數據后，算法經過有窮時間的計算能給出正確的答案。但在多機器人路徑規劃算法中，正確性主要指:路徑規劃算法要生成多個機器人協調運動的無碰安全路徑;這條路徑是優化的。

2)安全性 一般指多機器人所生成的各路徑中節點與障礙物有一定的距離。但在實際的應用背景下，有人認為安全性可以從兩個方面來理解：a）狹義地講，它就是機器人在行走過程中所做的功。在一定的條件下，它與路徑長度準則是一致的。b）廣義地講，它是各種優化條件加權綜合而得到的結果。

3)復雜度 一個算法的復雜性高低體現在該算法所需要的計算機資源的多少上面。所需要的資源越多，該算法的復雜性越高；反之，所需要的資源越少，該算法的復雜性就越低。算法的復雜性包括時間復雜度和空間復雜度。

在多機器人的路徑規劃算法中，算法的復雜度分析顯得尤為重要。一般地，單機器人路徑規劃算法的時空復雜度已經頗高，它們的數量級至少是O(n2)；多機器人的路徑規劃算法不僅是m-O(n2)(即m個機器人路徑規劃簡單地疊加)，它們之間還存在著對運動空間競爭的沖突，面對不斷變化的沖突的協調需要花費大量的時間和空間。通常多機器人的路徑規劃算法與機器人的個數呈指數關系O(km×n2)（k為常數）。這對多機器人路徑規劃算法的時間/空間復雜度控制是一個很嚴峻的考驗。

4)并行性 算法的并行性從算法設計、編寫程序、編譯和運行等多個不同的層次來體現。路徑規劃過程需要大量的計算，當處理的環境比較復雜，機器人工作的環境過于緊湊，尤其是機器人數量很多時，算法的時間/空間復雜度勢必會成為算法效率的關鍵。因此，在算法設計和運行上的并行性是通常考慮的方法。對多個機器人的路徑規劃盡量采用分布式多進程的規劃機制，以實現每個機器人路徑規劃的并行性。

5)可靠性 把多個機器人及其工作環境看成是一個系統，多機器人處于它們各自的起始點時，稱該系統處于初始狀態；當它們處于各自的目標點時，稱該系統處于目標狀態。多機器人的路徑規劃就是在該系統的這兩個狀態間建立一串合理的狀態變遷。這一狀態變遷過程可能會歷經許多狀態，如果在狀態變遷過程中，路徑規劃算法控制不好各狀態間的轉移關系，就會導致系統紊亂，出現機器人間的碰撞、找不到路徑等惡性后果，使任務失敗。所以這就對算法的可靠性和完備性提出了挑戰。為了很好地克服這一困難，需要對系統的各種可能狀態建模，分析它們相互間的關系，建立有限狀態自動機模型或Petri網模型，并以此為指導，按照軟件工程的思想，構造恰當的算法輸入來對算法的可靠性進行檢驗。

6)可擴展性 在多機器人的路徑規劃算法中，可擴展性主要是指一種路徑規劃算法在邏輯上，或者說在實現上能否容易地從2D空間擴展到3D空間，從低自由度擴展到高自由度，從較少的機器人數到更多的機器人數。可擴展性在各種路徑規劃算法之間沒有一種量的比較標準，只能從實際的具體情況出發、從對環境描述的適宜程度出發、從算法解決這一問題的復雜度出發、從算法本身的自適應出發等來考慮。

7)魯棒性和學習 魯棒性對于多機器人系統非常重要。因為許多應用，如路徑規劃要求連續的作業、系統中的單個機器人出現故障或被破壞，要求機器人利用剩余的資源仍然能夠完成任務。學習是在線適應特定的任務。雖然通用的系統非常有用，但將它用于特定應用上時，通常需要調整一些參數。具有在線調整相關參數的能力是非常吸引人的，這在將體系結構轉移到其他應用時可以節省許多工作。尤其是多機器人系統中機器人的自身學習和相互間的學習能夠大大提高整個系統的效率和系統的穩定性。

8）最優化 對動態環境有優化反應。由于有些應用領域涉及的是動態的環境條件，具有根據條件優化系統的反應能力成為能否成功的關鍵。

5 結束語

綜上所述，國內外研究者在多機器人路徑規劃取得了一些成果，但是在協作、學習、通信機制等方面仍面臨很大的困難和不足。如何進一步提高機器人間的協調性，增強機器人自身以及相互間的學習以提高多機器人系統的效率和魯棒性都有待深入研究。近年來無線通信技術得到長足發展，但在目前的技術條件下，在多機器人系統中實現所有機器人之間的點對點實時通信還有較大困難，這也是大多數多機器人系統仍然采用集中通信方式的主要原因。因此，如何降低多機器人系統對通信速度的依賴程度也是一個非常重要的問題。

總之，多機器人路徑規劃設計和實現是一項極其復雜的系統工程，展望其能在結合計算智能方法，如差分進化、遺傳算法、粒子群算法、免疫算法、模糊邏輯算法、BP網絡、人工勢場的改進、模擬退火和環境建模方法等方面取得新的突破。

參考文獻：

［1］WEISS G.Multiagent systems:a modern approach to distributed modern approach to artificial intelligence[M].Cambridge， Massachusetts：MIT Press，1999：121-161.

[2]蔡自興，徐光祐.人工智能及其應用:研究生用書[M].3版.北京：清華大學出版社，2004：124-198.

[3]譚民，王碩，曹志強.多機器人系統[M].北京：清華大學出版社，2005：6-81.

[4]薄喜柱，洪炳熔.動態環境下多移動機器人路徑規劃的一種新方法[J].機器人，2001，23（5）：407-410.

[5]顧國昌，李亞波.基于總體勢減小的動態調度技術解決多機器人的路徑規劃[J].機器人，2001，23（2）：171-174.

[6]孫樹棟，林茂.基于遺傳算法的多移動機器人協調路徑規劃[J].自動化學報，2000，26（5）：672-676.

[7]周明，孫樹棟，彭炎午.基于遺傳算法的多機器人系統集中協調式路徑規劃[J].航空學報，2000，21（2）：146-149.

[8]CAI Zixing，PENG Zhihong.Cooperative coevolutionary adaptive genetic algorithm in path planning of cooperative multimobile robot systems[J].Journal of Intelligent and Robotic Systems:Theory and Applications，2002，33(1):61-71.

[9]朱慶保.全局未知環境下多機器人運動螞蟻導航算法[J].軟件學報，2006，17（9）：1890-1898.

[10]SANDHOLM T W，CRITES R H.Multiagent reinforcement learning in the iterated prisoner’s dilemma[J].BioSystems，1996，37(1):147-166.

[11]高陽，陳世福，陸鑫.強化學習研究綜述[J].自動化學報，2004，30（1）：

86-100.

[12]MATARIC M J.Interaction and intelligent behavior[D].Massachusetls:Department of Electrical Engineering and Computer Science，MIT，1994.

[13]張芳，顏國正，林良明.基于再勵學習的多移動機器人協調避障路徑規劃方法[J].計算機工程與應用，2003，39（3）：80-83.

[14]王醒策，張汝波，顧國昌.多機器人動態編隊的強化學習算法研究[J].計算機研究與發展，2003，40（10）：1444-1450.

[15]宋一然.基于強化學習的多機器人路徑規劃方法[J].莆田學院學報，2006，13（2）：38-41.

[16]韓學東，洪炳熔.基于人工神經網絡的多機器人協作學習研究[J].計算機工程與設計，2002，23（6）：1-3.

[17]唐振民，趙春霞，楊靜宇，等.基于動態規劃思想的多機器人路徑規劃[J].南京理工大學學報，2003，27（5）：610-615.

[18]孫茂相，周明，王艷紅，等.多移動機器人實時最優運動規劃[J].控制與決策，1998，

13（2）：125-130.

[19]焦立男，唐振民.基于局部傳感和通訊的多機器人運動規劃框架[J].計算機工程與應用，2007，43(17)：89-93.

[20]沈捷，費樹岷，鄭波.多移動機器人保持隊形路徑規劃[J].東南大學學報，2005，35(3):391-395.

[21]MANSOR M A，MORRIS A S.Path planning in unknown environment with obstacles using virtual window[J].Journal of Intelligent and Robotic Systems，1999，24(3):235-251.

[22]徐潼，唐振民.多機器人系統中的動態避碰規劃[J].計算機工程，2003，29(17):

79-81，104.

[23]周明，孫茂相，尹朝萬，等.多移動機器人分布式智能避撞規劃系統[J].機器人，1999，21（2）：139-143.

[24]任炏，陳宗海.基于強化學習算法的多機器人系統的沖突消解的方法[J].控制與決策，2006，21(4):430-434，439.

[25]歐錦軍，朱楓.一種多移動機器人避碰規劃方法[J].機器人，2000，22(6):474-481.

[26]景興建，王越超，談大龍.基于人工協調場的多移動機器人實時協調避碰規劃[J].控制理論與應用，2004，21(5):757-764.

[27]PANAIT L，LUKE S.Cooperative multiagent learning:the state of the art[J].Autonomous Agents and MultiAgent Systems，2005，11(3):387-434.

[28]TZAFESTAS C S，PROKOPIOU P A，TZAFESTAS S G.Path planning and control of a cooperative three robot system manipulating large objects[J].Journal of Intelligent and Robotic Systems，1998，22(2):99-116.

[29]薛宏濤，葉媛媛，沈林成，等.多智能體系統體系結構及協調機制研究綜述[J].機器人，2001，23（1）：85-90.

[30]周風余，李貽斌，宋銳，等.基于混合式多智能體系統的協作多機器人系統研究[J].山東大學學報:工學版，2005，35(1):82-87.

[31]夏冰，張佐，張毅，等.基于多智能體系統的動態路徑選擇算法研究[J].公路交通科技，2003，20（1）：93-96.

[32]陳雪江.基于強化學習的多機器人協作機制研究[D].杭州：浙江工業大學，2004.

篇（5）

我國目前白車身焊接機器人焊接路徑規劃方面仍處于落后水平，相關路徑規劃也極為不完善，機器人工作的過程中經常出現作業順序不合理的狀況，導致生產周期增長，影響整個焊接線路的發展。所以如何制定出一條合理的路徑規劃是當前首要目標，本文立足實際就針對這個問題提出一些有效性策略。

一、路徑規劃的意義

白車身焊接機器人焊接中制定出一條合理的路徑規劃可以有效縮短機器人生產時間，進而縮短整個工期，提高整個生產效率，某種程度上降低了生產成本。另一方面，白車身焊接機器人焊接路徑規劃具有一定的典型性，在自動駕駛、服務機器人、挖掘機器人等路徑規劃研究方面具有重要的借鑒意義，具有較高的社會價值和經濟價值。

二、白車身焊接機器人焊接路徑規劃

（一）路徑規劃的基本任務

現代化工業生產的主要目標是為了獲得較高的制造質量、取得較高的生產率，而付出較低的生產成本，這是現代企業提高自身競爭力的重要手段，也是路徑規劃中的主要任務之一，而在路徑規劃的過程中要想保證焊接質量主要取決于以下兩點：

第一，最大程度的使用機器人工位。使用機器人工位能夠有效降低工人的勞動強度，減少人為錯誤幾率，提高焊接的準確性，保證焊接的順利進行，從而保證焊接的穩定性。

第二，要完成所有的焊接點，保證焊接的工藝參數。

要想實現較低的制造成本就是最大化的利用現有資源，提高機器人的工作效率，縮短機器人工位的生產周期，減少機器人的使用數量。路徑規劃的重要方向就是提高生產率，保證生產環節的順利進行，縮短生產周期，提高生產率。

（二）路徑規劃

白車身焊接機器人焊接路徑規劃主要有兩個分支，一是改變工藝參數，使用新的工藝方法和輔助設備。二是要提高分配的合理性、提高焊接順序的合理性，提高合理性的目標是為了減少機器人工位的生產周期。第二個分支實現的途徑主要是通過提高機器人焊接路徑的合理性，從而提高單個機器人的生產效率，最終縮短整個生產周期。

（三）遺傳算法

遺傳算法是進化算法中產生最早、應用最廣泛的一種基本算法，在工程技術和經濟管理領域都有廣泛的應用。遺傳算法有群體搜索和遺傳算子兩個基本特征，所謂的群體搜索打破了領域的限制，使信息可以廣泛分布于整個空間。而遺傳算子就是使染色體進行隨機操作，以降低人機交互的依賴。兩個特征保證了遺傳算法具有最優的搜索能力、最簡明的操作能力以及信息處理的隱秘能力。

白車身焊接路徑規劃主要問題如下：

第一，白車身中所需要焊接的焊接點眾多。

第二，在生產的過程中常常追求沒有意義的高精度。

第三，在解答相關問題時需要運用數學方法。

第四，因為方案最終應用于企業，所以數學方法最好要簡潔明了，便于學習。

綜上，在路徑研究時需要運用遺傳算法，主要優勢在于：

第一，遺傳算法的計算步驟比較簡單明了，在實際操作時便于學習和使用。在計算時大大減少了計算量，從而節約時間。

第二，能夠在很大程度上優化焊接作業順序，減輕焊接的工作量。

第三，減少定量分析與定性分析的工作量。

第四，能夠很好的掌控全局，在全局中找到最優解。

三、路徑規劃的仿真

（一）仿真系統的各要素

路徑仿真系統一般要具有以下幾個基本要素：

第一，對仿真問題的描述。模型和仿真運行控制共同組成了一個仿真系統，而一個特定的模型又是由一個參數和一組參數值構成。例如白車身點焊機器人焊接路徑的參數模型一般包括家具模型、機器人模型、側圍模型，在這基礎之上還加入了具體的參數值，就形成了特定的模型。

第二，行為產生器。模型確定以后就要對模型進行試驗，這是一套試驗的軟件，行為產生器可以生成一組根據時間變化的數據，這類數據是仿真的物資基礎。

第三，模型行為及對行為的處理。

模型行為可以大致分為三種：軌跡行為、結構行為以及點行為。

仿真系統中都要獲取軌跡行為，這些行為的獲取主要是根據時間的推移而產生的。

（二）仿真軟件的選擇

一個完善的機器人仿真系統可以依據機器人的運動學、動力學、行為軌跡等多項內容進行仿真計算，并可以根據機器人的實際操作內容進行仿真操作過程，并不依賴于真正的機器人。但目前最主要的工作是對機器人的路徑規劃做一個仿真方案，而不是設計出一個機器人的仿真系統。在進行機器人路徑規劃時需要一定的條件，在現實生活中可以有多個選擇，最好的選擇就是使用一些類似CAR這種專業軟件，如果條件不允許可以選擇VC++或者使用CATIA等軟件進行仿真。VC++自主編寫的優點在于針對性比較強，在做路徑時可以考慮多方面因素，然而缺點是不能建立詳細的三維模型，在實際操作時不能全方面的展現白車身焊接工位情況，且工作量較大。CATIA與VC++相比最大的優勢就是可以建立詳細的三維模型，能夠全方位展現工位情況，仿真軌跡最為真實，在仿真過程中還可以檢查是否干涉。而缺點也是比較明顯的，在仿真的過程中不能將動力學和控制算法考慮在內。

四、小結

白車身主要是以鋼結構為主的支架，是汽車中重要組成部分。而車身制造是整個環節中比較復雜又極為重要的一環，影響整個汽車的質量。我國研究白車身焊接機器人焊接路徑仍處于落后階段，為了提高綜合競爭力需要加大技術投資，提高我國白車身制造綜合競爭。

參考文獻：

篇（6）

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

An Improved RRT Algorithm of Local Path Planning for Vehicle Collision Avoidance

SONG Xiaolin，ZHOU Nan，HUANG Zhengyu，CAO Haotian

（Stake Key Laboratory of Advanced Design and Manufacturing for Vehicle Body， Hunan University，Changsha 410082，China）

Abstract：The original Rapidly-exploring Random Trees（RRT） algorithm has a rapid exploring-speed and short required time in path planning though it has large randomness and lacks of constraints. Thus， an improved RRT was proposed where the expected paths were built in both straight and curved roads. The random points were accorded with normal distribution around the expected paths. Heuristic search method that led the random points to the goal with a certain probability was also used for improvement. Compared with the original RRT algorithm， it performs quite well in both time-efficient and path quality in the simulation. Meanwhile， the effectiveness of the improved RRT algorithm was verified in Prescan. The path can be followed well and the secure lateral acceleration was satisfied. In conclusion， the improved RRT is effective in the path planning for vehicle collision avoidance.

Key words： rapidly-exploring random trees； vehicle path planning； Gauss distribution； path following

近年來隨著汽車向智能化的不斷發展，無人駕駛汽車技術引得越來越多人開始關注.路徑規劃作為其中一項關鍵技術，許多學者開展了有益的探索，并取得了一些研究成果.比如A*算法[1]、D*算法[2]等啟發式搜索算法，在復雜環境下有著很好的規劃速度，但是路徑并不理想；人工勢場法[3]是一種虛擬力算法，其優點是規劃的路徑平滑，但是容易陷入局部最優解；人工勢場法與彈性繩模型結合[4-6]在車輛局部路徑規劃時有理想的路徑，但由于模型比較復雜，搜索效率低；此外蟻群算法、遺傳算法、神經網絡算法、水滴算法等智能仿生算法[7-10]，在理復雜動態環境信息時有較好表現，但由于需迭代計算，時效性不夠好.

快速搜索隨機樹算法（RRT）[11]由Lavalle于1998年提出，是一種基于樹結構的典型算法，在移動機器人路徑規劃中有著較早應用.由于算法在進行路徑規劃時是隨機采樣，不需要預處理，因此有著很快的搜索速度.路徑點之間可以經過運動學、動力學仿真生成可執行曲線，因此該方法可用于解決含有運動學約束的路徑規劃問題.但RRT算法存在一些不足：1）重現性差，對同一環境進行多次路徑規劃結果不同；2）尋找最優或者次優路徑能力較差；3）隨機采樣點在整個可行域內隨機尋點的搜索方式，存在很多不必要的運算，影響算法速度.

隨著RRT算法的應用和改進，一些學者也提出了不同的方法.偏向RRT[12]以及雙向RRT[13]的提出使得算法的搜索效率得到了提高；DRRT[14]與MP-RRT[15]原算法在搜索路徑的穩定性上做出了改進.但上述改進之后的結果并不適用于汽車行駛路徑.針對以上不足，本文將建立道路模型，考慮路徑約束，改進RRT算法，使其規劃出的路徑能夠適用于汽車運動.

1 道路環境建模

在環境已知的情況下，建立道路環境模型.直道環境模型根據道路長度以及車道寬即可得到，彎道環境模型如圖1所示，位于道路上的慣性坐標系的原點選取在道路中心線上，道路寬度為W，規劃起始點即主車位置A，目標點C，障礙車位置為B.高速路直線之間的緩和曲線通常采用回旋線來實現平滑過渡，回旋線的特征是其曲率變化為常數.假定長度為l的回旋線線段起始曲率為C1，終止曲率為Cf，變化常數為C2，則有C（l）=C1+C2×l成立，C2=（Cf-C1）/l.回旋線常采用多項式逼近的形式表示：

式中：R0為道路中心線初始橫向偏移；C0為初始的方向角.根據圖1，結合邊界條件R（0）=0，R′（0）=0可以將R0和C0消除掉.

為了保持車道寬度一致，彎道的左右邊界是通過中心線上點向著其法線方向上下平移單個車道寬度來得到.在道路坐標系下中心線上的點可由式（2）表示.

中心線上一點的切向量和法向量則可以表示成：

因此道路左右界則可以由（4）來表示

2 RRT算法原理

基本的RRT算法如圖2所示，RRT算法以給定的起始點為隨機樹根節點，根據當前環境快速有效地搜索可行域空間，通過隨機采樣點，將搜索導向空白區域并增加隨機樹的葉節點直至目標點區域，從而生成從起始點到目標點的路徑.

算法的一般步驟如下：

1）首先通過environment（）函數建立環境數據模型，初始化各項參數；

2） 通過while循環來判斷樹節點是否達到目標點goal范圍內，若沒有，則開始擴展點.先生成隨機采樣點Prand，在樹節點上通過函數Nearest（）選擇距離Prand最近的樹節點作為擴展節點Pnear，通過擴展函數New得到新的樹節點Tnew，并將其添加到隨機樹上，直到循環終止.

3）通過getpath（）函數來得到生成的路徑path.

原算法主體程序如下：

如圖3所示，傳統的RRT算法應用到車輛路徑規劃中存在以下問題：

1）由于隨機采樣點隨機性大，導致搜索空間中有過多的冗余搜索，表現為搜索樹布滿了道路環境空間；

2）搜索出來的路徑曲率變化過大，甚至出現小范圍內直角變化，這樣的路徑并不能滿足汽車行駛的正常狀態；

3）路徑在靠近障礙時才開始避障，對于運動中的汽車會造成失穩或者與障礙物發生碰撞.

道路長度/m

3 RRT算法的改進

3.1 期望路徑模型

針對原RRT算法表現出來的問題，提出了一種隨機采樣點高斯分布的改進RRT算法.根據汽車行駛環境不同，設計了兩種期望路徑模型.

3.1.1 直道模型

駕駛經驗豐富的駕駛員期望的避障路徑模型如圖4（a）所示.期望路徑以函數Epz表示，其中各段均為直線段，start為起始點，goal為目標點.

提前避障在車輛避障路徑規劃中是必要的，故在模型中需要添加提前避障距離S，并根據車速調整大小.設V為當前車速，tc為換道時間，通常完成換道時間tc為1～2 s，ΔS為自定義安全提前量.

對于車速為V的汽車其剎車距離

則提前避障距離

圖4（a）中fz2表示提前避障區域，區間長度為S，fz4區間長度也為S.

期望路徑只是粗略的路徑模型，在此基礎上進行平滑得出的路徑并不能滿足汽車安全穩定行駛的要求.因此采用RRT算法進行路徑尋優搜索.為了使隨機采樣點分布在期望路徑周圍，利用高斯分布函數生成的點集中在其均值周圍的特點，結合期望路徑函數則可以實現這一目的.在道路坐標系下隨機采樣點的高斯分布概率函數為：

令μ=Epz（x），則可以得到如圖4（b）所示的隨機采樣點分布趨勢圖.

道路長度/m（a）期望路徑模型

道路長度/m（b）隨機采樣點高斯分布

σ的大小決定了隨機點在Epz（x）周圍的集中程度，σ越小越靠近Epz（x）.特別地，對于fz2與fz4周圍的隨機采樣點，如圖4（a）以fz2為例，通過相應水平范圍的隨機點高斯分布旋轉處理得到，即對

旋轉角度：

3.1.2 彎道模型

將彎道分為多段，采用直線代替彎道曲線的形式來完成期望路徑模型的建立.如圖5（a）彎道的期望路徑以函數Epw來表示.

隨機采樣點在fw各段函數區間的分布同直道的處理相同，從而可以得到如圖5（b）所示的分布趨勢圖.

3.2 約束條件

要使一條規劃出來的路徑有效地應用于汽車運動，即路徑可跟蹤，則規劃路徑時必須滿足道路環境約束.首先，隨機樹節點的生成要滿足道路環境約束，設Bleft，Bright分別為道路的左右邊界，則樹節點位置坐標要滿足：

考慮到汽車是具有幾何形體的，設其車寬為D，則上述y方向的約束變為：

假定汽車質心沿著規劃的路徑運動，為了保證行駛過程中的穩定性，規劃出的路徑的曲率變化不能過大.若在實際情況下前輪最大轉角為θmax，則路徑中子節點與其父節點的連線和父節點與其父節點的連線之間的夾角β必須滿足β

其中：K1為直線TaTb的斜率；K2為TcTb的斜率.βT為夾角限制值.

為了保證所擴展的點不與障礙車有交集，即樹節點不與障礙車碰撞的要求，采用安全橢圓包絡障礙車，并適當放大安全橢圓以保證避障要求.若新節點與其父節點的連線不與安全橢圓相交，則所擴展的新點滿足避障要求.取連線上的五等分點Pi（x，y），則約束方程表現為：

其中（xob，yob）為障礙車的位置，半車長a=2 m；半車寬b=1 m；s為安全橢圓放大系數，當s=2時，安全橢圓正好包絡矩形的障礙車，因此從安全避障考慮，s≥2.

3.3 啟發式搜索

原算法在擴展隨機樹時，由于缺乏導向機制，算法的收斂速度在一定程度上受到了影響，為了提高算法計算速度，引入啟發式機制來對隨機采樣點以及隨機樹節點的選擇進行處理.采樣點Prand在隨機生成過程中會以一定概率ρ0選擇目標點，從而將隨機樹節點向目標點引導，通常ρ0=0.1.

其中，GaussRand（）為隨機采樣點生成函數.

另外，在選擇Pnear時不再單獨以距離Prand最近作為選擇標準，而是以隨機樹節點的擇優系數Ch來決定，Pnear確定為Ch值最小所對應的樹節點.

其中ωi，ωj為權重系數，且ωi+ωj=1；Dpr為樹節點到Prand的距離，Dg為樹節點到目標點goal的距離.當ωj>ωi時，選擇出的Pnear具有向目說憧拷的趨勢.通過以上啟發式的處理，使得算法更快地收斂，減少計算時間.

3.4 平滑處理

RRT算法規劃出來的路徑通常會存在小范圍內的曲折現象，路徑并不連續.為了使得路徑能夠滿足汽車在運動時的穩定性和安全性要求，需要對規劃出來的路徑進行光滑處理.B樣條在處理路徑光滑時能夠不改變整個路徑形狀而進行局部調整[16]，利用B樣條這一特性，來對算法所規劃出來的路徑進行插值擬合，從而達到光滑路徑的目的，通常所采用的為3次B樣條曲線.

當有m+1個控制頂點Pi（i=0，1，…，m）時，3次B樣條曲線表示為：

3.5 算法流程

隨機樹節點的擴展受到隨機采樣點的影響，通過以上方式的處理，隨機采樣點不再是在可行域內隨機分布，而是具有一定的趨向性.這樣使得隨機樹節點的分布也具有趨向性，算法的隨機性得到了改善，所規劃出來的路徑質量得到提高.主體程序如下：

算法的實現過程如下：

1）初始化階段，首先通過environment（）函數建立道路環境模型，根據現有的環境模型，以expect（）函數建立期望路徑模型.

2） 路徑求解階段，進入while循環來判斷樹節點是否達到目標點goal范圍內，若沒有，則開始擴展點.隨機采樣點Prand通過Pick（）函數在goal和GaussRand（）函數所生成的點之間進行概率選擇；根據當前Prand計算樹節點的擇優系數Ch，并由Fitbest（）函數得出Pnear；通過函數New在Pnear的基礎上擴展出新節點Tnew，當新節點滿足約束函數constraint（）時，新節點則添加到整個隨機樹Tree上，否則，返回循環重新尋點直到其終止.

3）路徑處理階段，getPath（）函數從所得的Tree中獲取最短路徑，最后通過函數smoothing（）對所得路徑path進行光滑處理，得到一條平緩的路徑.

4 仿真實驗驗證

改進的RRT在應用于信息多變的不確定環境時會存在建模困難的缺陷，本文主要對確定車道環境下的改進RRT開展研究.由于條件有限，不能在實際車輛中進行試驗驗證.而Prescan軟件能夠對實際場景進行建模，并且有根據實車建立的車輛模型數據庫，能夠模擬實際車輛行駛過程.因此，為驗證改進RRT算法的有效性，在Prescan軟件平臺中搭建直道和彎道場景如圖6所示，仿真實驗硬件平臺Win10+Core-i7@3.6Hz+ARM@8G.仿真參數如表1～表3所示.

4.1 規劃時間的影響參數分析

影響算法計算效率的重要參數主要包括搜索步長ΔL、約束夾角βT.步長越小，為了搜索到目標點所需要的節點數目也就越多，計算時間越長；約束夾角βT越小，規劃路徑也越平緩，但計算時間也越長.改變步長以及約束夾角并進行大量仿真實驗，統計表明：在ΔL=3，βT=15°時，改進RRT算法在規劃時間以及路徑效果上的綜合表現較好.圖7為ΔL=3時，不同角度下計算時間的統計，以20次計算時間平均值做一次統計.

4.2 規劃路徑對比

為說明改進RRT算法的效果，在直道場景中，采用了其余2種規劃算法來進行對比.一種是蟻群算法[7]，另一種是彈性繩算法[5].直道仿真對比結果如圖8所示，改進前后的算法規劃效果在彎道中的對比如圖9所示，路徑效果參數對比如表4所示.由圖和表的結果對比可知：

1）相對于蟻群算法和原RRT算法，改進RRT算法與彈性繩算法規劃的路徑都更為平滑，不存在頻繁的大曲率變化，且路徑較短.

2）從直道的規劃時間上看，傳統的蟻群算法用時最長，而彈性繩算法平均計算時間為1.42 s.改進后的RRT算法平均計算時間0.25 s，相對于原RRT計算時間略有增加，這是由于增加了模型處理過程以及各約束條件所導致的.但與其余2種算法相比，改進RRT算法依然保持其在計算時間上的優勢.

3） 原RRT算法在靠近障礙時才開始避障，改進RRT算法能夠實現提前避障，并且根據車速不同自動調節避障提前量，這對安全行駛很重要.

4.3 路徑跟隨驗證

對一條規劃出來的路徑，需要驗證其有效性，即路徑的跟隨性，本文采用路徑跟隨時主車的側向加速度曲線監測路徑的穩定性，跟隨速度20 m/s.直道和彎道仿真結果分別如圖10、圖11所示.

由圖10（a）（b）可知，直道跟隨路徑基本和目標路徑一致，跟隨誤差在0.2 m以內，誤差較小；車輛保持穩定行駛時的最大側向加速度由地面附著力決定，通常為0.8g.由圖10（c）可知，跟隨時的側向加速度在0.4g以內，說明整個過程中都能夠保證主車按照路徑行駛時的穩定性.彎道仿真結果如圖11所示，跟隨誤差都在0.1 m以內，跟隨效果好；側向加速度都在0.5g范圍內，滿足穩定性要求.

5 結 論

本文在將RRT算法應用到汽車避障局部路徑規劃時，針對原算法在隨機性以及路徑曲率變化上的不足，建立了直道和彎道的期望路徑模型，使隨機采樣點在期望路徑模型周圍近似呈高斯分布，采用啟發式搜索方式使采樣點和隨機樹節點向目標點靠近，從而降低算法的隨機性；并且在路徑規劃時加入約束，使得所規劃出的路徑更為合理.仿真實驗結果表明：改進RRT算法不僅規劃出的路徑質量高、實時好、跟隨性強，而且車輛的穩定性也滿足要求.因此，改進RRT算法可以應用于實時汽車路徑規劃.

參考文獻

[1] YAO J， LIN C， XIE X， et al. Path planning for virtual human motion using improved A* algorithm[C]//Proceedings of the Conference on Information Technology： New Generations （ITNG）.Washington， DC： IEEE Computer Society， 2010： 1154-1158.

[2] DIJKSTRA E W. A note on two problems in connexion with graphs[J]. Numerische Mathematik， 1959， 1（1）： 269-271.

[3] KHATIB O. Real-time obstacle avoidance for manipulators and mobile robots[J]. The International Journal of Robotics Research， 1986， 5（1）： 90-98.

[4] SONG X， CAO H， HUANG J. Vehicle path planning in various driving situations based on the elastic band theory for highway collision avoidance[J]. Proceedings of the Institution of Mechanical Engineers， Part D： Journal of Automobile Engineering， 2013， 227（12）： 1706-1722.

[5] SONG X， CAO H， HUANG J. Influencing factors research on vehicle path planning based on elastic bands for collision avoidance[J]. SAE International Journal of Passenger Cars-Electronic and Electrical Systems， 2012， 5（2）：625-637.

[6] 肖浩， 宋曉琳， 曹昊天. 基于危險斥力場的自動駕駛汽車主動避撞局部路徑規劃[J]. 工程設計學報， 2012，19（5）： 379-384.

XIAO Hao， SONG Xiaolin， CAO Haotian.Local path planning for autonomous vehicle collison avoidance based on dangerous repellant fields[J]. Chinese Journal of Engineering Design，2012， 19（5）： 379-384.（In Chinese）

[7] 康冰， 王曦輝， 劉富. 基于改進蟻群算法的搜索機器人路徑規劃[J]. 吉林大學學報：工學版， 2014， 44（4）：1062-1068.

KANG Bing， WANG Xihui， LIU Fu. Path planning of searching robot based on improved ant colony algorithm[J]. Journal of Jilin University：Engineering and Technology Edition， 2014， 44（4）： 1062-1068.（In Chinese）

[8] HU Y， YANG S X. A knowledge based genetic algorithm for path planning of a mobile robot[C]//Proceedings of the Conference on Robotics and Automation. Washington，DC： IEEE Computer Society， 2004： 4350-4355.

[9] 吳乙萬，黃智.基于動態虛擬障礙物的智能車輛局部路徑規劃方法[J].湖南大學學報：自然科學，2013，40（1）：33-37.

WU Yiwan， HUANG Zhi. Dynamic virtual obstacle based local path planning for intelligent vehicle[J]. Journal of Hunan University： Natural Sciences， 2013，40（1）：33-37.（In Chinese）

[10]SHAH-HOSSEINI H. Problem solving by intelligent water drops[C]// Proceedings of the Conference on Evolutionary Computation.Washington，DC： IEEE Computer Society， 2007： 3226-3231.

[11]LAVALLE S M.Rapidly-exploring random trees： A new tool for path planning[J]. Algorithmic & Computational Robotics New Directions， 1998：293-308.

[12]LAVALLE S M， KUFFNER J J. Rapidly-exploring random trees： progress and prospects[J]. Algorithmic & Computational Robotics New Directions， 2000：293-308.

[13]KUFFNER J J， LAVALLE S M. RRT-connect： An efficient approach to single-query path planning[C]// Proceedings of International Conference on Robotics and Automation.Washington，DC： IEEE Computer Society， 2003：995-1001.

[14]FERGUSON D， KALRA N， STENTZ A. Replanning with rrts [C]//Proceedings of International Conference on Robotics and Automation.Washington，DC： IEEE Computer Society， 2006： 1243-1248.

篇（7）

中圖分類號：P208 文獻標識碼：A 文章編號：1007-9599 （2013） 02-0000-02

1 概述

物流產業隨著基礎工業的不斷壯大及消費市場的蓬勃發展而快速興起。而中國的物流企業不論從技術裝備還是管理水平與國外仍存在較大差距，概括起來有一下幾個方面：對現代物流理念上的差距，企業規模方面的差距，社會需求方面的差距，管理體制方面的差距，專業手段方面的差距，專門人才方面的差距。據對美國物流業的統計與分析，以運輸為主的物流企業年平均資產回報率為8.3%（irr），倉儲為7.1%，綜合服務為14.8%。在中國大部分物流企業的年平均資產回報率僅為1%。這一數據，不僅說明了中國物流效率低下，同時企業仍有很大的空間通過物流來降低成本。

如何應用先進的技術手段來提高物流業的經營效率，及時高效、經濟地將商品配送到客戶手中，成了大家探討的話題，這也就是現代物流領域中備受關注的車輛路徑問題（vehicle routing problem，VRP）。物流配送路徑規劃的優化與否，對物流配送效率、費用和服務水平影響較大。而此類問題都涉及如何處理大量的空間數據與屬性數據而縮短物流時間、降低成本的問題。

地理信息系統作為不僅具有對空間和屬性數據采集、處理和顯示功能，而且可為系統用戶進行預測，監測、規劃管理和決策提供科學依據。它可以有效的結合最優路徑、各種VRP模型、車輛行駛成本等要素，在可視化分析以及物流規劃路徑分析等方面具有不可替代的作用。GIS技術與現代物流工程技術相結合，給現代物流行業提供了巨大的發展空間，為物流企業完善管理手段、減低管理成本、提高經濟效益、最終提升核心競爭力提供了機遇。

2 技術實現途徑研究

物流配送車輛路線優化問題由Dautzig和Ramser于1959年首次提出，該問題一般定義為：對一系列給定的顧客（取貨點或送貨點），確定適當的配送車輛行駛路線，使其從配送中心出發，有序地通過它們，最后返回配送中心。并在滿足一定的約束條件下（如車輛容量限制、顧客需求量、交發貨時間等），達到一定的目標（如路程最短、費用最少等）。配送中心的每次配送活動通常面對多個非固定用戶，并且這些用戶分布在不同的地點，同時他們的配送時間和配送數量也都不盡相同。如果配送中心不合理規劃車輛、貨物的運輸路線，常會影響了配送服務水平，還會造成運輸成本的上升，因此對車輛及貨物的配送路線進行規劃是配送中心的一項重要工作。

車輛路線優化問題一般可根據空間特性和時間特性分為車輛路線規劃問題和車輛調度問題。當不考慮時間要求，僅根據空間位置安排車輛的線路時稱為車輛線路或車輛路徑規劃問題（VRP）。當考慮時間要求安排運輸線路時稱為車輛調度問題（VSP）。本文不考慮時間要求，主要針對第一類VRP問題，提出相應的技術實現方案研究。

典型的VRP具有以下特征：（1）所有車輛從倉庫出發，并最終回到倉庫；（2）所有車輛必須滿足一定的約束；（3）多輛車負責多個客戶；（4）每個客戶由一輛車訪問一次；（5）車輛的路線上可以取送貨。目前研究的車輛路線規劃的模型主要有兩類，一類為網絡圖模型，另一類為數學模型。由于VRP難以用精確算發求解，啟發式算法是求解車輛運輸問題的主要方法，多年來許多學者對車輛運輸問題進行了研究，提出了各種各樣的啟發式方法。

物流公司的業務一般具有配送范圍廣的特點，本文主要針對大范圍跨省配送的案例進行智能路徑規劃，因此影響因素較多，主要包括：（1）大范圍、跨省的配送交通網絡圖；（2）復雜的車輛運作規則，包括運行時間、運載能力、運行成本計算、駕駛員工作時間限制等；（3）復雜的道路選擇優先級；（4）復雜的運輸車輛優先級；（5）客戶訂單及運輸車輛數據；（6）取貨及分發過程；（7）繁雜的配送規則，如倉庫、貨物、客戶的時間等；（8）運輸車輛的重復利用，要求同一輛車在符合多個約束條件下盡可能多的參與到不同路線的配送中。

本文主要基于ArcObjects的網絡分析和地圖展示等組件進行二次開發，同時對其提供的車輛路徑規劃算法進行了拓展性研究。

3 功能模塊設計方案

3.1 軟件架構設計

系統建設遵循SOA架構，由數據資源層、組件層、服務層和表現層組成。數據資源層包括各種數據庫、關系型數據庫和空間數據庫引擎ArcSDE，實現對物流業務數據的存儲和管理；組件層包括接口協議、GIS組件、其他中間件；服務層實現計算功能，接受表現層的請求進行計算；表現層采用多種形式展現分析結果。

3.2 軟件功能設計

本系統是物流業務管理系統的一部分，主要提供歷史數據管理模塊、線路優化分析模塊、地圖操作模塊，同時提供與其他相關業務系統的擴展功能。

（1）線路優化分析模塊

線路優化分析模塊是系統的關鍵，提供兩種分析結果：一種是基于AO自帶的網絡分析模塊設計，計算分析結果；另一種是歷次根據具體路況等信息的實際調度結果。

實際調度結果來自車輛GPS監控數據，并將實際調度結果作為輸入，用來校正線路優化分析方法，最后生成最優路徑規劃。

（2）地圖展示模塊

地圖展示模塊，在配送交通網絡圖上展示道路基本信息、周邊環境、倉庫及客戶地點、車輛位置信息等。同時將各種車輛路徑規劃分析結果以地圖形式展示。基于ArcGIS提供的基礎地圖操作功能，實現地圖縮放、瀏覽、鷹眼、圖層控制、測量、選擇、標注、信息查詢等功能。

（3）歷史數據管理模塊

歷史數據管理主要存儲歷史客戶訂單數據、實時路況信息、歷史路徑規劃分析結果、實際運輸路徑等，可支持對歷史數據的查詢和修改。

（4）擴展功能模塊

提供與其他相關業務系統、車載GPS設備、車輛監控設備等的接口，便于系統的擴展。

3.4 數據庫設計

本系統中涉及的數據庫主要包括元數據庫、基礎地理空間數據庫、業務數據庫、分析模型數據庫、歷史數據庫等。

4 結束語

本文將物流車輛路徑規劃理論算法的研究與地理信息系統的網絡分析模塊相結合，經過二次開發，形成了用于實際的物流車輛路徑規劃信息系統。另外車輛路徑規劃設計約束較多，本文中不考慮時間要求，僅根據空間位置安排車輛的線路，同時不考慮裝箱問題。

車輛路徑規劃問題是現代物流業的熱點問題，但是基本停留在理論算法層面，隨著技術的不斷進步，必然出現考慮更多約束的先進算法，希望將這些算法真正與現代物流業結合，那將會是一個跨越式的進步。

篇（8）

DOI：10.16640/ki.37-1222/t.2016.21.135

0 前言

移動機器人的實現涉及自動控制、智能、機械等多種學科。它通常被應用在醫療領域、工業領域等方面。從整體角度來講，移動機器人的應用促進了生產效率的顯著提升。路徑規劃技術是移動機器人的關鍵技術之一，研究該技術具有一定的現實意義。

1 路徑規劃技術的作用

將路徑規劃技術應用在移動機器人中，能夠產生的作用主要包含以下幾種：

（1）運動方面。路徑規劃技術的主要作用是其能夠保證移動機器人完成從起點到終點的運動。（2）障礙物方面。設計移動機器人的最終目的是將其應用在實際環境中，在實際環境下，移動機器人的運行路線中可能存在一定數量的障礙物，為了保證最終目的地的順利達到，需要利用路徑規劃技術實現對障礙物的有效避開[1]。（3）運行軌跡方面。對于移動機器人而言，除了實現障礙物躲避、達到最終目的地這兩種作用之外，應用路徑規劃技術還可以產生一定的優化運行軌跡作用。在移動機器人的使用過程中，在路徑規劃技術的作用下，機器人可以完成對最佳運行路線的判斷，進而更好地完成相應任務。

2 移動機器人路徑規劃技術綜述

移動機器人的路徑規劃技術主要包含以下幾種：

2.1 局部路徑規劃方面

在局部路徑規劃方面，能夠被應用在移動機器人中的技術主要包含以下幾種：

（1）神經網絡路徑規劃技術。從本質上講，可以將移動機器人的路徑規劃看成是空間到行為空間感知過程的一種映射，因此，可以利用神經網絡的方式將其表現出來。就神經網絡路徑規劃技術而言，首先需要將相關傳感器數據當成網絡輸入，并將網絡輸出看成是某固定場合中期望運動方向角增量。在這種情況下，原始樣本集則可以用不同選定位置對應的數據代替。為了保證樣本集數據的有效性，需要將原始樣本集中的沖突樣本數據以及重復樣本數據剔除掉。對最終樣本集應用模糊規則，實現神經網絡的有效訓練。當典型樣本學習完成之后，移動機器人對規則的掌握水平發生了顯著提升，進而使得移動機器人在產生智能性能的基礎上，順利完成相應運動[2]。

（2）人工勢場路徑規劃技術。這種規劃技術是指，將移動機器人在實際環境中的運動過程當成其在虛擬人工受力場中的一種運動。在虛擬人工受力場中，目標終點會對移動機器人產生一定的引力，而該受力場中的障礙物則會對其產生一定的斥力。在某固定算法的作用下，這兩種不同的作用力會產生相應的勢，進而形成勢場。當移動機器人在該場中運動時，勢場中的抽象力會作用在移動機器人上，使得其完成對障礙物的有效避開。在人工勢場路徑規劃技術的實際應用過程中，由于結構簡單等因素的影響，移動機器人在到達終點之前可能會停留在局部最優點位置上。對此，需要從數學的角度出發，對勢場方程進行重新定義，通過這種方式排除勢場中的局部極值，繼而保證移動機器人運動的順利進行[3]。

（3）遺傳路徑規劃技術。這種路徑規劃技術建立在自然遺傳機制等理論的基礎上。這種技術通過變異、選擇以及交叉對控制機構的正確計算程序進行合理編制，進而實現數學方式基礎上生物進化過程的合理模擬。當移動機器人的適應度函數為正數時，允許適應度函數具有不連續或不可導特點。由于這種路徑規劃技術不涉及梯度信息，因此其能夠更好地解決移動機器人在實際運動過程中遇到的問題。遺傳路徑規劃技術的應用優勢在于，它能夠實現跟蹤與規劃的同時進行，因此，遺傳路徑規劃技術通常被應用在具有時變特點的未知環境中。

2.2 全局路徑規劃方面

在該方面，可以被應用在移動機器人中的技術主要包含以下幾種：

（1）柵格路徑規劃技術。這種技術是指，在將實際工作環境分成許多包含二值信息的網格單元的基礎上，應用優化算法完成最佳路徑的規劃搜索。在這種規劃技術中，其網格單元通常是由八叉樹或者四叉樹的方式表示出來。在該技術的應用中，柵格的作用是完成相關環境信息的記錄。如果柵格中某位置的累計值相對較低，代表移動機器人可以從該位置通過；如果柵格中某個位置的累計值相對較高，則表示該位置存在障礙物，此時，移動機器人需要利用優化算法將該障礙物避開[4]。

（2）可視圖路徑規劃技術。這種路徑規劃技術是指，將整個移動機器人看成一個點，然后分別將其與障礙物以及目標終點連接起來，上述連線要求為保證所連直線不會碰觸障礙物。當所有連線都連完之后，即完成了一整張可視圖。在該可視圖中，由于起點到目標終點之間的連線都不涉及障礙物，因此上述所有連線都屬于有效直線。在這種情況下，需要解決的問題主要是從這些連線中找出一條距離最短的連線。對此，需要應用優化算法將可視圖中距離較長的連線刪除，這種處理方式能夠有效提升移動機器人的搜索時間。

（3）拓撲路徑規劃技術。這種規劃技術是指，將移動機器人的移動范圍，即規劃區域分成多個具有拓撲特征的子空間，然后利用不同子空間之間的連通性完成拓撲網絡的構建。當該網絡構建完成后，直接從網絡中找出能夠使得機器人順利從起點移動到終點的拓撲路徑，將所得的拓撲路徑作為參考依據完成幾何路徑的計算。這種規劃技術的劣勢主要表現為其拓撲網絡的構建過程較為復雜。但這種規劃技術可以實現移動機器人搜索空間的有效縮小[5]。

3 結論

路徑規劃技術主要分為局部規劃和全局規劃兩方面。這兩方面分別包含人工勢場路徑規劃技術以及神經網絡路徑規劃技術等。應用這些規劃技術之后，移動機器人可以在避開障礙物的基礎上，順利完成起點到終點最優運行軌跡的運動。

參考文獻：

[1]朱大奇，顏明重.移動機器人路徑規劃技術綜述[J].控制與決策，2010（07）：961-967.

[2]張捍東，鄭睿，岑豫皖.移動機器人路徑規劃技術的現狀與展望[J].系統仿真學報，2005（02）：439-443.

[3]鮑慶勇，李舜酩，沈`，門秀花.自主移動機器人局部路徑規劃綜述[J].傳感器與微系統，2009（09）：1-4+11.

篇（9）

中圖分類號： TN911.1?34； TP312 文獻標識碼： A 文章編號： 1004?373X（2017）13?0181?03

Abstract： The path optimization is an important way to solve the traffic congestion and blocking. The traditional Dijkstra algorithm based on monophyletic shortest path can find the shortest path information from the starting point to other points， but its search time is long in the situation of various map obstacles. The A* algorithm with heuristic function in the field of artificial intelligence can select the optimum path by itself because of its memory function. With the increase of obstacle information and location information， the search efficiency of A* algorithm becomes higher. The A* algorithm and traditional Dijkstra algorithm were simulated and compared with experiments， and their search speed and search efficiency were compared. The simulation results show that the search effect of A* algorithm is more effective in the actual road network.

Keywords： shortest path； A* algorithm； Dijkstra algorithm； path optimization

最短路轎侍[1]是圖論中網絡分析的經典問題，近年來，隨著路徑搜索技術的不斷發展，已經涌現出很多成熟的路徑規劃算法，比如，基于圖論的Dijkstra算法[2?3]，以及關于人工智能領域的啟發式搜索算法和動態規劃算法等。A*啟發式搜索算法作為人工智能領域的重要組成部分，其針對網格數據有著更高的運算效率，而且利用啟發信息大幅度提高了搜索速度。這種全新的啟發式搜索算法[4]將會極大地改變現有的交通管理與服務模式。

1 A*算法原理

傳統的BFS算法的評估函數只考慮當前點與終點的距離，其策略是選擇與終點最近的點進行搜索。而Dijkstra算法則只關注當前點與起點的距離，選擇與起點最近的點開始搜索。A*算法[5]則是將二者結合起來，其啟發函數采用如下的計算公式：

式中：就是A*算法[5]對每個節點的評估函數[2]，其包含兩部分信息：是從起點到當前節點的實際代價，也就是從起點到當前節點的移動距離；相鄰的兩個點的移動距離是1，當前點距離起點越遠，這個值就越大。是從當前節點到終點的距離評估值，這是一個從當前節點到終點的移動距離的估計值。

A*算法的搜索過程需要兩個表：一個是OPEN表，存放當前已經被發現但是還沒有搜索過的節點；另一個是CLOSE表，存放已經搜索過的節點，具體的算法流程圖如圖1所示。

1.1 常用的距離評估函數

是A*算法的距離估計值[6]，A*算法需要一個距離評估函數來計算這個值。常用的距離評估函數有曼哈頓距離、歐式幾何平面距離和切比雪夫距離。在沒有障礙物的地圖上，這三種距離評估函數得到的效果是一樣的，但是在有障礙物的情況下，這三種距離評估函數的效果略有差異。當距離評估函數總是0時，A*算法就退化為Dijkstra算法[6]的效果。

1.1.1 曼哈頓距離

從數學上描述，曼哈頓距離是兩個點在各個坐標軸上的距離差值的總和，維幾何空間中曼哈頓距離的數學描述為：

對于二維平面上的兩個點和，其曼哈頓距離為：

即歐式幾何平面距離為在直角坐標系中兩個坐標軸上的投影距離和。

1.1.2 歐式幾何平面距離

歐式幾何平面距離（Euclidean distance）又稱為歐式距離或歐幾里得距離[7]，其數學定義是維空間中兩個點之間的真實距離（幾何距離），其數學符號可以描述為：

對于二維平面上的兩個點和其歐式幾何平面距離為：

即平面幾何中兩點之間的幾何距離。

1.1.3 切比雪夫距離

切比雪夫距離（Chebyshev Distance）是由一致范數（或稱上確界范數）衍生的度量，從數學角度上理解，對于兩個向量和其切比雪夫距離就是向量中各個分量的差的絕對值中最大的那一個，用數學符號可以描述為：

特別情況下，對于平面上的兩個點和，其切比雪夫距離為：

距離評估函數與A*算法的結果之間存在很微妙的關系，如果令始終為0，相當于一點啟發信息都沒有，則A*算法[5]退化為Dijkstra算法，這種情況即為最差的A*算法。的值越小，啟發信息越少，搜索范圍越大，速度越慢，但是越有希望得到最短路徑；的值越大，啟發信息越多，搜索的范圍越大，但是其有可能得不到真正的最短路徑。當大到一定程度時，公式中的就可以忽略不計，則A*算法演化成為BFS（廣度優先搜索算法），速度最快，但是不一定能夠得到最短路徑。所以通過調整和函數，可以使得A*算法[6]在速度與準確性之間獲得一個折中的效果。

1.2 A*算法的實現

A*算法實現的關鍵在于維護OPEN表和CLOSE表，其中對于OPEN表的主要操作就是查詢最小的節點以及刪除節點，因此考慮在算法實現時將OPEN表[7]設計為有序表。這樣在OPEN列表存儲數據時就可以自動將數據按照距離進行排序，這樣算法的執行效率比較高。A*算法的參數設置見表1，參數的迭代次數見圖2。

通過仿真實驗分析可以得出，A*算法[5]在有障礙物的情況下中和了BFS算法和Dijkstra算法的優點，能夠更有效地找到最終的最短路徑。

2 A*算法與Dijkstra算法效率的比較

Dijkstra算法是典型的單源最短路徑算法，其適用于求解沒有負權邊的帶權有向圖的單源最短路徑問題。由于Dijkstra算法[2?3]使用了廣度優先搜索的策略，它可以一次得到所有點的最短路徑。但是，它只是簡單地做廣度優先搜索而忽略了很多有用的信息。盲目搜索的效率很低，耗費很多時間和空間。考慮到實際地圖上面兩點之間存在位置和距離等信息，A*算法既能夠像Dijkstra算法那樣搜索到最短路徑，又能像BFS（廣度優先搜索算法）一樣使用啟發式函數進行啟發式搜索，是目前各種尋徑算法中最受歡迎的選擇。

將A*算法同Dijkstra算法[6]進行仿真比較，用于比較性能的主要指標有：時間復雜度分析；搜索到最短路徑的成功率分析。利用C++語言編制了三種算法的最短路徑搜索程序，運行在本地計算機上，并得出仿真模擬圖。

搜索效率的對比結果如表2所示。

由表2可以看出：當地圖節點的個數和弧的條數比較多時，A*算法[5]的搜索效率比Dijkstra算法快很多，當節點數不斷增多時，其搜索最短路徑的效率更高。在相同路網和位置信息的條件下進行仿真實驗的結果如圖3所示。

由圖3可以看出，兩種算法在相同障礙物條件下進行模擬仿真時，A*算法的搜索效率和時間復雜度要明顯優于Dijkstra算法，并對不同實驗場景下的效率進行對比，結果如圖4所示。

3 結 語

從Dijkstra算法和A*算法[2]的實現可知，Dijkstra算法的時間復雜度是其中是有向圖中頂點的個數。對于不含負權邊的有向圖來說，Dijkstra算法是目前最快單源最短路徑算法。A*算法兼有Dijkstra算法和廣度優先搜索算法的特點，在速度和準確性之間有很大的靈活性。除了調整和可以獲得不同的效果外，A*算法還有很多可以提高效率的改進方法。比如，在地圖比較大的情況下使用二叉堆來維護OPEN表以獲得更好的運算效率。

參考文獻

[1] WORBOYS M. Event?oriented approaches to geographic phenomena [J]. International journal of geographical information science， 2010， 19（1）： 1?28.

[2] NARAYANASAMY V. Game programming gems 6 [EB/OL]. [2015?05?12]. /data.

[3] DYBSAND E. A finite state machine class [J]. Game programming gems， 2000（1）： 237?248.

[4] 周郭許，唐西林.基于柵格模型的機器人路徑規劃快速算法[J].計算機工程與應用，2006，42（21）：197?199.

[5] 李大生，劉欣，吳明華，等.基于動力學約束的機器人無碰運動規劃[J].機器人，1990（5）：14?19.

[6] VIDALVERD? F， BARQUERO M J， CASTELLANOSRAMOS J， et al. A large area tactile sensor patch based on commercial force sensors [J]. Sensors， 2010， 11（5）： 5489?5507.

[7] 李得偉，韓寶明，韓宇.一種逆向改進型A*路徑搜索算法[J].系統仿真學報，2007，19（22）：5175?5177.

[8] 林丹.一種室內清潔機器人返回路徑規劃算法[J].重慶科技學院學報（自然科學版），2009，12（1）：110?113.

篇（10）

中圖分類號：TP393文獻標識碼：A文章編號：1009-3044(2011)21-5080-03

Research on Technology of Nodes Localization Based on Mobile Beacon for Wireless Sensor Network (WSN)

DING Hui, LI Bo-yong, AI Shu-liang

(Chenzhou Vocational and Technical College, Chenzhou 423000, China)

Abstract：Wireless sensor network has been used in many field. Nodes location of WSN has provided the basic information for many applications. Nodes location based on mobile beacon is one of the important research fields. Some basic principles and performance evaluating criterions of nodes localization based on mobile beacon for WSN are introduced. Some issues which need to be resolved in future are discussed.

Key words: wireless sensor network (WSN); mobile beacon; nodes localization

隨著傳感器技術、無線通信、微電子技術以及嵌入式計算等技術的發展，無線傳感器網絡(Wireless Sensor Network 簡稱WSN)得到了廣泛應用，成為當今活躍的研究領域。無線傳感器網絡是新型的傳感器網絡，同時也是一個多學科交叉的領域，與當今主流無線網絡技術一樣，均使用802.15.4的標準，由具有感知能力、通信能力和計算能力的大量微型傳感器節點組成，具有低成本、低功耗的優點和強大的數據獲取和處理能力。

在無線傳感器網絡的眾多應用中,如：國防軍事、環境監測、交通管理、醫療衛生、目標跟蹤、物流管理、入侵檢測、交通流量監控和勘測應用等領域, 監測到事件之后需要確定事件發生的位置，信息融合后得到的相關數據信息如果不包含事件位置信息將毫無意義，只有帶有標識位置信息的傳感數據才有實際的意義。傳感器節點自身的正確定位是提供事件位置信息的前提, 因此節點的精確定位基礎而關鍵[1] 。

1 無線傳感器網絡節點定位的分類及基本方法

節點定位是指確定傳感器節點的相對位置或絕對位置，節點所采集到的數據必須結合其在測量坐標系內的位置信息才有意義。人工部署傳感節點和為所有節點安裝GPS接收器都會受到成本、功耗、節點體積、擴展性等方面的限制，甚至在某些應用中是根本無法實現的。通常是為部分節點配置定位裝置（如GPS接收器）或事先標定其準確位置，這些節點稱為信標節點（也稱錨節點），再利用信標節點的相關信息采用一定的機制與算法實現無線傳感器網絡節點的自身定位。目前人們提出了兩類節點定位算法[2]：基于測量距離的定位算法與測量距離無關的定位算法。基于距離的定位方法首先使用測距技術測量相鄰節點間的實際距離或方位，然后使用三邊測量法、三角測量法、最小二乘估計法等方法進行定位。與測量距離無關的定位算法主要包括：APIT、質心算法、DV-Hop、Amorphous等。

1.1 基于無線傳感器網絡自身定位系統的分類[1,3-5]

1) 絕對定位與相對定位。絕對定位與物理定位類似，定位結果是一個坐標位置，如經緯度。而相對定位通常是以傳感區域某點為參考，建立整個網絡的相對坐標系統。

2) 物理定位與符號定位。經緯度就是物理位置；而某個節點在某街道的某門牌的建筑物內就是符號位置。一定條件下，物理定位和符號定位可以相互轉換。與物理定位相比，符號定位在一些特定的應用場合更加便于使用。

3) 集中式計算與分布式計算定位。集中式計算是指把所需信息傳送到某個中心節點，并在那里進行節點定位計算的方式；分布式計算是指依賴節點間的信息交換和協調，由節點自行計算的定位方式。

4) 移動信標與固定信標定位。移動信標節點是一類裝備了GPS或其它定位裝置的可移動節點，它在移動的過程中周期性自己的位置信息。基于移動信標的未知節點定位有很多優點，如定位成本低，容易達到很高的定位精度、可實現分布式定位計算、易于實現三維定位等。而固定信標節點是一類裝備了GPS或其它定位裝置的不可移動節點。

1.2 基于距離的節點坐標計算基本方法

待定位節點在獲得與鄰近信標節點的距離信息后，通常采用下列方法計算自身的位置[3]。

1) 三邊測量法：利用網絡中三個信標節點的位置坐標以及未知節點到這三個信標節點的距離，運用幾何方法求出未知節點的坐標。

2) 三角測量法：利用網絡中三個信標節點的位置坐標以及未知節點為角頂點角邊分別為三個信標節點的角度，運用幾何方法求出未知節點的坐標。

3) 最小二乘估計法：利用未知節點的相鄰節點中的多個信標節點的位置坐標以及它們與未知節點的距離或角度，運用最小均方差估計方法求出未知節點的坐標。

1.3 常用的測距方法

1) 信號接收強度（RSSI）測距法

已知發射功率和天線接收增益，在接收節點測量信號接收功率，計算傳播損耗，使用理論或經驗的無線電傳播模型由傳播損耗計算出信源與接收者間的距離。通常使用下列對數-常態分布模型來計算節點間的距離[1]。

PL(d)=PL(d0)+10λ?log(d/d0)+X （1）

PL(d0)=32.44+10λ?log(d0)+ 10λ?log(f) （2）

RSSI=發射功率+天線增益-路徑損耗(PL(d)) （3）

其中PL(d)[dB]是經過距離d后的路徑損耗，X是平均值為0的高斯分布隨機變數，其標準差取為4至10，λ為取衰減因子通常為2至3.5，f是頻率，取d0=1(m)，這樣根據上述3式可得節點間的距離。

2) 到達時間測距法

到達時間(TOA)技術通過測量信號傳播時間來測量距離，若電波從信標節點到未知節點的傳播時間為t，電波傳播速度為c，則信標節點到未知節點的距離為t×c。

3) 時間差測距法

TDOA測距是通過測量兩種不同信號到達未知節點的時間差，再根據兩種信號傳播速度來計算未知節點與信標節點之間的距離，通常采用電波和超聲波組合。

4) 到達角定位法

到達角(AOA)定位法采用陣列天線或多個接收器組合來獲取相鄰節點所處位置的方向，從而構成從接收機到發射機的方位線。兩條方位線的交點就是未知節點的位置。

1.4 典型非測距算法

基于距離測量和角度測量的定位算法的缺點是對專用硬件有一定的要求，從而使傳感器節點成本和體積加大，限制了它的實用性。非測距的算法不需要測量未知節點到信標節點的距離，在成本和功耗方面比基于測距的定位方法具有一定的優勢，但是精度相對不足。

1) DV－hop算法

為了避免對節點間距離的直接測量， Niculescu等人提出了DV－hop算法[3]。該算法基本思想是：用網絡中節點的平均每跳距離和信標到待定位節點之間的跳數乘積來表示待定位節點到信標節點之間的距離，再用三角定位來獲得待定位節點的位置坐標。

2) 質心法

質心法由南加州大學Nirupama Bulusu等學者提出[3]，該算法是未知節點以所有可收到信號的信標節點的幾何質心作為自己的估計位置，它是一種基于網絡連通性的室外節點定位算法。

3) APIT 算法

一個未知節點任選3個能夠與之通信的信標節點構成一個三角形，并測試自身位置是在這個三角形內部還是在其外部；然后再選擇另外3個信標節點進行同樣的測試，直到窮盡所有的組合或者達到所需的精度。

4) Amorphous 算法

Amorphous 定位算法[3]采用與 DV-Hop 算法類似的方法獲得距信標節點的跳數，稱為梯度值。未知節點收集鄰居節點的梯度值，計算關于某個信標節點的局部梯度平均值。Amorphous 算法假定預先知道網絡的密度，然后離線計算網絡的平均每跳距離，最后當獲得3個或更多錨節點的梯度值后，未知節點計算與每個錨節點的距離，并使用三邊測量法和最大似然估計法估算自身位置。

2 基于移動信標的無線傳感器網絡節點定位技術

無論是距離相關還是距離無關定位算法，常采用固定信標節點方式測量距離、相對角度、傳播時間差及傳播時間等進行節點定位[1]。通常參與定位的固定信標節點越多, 定位精度將越高。但是信標節點的成本遠遠高于普通節點，當定位工作完成后，信標節點將轉成普通的傳感器節點使用。因此信標點越多，布設整個網絡的成本將會增大, 定位算法的計算負荷以及通訊負荷將會增大[1] ，過多的信標節點將會造成較大的浪費。所以利用移動節點發出的虛擬坐標點進行輔助定位的思想將成為節點定位研究的一個重要研究方向。

假定整個WSN由靜止節點以及移動節點(如撒播節點完畢的飛機、運動的車輛、移動的小型機器人或普通的能移動的傳感器節點等) 兩種類型節點構成。根據傳感器網絡的規模大小, 可以配置一個或者多個移動節點。各移動節點均配置一個GPS接收器用于定位移動信標節點本身, 并有足夠的能量自我移動或捆綁移動機器人、移動車輛或三維空間中的飛機等工具。移動節點在傳感器區域內按照一定的運動路徑移動, 并周期性地發送坐標位置信息, 待定位節點根據接收到的坐標信息與采用適當的定位算法完成定位[6] 。

近幾年有一些研究者對移動錨節點路徑規劃展開研究，提出了一些比較好的路徑規劃方案。移動錨節點路徑規劃主要有兩個目標：

1) 移動軌跡能夠覆蓋網絡中的所有未知節點；

2) 為未知節點定位提供質量好的信標點。

如果滿足網絡節點均勻分布的條件，規劃路徑通常采用靜態規劃路徑，移動錨節點都按照預先規劃的路徑移動，不具有根據節點分布狀況靈活變化的性能。文獻[7]針對移動錨節點的路徑規劃問題利用空間填充線理論提出了SCAN、DOUBLESCAN以及HILBERT路徑規劃方法，分別如圖1、圖2和圖3所示。在節點通信距離小和空間填充線密度大的條件下， SCAN路徑比HILBERT路徑的定位結果準確。但是在節點通信距離大、空間填充線密度較小時，HILBERT路徑明顯優于SCAN路徑。

SCAN路徑存在明顯的缺點就是提供了大量共線的信標點，HILBERT路徑通過增加移動路徑長度解決了信標點共線性的問題，只要達到一定的密度就可以為定位提供優質的不共線信標點。為了解決信標點存在共線性的問題，文獻[8]提出了圓形規劃路徑和S形規劃路徑方法，如圖4和圖5所示。圓形規劃路徑完全覆蓋方形網絡區域時必須增加大圓路徑，這很大程度增加了路徑的長度。而圓形的直徑非常大時，在局部帶來了信標點的共線性問題。S形路徑通過引入S形曲線代替直線，解決了信標點共線性問題。

而對于實際環境中節點非均勻分布的情況，文獻[9]提出了提出了寬度優先和回溯式貪婪算法。這種方法能夠根據網絡信息自適應進行路徑規劃，規劃路徑不再是規則的圖形，能夠充分利用節點分布信息覆蓋所有節點，保證路徑最短，克服了靜態路徑規劃的缺點。文獻[10]提出讓一個攜帶GPS的移動信標采用隨機移動模型的方式盡量遍歷傳感區域，然后采用分布式算法為未知節點定位，該方法結合了基于測距方法的優點，并且無需布置固定的信標節點，節省了成本開銷，但是由于移動信標的移動模型采用隨機的方式，難以讓其移動范圍覆蓋整個傳感區域，從而有些未知節點無法定位。

3 定位算法的評價標準

定位算法設計的優劣通常以下列幾個評價標準[11]來評價：

1）定位精度：一般用誤差值與節點無線射程的比例表示，是定位技術首要的評價指標。

2）定位覆蓋率：指利用定位算法能夠進行定位的節點數與總的未知節點個數之比，它是評價定位算法的另外一個重要的指標。

3）信標節點密度：信標節點占所有節點的比例或者是單位區域內信標節點的數目。

4）節點密度：節點密度通常以網絡的平均連通度來表示。

5）功耗：功耗是指傳感器節點在單位時間內所消耗的能源的數量。由于傳感器節點不會始終在工作的，有時候會處于休眠狀態，但這同樣也會消耗少量的能量，因此，傳感器節點的功耗一般會有兩個，一個是工作時的功耗，另一個是待機時的功耗。

6）成本：包括時間、空間和費用。時間指一個系統的安裝、配置和定位所需的時間。空間包括一個定位系統或算法所需的基礎設施和網絡節點的數量、安裝尺寸等。費用則包括實現某種定位系統或算法的基礎設施、節點設備的總費用。

7）魯棒性：定位系統和算法必須具有很強的容錯性和自適應性，能夠通過自身調整或重構糾正錯誤、適應環境、減小各種誤差的影響，以提高定位精度。

上述的這些評價指標不僅是評價WSN自身定位系統和算法的標準，也是其設計和實現的優化目標。

4 結束語

使用移動信標節點來完成WSN所有節點的定位，就必須要足夠的時間讓移動信標節點遍歷完整個網絡, 為了減小所有節點定位所需的時間以及提高定位效率，如何進一步優化移動信標節點的運動路徑將成為基于移動信標的WSN節點定位技術更研究的重要方向。

參考文獻：

[1] 孫利民.無線傳感器網絡[M].北京:清華大學出版社,2005.

[2] A l-Karaki.JN, Kamal.AE. Routing Techniques in Wireless Sensor Networks: A Survey[J].In Wireless Communications,IEEE,Volume:11,Issue:6, Dec,2004:6-28.

[3] 王福豹,史龍,任豐原.無線傳感器網絡中的自身定位系統和算法[J].軟件學報,2005,16(5):857-869.

[4] Kushwaha,M. Molnar,K. Sallai,J. Volgyesi, P. Maroti, M. Ledeczi, A. Sensor Node Localization Using Mobile Acoustic Beacons[C], In proc. 2005. IEEE International Conference on Mobile Adhoc and Sensor Systems Conference, Nov,2005.

[5] 倪巍,王宗欣.基于接收信號強度測量的室內定位算法[J].復旦學報(自然科學版),2004.43(1):72-76.

[6] Mihail L. Sichitiu ,Vaidyanathan Ramadurai. Localization of Wireless Sensor Networks with a Mobile Beacon[C].//IEEE 2004:174-182.

[7] Koutsonilas D, Das S M, Hu Y Charlie. Path Planning of mobile landmarks for localization in wireless sensor networks[J].Computer Communication.2007,30(13): 2577-259.

[8] Rui Huang,Zaruba Gergely V. Static Pathplanning for mobile beaeons to localize sensor networks[C] / /Proc of IEEE PerComW. Piscataway,NJ:IEEE，2007:323-330.

[9] Hongjun Li,Jianwen Wang,Xun Li and Hongxu Ma. Real-time Path Planning of Mobile Anchor Node in Localization for Wireless Sensor Networks[C].//Proeeedings of the 2008 IEEE International Conference on Information and Automation,Zhangjiajie,China,June,20-23,2008.

篇（11）

中圖分類號:G642 文獻標識碼:B

1背景

數據結構和算法是計算機科學與技術、軟件工程等相關專業的專業基礎課,其重要性不言而喻,在教學過程中需要運用多種教學方法,讓學生領會算法實現的過程和本質,加深對所學知識的理解、記憶和應用。在數據結構和算法課程教學中,圖狀結構的教學是一個難點,特別是涉及到圖的具體應用時,更讓學生難以掌握,本文將圖示教學法應用到數據結構中關于圖狀結構的一個典型應用――最小生成樹問題,給出該教學方法的基本方法和過程,取得了良好的教學效果。

最小生成樹是圖狀(網絡)結構中一個典型的實踐應用,可以解決實際中諸如公路網的規劃,即在n個城市中,如何規劃n-1條公路,使得n個城市都可以連接起來,而所有城市間的連接線長度的總和最短(所要修建的公路長度最短,因而費用最少)。

對于這個典型的應用,絕大多數教科書均介紹了普里姆(Prim)算法,用于求最小生成樹問題,然而教科書對這個算法實現的論述,一般是先介紹應用背景,然后就給出算法實現的過程,缺少形象的算法分析過程,課堂教學講解如果按照這種方式去傳授,學生在理解上十分吃力,而且不能有效地長期記憶。筆者結合自己在教學中的經驗,將以上算法采用了圖示教學法來分析其基本原理和實現過程,并給出算法實現過程,取得了良好的效果。

2教學方法

圖示教學法就是用各種圖形表示的方法描述問題、引導學生的思考,增強對新知識的記憶,并在教學中被廣泛使用。最小生成樹屬于網絡的實踐應用,下面以圖1為例,用圖示教學法來對最小生成樹算法進行圖示過程分析。

假設某一區域內有n個城市,現要為這些城市修建城間公路,使得任意兩城市間都能夠相互通達(連通),由于要求所有的城市都在該公路網上,某兩個城市間的道路稱為一個路段,則修建的道路路段總數應等于n-1個(容易理解:如果路段總數小于n-1,則會有存在城市不能處在該道路網的節點上;如果路段總數大于n-1則會存在某兩個城市間有至少兩個路段,則路段距離的總和將不是最小),先從這些城市中任選一個作為種子,把剩下的城市用路段連接到由該種子城市為起始點的城市網絡中,保證路段長度總和最小(最優路段網),則最后連接好的路段即為最小生成樹。

如圖1,每個帶圈的數字表示一個城市,城市間的邊表示城市間的距離,如果兩城市間沒有邊存在,則表示這兩個城市間不適宜修道路(如有山脈或河流隔斷,造價太高),假設種子城市為數字1(選定的網絡的起始頂點),通過圖示教學法求最優路段網的過程如圖2:

圖中,Li-j表示城市i與城市j間的距離,例如在(b)中,當把城市2加入到最優路段網后,城市3、4、6與該最優路段網的距離發生了變化,例如城市3,由于由L1-3(=∞)> L2-3(=5),故其與最優路段網的距離由原先的∞也轉變為5

首先構造一個初始最優路段網,但該網絡只有一個節點,即“種子城市”,其位于圖2(a)中的中心圓圈內,圈外的節點稱為節點或城市。然后根據圖1城市間的距離(網絡節點間的邊的權值),求其它所有城市(網絡節點)與種子城市間的距離(通過訪問網絡的物理存儲結構如鄰接表獲取),該圖表示僅通過了種子城市來連接所有的其它城市,圖中中心圓圈外的城市當前還沒有加入到最優路段網規劃中,圈外連接每個城市與中心圓圈的實線表示該城市如果按當前規劃方案加入到該路段網時所需要建造的路段長度(即網絡邊的權),圈內的虛線表示當前城市通過某一個最優路段網中的某城市為“橋梁”,而進入到該網絡中。例如,城市2如果通過城市1進入規劃網,則需要修建長度為16(僅表示相對數值)的道路,城市5要修建長度19的道路,城市6要修建長度21的道路,而城市3和城市4無法通過城市1來連接到最優路段網中(距離為無窮大,∞),而必須通過其它城市作為“橋梁”,來進入該規劃網絡中。很明顯,如果按照該方案來把所有的城市都加入到初始最優路段網,得到的路段網如圖2(g),需要修建的路段網總長度為∞,顯然不是最優路段網。

注意到為了使規劃的路段網是最優的(路段長度總和最小),只要保證每次加入到最優路段網中的城市都具有最短路段長度,則最后的路段總長度也必然最小。在圖2(a)中,城市2與種子城市具有最小的距離(16),因而不可能找到其它任何一個路段,實現“種子城市與其它城市實現互連時,種子城市到其它任意一個城市的路段距離小于該值”,因而路段②-①必然是滿足種子城市連通其它城市的最優路段,將城市2加入到最優路段網后,得到圖2(b)。注意到當城市2加入到最優路段網后,城市3、4、6如果是通過城市2為“橋梁”(圖中的虛線所示),加入到該最優路段網中,可以使各自的路段長度由原先的∞、∞和21分別縮短到5、6、11(其它城市通過城市2無法實現路段長度縮短,因為保持不變),此時路段總長度也由原先的∞縮小到57(即16+5+6+19+11),較圖2(a),該方案有了很大的進步。然而該網絡仍不是最優路段網,因為其僅保證了路段②-①的最優性(注意圓圈內的網絡是最優的),而其它城市到該網絡中的路段并非最優,這樣不能保證路段總長度最小。

進一步注意到,在所有的當前城市中,城市3距離最優路段網的距離最短(5),也就是為了使當前最優路段網(圓圈內的城市及連線)與其它城市能夠實現連通,且連通后的路段總長度最小,所以當前應加入城市3(圖2(c))。城市3的加入或許可以使得其它的城市通過該城市為“橋梁”,而縮短城市到最優路段網的距離(當然這里城市3的加入實際并沒有使其它城市到最優路段網的距離縮小)。同樣的道理,在第4步(圖2(d)),將城市4加入到最優路段網中(因為在余下的城市中,城市4到最優路段網的距離最小),該城市的加入,也使得城市1以該城市為“橋梁”而到最優路段網的距離由原來的19縮短到18(其它路段不變)。第5步將城市6加入到最優路段網中(圖2(e)),該城市的加入沒有影響余下的城市(當前僅剩一個城市,即城市5),最后將城市5加入到最優路段網中(圖2(f))。得到的最終的最優路段網如圖2(h),其路段長度的總和為56(16+5+11+6+18)。

3算法求解

有了如上的圖示教學法描述的計算最小生成樹實現基本過程,在講解算法時就比較容易了。算法在實現時需要構造三個輔助數組:第1個數組A[n](n為節點數)記錄當前節點是節點還是已加入最短路段(路徑)網的節點,數組元素A[i]=0或1,0表示節點i是一個節點,當加入到最短路段(路徑)網后,A[i]=1;第2個數組B[n]記錄各節點到最短路段(路徑)網的距離,用B[n]表示;第3個數組C[n]記錄節點通過最短路段(路徑)網內的哪一個節點為“橋梁”而進入該路段(路徑)網的。注意這里的路徑R和路段L是兩個不同的概念,路段是節點的邊,而路徑是具有共同節點的有序邊起節點與尾節點首尾相連在一起的序列,如在圖1中,其中的一個路徑R1-3=L1-2+L2-3。下面結合圖2和圖3,給出這些數組的值在計算過程中的變化情況。

輔助數組的變化情況如下圖3所示,其中圖3(a)即對應于圖2(a),圖3(b)對應于圖2(b),依此類推。在圖3(a)中,首先只有第一個節點進入最短路段網,因此A[1]=1,其它的A元素均為0,節點與最短路段網的距離B[i]與圖2(a)中的距離對應,這里節點1由于已在最短路段網,所以B[1]=0,由于所有的節點目前都是通過節點1與最短路段網連接,因而所有的C[i]的值都是1。在圖3(b)中,由于節點2距最短路段網的距離最小(16),節點2進入最短路段網,因而A[2]=1,此時由于節點2已進入最短路段網,因而B[2]=0,而節點3和節點4通過節點2,使它們距最短路段網的距離由原先的∞縮短到5和6,節點6也通過節點2使B[6]由21縮小到11。圖3(c)、3(d)、3(e)、3(f)的過程不再贅述。最后的結果(圖3(f))表明,節點1通過其本身進入最短路段網,節點2通過節點1進入最短路段網,節點3、4、6均通過節點2為“橋梁”進入最短路段網,而節點5通過節點4進入最短路段網。

基于上述分析,不難給出以上算法的實現描述:

(1) 初始化數組A、B、C,結果如圖2(a)、圖3(a),這里假設以節點1為起始(源)節點,共有n個節點。

(2) 反復執行如下操作:將B[i]中值最小的元素對應的編號i(即節點i)放入A中(即修改A[i]為1),然后修改A[j]!=0(j!=i)對應的B[j]和C[j]的值,修改的依據是:如果B[j]>Li-j,則用B[j]的值更改為Li-j。直至所有的A[i](1

(3) 輸出結果,將B、C的最后值輸出即可以得到最后結果,B所有的元素最后都為0,表示所有的元素都進入了最短路段網(最小生成數網),而C中的元素值表示的是當前節點元素(即節點1、2、3、4、5或6)是通過C中表示的節點編號而進入最短路段網的,即:節點1是通過其自身進入路段網,節點2通過節點1進入路段網,節點3、4和6均通過節點2進入路段網,節點5通過節點4進入路段網。

4結論

本文提出將圖示教學法可應用于數據結構和算法課程教學的多個環節中,有些算法在大多數教科書中有了一定的圖示過程表示,而有些算法卻沒有給出形象的圖示表示,因而需要在教學中應補充。本文以圖狀結構中的最小生成樹算法為例,通過圖示分析,詳細地講解這個算法的核心思想和實現過程,通過視覺刺激,使學生能夠加深對這個算法過程的把握,取得了良好的教學效果。

參考文獻:

[1] 戴敏,于長云,董玉濤. 高效學習數據結構[J]. 計算機教育,2006(2):59-60.