改進(jìn)A*算法的機(jī)器人最短路徑規(guī)劃研究?

陳 晨

（南京理工大學(xué) 南京 210094）

1 引言

移動(dòng)機(jī)器人如今在各行各業(yè)都扮演著一定的角色［1～3］，而路徑規(guī)劃作為機(jī)器人完成導(dǎo)航以及其他任務(wù)的前提，在機(jī)器人領(lǐng)域中有著重要的地位。路徑規(guī)劃的目的是在有障礙物的環(huán)境中為移動(dòng)機(jī)器人從起始位置到目標(biāo)位置規(guī)劃出一條最優(yōu)并且安全無碰撞的路線，是自主移動(dòng)機(jī)器人的基礎(chǔ)［4］。對機(jī)器人路徑規(guī)劃的研究非常之多，常用方法主要有蟻群算［5］、粒子群優(yōu)化算法［6］、柵格法［7］、神經(jīng)網(wǎng)絡(luò)算法［8］等。在移動(dòng)機(jī)器人的路徑規(guī)劃中，最為常用也最為簡單的柵格法沿用至今，其原理簡單（0，1分別代表可通行區(qū)域和障礙物），對移動(dòng)機(jī)器人的傳感器要求也不高。A*算法用柵格圖作為路徑規(guī)劃的基圖，在上面進(jìn)行路徑的搜索。針對這種方式，文獻(xiàn)［9］對傳統(tǒng)A*算法中延申結(jié)點(diǎn)的等級進(jìn)行了賦值，實(shí)現(xiàn)路徑遠(yuǎn)離障礙物，避免了實(shí)際中移動(dòng)機(jī)器人會(huì)碰撞到障礙物邊緣的問題；文獻(xiàn)［10］雖然解決了實(shí)際移動(dòng)機(jī)器人行駛中路徑的平滑性能，但是因?yàn)槠涓倪M(jìn)的原理是將搜索當(dāng)前節(jié)點(diǎn)的8 個(gè)方向改成無限個(gè)方向，無疑大幅增加了計(jì)算的難度，使得搜索的時(shí)間變長。文獻(xiàn)［11］通過虛擬障礙物的設(shè)置，在障礙物的周邊設(shè)置虛擬障礙，即障礙物邊緣膨脹化處理，避免規(guī)劃的路徑太過靠近障礙物而發(fā)生碰撞。文獻(xiàn)［12］通過修改搜索策略，采用JPS 跳點(diǎn)搜索策略，根據(jù)一定的規(guī)則從柵格中選擇一些點(diǎn)進(jìn)行擴(kuò)展，極大地提高了效率，文獻(xiàn)［13］為了提高路徑的平滑度和降低搜索的時(shí)間，將現(xiàn)實(shí)世界里的元素信息加入到啟發(fā)函數(shù)中，文獻(xiàn)［14］為了提升傳統(tǒng)A*算法的速率，用確定的方向搜索減少搜索區(qū)域。文獻(xiàn)［15］提出了基于A*算法的跳點(diǎn)搜索策略，通過省略中間直線部分的搜索點(diǎn)，從而減少了算法的計(jì)算量，文獻(xiàn)［16］采用的方式是將原先冗余的兩條相鄰邊，使用與它們相近的共有邊來代替，一定程度上將趨于目標(biāo)點(diǎn)的要求進(jìn)行了簡單化，但有一個(gè)缺陷是當(dāng)環(huán)境變得復(fù)雜且節(jié)點(diǎn)交錯(cuò)時(shí)搜索的效率提升不大。

基于以上各方法的特點(diǎn)，本文通過對啟發(fā)函數(shù)加入當(dāng)前節(jié)點(diǎn)父節(jié)點(diǎn)的信息，并用歐式距離和曼哈頓距離的中值來代替原先的啟發(fā)函數(shù)，提高了啟發(fā)函數(shù)h（n）的值，使之更加接近真實(shí)的路徑代價(jià)，效率更高，速度更快。

2 A*理論基礎(chǔ)

2.1 環(huán)境建模

環(huán)境模型的建立是進(jìn)行機(jī)器人控制的基礎(chǔ)，合理的地圖模型可以提高規(guī)劃的效率，其中無約束柵格為圖中白色網(wǎng)格，帶約束柵格為圖中黑色網(wǎng)格，每個(gè)柵格都代表著整個(gè)實(shí)驗(yàn)場景中的其中一部分，他們共同組成了實(shí)驗(yàn)的現(xiàn)實(shí)環(huán)境地圖。如圖1所示。

圖1 柵格地圖

2.2 算法流程

A*算法是一種經(jīng)典的啟發(fā)式搜索算法，其搜索方向主要有兩種，如圖2所示。

圖2 柵格地圖及機(jī)器人移動(dòng)方向

A*算法的核心表達(dá)式為

式中f（n）表示從初始柵格經(jīng)過節(jié)點(diǎn)n 到達(dá)目標(biāo)柵格的總的代價(jià)消耗，g（n）表示從初始柵格到節(jié)點(diǎn)n 所在柵格的實(shí)際代價(jià)消耗，h（n）表示從節(jié)點(diǎn)n到目標(biāo)柵格的估計(jì)代價(jià)消耗，其中f（n）的大小幾乎取決于h（n）的大小。因此分析A*算法的關(guān)鍵在于對啟發(fā)函數(shù)h（n）的研究。當(dāng)預(yù)估的代價(jià)h（n）小于真實(shí)的路徑代價(jià)，搜索的范圍會(huì)比較廣，得到的路徑也比較短，相應(yīng)帶來的問題就是耗時(shí)較長，當(dāng)預(yù)估的代價(jià)h（n）大于真實(shí)的路徑代價(jià)，搜索的速度會(huì)比較快，相應(yīng)的問題是路徑可能不是最短的，h（n）越接近真實(shí)的路徑代價(jià)，算法的速度和效果越好。因此，在復(fù)雜、規(guī)模較大的環(huán)境中我們更要對啟發(fā)函數(shù)進(jìn)行一個(gè)改進(jìn)，在提高速度的同時(shí)也能得到更短的路徑。

A*全局路徑規(guī)劃流程如圖3所示。

圖3 A*算法流程圖

3 改進(jìn)的A*算法

3.1 啟發(fā)函數(shù)的修改

由第一部分的計(jì)算公式可得，預(yù)估的代價(jià)損耗h（n）極大程度地影響著整體的預(yù)估代價(jià)，實(shí)驗(yàn)表明，算法的效率高低取決于h（n）的大小與實(shí)際損耗代價(jià)的差值，h（n）越接近真實(shí)損耗，算法的效率越高，一般的代價(jià)方式有曼哈頓距離（式（2）），歐式距離（式（3））和切比雪夫距離（式（4））3 種。而實(shí)際中，曼哈頓距離相對于實(shí)際距離偏大，歐式距離相對于實(shí)際距離偏小。

其中柵格n 的坐標(biāo)為（nx，ny），目標(biāo)柵格的坐標(biāo)為（goalx，goaly）。

如圖4所示，點(diǎn)G為目標(biāo)點(diǎn)，點(diǎn)N為目前所處的點(diǎn)，可以看出，歐式距離是兩點(diǎn)的直線距離，由于移動(dòng)機(jī)器人在規(guī)劃時(shí)肯定會(huì)遇到各種各樣的障礙物，所以實(shí)際消耗的代價(jià)肯定要比歐式距離要大很多，曼哈頓距離為兩條直角邊的和，在絕大多數(shù)的移動(dòng)機(jī)器人場景中這個(gè)距離是大于實(shí)際行走路線的距離，所以可以取曼哈頓和歐式距離的中值作為啟發(fā)函數(shù)

圖4 歐式距離和曼哈頓距離

h（n）的估計(jì)值。根據(jù)以上所述，定義新的啟發(fā)函數(shù)：

3.2 增加父節(jié)點(diǎn)信息

A*算法按照傳統(tǒng)的啟發(fā)函數(shù)h（n）進(jìn)行路徑搜索時(shí)，會(huì)不斷的往返搜索，導(dǎo)致搜索的節(jié)點(diǎn)過多，增加了計(jì)算節(jié)點(diǎn)的數(shù)量，降低了效率。本文加入當(dāng)前節(jié)點(diǎn)父節(jié)點(diǎn)的信息，主要是把當(dāng)前節(jié)點(diǎn)到起點(diǎn)的代價(jià)，當(dāng)前節(jié)點(diǎn)到目標(biāo)點(diǎn)的預(yù)估代價(jià)以及當(dāng)前節(jié)點(diǎn)父節(jié)點(diǎn)到目標(biāo)點(diǎn)的預(yù)估代價(jià)這三者這和作為衡量當(dāng)前節(jié)點(diǎn)是否為目前最佳路徑上的節(jié)點(diǎn)的量度，該想法的表達(dá)式（6）：

式中h（p）是當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)到目標(biāo)點(diǎn)的預(yù)估距離。改進(jìn)的啟發(fā)函數(shù)使得A*算法的搜索方向在實(shí)際搜索中更有目的性地接近終點(diǎn)，減少了算法的遍歷點(diǎn)數(shù)量，提高了算法的速度。當(dāng)然，并不是加入越多的評估點(diǎn)算法效率就越高，隨著評估點(diǎn)的增多，該算法的存儲(chǔ)容量就會(huì)越大，影響算法的性能。故只增加了當(dāng)前節(jié)點(diǎn)父節(jié)點(diǎn)的信息來提高算法速度。當(dāng)然，在后面的仿真實(shí)驗(yàn)中，也驗(yàn)證了本文提出的的這個(gè)改進(jìn)的合理性。

4 仿真結(jié)果及分析

此次實(shí)驗(yàn)的環(huán)境和編譯工具分別為Intel 的Windows 和Matlab 仿真軟件。改進(jìn)過后的A*算法與傳統(tǒng)算法分別進(jìn)行了多次實(shí)驗(yàn)，取其中經(jīng)典的差異進(jìn)行展示，展示的柵格地圖尺寸選取的為100×100，地圖中黑色的方塊均為障礙物，灰色部分為路徑規(guī)劃時(shí)拓展的節(jié)點(diǎn)，白色的線代表著規(guī)劃出來的路徑。仿真結(jié)果如圖5所示。

圖5 A*和改進(jìn)A*算法搜索效果對比圖

從圖5（a）可以看出傳統(tǒng)的A*算法擴(kuò)展的節(jié)點(diǎn)過多，由此帶來占用內(nèi)存過大，計(jì)算時(shí)間過長等問題，導(dǎo)致移動(dòng)機(jī)器人的規(guī)劃時(shí)間較長，沒有很好的實(shí)時(shí)性。改進(jìn)過后的A*算法圖5（b）解決了上述問題，擴(kuò)展結(jié)點(diǎn)大大縮減，規(guī)劃路徑幾近等于擴(kuò)展出來的節(jié)點(diǎn)，沒有大量的往返之前的節(jié)點(diǎn)，計(jì)算速度因此大幅提升，移動(dòng)機(jī)器人的行駛效率也因此得到了大幅提升。具體數(shù)據(jù)對比見表1。

表1 A*算法與改進(jìn)A*算法數(shù)據(jù)對比

由表1 可知，本文改進(jìn)算法在保證得到相似路徑的基礎(chǔ)上，減少了大量不必要柵格的訪問，有效地降低了計(jì)算量，減少了計(jì)算機(jī)資源的消耗，使得移動(dòng)機(jī)器人在實(shí)時(shí)性方面有了很大的改善。經(jīng)過多次仿真實(shí)驗(yàn)驗(yàn)證，本文算法較傳統(tǒng)的A*算法運(yùn)行時(shí)間平均減少了85%，地圖規(guī)模越大，計(jì)算提升時(shí)間越大，保證了移動(dòng)機(jī)器人路徑規(guī)劃的實(shí)時(shí)性。

5 結(jié)語

A*算法在路徑規(guī)劃上存在實(shí)時(shí)性低，內(nèi)存消耗嚴(yán)重的問題，不能滿足機(jī)器人在復(fù)雜、大規(guī)模環(huán)境下的實(shí)時(shí)規(guī)劃要求。為了解決這一關(guān)鍵性問題，本文對A*算法的啟發(fā)函數(shù)進(jìn)行了改進(jìn)，使其更加接近真實(shí)的路徑代價(jià)，同時(shí)增加了父節(jié)點(diǎn)的信息，提高了啟發(fā)函數(shù)在整個(gè)預(yù)估函數(shù)的比重，避免了大部分不必要節(jié)點(diǎn)的探索。仿真結(jié)果表明，無論在大規(guī)模，還是小規(guī)模地圖中，改進(jìn)的A*算法都能大大提升路徑搜索的效率。