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

篇（1）

交通運(yùn)輸?shù)默F(xiàn)代化使人們享受便利的同時(shí)，也面臨道路擁堵、事故頻發(fā)等問}。近年來，智能交通系統(tǒng)越來越受到人們的重視，它涉及到交通領(lǐng)域諸多方面，如最優(yōu)路徑選擇、車輛路徑規(guī)劃、動(dòng)態(tài)車輛調(diào)度、交通流量控制等。其中一個(gè)重要的應(yīng)用是一類典型的以數(shù)學(xué)理論為基礎(chǔ)的組合優(yōu)化問題，而蟻群算法具有內(nèi)在的搜索機(jī)制及正反饋性，適合求解一系列的組合優(yōu)化問題。

1 蟻群算法描述

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

螞蟻a從節(jié)點(diǎn)j移動(dòng)至k的轉(zhuǎn)移概率可以從式（1）中獲取：

（1）

（2）

（3）

2 蟻群算法的應(yīng)用優(yōu)勢(shì)

蟻群算法，又名螞蟻算法，螞蟻可以利用信息素的濃度大小從而尋找到覓食的最優(yōu)路徑。該算法的優(yōu)點(diǎn)可以總結(jié)為：

2.1 并行分布式計(jì)算

每個(gè)螞蟻都是獨(dú)立的個(gè)體，在覓食過程中屬于多起點(diǎn)同時(shí)啟動(dòng)，互不影響，從根本上分析該過程屬于分布式的多Agent系統(tǒng)，整體蟻群最終任務(wù)的順利完成不會(huì)由于某些個(gè)體的缺陷而受到影響。該算法具有真實(shí)可用性，并且可用于解決對(duì)單目標(biāo)的優(yōu)化或者對(duì)多目標(biāo)的優(yōu)化等重要問題。此外，螞蟻算法還可進(jìn)行并行計(jì)算。

2.2 魯棒性

蟻群算法的最終結(jié)果與螞蟻?zhàn)畛踹x擇的路徑無太大關(guān)系，在利用人工仿真螞蟻進(jìn)行問題求解過程中，不需要對(duì)其進(jìn)行人工的修整。把問題簡單化，可以和其他算法相互結(jié)合求解最優(yōu)問題。

2.3 自組織性

蟻群算法組織指令的來源為系統(tǒng)內(nèi)部，它不受外界環(huán)境的干擾，因此該算法具有自組織性。

2.4 正反饋性

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

2.5 易于實(shí)現(xiàn)

它是一種啟發(fā)示算法，其計(jì)算復(fù)雜性為，整個(gè)算法的空間復(fù)雜度是：。

3 蟻群算法在智能交通領(lǐng)域的應(yīng)用空間

蟻群算法在解決組合優(yōu)化問題方面有著明顯的優(yōu)勢(shì)，從而在智能交通領(lǐng)域也有著廣泛的應(yīng)用空間。

3.1 車輛路徑導(dǎo)航

根據(jù)行車人員的需要，根據(jù)對(duì)實(shí)時(shí)路況信息的統(tǒng)計(jì)，系統(tǒng)可以智能的為其推薦最優(yōu)路徑，節(jié)省時(shí)間，節(jié)省資源。

3.2 動(dòng)態(tài)車輛調(diào)度

當(dāng)客戶需要調(diào)度中心為其進(jìn)行車輛服務(wù)時(shí)，調(diào)度中心要考慮到客戶的情況，要考慮到效率的問題，要考慮到行車路線、行駛時(shí)間等問題。蟻群算法便可迅速得到合理的解決方案，使客戶和調(diào)度中心均可受益。

3.3 車輛路徑規(guī)劃

面對(duì)多個(gè)客戶不同的要求時(shí)，配送中心要根據(jù)實(shí)際情況進(jìn)行車輛的配送，通過蟻群算法系統(tǒng)獲取整體的最優(yōu)路線，根據(jù)路線規(guī)劃，及時(shí)進(jìn)行車輛出發(fā)以滿足客戶要求，同時(shí)充分利用了道路資源和車輛資源。

3.4 公共交通智能化調(diào)度

利用先進(jìn)的技術(shù)手段、大型數(shù)據(jù)庫技術(shù)等動(dòng)態(tài)地獲取實(shí)時(shí)交通信息，實(shí)現(xiàn)對(duì)車輛的實(shí)時(shí)監(jiān)控和調(diào)度，最終建立集運(yùn)營指揮調(diào)度、綜合業(yè)務(wù)通信及信息服務(wù)等為一體的智能化管理系統(tǒng)。

3.5 交通流量控制

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

參考文獻(xiàn)

[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]楊海.蟻群算法及其在智能交通中的應(yīng)用[D].濟(jì)南：山東師范大學(xué)，2008：14-18

作者簡介

白曉（1979-），女。工學(xué)碩士學(xué)位。現(xiàn)供職于廈門軟件職業(yè)技術(shù)學(xué)院軟件工程系。主要研究方向?yàn)檐浖こ獭⒅悄芩惴ā?/p>

篇（2）

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

一、對(duì)最佳路徑的分析

配電網(wǎng)故障區(qū)域恢復(fù)供電的最佳路徑事實(shí)上是在故障情況下的配電網(wǎng)絡(luò)重構(gòu)。主要的目的在于，能夠快速的將非故障區(qū)域供電恢復(fù)，與此同時(shí)，還能夠有效的滿足線路負(fù)載容量的要求以及線損最小等各個(gè)方面的條件。現(xiàn)階段，在配網(wǎng)自動(dòng)化領(lǐng)域中研究最多的在于怎樣能夠快速的實(shí)現(xiàn)故障隔離以及快速的恢復(fù)費(fèi)故障區(qū)域的供電技術(shù)方法，因此，在恢復(fù)路徑的最優(yōu)化選擇方面出現(xiàn)了較多的研究。

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

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

雖然，對(duì)于GIS空間發(fā)展研究GeoSQL為一種有效的處理最短路徑的手段，但是GIS受到數(shù)據(jù)庫技術(shù)發(fā)展的制約與影響，導(dǎo)致實(shí)際的應(yīng)用領(lǐng)域和背景的不同，使其和商用之間還有很長的一段距離。

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

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

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

事實(shí)上，配電網(wǎng)故障區(qū)域恢復(fù)供電的最佳路徑并不是簡單的路徑問題，而是多目標(biāo)最佳路徑問題。為此，在研究配電網(wǎng)非故障區(qū)域恢復(fù)供電的最佳路徑過程中，需要對(duì)其展開綜合的分析。

首先，在多目標(biāo)分析方面，通常在選擇配電網(wǎng)非故障區(qū)域恢復(fù)供電最佳路徑的時(shí)候，最為重視的目標(biāo)為：

第一，在恢復(fù)供電路徑的過程中，饋線負(fù)荷不能過載，同時(shí)，還需要確保恢復(fù)區(qū)域的電壓質(zhì)量能夠與實(shí)際規(guī)定的標(biāo)準(zhǔn)要求相吻合。當(dāng)供電質(zhì)量可靠性最高的時(shí)候，那么恢復(fù)的時(shí)間將會(huì)很短[3]；這與鄧?yán)ビⅲ豇P嬌，饒杰等在《智能配電網(wǎng)有功自治互動(dòng)建模研究》一文中的觀點(diǎn)極為相似。另外，供電過程中，線損最低，證明開關(guān)拉合的次數(shù)最少，同時(shí)現(xiàn)場的操作點(diǎn)也會(huì)最少。

第二，在動(dòng)態(tài)規(guī)劃技術(shù)恢復(fù)供電的最短路徑方面需要明確，動(dòng)態(tài)規(guī)劃主要是運(yùn)籌學(xué)的一個(gè)分支，它是求解決策過程的最優(yōu)的數(shù)學(xué)方式。早在很久以前，就已經(jīng)有研究人員對(duì)多階段過程轉(zhuǎn)化問題轉(zhuǎn)化為一系列的單階段問題，并且逐一進(jìn)行求解，這標(biāo)志著解決這類過程優(yōu)化問題的新方法的創(chuàng)立，即動(dòng)態(tài)規(guī)劃技術(shù)。

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

總結(jié)

本文主要從兩個(gè)方面左手，共同分析了采用動(dòng)態(tài)規(guī)劃技術(shù)實(shí)現(xiàn)配電網(wǎng)恢復(fù)供電的方法與效果，一方面著手于最佳路徑的分析，另一方面著手于最佳路徑的選擇方法。從這兩個(gè)方面可以看出，利用動(dòng)態(tài)規(guī)劃技術(shù)去實(shí)現(xiàn)配電網(wǎng)恢復(fù)供電是一種可行的方法。但是，受到歷史原因的影響，我國城市配電網(wǎng)絡(luò)還缺少標(biāo)準(zhǔn)的規(guī)范要求，導(dǎo)致配電網(wǎng)常常出現(xiàn)一些事故。因此，恢復(fù)配電網(wǎng)供電已經(jīng)成為當(dāng)務(wù)之急。隨著科技的發(fā)展，智能配電網(wǎng)已經(jīng)被廣泛的應(yīng)用在供電方面，這為平穩(wěn)供電提供了一定的保障，同時(shí)也為恢復(fù)配電網(wǎng)故障供電創(chuàng)建了良好的環(huán)境與條件等。

參考文獻(xiàn)

[1]鄧群，孫才新，周駁.采用動(dòng)態(tài)規(guī)劃技術(shù)實(shí)現(xiàn)配電網(wǎng)恢復(fù)供電[J].重慶大學(xué)學(xué)報(bào)（自然科學(xué)版），2006，29（3）：40-44.

[2]李振坤，周偉杰，錢嘯等.有源配電網(wǎng)孤島恢復(fù)供電及黑啟動(dòng)策略研究[J].電工技術(shù)學(xué)報(bào)，2015，30（21）：67-75.

[3]鄧?yán)ビⅲ豇P嬌，饒杰等.智能配電網(wǎng)有功自治互動(dòng)建模研究[J].機(jī)電工程技術(shù)，2014，（2）：4-7.

篇（3）

為了減輕交通壓力，人們?cè)絹碓疥P(guān)心交通系統(tǒng)的智能化進(jìn)程。智能交通系統(tǒng)主要的研究方向之一就是動(dòng)態(tài)路徑誘導(dǎo)系統(tǒng)，它可根據(jù)外出的人們的需求，為駕駛員提供最新的路況信息和最佳路徑選擇，以此避免交通擁堵現(xiàn)象的發(fā)生，從而優(yōu)化交通狀況，最終使交通時(shí)時(shí)地保持一個(gè)合理的動(dòng)態(tài)分配。目前，最優(yōu)路徑選擇的方法有很多，但是真正需要解決大型問題時(shí)，計(jì)算機(jī)需要搜索的選擇范圍太大，傳統(tǒng)的動(dòng)態(tài)算法基本上無法處理。1995年，神經(jīng)動(dòng)態(tài)規(guī)劃算法被提出，該算法把復(fù)雜的問題分成若干子問題，這些子問題被拆分后更容易解決，使計(jì)算過程大幅簡化，且更容易被計(jì)算機(jī)處理。采用這種方法，可準(zhǔn)確、快速、實(shí)時(shí)、穩(wěn)定地選擇出最優(yōu)路徑，值得推廣。

1 神經(jīng)動(dòng)態(tài)規(guī)劃概述與核心思想

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

在路徑優(yōu)化中，動(dòng)態(tài)規(guī)劃是一種非常經(jīng)典的計(jì)算方法，但在處理實(shí)際問題的時(shí)，我們肯定會(huì)遇到缺少一個(gè)完整信息或者維數(shù)災(zāi)等一系列問題，所以，引進(jìn)神經(jīng)網(wǎng)絡(luò)對(duì)動(dòng)態(tài)規(guī)劃具有較大的解決實(shí)際問題的意義。神經(jīng)動(dòng)態(tài)規(guī)劃如圖1所示。

2 基于神經(jīng)動(dòng)態(tài)規(guī)劃算法的最優(yōu)路徑實(shí)現(xiàn)

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

（2）求解狀態(tài)和狀態(tài)變量。每個(gè)子階段具體的起始位置可以依靠自然狀態(tài)來指導(dǎo)，其中客觀條件階段性數(shù)目的狀態(tài)是自然狀態(tài)中的一種，它傳達(dá)每個(gè)子階段的關(guān)鍵信息，此外，一組或者無后效性的變量同樣可以用來表示狀態(tài)變量。本文用Hx來表示第x級(jí)的狀態(tài)變量。

（3）求解原問題決策變量和集合。從目前階段到下一個(gè)階段狀態(tài)選擇時(shí)，決策者需要做出恰當(dāng)?shù)臎Q策，決策變量的范圍稱為集合。本文用Dx表示決策集合，用Ux表示決策變量。

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

（5）研究指標(biāo)函數(shù)。因?yàn)閚和vi的遞進(jìn)性和可分離性，所以很容易找到指標(biāo)函數(shù)n和vi之間的關(guān)系，顯然，指標(biāo)函數(shù)的求解也相對(duì)簡單化。

（6）動(dòng)態(tài)規(guī)劃函數(shù)的基本方程。邊界條件為；

，第x-m階的最優(yōu)動(dòng)態(tài)規(guī)劃函數(shù)是。

3 仿真結(jié)果

將上述模型，在Matlab仿真軟件上進(jìn)行模擬仿真，分解原始問題并確定各個(gè)子階段的最佳方案，將這個(gè)問題用網(wǎng)格的形式如圖2進(jìn)行表示：A為起始地點(diǎn)，E為目標(biāo)地點(diǎn)，從起始地點(diǎn)到目標(biāo)終點(diǎn)有很多路徑，假設(shè)經(jīng)過每個(gè)節(jié)點(diǎn)需要一定的運(yùn)輸成本，在Matlab仿真軟件上進(jìn)行仿真后依據(jù)動(dòng)態(tài)規(guī)則算法的要求，設(shè)定好相應(yīng)的算法模型以及相應(yīng)的計(jì)算公式，這樣便可以找到最優(yōu)路徑。

由圖2可以非常清楚的看出，成本最低的路線為：或者或者，成本都是110。仿真結(jié)果可以看出神經(jīng)動(dòng)態(tài)規(guī)劃算法具有較多優(yōu)點(diǎn)：得到清晰運(yùn)算結(jié)果；很容易找到全局的最優(yōu)路徑；可以找到一組完善的解，有利進(jìn)一步的分析。

4 結(jié)語

我們?cè)谑褂蒙窠?jīng)動(dòng)態(tài)規(guī)劃算法來探索最優(yōu)路徑的時(shí)候，具有很多優(yōu)勢(shì)，首先其具有穩(wěn)定、可靠的步驟，過程并不復(fù)雜，但是給予我們的結(jié)果十分清晰明確，且適用于現(xiàn)實(shí)生活。使用這種動(dòng)態(tài)規(guī)劃算法解決復(fù)雜的問題時(shí)，可以非常容易找到解決方案，而且效率很高。當(dāng)然，該算法也有一定的局限，但只要我們不斷地改進(jìn)完善，日后繼續(xù)研究神經(jīng)動(dòng)態(tài)規(guī)劃算法，相信一定可以攻克更多的局限，能夠使其更好地被應(yīng)用。

參考文獻(xiàn)

[1]謬慧芬，邵小兵.動(dòng)態(tài)規(guī)劃算法的原理及應(yīng)用[J].中國科技信息，2006（23）：32.

[2]楊琰，廖偉志，李文敬，楊文，李杰.基于Petri網(wǎng)的顧及轉(zhuǎn)向延誤的最優(yōu)路徑算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2013（10）.

作者簡介

篇（4）

關(guān)鍵詞：多機(jī)器人；路徑規(guī)劃；強(qiáng)化學(xué)習(xí)；評(píng)判準(zhǔn)則

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)成為人工智能研究的一個(gè)重要分支。DAI研究大致可以分為DPS（distributed problem solving）和MAS（multiagent system）兩個(gè)方面。一些從事機(jī)器人學(xué)的研究人員受多智能體系統(tǒng)研究的啟發(fā)，將智能體概念應(yīng)用于多機(jī)器人系統(tǒng)的研究中，將單個(gè)機(jī)器人視做一個(gè)能獨(dú)立執(zhí)行特定任務(wù)的智能體，并把這種多機(jī)器人系統(tǒng)稱為多智能體機(jī)器人系統(tǒng)（MARS）。因此，本文中多機(jī)器人系統(tǒng)等同于多智能體機(jī)器人系統(tǒng)。目前，多機(jī)器人系統(tǒng)已經(jīng)成為學(xué)術(shù)界研究的熱點(diǎn)，而路徑規(guī)劃研究又是其核心部分。

機(jī)器人路徑規(guī)劃問題可以建模為一個(gè)帶約束的優(yōu)化問題，其包括地理環(huán)境信息建模、路徑規(guī)劃、定位和避障等任務(wù)，它是移動(dòng)機(jī)器人導(dǎo)航與控制的基礎(chǔ)。單個(gè)移動(dòng)機(jī)器人路徑規(guī)劃研究一直是機(jī)器人研究的重點(diǎn)，且已經(jīng)有許多成果[1~3]，例如在靜態(tài)環(huán)境中常見的有連接圖法、可視圖法、切線圖法、Voronoi圖法、自由空間法、柵格法、拓?fù)浞ā㈡溄訄D法、DempsterShafer證據(jù)理論建圖等；動(dòng)態(tài)環(huán)境中常見的有粒子群算法、免疫算法、遺傳算法、神經(jīng)網(wǎng)絡(luò)、蟻群算法、模擬退火算法、人工勢(shì)場法等。然而，多機(jī)器人路徑規(guī)劃研究比單個(gè)機(jī)器人路徑規(guī)劃要復(fù)雜得多，必須考慮多機(jī)器人系統(tǒng)中機(jī)器人之間的避碰機(jī)制、機(jī)器人之間的相互協(xié)作機(jī)制、通信機(jī)制等問題。

1 多機(jī)器人路徑規(guī)劃方法

單個(gè)機(jī)器人的路徑規(guī)劃是找出從起始點(diǎn)至終點(diǎn)的一條最短無碰路徑。多個(gè)機(jī)器人的路徑規(guī)劃側(cè)重考慮整個(gè)系統(tǒng)的最優(yōu)路徑，如系統(tǒng)的總耗時(shí)間最少路徑或是系統(tǒng)總路徑最短等。從目前國內(nèi)外的研究來看，在規(guī)劃多機(jī)器人路徑時(shí)，更多考慮的是多機(jī)器人之間的協(xié)調(diào)和合作式的路徑規(guī)劃。

目前國內(nèi)外多機(jī)器人路徑規(guī)劃研究方法分為傳統(tǒng)方法、智能優(yōu)化方法和其他方法三大類。其中傳統(tǒng)方法主要有基于圖論的方法（如可視圖法、自由空間法、柵格法、Voronoi圖法以及人工勢(shì)場方法等）；智能優(yōu)化方法主要有遺傳算法、蟻群算法、免疫算法、神經(jīng)網(wǎng)絡(luò)、強(qiáng)化學(xué)習(xí)等；其他方法主要有動(dòng)態(tài)規(guī)劃、最優(yōu)控制算法、模糊控制等。它們中的大部分都是從單個(gè)機(jī)器人路徑規(guī)劃方法擴(kuò)展而來的。

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

2）智能優(yōu)化方法 多機(jī)器人路徑規(guī)劃的智能優(yōu)化方（算）法是隨著近年來智能計(jì)算發(fā)展而產(chǎn)生的一些新方法。其相對(duì)于傳統(tǒng)方法更加智能化，且日益成為國內(nèi)外研究的重點(diǎn)。

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

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

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

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

朱慶保[9]提出了在全局未知環(huán)境下多機(jī)器人運(yùn)動(dòng)螞蟻導(dǎo)航算法。該方法將全局目標(biāo)點(diǎn)映射到機(jī)器人視野域邊界附近作為局部導(dǎo)航子目標(biāo)，再由兩組螞蟻相互協(xié)作完成機(jī)器人視野域內(nèi)局部最優(yōu)路徑的搜索，然后在此基礎(chǔ)上進(jìn)行與其他機(jī)器人的碰撞預(yù)測與避碰規(guī)劃。因此，機(jī)器人的前進(jìn)路徑不斷被動(dòng)態(tài)修改，從而在每條局部優(yōu)化路徑引導(dǎo)下，使機(jī)器人沿一條全局優(yōu)化的路徑到達(dá)目標(biāo)點(diǎn)。但其不足是在動(dòng)態(tài)不確定的環(huán)境中路徑規(guī)劃時(shí)間開銷劇增，而且機(jī)器人缺乏必要的學(xué)習(xí)，以至于整個(gè)機(jī)器人系統(tǒng)路徑難以是最優(yōu)路徑。

強(qiáng)化學(xué)習(xí)[10，11] (又稱再激勵(lì)學(xué)習(xí))是一種重要的機(jī)器學(xué)習(xí)方法。它是一種智能體從環(huán)境狀態(tài)到行為映射的學(xué)習(xí)，使得行為從環(huán)境中獲得積累獎(jiǎng)賞值最大。其原理如圖1所示。

強(qiáng)化學(xué)習(xí)算法一般包含了兩個(gè)步驟：a）從當(dāng)前學(xué)習(xí)循環(huán)的值函數(shù)確定新的行為策略；b）在新的行為策略指導(dǎo)下，通過所獲得的瞬時(shí)獎(jiǎng)懲值對(duì)該策略進(jìn)行評(píng)估。學(xué)習(xí)循環(huán)過程如下所示，直到值函數(shù)和策略收斂:

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

目前比較常見的強(qiáng)化學(xué)習(xí)方法有：Monte Carlo方法、動(dòng)態(tài)規(guī)劃方法、TD（時(shí)間差分）方法。其中TD算法包含Sarsa算法、Q學(xué)習(xí)算法以及Dyna-Q算法等。其Q值函數(shù)迭代公式分別為

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′學(xué)習(xí)算法： Qπ(s，a)=∑Pαss′[Rass′+γVπ(s′)]

近年來，基于強(qiáng)化學(xué)習(xí)的路徑規(guī)劃日益成為國內(nèi)外學(xué)者研究的熱點(diǎn)。M. J. Mataric[12]首次把強(qiáng)化學(xué)習(xí)引入到多機(jī)器人環(huán)境中。而基于強(qiáng)化學(xué)習(xí)的多機(jī)器人路徑規(guī)劃的優(yōu)點(diǎn)主要體現(xiàn)在：無須建立精確的環(huán)境模型，簡化了智能體的編程；無須構(gòu)建環(huán)境地圖；強(qiáng)化學(xué)習(xí)可以把路徑規(guī)劃、避碰、避障、協(xié)作等問題統(tǒng)一解決。

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

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

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

2 多機(jī)器人避碰和避障

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

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

人工勢(shì)場方法的特點(diǎn)是計(jì)算簡潔、實(shí)時(shí)性強(qiáng)、便于數(shù)學(xué)描述，且適合于多自由度機(jī)器人環(huán)境，但容易產(chǎn)生抖動(dòng)和陷入局部極小。為了克服其缺點(diǎn)，景興建等人[26]提出了人工協(xié)調(diào)場的方法，在傳統(tǒng)排斥力場中增加一個(gè)協(xié)調(diào)力，并將吸引力、排斥力和協(xié)調(diào)力與局部環(huán)境下機(jī)器人的運(yùn)動(dòng)狀態(tài)和運(yùn)動(dòng)要求結(jié)合起來，有效地保證機(jī)器人的安全性，提高機(jī)器人在復(fù)雜動(dòng)態(tài)環(huán)境下行為決策的準(zhǔn)確性和魯棒性。

3 多機(jī)器人協(xié)作和協(xié)調(diào)機(jī)制

多機(jī)器人間的運(yùn)動(dòng)協(xié)調(diào)[27~31]是多機(jī)器人路徑規(guī)劃的關(guān)鍵，也是多機(jī)器人與單機(jī)器人路徑規(guī)劃相區(qū)別的根本所在。多機(jī)器人系統(tǒng)在復(fù)雜動(dòng)態(tài)實(shí)時(shí)環(huán)境下，由于受到時(shí)間、資源及任務(wù)要求的約束，需要在有限時(shí)間、資源的情況下進(jìn)行資源分配、任務(wù)調(diào)配、沖突解決等協(xié)調(diào)合作問題，而機(jī)器人間的協(xié)調(diào)與協(xié)作，能夠大大地提高整個(gè)系統(tǒng)的效率和魯棒性，成為系統(tǒng)完成控制或解決任務(wù)的關(guān)鍵。

目前已有的協(xié)調(diào)方式分為集中式、分布式和混合式三種。在集中式協(xié)調(diào)中，集中規(guī)劃器詳細(xì)地規(guī)劃出每個(gè)機(jī)器人的動(dòng)作，通常的做法是將多個(gè)機(jī)器人看做一個(gè)多自由度的機(jī)器人進(jìn)行規(guī)劃；而分布式協(xié)調(diào)規(guī)劃中，機(jī)器人之間進(jìn)行合作，將一個(gè)任務(wù)分成多個(gè)子任務(wù)，根據(jù)各自的特點(diǎn)完成不同的子任務(wù)，從而共同完成總?cè)蝿?wù)；混合式協(xié)調(diào)是集中式和分布式混合在一起的形式。

多機(jī)器人間典型的協(xié)調(diào)方法[32]有合同網(wǎng)協(xié)議[33]、黑板模型、結(jié)果共享的協(xié)同方法、市場機(jī)制。近年來強(qiáng)化學(xué)習(xí)在多機(jī)器人協(xié)作方面也得到很好的應(yīng)用，陳雪江[32]在基于強(qiáng)化學(xué)習(xí)的多機(jī)器人協(xié)作方面展開了研究，提出了多智能體協(xié)作的兩層強(qiáng)化學(xué)習(xí)方法來求解在多智能體完全協(xié)作、有通信情況下的協(xié)作問題。其主要通過在單個(gè)智能體中構(gòu)筑兩層強(qiáng)化學(xué)習(xí)單元來實(shí)現(xiàn)：第一層強(qiáng)化學(xué)習(xí)單元負(fù)責(zé)學(xué)習(xí)智能體的聯(lián)合任務(wù)協(xié)作策略；第二層強(qiáng)化學(xué)習(xí)單元負(fù)責(zé)學(xué)習(xí)在本智能體看來是最有效的行動(dòng)策略。陳偉等人[34]提出基于多目標(biāo)決策理論的多機(jī)器人協(xié)調(diào)方法；通過對(duì)環(huán)境的拓?fù)浣＃瑥幕谛袨榈臋C(jī)器人學(xué)角度出發(fā)，對(duì)任務(wù)進(jìn)行分解并設(shè)計(jì)目標(biāo)行為，以多目標(biāo)行為決策理論作為決策支持，從而達(dá)到多機(jī)器人運(yùn)動(dòng)協(xié)調(diào)的目的。

4 多機(jī)器人路徑規(guī)劃方(算)法的判優(yōu)準(zhǔn)則

通常評(píng)價(jià)機(jī)器人路徑規(guī)劃方(算)法的標(biāo)準(zhǔn)文獻(xiàn)[35]有正確性、時(shí)間/空間復(fù)雜度、并行性、可靠性、擴(kuò)展性、魯棒性和學(xué)習(xí)。而多機(jī)器人的路徑規(guī)劃除了以上一些衡量標(biāo)準(zhǔn)之外，還需要考慮整個(gè)系統(tǒng)的最優(yōu)化以及機(jī)器人間的協(xié)調(diào)性。

1)正確性 是分析算法的最基本的原則之一。一般來說算法的正確性是指:在給定有效的輸入數(shù)據(jù)后，算法經(jīng)過有窮時(shí)間的計(jì)算能給出正確的答案。但在多機(jī)器人路徑規(guī)劃算法中，正確性主要指:路徑規(guī)劃算法要生成多個(gè)機(jī)器人協(xié)調(diào)運(yùn)動(dòng)的無碰安全路徑;這條路徑是優(yōu)化的。

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

3)復(fù)雜度 一個(gè)算法的復(fù)雜性高低體現(xiàn)在該算法所需要的計(jì)算機(jī)資源的多少上面。所需要的資源越多，該算法的復(fù)雜性越高；反之，所需要的資源越少，該算法的復(fù)雜性就越低。算法的復(fù)雜性包括時(shí)間復(fù)雜度和空間復(fù)雜度。

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

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

5)可靠性 把多個(gè)機(jī)器人及其工作環(huán)境看成是一個(gè)系統(tǒng)，多機(jī)器人處于它們各自的起始點(diǎn)時(shí)，稱該系統(tǒng)處于初始狀態(tài)；當(dāng)它們處于各自的目標(biāo)點(diǎn)時(shí)，稱該系統(tǒng)處于目標(biāo)狀態(tài)。多機(jī)器人的路徑規(guī)劃就是在該系統(tǒng)的這兩個(gè)狀態(tài)間建立一串合理的狀態(tài)變遷。這一狀態(tài)變遷過程可能會(huì)歷經(jīng)許多狀態(tài)，如果在狀態(tài)變遷過程中，路徑規(guī)劃算法控制不好各狀態(tài)間的轉(zhuǎn)移關(guān)系，就會(huì)導(dǎo)致系統(tǒng)紊亂，出現(xiàn)機(jī)器人間的碰撞、找不到路徑等惡性后果，使任務(wù)失敗。所以這就對(duì)算法的可靠性和完備性提出了挑戰(zhàn)。為了很好地克服這一困難，需要對(duì)系統(tǒng)的各種可能狀態(tài)建模，分析它們相互間的關(guān)系，建立有限狀態(tài)自動(dòng)機(jī)模型或Petri網(wǎng)模型，并以此為指導(dǎo)，按照軟件工程的思想，構(gòu)造恰當(dāng)?shù)乃惴ㄝ斎雭韺?duì)算法的可靠性進(jìn)行檢驗(yàn)。

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

7)魯棒性和學(xué)習(xí) 魯棒性對(duì)于多機(jī)器人系統(tǒng)非常重要。因?yàn)樵S多應(yīng)用，如路徑規(guī)劃要求連續(xù)的作業(yè)、系統(tǒng)中的單個(gè)機(jī)器人出現(xiàn)故障或被破壞，要求機(jī)器人利用剩余的資源仍然能夠完成任務(wù)。學(xué)習(xí)是在線適應(yīng)特定的任務(wù)。雖然通用的系統(tǒng)非常有用，但將它用于特定應(yīng)用上時(shí)，通常需要調(diào)整一些參數(shù)。具有在線調(diào)整相關(guān)參數(shù)的能力是非常吸引人的，這在將體系結(jié)構(gòu)轉(zhuǎn)移到其他應(yīng)用時(shí)可以節(jié)省許多工作。尤其是多機(jī)器人系統(tǒng)中機(jī)器人的自身學(xué)習(xí)和相互間的學(xué)習(xí)能夠大大提高整個(gè)系統(tǒng)的效率和系統(tǒng)的穩(wěn)定性。

8）最優(yōu)化 對(duì)動(dòng)態(tài)環(huán)境有優(yōu)化反應(yīng)。由于有些應(yīng)用領(lǐng)域涉及的是動(dòng)態(tài)的環(huán)境條件，具有根據(jù)條件優(yōu)化系統(tǒng)的反應(yīng)能力成為能否成功的關(guān)鍵。

5 結(jié)束語

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

總之，多機(jī)器人路徑規(guī)劃設(shè)計(jì)和實(shí)現(xiàn)是一項(xiàng)極其復(fù)雜的系統(tǒng)工程，展望其能在結(jié)合計(jì)算智能方法，如差分進(jìn)化、遺傳算法、粒子群算法、免疫算法、模糊邏輯算法、BP網(wǎng)絡(luò)、人工勢(shì)場的改進(jìn)、模擬退火和環(huán)境建模方法等方面取得新的突破。

參考文獻(xiàn)：

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

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

[3]譚民，王碩，曹志強(qiáng).多機(jī)器人系統(tǒng)[M].北京：清華大學(xué)出版社，2005：6-81.

[4]薄喜柱，洪炳熔.動(dòng)態(tài)環(huán)境下多移動(dòng)機(jī)器人路徑規(guī)劃的一種新方法[J].機(jī)器人，2001，23（5）：407-410.

[5]顧國昌，李亞波.基于總體勢(shì)減小的動(dòng)態(tài)調(diào)度技術(shù)解決多機(jī)器人的路徑規(guī)劃[J].機(jī)器人，2001，23（2）：171-174.

[6]孫樹棟，林茂.基于遺傳算法的多移動(dòng)機(jī)器人協(xié)調(diào)路徑規(guī)劃[J].自動(dòng)化學(xué)報(bào)，2000，26（5）：672-676.

[7]周明，孫樹棟，彭炎午.基于遺傳算法的多機(jī)器人系統(tǒng)集中協(xié)調(diào)式路徑規(guī)劃[J].航空學(xué)報(bào)，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]朱慶保.全局未知環(huán)境下多機(jī)器人運(yùn)動(dòng)螞蟻導(dǎo)航算法[J].軟件學(xué)報(bào)，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]高陽，陳世福，陸鑫.強(qiáng)化學(xué)習(xí)研究綜述[J].自動(dòng)化學(xué)報(bào)，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]張芳，顏國正，林良明.基于再勵(lì)學(xué)習(xí)的多移動(dòng)機(jī)器人協(xié)調(diào)避障路徑規(guī)劃方法[J].計(jì)算機(jī)工程與應(yīng)用，2003，39（3）：80-83.

[14]王醒策，張汝波，顧國昌.多機(jī)器人動(dòng)態(tài)編隊(duì)的強(qiáng)化學(xué)習(xí)算法研究[J].計(jì)算機(jī)研究與發(fā)展，2003，40（10）：1444-1450.

[15]宋一然.基于強(qiáng)化學(xué)習(xí)的多機(jī)器人路徑規(guī)劃方法[J].莆田學(xué)院學(xué)報(bào)，2006，13（2）：38-41.

[16]韓學(xué)東，洪炳熔.基于人工神經(jīng)網(wǎng)絡(luò)的多機(jī)器人協(xié)作學(xué)習(xí)研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2002，23（6）：1-3.

[17]唐振民，趙春霞，楊靜宇，等.基于動(dòng)態(tài)規(guī)劃思想的多機(jī)器人路徑規(guī)劃[J].南京理工大學(xué)學(xué)報(bào)，2003，27（5）：610-615.

[18]孫茂相，周明，王艷紅，等.多移動(dòng)機(jī)器人實(shí)時(shí)最優(yōu)運(yùn)動(dòng)規(guī)劃[J].控制與決策，1998，

13（2）：125-130.

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

[20]沈捷，費(fèi)樹岷，鄭波.多移動(dòng)機(jī)器人保持隊(duì)形路徑規(guī)劃[J].東南大學(xué)學(xué)報(bào)，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ī)器人系統(tǒng)中的動(dòng)態(tài)避碰規(guī)劃[J].計(jì)算機(jī)工程，2003，29(17):

79-81，104.

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

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

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

[26]景興建，王越超，談大龍.基于人工協(xié)調(diào)場的多移動(dòng)機(jī)器人實(shí)時(shí)協(xié)調(diào)避碰規(guī)劃[J].控制理論與應(yīng)用，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]薛宏濤，葉媛媛，沈林成，等.多智能體系統(tǒng)體系結(jié)構(gòu)及協(xié)調(diào)機(jī)制研究綜述[J].機(jī)器人，2001，23（1）：85-90.

[30]周風(fēng)余，李貽斌，宋銳，等.基于混合式多智能體系統(tǒng)的協(xié)作多機(jī)器人系統(tǒng)研究[J].山東大學(xué)學(xué)報(bào):工學(xué)版，2005，35(1):82-87.

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

[32]陳雪江.基于強(qiáng)化學(xué)習(xí)的多機(jī)器人協(xié)作機(jī)制研究[D].杭州：浙江工業(yè)大學(xué)，2004.

篇（5）

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

一、路徑規(guī)劃的意義

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

二、白車身焊接機(jī)器人焊接路徑規(guī)劃

（一）路徑規(guī)劃的基本任務(wù)

現(xiàn)代化工業(yè)生產(chǎn)的主要目標(biāo)是為了獲得較高的制造質(zhì)量、取得較高的生產(chǎn)率，而付出較低的生產(chǎn)成本，這是現(xiàn)代企業(yè)提高自身競爭力的重要手段，也是路徑規(guī)劃中的主要任務(wù)之一，而在路徑規(guī)劃的過程中要想保證焊接質(zhì)量主要取決于以下兩點(diǎn)：

第一，最大程度的使用機(jī)器人工位。使用機(jī)器人工位能夠有效降低工人的勞動(dòng)強(qiáng)度，減少人為錯(cuò)誤幾率，提高焊接的準(zhǔn)確性，保證焊接的順利進(jìn)行，從而保證焊接的穩(wěn)定性。

第二，要完成所有的焊接點(diǎn)，保證焊接的工藝參數(shù)。

要想實(shí)現(xiàn)較低的制造成本就是最大化的利用現(xiàn)有資源，提高機(jī)器人的工作效率，縮短機(jī)器人工位的生產(chǎn)周期，減少機(jī)器人的使用數(shù)量。路徑規(guī)劃的重要方向就是提高生產(chǎn)率，保證生產(chǎn)環(huán)節(jié)的順利進(jìn)行，縮短生產(chǎn)周期，提高生產(chǎn)率。

（二）路徑規(guī)劃

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

（三）遺傳算法

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

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

第一，白車身中所需要焊接的焊接點(diǎn)眾多。

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

第三，在解答相關(guān)問題時(shí)需要運(yùn)用數(shù)學(xué)方法。

第四，因?yàn)榉桨缸罱K應(yīng)用于企業(yè)，所以數(shù)學(xué)方法最好要簡潔明了，便于學(xué)習(xí)。

綜上，在路徑研究時(shí)需要運(yùn)用遺傳算法，主要優(yōu)勢(shì)在于：

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

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

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

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

三、路徑規(guī)劃的仿真

（一）仿真系統(tǒng)的各要素

路徑仿真系統(tǒng)一般要具有以下幾個(gè)基本要素：

第一，對(duì)仿真問題的描述。模型和仿真運(yùn)行控制共同組成了一個(gè)仿真系統(tǒng)，而一個(gè)特定的模型又是由一個(gè)參數(shù)和一組參數(shù)值構(gòu)成。例如白車身點(diǎn)焊機(jī)器人焊接路徑的參數(shù)模型一般包括家具模型、機(jī)器人模型、側(cè)圍模型，在這基礎(chǔ)之上還加入了具體的參數(shù)值，就形成了特定的模型。

第二，行為產(chǎn)生器。模型確定以后就要對(duì)模型進(jìn)行試驗(yàn)，這是一套試驗(yàn)的軟件，行為產(chǎn)生器可以生成一組根據(jù)時(shí)間變化的數(shù)據(jù)，這類數(shù)據(jù)是仿真的物資基礎(chǔ)。

第三，模型行為及對(duì)行為的處理。

模型行為可以大致分為三種：軌跡行為、結(jié)構(gòu)行為以及點(diǎn)行為。

仿真系統(tǒng)中都要獲取軌跡行為，這些行為的獲取主要是根據(jù)時(shí)間的推移而產(chǎn)生的。

（二）仿真軟件的選擇

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

四、小結(jié)

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

參考文獻(xiàn)：

篇（6）

中圖分類號(hào)：TP242 文獻(xiàn)標(biāo)志碼：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

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

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

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

1 道路環(huán)境建模

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

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

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

中心線上一點(diǎn)的切向量和法向量則可以表示成：

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

2 RRT算法原理

基本的RRT算法如圖2所示，RRT算法以給定的起始點(diǎn)為隨機(jī)樹根節(jié)點(diǎn)，根據(jù)當(dāng)前環(huán)境快速有效地搜索可行域空間，通過隨機(jī)采樣點(diǎn)，將搜索導(dǎo)向空白區(qū)域并增加隨機(jī)樹的葉節(jié)點(diǎn)直至目標(biāo)點(diǎn)區(qū)域，從而生成從起始點(diǎn)到目標(biāo)點(diǎn)的路徑.

算法的一般步驟如下：

1）首先通過environment（）函數(shù)建立環(huán)境數(shù)據(jù)模型，初始化各項(xiàng)參數(shù)；

2） 通過while循環(huán)來判斷樹節(jié)點(diǎn)是否達(dá)到目標(biāo)點(diǎn)goal范圍內(nèi)，若沒有，則開始擴(kuò)展點(diǎn).先生成隨機(jī)采樣點(diǎn)Prand，在樹節(jié)點(diǎn)上通過函數(shù)Nearest（）選擇距離Prand最近的樹節(jié)點(diǎn)作為擴(kuò)展節(jié)點(diǎn)Pnear，通過擴(kuò)展函數(shù)New得到新的樹節(jié)點(diǎn)Tnew，并將其添加到隨機(jī)樹上，直到循環(huán)終止.

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

原算法主體程序如下：

如圖3所示，傳統(tǒng)的RRT算法應(yīng)用到車輛路徑規(guī)劃中存在以下問題：

1）由于隨機(jī)采樣點(diǎn)隨機(jī)性大，導(dǎo)致搜索空間中有過多的冗余搜索，表現(xiàn)為搜索樹布滿了道路環(huán)境空間；

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

3）路徑在靠近障礙時(shí)才開始避障，對(duì)于運(yùn)動(dòng)中的汽車會(huì)造成失穩(wěn)或者與障礙物發(fā)生碰撞.

道路長度/m

3 RRT算法的改進(jìn)

3.1 期望路徑模型

針對(duì)原RRT算法表現(xiàn)出來的問題，提出了一種隨機(jī)采樣點(diǎn)高斯分布的改進(jìn)RRT算法.根據(jù)汽車行駛環(huán)境不同，設(shè)計(jì)了兩種期望路徑模型.

3.1.1 直道模型

駕駛經(jīng)驗(yàn)豐富的駕駛員期望的避障路徑模型如圖4（a）所示.期望路徑以函數(shù)Epz表示，其中各段均為直線段，start為起始點(diǎn)，goal為目標(biāo)點(diǎn).

提前避障在車輛避障路徑規(guī)劃中是必要的，故在模型中需要添加提前避障距離S，并根據(jù)車速調(diào)整大小.設(shè)V為當(dāng)前車速，tc為換道時(shí)間，通常完成換道時(shí)間tc為1～2 s，ΔS為自定義安全提前量.

對(duì)于車速為V的汽車其剎車距離

則提前避障距離

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

期望路徑只是粗略的路徑模型，在此基礎(chǔ)上進(jìn)行平滑得出的路徑并不能滿足汽車安全穩(wěn)定行駛的要求.因此采用RRT算法進(jìn)行路徑尋優(yōu)搜索.為了使隨機(jī)采樣點(diǎn)分布在期望路徑周圍，利用高斯分布函數(shù)生成的點(diǎn)集中在其均值周圍的特點(diǎn)，結(jié)合期望路徑函數(shù)則可以實(shí)現(xiàn)這一目的.在道路坐標(biāo)系下隨機(jī)采樣點(diǎn)的高斯分布概率函數(shù)為：

令μ=Epz（x），則可以得到如圖4（b）所示的隨機(jī)采樣點(diǎn)分布趨勢(shì)圖.

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

道路長度/m（b）隨機(jī)采樣點(diǎn)高斯分布

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

旋轉(zhuǎn)角度：

3.1.2 彎道模型

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

隨機(jī)采樣點(diǎn)在fw各段函數(shù)區(qū)間的分布同直道的處理相同，從而可以得到如圖5（b）所示的分布趨勢(shì)圖.

3.2 約束條件

要使一條規(guī)劃出來的路徑有效地應(yīng)用于汽車運(yùn)動(dòng)，即路徑可跟蹤，則規(guī)劃路徑時(shí)必須滿足道路環(huán)境約束.首先，隨機(jī)樹節(jié)點(diǎn)的生成要滿足道路環(huán)境約束，設(shè)Bleft，Bright分別為道路的左右邊界，則樹節(jié)點(diǎn)位置坐標(biāo)要滿足：

考慮到汽車是具有幾何形體的，設(shè)其車寬為D，則上述y方向的約束變?yōu)椋?/p>

假定汽車質(zhì)心沿著規(guī)劃的路徑運(yùn)動(dòng)，為了保證行駛過程中的穩(wěn)定性，規(guī)劃出的路徑的曲率變化不能過大.若在實(shí)際情況下前輪最大轉(zhuǎn)角為θmax，則路徑中子節(jié)點(diǎn)與其父節(jié)點(diǎn)的連線和父節(jié)點(diǎn)與其父節(jié)點(diǎn)的連線之間的夾角β必須滿足β

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

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

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

3.3 啟發(fā)式搜索

原算法在擴(kuò)展隨機(jī)樹時(shí)，由于缺乏導(dǎo)向機(jī)制，算法的收斂速度在一定程度上受到了影響，為了提高算法計(jì)算速度，引入啟發(fā)式機(jī)制來對(duì)隨機(jī)采樣點(diǎn)以及隨機(jī)樹節(jié)點(diǎn)的選擇進(jìn)行處理.采樣點(diǎn)Prand在隨機(jī)生成過程中會(huì)以一定概率ρ0選擇目標(biāo)點(diǎn)，從而將隨機(jī)樹節(jié)點(diǎn)向目標(biāo)點(diǎn)引導(dǎo)，通常ρ0=0.1.

其中，GaussRand（）為隨機(jī)采樣點(diǎn)生成函數(shù).

另外，在選擇Pnear時(shí)不再單獨(dú)以距離Prand最近作為選擇標(biāo)準(zhǔn)，而是以隨機(jī)樹節(jié)點(diǎn)的擇優(yōu)系數(shù)Ch來決定，Pnear確定為Ch值最小所對(duì)應(yīng)的樹節(jié)點(diǎn).

其中ωi，ωj為權(quán)重系數(shù)，且ωi+ωj=1；Dpr為樹節(jié)點(diǎn)到Prand的距離，Dg為樹節(jié)點(diǎn)到目標(biāo)點(diǎn)goal的距離.當(dāng)ωj>ωi時(shí)，選擇出的Pnear具有向目說憧拷的趨勢(shì).通過以上啟發(fā)式的處理，使得算法更快地收斂，減少計(jì)算時(shí)間.

3.4 平滑處理

RRT算法規(guī)劃出來的路徑通常會(huì)存在小范圍內(nèi)的曲折現(xiàn)象，路徑并不連續(xù).為了使得路徑能夠滿足汽車在運(yùn)動(dòng)時(shí)的穩(wěn)定性和安全性要求，需要對(duì)規(guī)劃出來的路徑進(jìn)行光滑處理.B樣條在處理路徑光滑時(shí)能夠不改變整個(gè)路徑形狀而進(jìn)行局部調(diào)整[16]，利用B樣條這一特性，來對(duì)算法所規(guī)劃出來的路徑進(jìn)行插值擬合，從而達(dá)到光滑路徑的目的，通常所采用的為3次B樣條曲線.

當(dāng)有m+1個(gè)控制頂點(diǎn)Pi（i=0，1，…，m）時(shí)，3次B樣條曲線表示為：

3.5 算法流程

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

算法的實(shí)現(xiàn)過程如下：

1）初始化階段，首先通過environment（）函數(shù)建立道路環(huán)境模型，根據(jù)現(xiàn)有的環(huán)境模型，以expect（）函數(shù)建立期望路徑模型.

2） 路徑求解階段，進(jìn)入while循環(huán)來判斷樹節(jié)點(diǎn)是否達(dá)到目標(biāo)點(diǎn)goal范圍內(nèi)，若沒有，則開始擴(kuò)展點(diǎn).隨機(jī)采樣點(diǎn)Prand通過Pick（）函數(shù)在goal和GaussRand（）函數(shù)所生成的點(diǎn)之間進(jìn)行概率選擇；根據(jù)當(dāng)前Prand計(jì)算樹節(jié)點(diǎn)的擇優(yōu)系數(shù)Ch，并由Fitbest（）函數(shù)得出Pnear；通過函數(shù)New在Pnear的基礎(chǔ)上擴(kuò)展出新節(jié)點(diǎn)Tnew，當(dāng)新節(jié)點(diǎn)滿足約束函數(shù)constraint（）時(shí)，新節(jié)點(diǎn)則添加到整個(gè)隨機(jī)樹Tree上，否則，返回循環(huán)重新尋點(diǎn)直到其終止.

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

4 仿真實(shí)驗(yàn)驗(yàn)證

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

4.1 規(guī)劃時(shí)間的影響參數(shù)分析

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

4.2 規(guī)劃路徑對(duì)比

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

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

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

3） 原RRT算法在靠近障礙時(shí)才開始避障，改進(jìn)RRT算法能夠?qū)崿F(xiàn)提前避障，并且根據(jù)車速不同自動(dòng)調(diào)節(jié)避障提前量，這對(duì)安全行駛很重要.

4.3 路徑跟隨驗(yàn)證

對(duì)一條規(guī)劃出來的路徑，需要驗(yàn)證其有效性，即路徑的跟隨性，本文采用路徑跟隨時(shí)主車的側(cè)向加速度曲線監(jiān)測路徑的穩(wěn)定性，跟隨速度20 m/s.直道和彎道仿真結(jié)果分別如圖10、圖11所示.

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

5 結(jié) 論

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

參考文獻(xiàn)

[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] 肖浩， 宋曉琳， 曹昊天. 基于危險(xiǎn)斥力場的自動(dòng)駕駛汽車主動(dòng)避撞局部路徑規(guī)劃[J]. 工程設(shè)計(jì)學(xué)報(bào)， 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ìn)蟻群算法的搜索機(jī)器人路徑規(guī)劃[J]. 吉林大學(xué)學(xué)報(bào)：工學(xué)版， 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] 吳乙萬，黃智.基于動(dòng)態(tài)虛擬障礙物的智能車輛局部路徑規(guī)劃方法[J].湖南大學(xué)學(xué)報(bào)：自然科學(xué)，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）

中圖分類號(hào)：P208 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9599 （2013） 02-0000-02

1 概述

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

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

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

2 技術(shù)實(shí)現(xiàn)途徑研究

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

車輛路線優(yōu)化問題一般可根據(jù)空間特性和時(shí)間特性分為車輛路線規(guī)劃問題和車輛調(diào)度問題。當(dāng)不考慮時(shí)間要求，僅根據(jù)空間位置安排車輛的線路時(shí)稱為車輛線路或車輛路徑規(guī)劃問題（VRP）。當(dāng)考慮時(shí)間要求安排運(yùn)輸線路時(shí)稱為車輛調(diào)度問題（VSP）。本文不考慮時(shí)間要求，主要針對(duì)第一類VRP問題，提出相應(yīng)的技術(shù)實(shí)現(xiàn)方案研究。

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

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

本文主要基于ArcObjects的網(wǎng)絡(luò)分析和地圖展示等組件進(jìn)行二次開發(fā)，同時(shí)對(duì)其提供的車輛路徑規(guī)劃算法進(jìn)行了拓展性研究。

3 功能模塊設(shè)計(jì)方案

3.1 軟件架構(gòu)設(shè)計(jì)

系統(tǒng)建設(shè)遵循SOA架構(gòu)，由數(shù)據(jù)資源層、組件層、服務(wù)層和表現(xiàn)層組成。數(shù)據(jù)資源層包括各種數(shù)據(jù)庫、關(guān)系型數(shù)據(jù)庫和空間數(shù)據(jù)庫引擎ArcSDE，實(shí)現(xiàn)對(duì)物流業(yè)務(wù)數(shù)據(jù)的存儲(chǔ)和管理；組件層包括接口協(xié)議、GIS組件、其他中間件；服務(wù)層實(shí)現(xiàn)計(jì)算功能，接受表現(xiàn)層的請(qǐng)求進(jìn)行計(jì)算；表現(xiàn)層采用多種形式展現(xiàn)分析結(jié)果。

3.2 軟件功能設(shè)計(jì)

本系統(tǒng)是物流業(yè)務(wù)管理系統(tǒng)的一部分，主要提供歷史數(shù)據(jù)管理模塊、線路優(yōu)化分析模塊、地圖操作模塊，同時(shí)提供與其他相關(guān)業(yè)務(wù)系統(tǒng)的擴(kuò)展功能。

（1）線路優(yōu)化分析模塊

線路優(yōu)化分析模塊是系統(tǒng)的關(guān)鍵，提供兩種分析結(jié)果：一種是基于AO自帶的網(wǎng)絡(luò)分析模塊設(shè)計(jì)，計(jì)算分析結(jié)果；另一種是歷次根據(jù)具體路況等信息的實(shí)際調(diào)度結(jié)果。

實(shí)際調(diào)度結(jié)果來自車輛GPS監(jiān)控?cái)?shù)據(jù)，并將實(shí)際調(diào)度結(jié)果作為輸入，用來校正線路優(yōu)化分析方法，最后生成最優(yōu)路徑規(guī)劃。

（2）地圖展示模塊

地圖展示模塊，在配送交通網(wǎng)絡(luò)圖上展示道路基本信息、周邊環(huán)境、倉庫及客戶地點(diǎn)、車輛位置信息等。同時(shí)將各種車輛路徑規(guī)劃分析結(jié)果以地圖形式展示。基于ArcGIS提供的基礎(chǔ)地圖操作功能，實(shí)現(xiàn)地圖縮放、瀏覽、鷹眼、圖層控制、測量、選擇、標(biāo)注、信息查詢等功能。

（3）歷史數(shù)據(jù)管理模塊

歷史數(shù)據(jù)管理主要存儲(chǔ)歷史客戶訂單數(shù)據(jù)、實(shí)時(shí)路況信息、歷史路徑規(guī)劃分析結(jié)果、實(shí)際運(yùn)輸路徑等，可支持對(duì)歷史數(shù)據(jù)的查詢和修改。

（4）擴(kuò)展功能模塊

提供與其他相關(guān)業(yè)務(wù)系統(tǒng)、車載GPS設(shè)備、車輛監(jiān)控設(shè)備等的接口，便于系統(tǒng)的擴(kuò)展。

3.4 數(shù)據(jù)庫設(shè)計(jì)

本系統(tǒng)中涉及的數(shù)據(jù)庫主要包括元數(shù)據(jù)庫、基礎(chǔ)地理空間數(shù)據(jù)庫、業(yè)務(wù)數(shù)據(jù)庫、分析模型數(shù)據(jù)庫、歷史數(shù)據(jù)庫等。

4 結(jié)束語

本文將物流車輛路徑規(guī)劃理論算法的研究與地理信息系統(tǒng)的網(wǎng)絡(luò)分析模塊相結(jié)合，經(jīng)過二次開發(fā)，形成了用于實(shí)際的物流車輛路徑規(guī)劃信息系統(tǒng)。另外車輛路徑規(guī)劃設(shè)計(jì)約束較多，本文中不考慮時(shí)間要求，僅根據(jù)空間位置安排車輛的線路，同時(shí)不考慮裝箱問題。

車輛路徑規(guī)劃問題是現(xiàn)代物流業(yè)的熱點(diǎn)問題，但是基本停留在理論算法層面，隨著技術(shù)的不斷進(jìn)步，必然出現(xiàn)考慮更多約束的先進(jìn)算法，希望將這些算法真正與現(xiàn)代物流業(yè)結(jié)合，那將會(huì)是一個(gè)跨越式的進(jìn)步。

篇（8）

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

0 前言

移動(dòng)機(jī)器人的實(shí)現(xiàn)涉及自動(dòng)控制、智能、機(jī)械等多種學(xué)科。它通常被應(yīng)用在醫(yī)療領(lǐng)域、工業(yè)領(lǐng)域等方面。從整體角度來講，移動(dòng)機(jī)器人的應(yīng)用促進(jìn)了生產(chǎn)效率的顯著提升。路徑規(guī)劃技術(shù)是移動(dòng)機(jī)器人的關(guān)鍵技術(shù)之一，研究該技術(shù)具有一定的現(xiàn)實(shí)意義。

1 路徑規(guī)劃技術(shù)的作用

將路徑規(guī)劃技術(shù)應(yīng)用在移動(dòng)機(jī)器人中，能夠產(chǎn)生的作用主要包含以下幾種：

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

2 移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)綜述

移動(dòng)機(jī)器人的路徑規(guī)劃技術(shù)主要包含以下幾種：

2.1 局部路徑規(guī)劃方面

在局部路徑規(guī)劃方面，能夠被應(yīng)用在移動(dòng)機(jī)器人中的技術(shù)主要包含以下幾種：

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

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

（3）遺傳路徑規(guī)劃技術(shù)。這種路徑規(guī)劃技術(shù)建立在自然遺傳機(jī)制等理論的基礎(chǔ)上。這種技術(shù)通過變異、選擇以及交叉對(duì)控制機(jī)構(gòu)的正確計(jì)算程序進(jìn)行合理編制，進(jìn)而實(shí)現(xiàn)數(shù)學(xué)方式基礎(chǔ)上生物進(jìn)化過程的合理模擬。當(dāng)移動(dòng)機(jī)器人的適應(yīng)度函數(shù)為正數(shù)時(shí)，允許適應(yīng)度函數(shù)具有不連續(xù)或不可導(dǎo)特點(diǎn)。由于這種路徑規(guī)劃技術(shù)不涉及梯度信息，因此其能夠更好地解決移動(dòng)機(jī)器人在實(shí)際運(yùn)動(dòng)過程中遇到的問題。遺傳路徑規(guī)劃技術(shù)的應(yīng)用優(yōu)勢(shì)在于，它能夠?qū)崿F(xiàn)跟蹤與規(guī)劃的同時(shí)進(jìn)行，因此，遺傳路徑規(guī)劃技術(shù)通常被應(yīng)用在具有時(shí)變特點(diǎn)的未知環(huán)境中。

2.2 全局路徑規(guī)劃方面

在該方面，可以被應(yīng)用在移動(dòng)機(jī)器人中的技術(shù)主要包含以下幾種：

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

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

（3）拓?fù)渎窂揭?guī)劃技術(shù)。這種規(guī)劃技術(shù)是指，將移動(dòng)機(jī)器人的移動(dòng)范圍，即規(guī)劃區(qū)域分成多個(gè)具有拓?fù)涮卣鞯淖涌臻g，然后利用不同子空間之間的連通性完成拓?fù)渚W(wǎng)絡(luò)的構(gòu)建。當(dāng)該網(wǎng)絡(luò)構(gòu)建完成后，直接從網(wǎng)絡(luò)中找出能夠使得機(jī)器人順利從起點(diǎn)移動(dòng)到終點(diǎn)的拓?fù)渎窂剑瑢⑺玫耐負(fù)渎窂阶鳛閰⒖家罁?jù)完成幾何路徑的計(jì)算。這種規(guī)劃技術(shù)的劣勢(shì)主要表現(xiàn)為其拓?fù)渚W(wǎng)絡(luò)的構(gòu)建過程較為復(fù)雜。但這種規(guī)劃技術(shù)可以實(shí)現(xiàn)移動(dòng)機(jī)器人搜索空間的有效縮小[5]。

3 結(jié)論

路徑規(guī)劃技術(shù)主要分為局部規(guī)劃和全局規(guī)劃兩方面。這兩方面分別包含人工勢(shì)場路徑規(guī)劃技術(shù)以及神經(jīng)網(wǎng)絡(luò)路徑規(guī)劃技術(shù)等。應(yīng)用這些規(guī)劃技術(shù)之后，移動(dòng)機(jī)器人可以在避開障礙物的基礎(chǔ)上，順利完成起點(diǎn)到終點(diǎn)最優(yōu)運(yùn)行軌跡的運(yùn)動(dòng)。

參考文獻(xiàn)：

[1]朱大奇，顏明重.移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)綜述[J].控制與決策，2010（07）：961-967.

[2]張捍東，鄭睿，岑豫皖.移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)的現(xiàn)狀與展望[J].系統(tǒng)仿真學(xué)報(bào)，2005（02）：439-443.

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

篇（9）

中圖分類號(hào)： TN911.1?34； TP312 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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]是圖論中網(wǎng)絡(luò)分析的經(jīng)典問題，近年來，隨著路徑搜索技術(shù)的不斷發(fā)展，已經(jīng)涌現(xiàn)出很多成熟的路徑規(guī)劃算法，比如，基于圖論的Dijkstra算法[2?3]，以及關(guān)于人工智能領(lǐng)域的啟發(fā)式搜索算法和動(dòng)態(tài)規(guī)劃算法等。A*啟發(fā)式搜索算法作為人工智能領(lǐng)域的重要組成部分，其針對(duì)網(wǎng)格數(shù)據(jù)有著更高的運(yùn)算效率，而且利用啟發(fā)信息大幅度提高了搜索速度。這種全新的啟發(fā)式搜索算法[4]將會(huì)極大地改變現(xiàn)有的交通管理與服務(wù)模式。

1 A*算法原理

傳統(tǒng)的BFS算法的評(píng)估函數(shù)只考慮當(dāng)前點(diǎn)與終點(diǎn)的距離，其策略是選擇與終點(diǎn)最近的點(diǎn)進(jìn)行搜索。而Dijkstra算法則只關(guān)注當(dāng)前點(diǎn)與起點(diǎn)的距離，選擇與起點(diǎn)最近的點(diǎn)開始搜索。A*算法[5]則是將二者結(jié)合起來，其啟發(fā)函數(shù)采用如下的計(jì)算公式：

式中：就是A*算法[5]對(duì)每個(gè)節(jié)點(diǎn)的評(píng)估函數(shù)[2]，其包含兩部分信息：是從起點(diǎn)到當(dāng)前節(jié)點(diǎn)的實(shí)際代價(jià)，也就是從起點(diǎn)到當(dāng)前節(jié)點(diǎn)的移動(dòng)距離；相鄰的兩個(gè)點(diǎn)的移動(dòng)距離是1，當(dāng)前點(diǎn)距離起點(diǎn)越遠(yuǎn)，這個(gè)值就越大。是從當(dāng)前節(jié)點(diǎn)到終點(diǎn)的距離評(píng)估值，這是一個(gè)從當(dāng)前節(jié)點(diǎn)到終點(diǎn)的移動(dòng)距離的估計(jì)值。

A*算法的搜索過程需要兩個(gè)表：一個(gè)是OPEN表，存放當(dāng)前已經(jīng)被發(fā)現(xiàn)但是還沒有搜索過的節(jié)點(diǎn)；另一個(gè)是CLOSE表，存放已經(jīng)搜索過的節(jié)點(diǎn)，具體的算法流程圖如圖1所示。

1.1 常用的距離評(píng)估函數(shù)

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

1.1.1 曼哈頓距離

從數(shù)學(xué)上描述，曼哈頓距離是兩個(gè)點(diǎn)在各個(gè)坐標(biāo)軸上的距離差值的總和，維幾何空間中曼哈頓距離的數(shù)學(xué)描述為：

對(duì)于二維平面上的兩個(gè)點(diǎn)和，其曼哈頓距離為：

即歐式幾何平面距離為在直角坐標(biāo)系中兩個(gè)坐標(biāo)軸上的投影距離和。

1.1.2 歐式幾何平面距離

歐式幾何平面距離（Euclidean distance）又稱為歐式距離或歐幾里得距離[7]，其數(shù)學(xué)定義是維空間中兩個(gè)點(diǎn)之間的真實(shí)距離（幾何距離），其數(shù)學(xué)符號(hào)可以描述為：

對(duì)于二維平面上的兩個(gè)點(diǎn)和其歐式幾何平面距離為：

即平面幾何中兩點(diǎn)之間的幾何距離。

1.1.3 切比雪夫距離

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

特別情況下，對(duì)于平面上的兩個(gè)點(diǎn)和，其切比雪夫距離為：

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

1.2 A*算法的實(shí)現(xiàn)

A*算法實(shí)現(xiàn)的關(guān)鍵在于維護(hù)OPEN表和CLOSE表，其中對(duì)于OPEN表的主要操作就是查詢最小的節(jié)點(diǎn)以及刪除節(jié)點(diǎn)，因此考慮在算法實(shí)現(xiàn)時(shí)將OPEN表[7]設(shè)計(jì)為有序表。這樣在OPEN列表存儲(chǔ)數(shù)據(jù)時(shí)就可以自動(dòng)將數(shù)據(jù)按照距離進(jìn)行排序，這樣算法的執(zhí)行效率比較高。A*算法的參數(shù)設(shè)置見表1，參數(shù)的迭代次數(shù)見圖2。

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

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

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

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

搜索效率的對(duì)比結(jié)果如表2所示。

由表2可以看出：當(dāng)?shù)貓D節(jié)點(diǎn)的個(gè)數(shù)和弧的條數(shù)比較多時(shí)，A*算法[5]的搜索效率比Dijkstra算法快很多，當(dāng)節(jié)點(diǎn)數(shù)不斷增多時(shí)，其搜索最短路徑的效率更高。在相同路網(wǎng)和位置信息的條件下進(jìn)行仿真實(shí)驗(yàn)的結(jié)果如圖3所示。

由圖3可以看出，兩種算法在相同障礙物條件下進(jìn)行模擬仿真時(shí)，A*算法的搜索效率和時(shí)間復(fù)雜度要明顯優(yōu)于Dijkstra算法，并對(duì)不同實(shí)驗(yàn)場景下的效率進(jìn)行對(duì)比，結(jié)果如圖4所示。

3 結(jié) 語

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

參考文獻(xiàn)

[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ī)器人路徑規(guī)劃快速算法[J].計(jì)算機(jī)工程與應(yīng)用，2006，42（21）：197?199.

[5] 李大生，劉欣，吳明華，等.基于動(dòng)力學(xué)約束的機(jī)器人無碰運(yùn)動(dòng)規(guī)劃[J].機(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] 李得偉，韓寶明，韓宇.一種逆向改進(jìn)型A*路徑搜索算法[J].系統(tǒng)仿真學(xué)報(bào)，2007，19（22）：5175?5177.

[8] 林丹.一種室內(nèi)清潔機(jī)器人返回路徑規(guī)劃算法[J].重慶科技學(xué)院學(xué)報(bào)（自然科學(xué)版），2009，12（1）：110?113.

篇（10）

中圖分類號(hào)：TP393文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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

隨著傳感器技術(shù)、無線通信、微電子技術(shù)以及嵌入式計(jì)算等技術(shù)的發(fā)展，無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network 簡稱WSN)得到了廣泛應(yīng)用，成為當(dāng)今活躍的研究領(lǐng)域。無線傳感器網(wǎng)絡(luò)是新型的傳感器網(wǎng)絡(luò)，同時(shí)也是一個(gè)多學(xué)科交叉的領(lǐng)域，與當(dāng)今主流無線網(wǎng)絡(luò)技術(shù)一樣，均使用802.15.4的標(biāo)準(zhǔn)，由具有感知能力、通信能力和計(jì)算能力的大量微型傳感器節(jié)點(diǎn)組成，具有低成本、低功耗的優(yōu)點(diǎn)和強(qiáng)大的數(shù)據(jù)獲取和處理能力。

在無線傳感器網(wǎng)絡(luò)的眾多應(yīng)用中,如：國防軍事、環(huán)境監(jiān)測、交通管理、醫(yī)療衛(wèi)生、目標(biāo)跟蹤、物流管理、入侵檢測、交通流量監(jiān)控和勘測應(yīng)用等領(lǐng)域, 監(jiān)測到事件之后需要確定事件發(fā)生的位置，信息融合后得到的相關(guān)數(shù)據(jù)信息如果不包含事件位置信息將毫無意義，只有帶有標(biāo)識(shí)位置信息的傳感數(shù)據(jù)才有實(shí)際的意義。傳感器節(jié)點(diǎn)自身的正確定位是提供事件位置信息的前提, 因此節(jié)點(diǎn)的精確定位基礎(chǔ)而關(guān)鍵[1] 。

1 無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位的分類及基本方法

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

1.1 基于無線傳感器網(wǎng)絡(luò)自身定位系統(tǒng)的分類[1,3-5]

1) 絕對(duì)定位與相對(duì)定位。絕對(duì)定位與物理定位類似，定位結(jié)果是一個(gè)坐標(biāo)位置，如經(jīng)緯度。而相對(duì)定位通常是以傳感區(qū)域某點(diǎn)為參考，建立整個(gè)網(wǎng)絡(luò)的相對(duì)坐標(biāo)系統(tǒng)。

2) 物理定位與符號(hào)定位。經(jīng)緯度就是物理位置；而某個(gè)節(jié)點(diǎn)在某街道的某門牌的建筑物內(nèi)就是符號(hào)位置。一定條件下，物理定位和符號(hào)定位可以相互轉(zhuǎn)換。與物理定位相比，符號(hào)定位在一些特定的應(yīng)用場合更加便于使用。

3) 集中式計(jì)算與分布式計(jì)算定位。集中式計(jì)算是指把所需信息傳送到某個(gè)中心節(jié)點(diǎn)，并在那里進(jìn)行節(jié)點(diǎn)定位計(jì)算的方式；分布式計(jì)算是指依賴節(jié)點(diǎn)間的信息交換和協(xié)調(diào)，由節(jié)點(diǎn)自行計(jì)算的定位方式。

4) 移動(dòng)信標(biāo)與固定信標(biāo)定位。移動(dòng)信標(biāo)節(jié)點(diǎn)是一類裝備了GPS或其它定位裝置的可移動(dòng)節(jié)點(diǎn)，它在移動(dòng)的過程中周期性自己的位置信息。基于移動(dòng)信標(biāo)的未知節(jié)點(diǎn)定位有很多優(yōu)點(diǎn)，如定位成本低，容易達(dá)到很高的定位精度、可實(shí)現(xiàn)分布式定位計(jì)算、易于實(shí)現(xiàn)三維定位等。而固定信標(biāo)節(jié)點(diǎn)是一類裝備了GPS或其它定位裝置的不可移動(dòng)節(jié)點(diǎn)。

1.2 基于距離的節(jié)點(diǎn)坐標(biāo)計(jì)算基本方法

待定位節(jié)點(diǎn)在獲得與鄰近信標(biāo)節(jié)點(diǎn)的距離信息后，通常采用下列方法計(jì)算自身的位置[3]。

1) 三邊測量法：利用網(wǎng)絡(luò)中三個(gè)信標(biāo)節(jié)點(diǎn)的位置坐標(biāo)以及未知節(jié)點(diǎn)到這三個(gè)信標(biāo)節(jié)點(diǎn)的距離，運(yùn)用幾何方法求出未知節(jié)點(diǎn)的坐標(biāo)。

2) 三角測量法：利用網(wǎng)絡(luò)中三個(gè)信標(biāo)節(jié)點(diǎn)的位置坐標(biāo)以及未知節(jié)點(diǎn)為角頂點(diǎn)角邊分別為三個(gè)信標(biāo)節(jié)點(diǎn)的角度，運(yùn)用幾何方法求出未知節(jié)點(diǎn)的坐標(biāo)。

3) 最小二乘估計(jì)法：利用未知節(jié)點(diǎn)的相鄰節(jié)點(diǎn)中的多個(gè)信標(biāo)節(jié)點(diǎn)的位置坐標(biāo)以及它們與未知節(jié)點(diǎn)的距離或角度，運(yùn)用最小均方差估計(jì)方法求出未知節(jié)點(diǎn)的坐標(biāo)。

1.3 常用的測距方法

1) 信號(hào)接收強(qiáng)度（RSSI）測距法

已知發(fā)射功率和天線接收增益，在接收節(jié)點(diǎn)測量信號(hào)接收功率，計(jì)算傳播損耗，使用理論或經(jīng)驗(yàn)的無線電傳播模型由傳播損耗計(jì)算出信源與接收者間的距離。通常使用下列對(duì)數(shù)-常態(tài)分布模型來計(jì)算節(jié)點(diǎn)間的距離[1]。

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

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

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

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

2) 到達(dá)時(shí)間測距法

到達(dá)時(shí)間(TOA)技術(shù)通過測量信號(hào)傳播時(shí)間來測量距離，若電波從信標(biāo)節(jié)點(diǎn)到未知節(jié)點(diǎn)的傳播時(shí)間為t，電波傳播速度為c，則信標(biāo)節(jié)點(diǎn)到未知節(jié)點(diǎn)的距離為t×c。

3) 時(shí)間差測距法

TDOA測距是通過測量兩種不同信號(hào)到達(dá)未知節(jié)點(diǎn)的時(shí)間差，再根據(jù)兩種信號(hào)傳播速度來計(jì)算未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間的距離，通常采用電波和超聲波組合。

4) 到達(dá)角定位法

到達(dá)角(AOA)定位法采用陣列天線或多個(gè)接收器組合來獲取相鄰節(jié)點(diǎn)所處位置的方向，從而構(gòu)成從接收機(jī)到發(fā)射機(jī)的方位線。兩條方位線的交點(diǎn)就是未知節(jié)點(diǎn)的位置。

1.4 典型非測距算法

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

1) DV－h(huán)op算法

為了避免對(duì)節(jié)點(diǎn)間距離的直接測量， Niculescu等人提出了DV－h(huán)op算法[3]。該算法基本思想是：用網(wǎng)絡(luò)中節(jié)點(diǎn)的平均每跳距離和信標(biāo)到待定位節(jié)點(diǎn)之間的跳數(shù)乘積來表示待定位節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)之間的距離，再用三角定位來獲得待定位節(jié)點(diǎn)的位置坐標(biāo)。

2) 質(zhì)心法

質(zhì)心法由南加州大學(xué)Nirupama Bulusu等學(xué)者提出[3]，該算法是未知節(jié)點(diǎn)以所有可收到信號(hào)的信標(biāo)節(jié)點(diǎn)的幾何質(zhì)心作為自己的估計(jì)位置，它是一種基于網(wǎng)絡(luò)連通性的室外節(jié)點(diǎn)定位算法。

3) APIT 算法

一個(gè)未知節(jié)點(diǎn)任選3個(gè)能夠與之通信的信標(biāo)節(jié)點(diǎn)構(gòu)成一個(gè)三角形，并測試自身位置是在這個(gè)三角形內(nèi)部還是在其外部；然后再選擇另外3個(gè)信標(biāo)節(jié)點(diǎn)進(jìn)行同樣的測試，直到窮盡所有的組合或者達(dá)到所需的精度。

4) Amorphous 算法

Amorphous 定位算法[3]采用與 DV-Hop 算法類似的方法獲得距信標(biāo)節(jié)點(diǎn)的跳數(shù)，稱為梯度值。未知節(jié)點(diǎn)收集鄰居節(jié)點(diǎn)的梯度值，計(jì)算關(guān)于某個(gè)信標(biāo)節(jié)點(diǎn)的局部梯度平均值。Amorphous 算法假定預(yù)先知道網(wǎng)絡(luò)的密度，然后離線計(jì)算網(wǎng)絡(luò)的平均每跳距離，最后當(dāng)獲得3個(gè)或更多錨節(jié)點(diǎn)的梯度值后，未知節(jié)點(diǎn)計(jì)算與每個(gè)錨節(jié)點(diǎn)的距離，并使用三邊測量法和最大似然估計(jì)法估算自身位置。

2 基于移動(dòng)信標(biāo)的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)

無論是距離相關(guān)還是距離無關(guān)定位算法，常采用固定信標(biāo)節(jié)點(diǎn)方式測量距離、相對(duì)角度、傳播時(shí)間差及傳播時(shí)間等進(jìn)行節(jié)點(diǎn)定位[1]。通常參與定位的固定信標(biāo)節(jié)點(diǎn)越多, 定位精度將越高。但是信標(biāo)節(jié)點(diǎn)的成本遠(yuǎn)遠(yuǎn)高于普通節(jié)點(diǎn)，當(dāng)定位工作完成后，信標(biāo)節(jié)點(diǎn)將轉(zhuǎn)成普通的傳感器節(jié)點(diǎn)使用。因此信標(biāo)點(diǎn)越多，布設(shè)整個(gè)網(wǎng)絡(luò)的成本將會(huì)增大, 定位算法的計(jì)算負(fù)荷以及通訊負(fù)荷將會(huì)增大[1] ，過多的信標(biāo)節(jié)點(diǎn)將會(huì)造成較大的浪費(fèi)。所以利用移動(dòng)節(jié)點(diǎn)發(fā)出的虛擬坐標(biāo)點(diǎn)進(jìn)行輔助定位的思想將成為節(jié)點(diǎn)定位研究的一個(gè)重要研究方向。

假定整個(gè)WSN由靜止節(jié)點(diǎn)以及移動(dòng)節(jié)點(diǎn)(如撒播節(jié)點(diǎn)完畢的飛機(jī)、運(yùn)動(dòng)的車輛、移動(dòng)的小型機(jī)器人或普通的能移動(dòng)的傳感器節(jié)點(diǎn)等) 兩種類型節(jié)點(diǎn)構(gòu)成。根據(jù)傳感器網(wǎng)絡(luò)的規(guī)模大小, 可以配置一個(gè)或者多個(gè)移動(dòng)節(jié)點(diǎn)。各移動(dòng)節(jié)點(diǎn)均配置一個(gè)GPS接收器用于定位移動(dòng)信標(biāo)節(jié)點(diǎn)本身, 并有足夠的能量自我移動(dòng)或捆綁移動(dòng)機(jī)器人、移動(dòng)車輛或三維空間中的飛機(jī)等工具。移動(dòng)節(jié)點(diǎn)在傳感器區(qū)域內(nèi)按照一定的運(yùn)動(dòng)路徑移動(dòng), 并周期性地發(fā)送坐標(biāo)位置信息, 待定位節(jié)點(diǎn)根據(jù)接收到的坐標(biāo)信息與采用適當(dāng)?shù)亩ㄎ凰惴ㄍ瓿啥ㄎ籟6] 。

近幾年有一些研究者對(duì)移動(dòng)錨節(jié)點(diǎn)路徑規(guī)劃展開研究，提出了一些比較好的路徑規(guī)劃方案。移動(dòng)錨節(jié)點(diǎn)路徑規(guī)劃主要有兩個(gè)目標(biāo)：

1) 移動(dòng)軌跡能夠覆蓋網(wǎng)絡(luò)中的所有未知節(jié)點(diǎn)；

2) 為未知節(jié)點(diǎn)定位提供質(zhì)量好的信標(biāo)點(diǎn)。

如果滿足網(wǎng)絡(luò)節(jié)點(diǎn)均勻分布的條件，規(guī)劃路徑通常采用靜態(tài)規(guī)劃路徑，移動(dòng)錨節(jié)點(diǎn)都按照預(yù)先規(guī)劃的路徑移動(dòng)，不具有根據(jù)節(jié)點(diǎn)分布狀況靈活變化的性能。文獻(xiàn)[7]針對(duì)移動(dòng)錨節(jié)點(diǎn)的路徑規(guī)劃問題利用空間填充線理論提出了SCAN、DOUBLESCAN以及HILBERT路徑規(guī)劃方法，分別如圖1、圖2和圖3所示。在節(jié)點(diǎn)通信距離小和空間填充線密度大的條件下， SCAN路徑比HILBERT路徑的定位結(jié)果準(zhǔn)確。但是在節(jié)點(diǎn)通信距離大、空間填充線密度較小時(shí)，HILBERT路徑明顯優(yōu)于SCAN路徑。

SCAN路徑存在明顯的缺點(diǎn)就是提供了大量共線的信標(biāo)點(diǎn)，HILBERT路徑通過增加移動(dòng)路徑長度解決了信標(biāo)點(diǎn)共線性的問題，只要達(dá)到一定的密度就可以為定位提供優(yōu)質(zhì)的不共線信標(biāo)點(diǎn)。為了解決信標(biāo)點(diǎn)存在共線性的問題，文獻(xiàn)[8]提出了圓形規(guī)劃路徑和S形規(guī)劃路徑方法，如圖4和圖5所示。圓形規(guī)劃路徑完全覆蓋方形網(wǎng)絡(luò)區(qū)域時(shí)必須增加大圓路徑，這很大程度增加了路徑的長度。而圓形的直徑非常大時(shí)，在局部帶來了信標(biāo)點(diǎn)的共線性問題。S形路徑通過引入S形曲線代替直線，解決了信標(biāo)點(diǎn)共線性問題。

而對(duì)于實(shí)際環(huán)境中節(jié)點(diǎn)非均勻分布的情況，文獻(xiàn)[9]提出了提出了寬度優(yōu)先和回溯式貪婪算法。這種方法能夠根據(jù)網(wǎng)絡(luò)信息自適應(yīng)進(jìn)行路徑規(guī)劃，規(guī)劃路徑不再是規(guī)則的圖形，能夠充分利用節(jié)點(diǎn)分布信息覆蓋所有節(jié)點(diǎn)，保證路徑最短，克服了靜態(tài)路徑規(guī)劃的缺點(diǎn)。文獻(xiàn)[10]提出讓一個(gè)攜帶GPS的移動(dòng)信標(biāo)采用隨機(jī)移動(dòng)模型的方式盡量遍歷傳感區(qū)域，然后采用分布式算法為未知節(jié)點(diǎn)定位，該方法結(jié)合了基于測距方法的優(yōu)點(diǎn)，并且無需布置固定的信標(biāo)節(jié)點(diǎn)，節(jié)省了成本開銷，但是由于移動(dòng)信標(biāo)的移動(dòng)模型采用隨機(jī)的方式，難以讓其移動(dòng)范圍覆蓋整個(gè)傳感區(qū)域，從而有些未知節(jié)點(diǎn)無法定位。

3 定位算法的評(píng)價(jià)標(biāo)準(zhǔn)

定位算法設(shè)計(jì)的優(yōu)劣通常以下列幾個(gè)評(píng)價(jià)標(biāo)準(zhǔn)[11]來評(píng)價(jià)：

1）定位精度：一般用誤差值與節(jié)點(diǎn)無線射程的比例表示，是定位技術(shù)首要的評(píng)價(jià)指標(biāo)。

2）定位覆蓋率：指利用定位算法能夠進(jìn)行定位的節(jié)點(diǎn)數(shù)與總的未知節(jié)點(diǎn)個(gè)數(shù)之比，它是評(píng)價(jià)定位算法的另外一個(gè)重要的指標(biāo)。

3）信標(biāo)節(jié)點(diǎn)密度：信標(biāo)節(jié)點(diǎn)占所有節(jié)點(diǎn)的比例或者是單位區(qū)域內(nèi)信標(biāo)節(jié)點(diǎn)的數(shù)目。

4）節(jié)點(diǎn)密度：節(jié)點(diǎn)密度通常以網(wǎng)絡(luò)的平均連通度來表示。

5）功耗：功耗是指傳感器節(jié)點(diǎn)在單位時(shí)間內(nèi)所消耗的能源的數(shù)量。由于傳感器節(jié)點(diǎn)不會(huì)始終在工作的，有時(shí)候會(huì)處于休眠狀態(tài)，但這同樣也會(huì)消耗少量的能量，因此，傳感器節(jié)點(diǎn)的功耗一般會(huì)有兩個(gè)，一個(gè)是工作時(shí)的功耗，另一個(gè)是待機(jī)時(shí)的功耗。

6）成本：包括時(shí)間、空間和費(fèi)用。時(shí)間指一個(gè)系統(tǒng)的安裝、配置和定位所需的時(shí)間。空間包括一個(gè)定位系統(tǒng)或算法所需的基礎(chǔ)設(shè)施和網(wǎng)絡(luò)節(jié)點(diǎn)的數(shù)量、安裝尺寸等。費(fèi)用則包括實(shí)現(xiàn)某種定位系統(tǒng)或算法的基礎(chǔ)設(shè)施、節(jié)點(diǎn)設(shè)備的總費(fèi)用。

7）魯棒性：定位系統(tǒng)和算法必須具有很強(qiáng)的容錯(cuò)性和自適應(yīng)性，能夠通過自身調(diào)整或重構(gòu)糾正錯(cuò)誤、適應(yīng)環(huán)境、減小各種誤差的影響，以提高定位精度。

上述的這些評(píng)價(jià)指標(biāo)不僅是評(píng)價(jià)WSN自身定位系統(tǒng)和算法的標(biāo)準(zhǔn)，也是其設(shè)計(jì)和實(shí)現(xiàn)的優(yōu)化目標(biāo)。

4 結(jié)束語

使用移動(dòng)信標(biāo)節(jié)點(diǎn)來完成WSN所有節(jié)點(diǎn)的定位，就必須要足夠的時(shí)間讓移動(dòng)信標(biāo)節(jié)點(diǎn)遍歷完整個(gè)網(wǎng)絡(luò), 為了減小所有節(jié)點(diǎn)定位所需的時(shí)間以及提高定位效率，如何進(jìn)一步優(yōu)化移動(dòng)信標(biāo)節(jié)點(diǎn)的運(yùn)動(dòng)路徑將成為基于移動(dòng)信標(biāo)的WSN節(jié)點(diǎn)定位技術(shù)更研究的重要方向。

參考文獻(xiàn)：

[1] 孫利民.無線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社,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] 王福豹,史龍,任豐原.無線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法[J].軟件學(xué)報(bào),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] 倪巍,王宗欣.基于接收信號(hào)強(qiáng)度測量的室內(nèi)定位算法[J].復(fù)旦學(xué)報(bào)(自然科學(xué)版),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）

中圖分類號(hào):G642 文獻(xiàn)標(biāo)識(shí)碼:B

1背景

數(shù)據(jù)結(jié)構(gòu)和算法是計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程等相關(guān)專業(yè)的專業(yè)基礎(chǔ)課,其重要性不言而喻,在教學(xué)過程中需要運(yùn)用多種教學(xué)方法,讓學(xué)生領(lǐng)會(huì)算法實(shí)現(xiàn)的過程和本質(zhì),加深對(duì)所學(xué)知識(shí)的理解、記憶和應(yīng)用。在數(shù)據(jù)結(jié)構(gòu)和算法課程教學(xué)中,圖狀結(jié)構(gòu)的教學(xué)是一個(gè)難點(diǎn),特別是涉及到圖的具體應(yīng)用時(shí),更讓學(xué)生難以掌握,本文將圖示教學(xué)法應(yīng)用到數(shù)據(jù)結(jié)構(gòu)中關(guān)于圖狀結(jié)構(gòu)的一個(gè)典型應(yīng)用――最小生成樹問題,給出該教學(xué)方法的基本方法和過程,取得了良好的教學(xué)效果。

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

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

2教學(xué)方法

圖示教學(xué)法就是用各種圖形表示的方法描述問題、引導(dǎo)學(xué)生的思考,增強(qiáng)對(duì)新知識(shí)的記憶,并在教學(xué)中被廣泛使用。最小生成樹屬于網(wǎng)絡(luò)的實(shí)踐應(yīng)用,下面以圖1為例,用圖示教學(xué)法來對(duì)最小生成樹算法進(jìn)行圖示過程分析。

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

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

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

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

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

進(jìn)一步注意到,在所有的當(dāng)前城市中,城市3距離最優(yōu)路段網(wǎng)的距離最短(5),也就是為了使當(dāng)前最優(yōu)路段網(wǎng)(圓圈內(nèi)的城市及連線)與其它城市能夠?qū)崿F(xiàn)連通,且連通后的路段總長度最小,所以當(dāng)前應(yīng)加入城市3(圖2(c))。城市3的加入或許可以使得其它的城市通過該城市為“橋梁”,而縮短城市到最優(yōu)路段網(wǎng)的距離(當(dāng)然這里城市3的加入實(shí)際并沒有使其它城市到最優(yōu)路段網(wǎng)的距離縮小)。同樣的道理,在第4步(圖2(d)),將城市4加入到最優(yōu)路段網(wǎng)中(因?yàn)樵谟嘞碌某鞘兄?城市4到最優(yōu)路段網(wǎng)的距離最小),該城市的加入,也使得城市1以該城市為“橋梁”而到最優(yōu)路段網(wǎng)的距離由原來的19縮短到18(其它路段不變)。第5步將城市6加入到最優(yōu)路段網(wǎng)中(圖2(e)),該城市的加入沒有影響余下的城市(當(dāng)前僅剩一個(gè)城市,即城市5),最后將城市5加入到最優(yōu)路段網(wǎng)中(圖2(f))。得到的最終的最優(yōu)路段網(wǎng)如圖2(h),其路段長度的總和為56(16+5+11+6+18)。

3算法求解

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

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

基于上述分析,不難給出以上算法的實(shí)現(xiàn)描述:

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

(2) 反復(fù)執(zhí)行如下操作:將B[i]中值最小的元素對(duì)應(yīng)的編號(hào)i(即節(jié)點(diǎn)i)放入A中(即修改A[i]為1),然后修改A[j]!=0(j!=i)對(duì)應(yīng)的B[j]和C[j]的值,修改的依據(jù)是:如果B[j]>Li-j,則用B[j]的值更改為Li-j。直至所有的A[i](1

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

4結(jié)論

本文提出將圖示教學(xué)法可應(yīng)用于數(shù)據(jù)結(jié)構(gòu)和算法課程教學(xué)的多個(gè)環(huán)節(jié)中,有些算法在大多數(shù)教科書中有了一定的圖示過程表示,而有些算法卻沒有給出形象的圖示表示,因而需要在教學(xué)中應(yīng)補(bǔ)充。本文以圖狀結(jié)構(gòu)中的最小生成樹算法為例,通過圖示分析,詳細(xì)地講解這個(gè)算法的核心思想和實(shí)現(xiàn)過程,通過視覺刺激,使學(xué)生能夠加深對(duì)這個(gè)算法過程的把握,取得了良好的教學(xué)效果。

參考文獻(xiàn):

[1] 戴敏,于長云,董玉濤. 高效學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)[J]. 計(jì)算機(jī)教育,2006(2):59-60.