8.Roadmap路線圖

即將學(xué)習(xí)的第一組離散化方法被稱為路線圖，該方法使用一個簡單的連通圖來表示配置空間——類似于用地鐵地圖來表示城市。

路線圖方法通常分兩個階段實(shí)現(xiàn):

—構(gòu)建階段從空間的連續(xù)表示中構(gòu)建圖形。這個階段通常會花費(fèi)大量的時間和精力，但是生成的圖可以用于多個查詢，只需要進(jìn)行最小的修改。

—查詢階段評估圖像以找到從開始位置到目標(biāo)位置的路徑。這是通過搜索算法來完成的。

在這個離散化部分，我們只討論和評估每個路線圖方法的構(gòu)建階段。而查詢階段將在離散化部分之后的圖搜索部分中更詳細(xì)地討論。

接下來將學(xué)習(xí)的兩個路線圖方法是可視性（Visibility）圖和Voronoi圖方法。

9.可視性（Visibility）圖

可視性圖通過將開始節(jié)點(diǎn)、所有障礙物的頂點(diǎn)和目標(biāo)節(jié)點(diǎn)相互連接(除了那些會導(dǎo)致與障礙物碰撞的節(jié)點(diǎn))來構(gòu)建路線圖。可視性圖之所以叫這個名字是有原因的——它將每個節(jié)點(diǎn)連接到從其位置“可見”的所有其他節(jié)點(diǎn)。

—節(jié)點(diǎn):起點(diǎn)、目標(biāo)和所有障礙頂點(diǎn)。

—邊:兩個節(jié)點(diǎn)之間不與障礙物相交的邊，包括障礙物邊。

下圖顯示了包含多邊形障礙物的配置空間的可見性圖。

構(gòu)建可視性圖的動機(jī)是，從開始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最短路徑將是一條分段線性路徑，只在障礙物的頂點(diǎn)處彎曲。這在直覺上是有道理的——路徑應(yīng)該盡可能地貼近障礙物的邊角，而不增加任何額外的長度。

一旦構(gòu)建了可視性圖，就可以應(yīng)用搜索算法找到從起點(diǎn)到目標(biāo)的最短路徑。下圖顯示了可見性圖中的最短路徑。

小測試：

雖然用于搜索路線圖的算法還沒有引入，但是否有任何算法能夠找到從開始到目標(biāo)的路徑，以及最優(yōu)路徑是否在路線圖內(nèi)，仍然值得分析。

完成測試后，現(xiàn)在應(yīng)該已經(jīng)看到了可見性圖方法的優(yōu)點(diǎn)?？梢娦詧D的一個缺點(diǎn)是它沒有為錯誤留有余地。穿越最佳路徑的機(jī)器人必須非常接近障礙物，這大大增加了碰撞的風(fēng)險。在某些應(yīng)用程序中，例如動畫或視頻游戲的路徑規(guī)劃，這是可以接受的。然而，現(xiàn)實(shí)世界機(jī)器人定位的不確定性使得該方法不切實(shí)際。

10.Voronoi（泰森多邊形法）圖

另一種生成路線圖的離散化方法稱為Voronoi圖，與生成最短路徑的可見性圖方法不同，Voronoi圖最大限度地提高了障礙物之間的間隙。Voronoi圖是一種邊緣平分障礙物之間自由空間的圖。每條邊都與周圍的障礙物保持等距離——盡可能留出最大的間隙。如下圖所示為配置空間的Voronoi圖：

?

11.單元分解法

另一種可用于將配置空間轉(zhuǎn)換為搜索算法可輕松探索的表示的離散化方法是單元分解法。單元格分解將空間劃分為離散的單元格，每個單元格是一個節(jié)點(diǎn)，相鄰單元格用邊連接。有兩種不同類型的單元分解:

• 精確單元格分解

• 近似單元格分解

精確單元格分解

精確單元格分解將空間劃分為不重疊的網(wǎng)格。這通常是通過將空間分割成三角形和梯形來實(shí)現(xiàn)的，這可以通過在每個障礙物的頂點(diǎn)添加垂直線段來實(shí)現(xiàn)。在下面的圖像中看到配置空間的精確單元格分解的結(jié)果：

?一旦空間被分解，得到的圖就可以用來搜索從起點(diǎn)到目標(biāo)的最短路徑。結(jié)果圖如下圖所示：

精確的單元格分解因?yàn)槠渚_性和完整性而顯得優(yōu)雅。每個單元要么是“滿的”，意味著它完全被障礙物占據(jù)，要么是“空的”，意味著它是自由的。所有單元的并集恰好代表了配置空間。如果存在從起點(diǎn)到終點(diǎn)的路徑，結(jié)果圖將包含它。

為了實(shí)現(xiàn)精確的單元分解，算法必須沿x軸對所有障礙頂點(diǎn)進(jìn)行排序，然后對每個頂點(diǎn)確定是否必須創(chuàng)建一個新單元，或者是否應(yīng)該將兩個單元合并在一起。這種算法稱為平面掃描算法。

精確的單元格分解導(dǎo)致單元格形狀怪異。形狀獨(dú)特的梯形和三角形的集合比規(guī)則的矩形網(wǎng)格更難處理。這導(dǎo)致了計算復(fù)雜度的增加，特別是對于具有較多維度的環(huán)境。當(dāng)障礙物不是多邊形而是不規(guī)則形狀時，分解計算也很困難。

由于這個原因，存在另一種類型的單元格分解，它在實(shí)現(xiàn)中更加實(shí)用。

12.近似單元格分解

近似單元格分解將配置空間劃分為簡單、規(guī)則形狀的離散單元格——例如矩形和正方形(或它們的多維等量物)。除了簡化單元格的計算外，該方法還支持空間的層次分解(下面將詳細(xì)介紹)。

簡單的分解

二維配置空間可以分解為矩形單元格的網(wǎng)格。然后，每個單元格可以像之前一樣標(biāo)記為滿或空。然后，搜索算法可以尋找一個空閑單元格序列來連接開始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)。

這種方法比精確的細(xì)胞分解更有效，但失去了完整性。一個特定的配置空間可能包含一個可行路徑，但是由于存在障礙物，單元格的分辨率導(dǎo)致一些包含路徑的單元格被標(biāo)記為“滿”。不管單元格中99%的空間被障礙物占據(jù)，還是只有1%的空間被障礙物占據(jù)，它都會被標(biāo)記為“滿”。顯然，這是不實(shí)在的。

迭代分解

還有一種將空間劃分為簡單單元格的方法。該方法不是立即將空間分解為大小相等的小單元，而是遞歸地將空間分解為四個象限。每個象限被標(biāo)記為滿、空或一個名為“混合”的新標(biāo)簽——用于表示一些被障礙物占據(jù)，但也包含一些空閑空間的單元格。如果從頭到尾找不到一個空閑空間的單元，那么混合單元將進(jìn)一步分解為另外四個象限。通過這個過程，更多的空閑單元將出現(xiàn)，最終揭示出一條路徑(如果存在的話)。這種方法的二維實(shí)現(xiàn)稱為四叉樹分解?？梢栽谙旅娴膱D表中看到：

算法

近似單元格分解背后的算法比精確單元格分解算法簡單得多。下面提供了該算法的偽代碼：

?

四叉樹的三維等效物是八叉樹，如下圖所示。離散具有任意維數(shù)的空間的方法遵循與上面描述的算法相同的過程，但是擴(kuò)展以適應(yīng)額外的維數(shù)。

?

盡管精確的單元格分解是一種更優(yōu)雅的方法，但對于非普通環(huán)境，它比近似的單元格分解計算成本要高得多。因此，在實(shí)踐中通常采用近似的單元分解方法。經(jīng)過足夠的計算，近似的單元格分解接近完整。然而，這并不是最優(yōu)的——最終的路徑取決于單元格如何分解。

近似的單元格分解可以快速找到明顯的解決方案。最優(yōu)路徑有可能擠過障礙物之間的一個極小的開口，但最終路徑在廣闊的開放空間中需要更長的路線——這是遞歸分解算法首先找到的。近似的單元分解是功能性的，但是像所有離散/組合路徑規(guī)劃方法一樣，它開始在高維環(huán)境中難以計算。

13.勢場Potential Field

本文要學(xué)習(xí)的最后一種離散化方法——勢場法。與迄今為止討論的將連續(xù)空間離散成連通圖的方法不同，勢場方法執(zhí)行不同類型的離散化。

為了完成它的任務(wù)，勢場法生成了兩個函數(shù)——一個將機(jī)器人吸引到目標(biāo)，另一個將機(jī)器人驅(qū)逐開障礙物。這兩個函數(shù)可以相加以創(chuàng)建離散化表示。通過應(yīng)用梯度下降等優(yōu)化算法，機(jī)器人可以在繞過障礙物的同時向目標(biāo)空間移動。讓我們更詳細(xì)地看看這些步驟是如何實(shí)現(xiàn)的。

吸引勢場

吸引勢場是在目標(biāo)配置下具有全局最小值的函數(shù)。如果一個機(jī)器人被放置在任意一點(diǎn)，并被要求沿著下降最陡的方向，它將最終達(dá)到目標(biāo)配置。這個函數(shù)不需要很復(fù)雜，一個簡單的二次函數(shù)就可以實(shí)現(xiàn)上面討論的所有要求。

排斥勢場

排斥勢場在自由空間中是一個等于零的函數(shù)，在障礙物附近增長到一個較大的值。創(chuàng)建這樣一個勢場的一種方法是使用下面的函數(shù)。

值ρ0控制勢場離障礙物的非零距離，以及障礙物周圍的區(qū)域有多陡。超過ρ0時，勢場為0。在距離障礙物的ρ0范圍內(nèi)，勢場隨距離障礙物的遠(yuǎn)近而成比例。

勢場和

將吸引函數(shù)和排斥函數(shù)相加，得到用于引導(dǎo)機(jī)器人從空間中的任何地方到達(dá)目標(biāo)的勢場。下圖顯示了函數(shù)的和，緊接著的圖像顯示了最終函數(shù)。

?

想象一下，在函數(shù)的表面上放置一個彈珠——它將從場上的任何地方朝目標(biāo)的方向滾動，而不會與任何障礙物碰撞(只要ρ0設(shè)置得當(dāng))!

函數(shù)的梯度決定了機(jī)器人應(yīng)該移動的方向，速度可以設(shè)置為常數(shù)，或者根據(jù)機(jī)器人和目標(biāo)之間的距離縮放。

勢場法的問題

勢場法并非沒有缺點(diǎn)，它既不完整也不最優(yōu)。在某些環(huán)境下，該方法將引導(dǎo)機(jī)器人到達(dá)局部最小值，而不是全局最小值。下面的圖片描述了這樣一個例子。根據(jù)機(jī)器人從哪里開始，它可能會被引導(dǎo)到微笑圖的底部。下圖描述了配置空間，后面圖顯示了對應(yīng)的勢場。

?

機(jī)器人陷入局部最小值的問題可以通過添加隨機(jī)行走和其他通常應(yīng)用于梯度下降的策略來解決，但最終該方法并不完整。

勢場法也不是最優(yōu)的，因?yàn)樗赡懿⒉豢偸钦业綇钠瘘c(diǎn)到目標(biāo)的最短(或最便宜)路徑。最短的路不一定是最陡峭的下坡路。此外，勢場沒有考慮每一步的代價。

本文總結(jié)如下圖示：

?文章來源地址http://www.zghlxwxcb.cn/news/detail-589053.html

?

?

?

?

?

?

?

?

?

?

到了這里，關(guān)于機(jī)器人學(xué)習(xí)-關(guān)于經(jīng)典路徑規(guī)劃（二）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！