移動(dòng)機(jī)器人路徑規(guī)劃綜述

瞿亦瀟 游曉明

摘要：移動(dòng)機(jī)器人技術(shù)是機(jī)器人技術(shù)的重要組成部分，也是人工智能的重要體現(xiàn)。本文總結(jié)了移動(dòng)機(jī)器人智能化發(fā)展過程中面臨的挑戰(zhàn)，描述了機(jī)器人與環(huán)境的關(guān)系，重點(diǎn)論述路徑規(guī)劃關(guān)鍵技術(shù)。為進(jìn)一步開展機(jī)器人技術(shù)的研究和設(shè)計(jì)奠定了基礎(chǔ)。

關(guān)鍵詞：路徑規(guī)劃；A*算法；D*算法；智能算法

0.引言

移動(dòng)機(jī)器人集機(jī)械、電子、計(jì)算機(jī)、傳感測(cè)控等多項(xiàng)技術(shù)為一體，是機(jī)械電子工程領(lǐng)域多學(xué)科互相結(jié)合、互相滲透的產(chǎn)物。移動(dòng)機(jī)器人技術(shù)的研究水平，反映了一個(gè)國(guó)家諸多相關(guān)技術(shù)學(xué)科的綜合發(fā)展水平，是一個(gè)國(guó)家綜合科技實(shí)力的集中體現(xiàn)；移動(dòng)機(jī)器人技術(shù)的研究還反過來作用于與它相關(guān)的各個(gè)學(xué)科，作為與它相關(guān)的諸多學(xué)科的研究載體和實(shí)驗(yàn)平臺(tái)，移動(dòng)機(jī)器人技術(shù)的進(jìn)步對(duì)一個(gè)國(guó)家的整體科技實(shí)力的增長(zhǎng)將起著重要的推進(jìn)作用。

路徑規(guī)劃技術(shù)是移動(dòng)機(jī)器人研究中的一項(xiàng)關(guān)鍵技術(shù)，其中全局路徑規(guī)劃是根據(jù)先驗(yàn)知識(shí)（如給定地圖），在某些約束條件下，規(guī)劃出一條從起點(diǎn)到終點(diǎn)的無碰路徑。全局路徑規(guī)劃是移動(dòng)機(jī)器人系統(tǒng)所有智能行為的基礎(chǔ)，在整個(gè)移動(dòng)機(jī)器人技術(shù)體系中占有重要地位。

1.路徑規(guī)劃

路徑規(guī)劃技術(shù)是移動(dòng)機(jī)器人領(lǐng)域中的核心問題之一，也是機(jī)器人學(xué)中研究人工智能問題的一個(gè)重要方面。下面綜述路徑規(guī)劃重要算法。

1.1 Dijkstra算法

Dijkstra 算法是由EW.Dijkstra提出的用在帶權(quán)有向圖上的最優(yōu)路徑算法。利用 Dijkstra 算法可以在有向圖中從某一個(gè)指定點(diǎn)找到到其他任意一個(gè)點(diǎn)的最短路徑。該算法的搜索步驟是：對(duì)每個(gè)頂點(diǎn)x指定一個(gè)數(shù)d（x），表示的是從起點(diǎn) s 到當(dāng)前頂點(diǎn) x 的最短路徑長(zhǎng)度。開始時(shí)， d （ s）=0， d （x）=∞，y為已標(biāo)注的最后一個(gè)頂點(diǎn)，首先對(duì) s 標(biāo)注。對(duì)于每個(gè)未標(biāo)注的頂點(diǎn) x， d （x）為如下式所示。

（1）

其中 a （ y，x）是 y，x 之間的弧長(zhǎng)。對(duì)具有 d （x）最小值的未標(biāo)注點(diǎn)進(jìn)行標(biāo)注，同時(shí)將 y 值定為 x。如果頂點(diǎn) t 已標(biāo)注，則算法終止。即已經(jīng)找到了一條從 s 到 t 的最短路徑。若 t 未標(biāo)注，則繼續(xù)上面的遍歷。

其最大特點(diǎn)就是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。但由于它遍歷計(jì)算的節(jié)點(diǎn)很多，所以效率低。

1.2 A*算法

A*算法是由 Nilsson 提出的一種搜索算法。其主要的思想是對(duì)目標(biāo)點(diǎn)進(jìn)行循環(huán)搜索，以獲得機(jī)器人的軌跡。它通過對(duì)狀態(tài)空間中每個(gè)搜索位置進(jìn)行評(píng)估，得到最好的位置，再根據(jù)這個(gè)最好位置進(jìn)行搜索，直到找到目標(biāo)點(diǎn)。這種方法可以省略大量不必要的搜索，提高了效率。

A*算法是一種在靜態(tài)路網(wǎng)中的路徑規(guī)劃方法[1]，A*算法最基本的尋路表達(dá)式為： f （ n）= g（n）+h（n），其中f （n）是當(dāng)前節(jié)點(diǎn) n 到終點(diǎn)的估價(jià)函數(shù)，g （n）為整個(gè)搜索空間里起始點(diǎn)到當(dāng)前節(jié)點(diǎn)n的距離代價(jià)值， h （n）是從當(dāng)前點(diǎn)n到下一搜索點(diǎn)估價(jià)最好的路線，與程序相對(duì)應(yīng)，為求得算法的最優(yōu)解，也就是說能夠確保找出最優(yōu)的路徑，其關(guān)鍵條件在于選取 h （n）的值，這時(shí)將會(huì)存兩種情況，當(dāng) h （ n）<=n時(shí)，會(huì)使得搜索時(shí)，可搜索的點(diǎn)數(shù)增加，從而使得搜索的范圍增大，增加了系統(tǒng)負(fù)擔(dān)，這樣固然可以得到最優(yōu)解，但是效率將會(huì)明顯降低，另一種情況，與之相反，減少搜索的點(diǎn)數(shù)，這樣系統(tǒng)效率固然上升了，但這樣有可能會(huì)忽略了某些優(yōu)點(diǎn)，導(dǎo)致最終不能得到最優(yōu)的解。

1.3 D*算法

在A*算法的基礎(chǔ)上，Stentz提出了一種動(dòng)態(tài)路徑規(guī)劃算法，即D*算法，能夠有效地利用己有的規(guī)劃計(jì)算信息[2]。

D*算法捜索得到的優(yōu)化路徑的好壞與算法代價(jià)估計(jì)函數(shù)的選取有著緊密的聯(lián)系，一個(gè)較優(yōu)的代價(jià)估計(jì)函數(shù)能夠使D*算法捜索到較優(yōu)的路徑，而一個(gè)不合適的代價(jià)估計(jì)函數(shù)會(huì)極大地影響D*算法的性能，極大降低路徑的可靠性和穩(wěn)定性，在較為復(fù)雜的環(huán)境中甚至找不到優(yōu)化路徑。

在利用D*捜索算法進(jìn)行路徑規(guī)劃的過程中，如果機(jī)器人在前進(jìn)過程中遇到障礙物，算法能夠利用前次規(guī)劃的信息重新捜索路徑，避免了對(duì)相同數(shù)據(jù)的重復(fù)計(jì)算，提高了二次路徑規(guī)劃的效率，因此D*算法能夠較好地應(yīng)用于動(dòng)態(tài)環(huán)境下的路徑規(guī)劃。但是，D*算法存在捜索空間較大的缺陷，尤其是在比較復(fù)雜的環(huán)境下，算法的搜索空間將大大増加，并且時(shí)間復(fù)雜度隨著地圖維數(shù)的増加呈指數(shù)級(jí)增長(zhǎng)，因此，極大地降低了路徑規(guī)劃的速度。

1.4 智能算法

人工智能路徑規(guī)劃技術(shù)是將現(xiàn)代人工智能技術(shù)應(yīng)用于移動(dòng)機(jī)器人的路徑規(guī)劃中，如人工神經(jīng)網(wǎng)絡(luò)、進(jìn)化計(jì)算、模糊邏輯與信息融合等，其中蟻群算法是較好應(yīng)用于組合優(yōu)化問題的智能優(yōu)化算法，該算法及其派生算法在機(jī)器人路徑規(guī)劃研究領(lǐng)域已得到應(yīng)用[3-6]，在蟻群算法較好解決旅行商問題（TSP） 的基礎(chǔ)上，許多學(xué)者進(jìn)一步將蟻群優(yōu)化算法引入到水下機(jī)器人（UV） 的路徑規(guī)劃研究中。由于模糊邏輯和信息融合技術(shù)在不確定性信息處理方面有極好的表現(xiàn)，且移動(dòng)機(jī)器人傳感器采集的環(huán)境信息存在不確定性和不完整性，使得模糊邏輯和信息融合技術(shù)在移動(dòng)機(jī)器人路徑規(guī)劃中有較好的應(yīng)用。

2.結(jié)束語

本文針對(duì)移動(dòng)機(jī)器人路徑規(guī)劃關(guān)鍵技術(shù)進(jìn)行了綜述，旨在為進(jìn)一步開展機(jī)器人技術(shù)的研究和設(shè)計(jì)奠定基礎(chǔ)。

參考文獻(xiàn)：

[1]吳超帥.改進(jìn)A*算法及其在ASR移動(dòng)機(jī)器人路徑規(guī)劃中的應(yīng)用[D].湘潭大學(xué)，2012.

[2]李凱業(yè).基于改進(jìn)分層D*搜索算法的室內(nèi)路徑規(guī)劃問題研究[D].合肥工業(yè)大學(xué)，2015.

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

[4]王俊.移動(dòng)機(jī)器人的定位方法研究[D].東北大學(xué)，2010.

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

[6]許長(zhǎng)嵐.移動(dòng)機(jī)器人設(shè)計(jì)及其全局路徑規(guī)劃[D].大連理工大學(xué)，2006.

作者簡(jiǎn)介：

1.瞿亦瀟，女，1996.10，山東人，單位：上海工程技術(shù)大學(xué)本科生，研究方向：智能信息處理.

2.游曉明，女，1963.12，湖北省黃石市人，博士，教授，研究領(lǐng)域?yàn)橹悄苄畔⑻幚砝碚摷皯?yīng)用、模式識(shí)別和人工智能、分布式并行智能處理及應(yīng)用。

通訊作者：游曉明

基金項(xiàng)目：上海工程技術(shù)大學(xué)課程改革與建設(shè)項(xiàng)目（No.y201702002，17XJG004，cs1702001）；上海高校本科重點(diǎn)教學(xué)改革項(xiàng)目（A1-0601-18-01137）