路徑規(guī)劃技術(shù)是智能機(jī)器人研究領(lǐng)域中的一個(gè)核心問(wèn)題，也是機(jī)器人學(xué)中研究人工智能問(wèn)題的一個(gè)重要方面，研究路徑規(guī)劃技術(shù)的目的是希望未來(lái) 的智能機(jī)器人能具有感知、規(guī)劃和控制等高層能力：它們能從周?chē)�的環(huán)境中收 集信息，構(gòu)建一個(gè)關(guān)于所在環(huán)境的模型，并且利用這個(gè)模型來(lái)規(guī)劃和執(zhí)行高層任務(wù)。

1)幾何法

幾何法是抽取環(huán)境的幾何特征，把自由位姿空間映射到一個(gè) 加權(quán)圖上，這樣就把原問(wèn)題轉(zhuǎn)換成一個(gè)簡(jiǎn)單的圖搜索問(wèn)題�；�于幾何法的路徑規(guī)劃Z具代表性的是可視圖法和自由空間法(環(huán)境分割法)。該方法適用于 環(huán)境中的障礙物是多邊形的情況。先構(gòu)造一個(gè)可視圖 VG,VG 由一系列的 節(jié)點(diǎn)和節(jié)點(diǎn)間的連接值組成，其中節(jié)點(diǎn)是由各障礙多邊形的D點(diǎn)組成的。如 果在VG 中將起點(diǎn)s 和目標(biāo)點(diǎn)g 也看成特殊的D點(diǎn)。就可以使用動(dòng)態(tài)規(guī)劃法 或者A* 算法搜索一條從s 到 g 的Z短路徑。由VG 法得到的路徑是具有Z短 長(zhǎng)度的，但是往往路徑過(guò)于靠近障礙物而得不到路徑的安全性能。環(huán)境分割 方法采用預(yù)先定義的基本形狀構(gòu)造自由空間，并且將這些基本單元及它們之 間的聯(lián)系組成一個(gè)連通圖，然后運(yùn)用圖搜索方法進(jìn)行路徑的搜索。這些方法 在某些情況下路徑會(huì)距離目標(biāo)太遠(yuǎn)，而且路徑會(huì)因復(fù)雜多折不利于智能機(jī)器 人的行走。

2)單元分解法

Brook 和 Lozano 在1983年提出了考慮旋轉(zhuǎn)物體的路徑 規(guī)劃單元分解法(Sub-division 算法),他們討論的基本問(wèn)題是具有兩個(gè)平移自由度和一個(gè)旋轉(zhuǎn)自由度的物體在多邊形障礙物環(huán)境中的運(yùn)動(dòng)。算法的思想很 簡(jiǎn)單，把狀態(tài)空間分解為許多矩形或者立方體，稱為單元(cell), 其中每個(gè)單元 都標(biāo)記為：①如果單元內(nèi)每一點(diǎn)均與狀態(tài)空間中的障礙物不相交，則單元為空 的；②如果單元內(nèi)每一點(diǎn)均與狀態(tài)空間中的障礙物相交，則單元為滿的；③如 果單元內(nèi)點(diǎn)既有與狀態(tài)空間中的障礙物相交的，也有不相交的，則單元為混 合的。 尋找一條由空的單元組成而且包含起點(diǎn)和目標(biāo)點(diǎn)的連通路徑，如果這樣 的路徑在初始化分的狀態(tài)空間中不存在，則要找出所有混合的單元，將其進(jìn)一 步細(xì)分，并且將劃分的結(jié)果進(jìn)行標(biāo)記，然后在空的單元中進(jìn)行搜索，如此反復(fù)， 直至成功。如果非空的單元?jiǎng)澐值筋A(yù)設(shè)的Z小值，則問(wèn)題無(wú)解。該算法的一 大特征是劃分空間與路徑搜索是交叉進(jìn)行的。使用該算法可以解決比較復(fù)雜 的問(wèn)題，但是其計(jì)算量也會(huì)相應(yīng)地變得很大。單元分解法研究得Z多的是柵 格解耦法，它也是目前研究Z廣泛的路徑規(guī)劃方法。

3)人工勢(shì)場(chǎng)法

傳統(tǒng)的人工勢(shì)場(chǎng)法把智能機(jī)器人在環(huán)境中的運(yùn)動(dòng)視為一 種在抽象的人造受力場(chǎng)中的運(yùn)動(dòng)，目標(biāo)點(diǎn)對(duì)智能機(jī)器人產(chǎn)生“引力”,障礙物對(duì)智能機(jī)器人產(chǎn)生“斥力”,Z后通過(guò)求合力來(lái)控制智能機(jī)器人的運(yùn)動(dòng)。但是，由 于人工勢(shì)場(chǎng)法把所有信息壓縮為單個(gè)合力，這樣就拋棄了有關(guān)障礙物分布的 有價(jià)值信息的缺陷，而且易陷入局部Z小值。

4)數(shù)學(xué)分析法

數(shù)學(xué)分析法用一個(gè)依賴位姿空間參數(shù)的不等式組來(lái)表示智能機(jī)器人躲避障礙物的要求，路徑規(guī)劃由起始位姿到目標(biāo)位姿尋找路徑時(shí) Z小化一個(gè)標(biāo)量函數(shù)而轉(zhuǎn)化成數(shù)學(xué)優(yōu)化問(wèn)題，通過(guò)數(shù)學(xué)分析方法可以求解這 個(gè)數(shù)學(xué)優(yōu)化問(wèn)題。

5)路徑搜索算法

給定一種智能機(jī)器人工作空間的表示方法和自由位姿 空間的表示方法后，路徑規(guī)劃問(wèn)題就轉(zhuǎn)變?yōu)閺慕o定的表示中找到一個(gè)從起始 位姿到目標(biāo)位姿的連續(xù)位姿序列的問(wèn)題。

6)基于微積分的搜索技術(shù)

該技術(shù)使用優(yōu)化問(wèn)題的解來(lái)滿足一組充分必 要條件，這種技術(shù)一般只能用于求解較簡(jiǎn)單的問(wèn)題。

7)枚舉技術(shù)

枚舉技術(shù)搜索目標(biāo)函數(shù)的域空間中的每一個(gè)節(jié)點(diǎn)，它們的 實(shí)現(xiàn)簡(jiǎn)單，但是可能需要大量的計(jì)算。動(dòng)態(tài)規(guī)劃是其中一種很好的方法。路 徑規(guī)劃技術(shù)常用的有深度優(yōu)先搜索、廣度優(yōu)先搜索、A*搜索、反復(fù)加深搜索、Z 優(yōu)搜索和Dijkstra 搜索。

8)有指導(dǎo)的隨機(jī)搜索技術(shù)

有指導(dǎo)的隨機(jī)搜索技術(shù)以枚舉技術(shù)為基礎(chǔ)， 但是附加了一些指導(dǎo)搜集過(guò)程信息。它們的應(yīng)用范圍很廣，并且能解決十分 復(fù)雜的問(wèn)題，其兩個(gè)主要的子集是模擬退火算法和進(jìn)化算法。