移動機器人路徑規劃綜述

瞿亦瀟 游曉明

摘要：移動機器人技術是機器人技術的重要組成部分，也是人工智能的重要體現。本文總結了移動機器人智能化發展過程中面臨的挑戰，描述了機器人與環境的關系，重點論述路徑規劃關鍵技術。為進一步開展機器人技術的研究和設計奠定了基礎。

關鍵詞：路徑規劃；A*算法；D*算法；智能算法

0.引言

移動機器人集機械、電子、計算機、傳感測控等多項技術為一體，是機械電子工程領域多學科互相結合、互相滲透的產物。移動機器人技術的研究水平，反映了一個國家諸多相關技術學科的綜合發展水平，是一個國家綜合科技實力的集中體現；移動機器人技術的研究還反過來作用于與它相關的各個學科，作為與它相關的諸多學科的研究載體和實驗平臺，移動機器人技術的進步對一個國家的整體科技實力的增長將起著重要的推進作用。

路徑規劃技術是移動機器人研究中的一項關鍵技術，其中全局路徑規劃是根據先驗知識（如給定地圖），在某些約束條件下，規劃出一條從起點到終點的無碰路徑。全局路徑規劃是移動機器人系統所有智能行為的基礎，在整個移動機器人技術體系中占有重要地位。

1.路徑規劃

路徑規劃技術是移動機器人領域中的核心問題之一，也是機器人學中研究人工智能問題的一個重要方面。下面綜述路徑規劃重要算法。

1.1 Dijkstra算法

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

（1）

其中 a （ y，x）是 y，x 之間的弧長。對具有 d （x）最小值的未標注點進行標注，同時將 y 值定為 x。如果頂點 t 已標注，則算法終止。即已經找到了一條從 s 到 t 的最短路徑。若 t 未標注，則繼續上面的遍歷。

其最大特點就是以起始點為中心向外層層擴展，直到擴展到終點為止。但由于它遍歷計算的節點很多，所以效率低。

1.2 A*算法

A*算法是由 Nilsson 提出的一種搜索算法。其主要的思想是對目標點進行循環搜索，以獲得機器人的軌跡。它通過對狀態空間中每個搜索位置進行評估，得到最好的位置，再根據這個最好位置進行搜索，直到找到目標點。這種方法可以省略大量不必要的搜索，提高了效率。

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

1.3 D*算法

在A*算法的基礎上，Stentz提出了一種動態路徑規劃算法，即D*算法，能夠有效地利用己有的規劃計算信息[2]。

D*算法捜索得到的優化路徑的好壞與算法代價估計函數的選取有著緊密的聯系，一個較優的代價估計函數能夠使D*算法捜索到較優的路徑，而一個不合適的代價估計函數會極大地影響D*算法的性能，極大降低路徑的可靠性和穩定性，在較為復雜的環境中甚至找不到優化路徑。

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

1.4 智能算法

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

2.結束語

本文針對移動機器人路徑規劃關鍵技術進行了綜述，旨在為進一步開展機器人技術的研究和設計奠定基礎。

參考文獻：

[1]吳超帥.改進A*算法及其在ASR移動機器人路徑規劃中的應用[D].湘潭大學，2012.

[2]李凱業.基于改進分層D*搜索算法的室內路徑規劃問題研究[D].合肥工業大學，2015.

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

[4]王俊.移動機器人的定位方法研究[D].東北大學，2010.

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

[6]許長嵐.移動機器人設計及其全局路徑規劃[D].大連理工大學，2006.

作者簡介：

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

2.游曉明，女，1963.12，湖北省黃石市人，博士，教授，研究領域為智能信息處理理論及應用、模式識別和人工智能、分布式并行智能處理及應用。

通訊作者：游曉明

基金項目：上海工程技術大學課程改革與建設項目（No.y201702002，17XJG004，cs1702001）；上海高校本科重點教學改革項目（A1-0601-18-01137）