基于改進(jìn)A*算法的機(jī)器人路徑搜索的研究

谷月 張德育 晉峰高

摘 ?要：隨著全球科技技術(shù)的不斷發(fā)展，人類對(duì)未知的不斷探索和對(duì)科技的需求不斷增加，移動(dòng)機(jī)器人也在科技的浪潮中應(yīng)運(yùn)而生，并且一直處在人工智能科技的前沿。移動(dòng)機(jī)器人的應(yīng)用與人們的生活聯(lián)系越來越緊密，其最重要的研究方向是對(duì)路徑搜索算法的研究，比如某些尋路游戲機(jī)器人、資源探索機(jī)器人、自動(dòng)尋路機(jī)器人、搜索營救機(jī)器人等。該文對(duì)機(jī)器人路徑搜索算法的研究，在A*算法的基礎(chǔ)上做了改進(jìn)，整體提高了搜索的效率。

關(guān)鍵詞：人工智能;移動(dòng)機(jī)器人;路徑搜索;A*算法

中圖分類號(hào)：TP242 ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-4706（2020）13-0030-03

Abstract：With the continuous development of global science and technology，humans continuous exploration of the unknown and the increasing demand for science and technology in the process，the development of intelligent robot also arises at the historic moment in the tide of science and technology，has been in the forefront of artificial intelligence technology. The application of mobile robot is more and more closely related to people's life. The most important research direction of intelligent robots is the study of path search algorithms，such as some pathfinding game robots，resource exploration robots，automatic pathfinding robots，search and rescue robots，etc. The research on the robot path search algorithm is improved on the basis of the A* algorithm，which improves the search efficiency as a whole.

Keywords：artificial intelligence;mobile robot;path search;A* algorithm

0 ?引 ?言

近年來，人工智能技術(shù)不斷發(fā)展，其在移動(dòng)機(jī)器人的應(yīng)用越來越廣泛，移動(dòng)機(jī)器人在實(shí)際生活中應(yīng)用最多、最重要的是路徑搜索問題。在未知環(huán)境中，通過移動(dòng)機(jī)器人進(jìn)行路徑搜索的研究還不是太完備，搜索算法的效率還有待提升。移動(dòng)機(jī)器人的路徑搜索問題主要是從搜索時(shí)間、搜索效率、搜索能耗等方面進(jìn)行研究的，機(jī)器人的路徑搜索所解決的問題是在復(fù)雜環(huán)境中自主搜索出一條可行的較優(yōu)路徑。目前廣泛使用的搜索算法是啟發(fā)式搜索算法中的A*算法，在簡(jiǎn)單環(huán)境下，A*算法可以較高效地搜索出最優(yōu)路徑。但是在復(fù)雜環(huán)境下，移動(dòng)機(jī)器人使用A*算法進(jìn)行路徑搜索卻變得不那么容易，搜索的效率還有待提高，因?yàn)閺?fù)雜環(huán)境下障礙物的分布多且形狀復(fù)雜，機(jī)器人需要在避障的同時(shí)搜索路徑，因此對(duì)路徑搜索算法的效率會(huì)有影響，一些常用的路徑搜索算法在復(fù)雜環(huán)境下的搜索效率也會(huì)受到很大的影響。

因此本文基于校內(nèi)對(duì)移動(dòng)機(jī)器人路徑搜索項(xiàng)目的研究，以A*算法為研究重點(diǎn)，進(jìn)行改進(jìn)，對(duì)移動(dòng)機(jī)器人路徑搜索的整個(gè)過程進(jìn)行研究。并提出改進(jìn)的想法，闡述改進(jìn)的過程。

1 ?復(fù)雜環(huán)境中環(huán)境模型的建立

環(huán)境模型的建立是路徑搜索算法研究過程中非常重要的一步，環(huán)境模型的建立有視圖法、拓?fù)浞ê蜄鸥穹ā鸥穹ㄊ怯梢粋€(gè)個(gè)大小相等的正方形小格組成，構(gòu)成一個(gè)連通圖，可用坐標(biāo)表示各個(gè)柵格，障礙物在柵格中用黑色表示。路徑搜索算法搜索路徑的過程就是設(shè)置一個(gè)初始節(jié)點(diǎn)和一個(gè)目標(biāo)節(jié)點(diǎn)，通過搜索算法生成從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最優(yōu)路徑。

機(jī)器人的環(huán)境模型是對(duì)其現(xiàn)實(shí)環(huán)境的仿照，為了更準(zhǔn)確地描述機(jī)器人所處的環(huán)境，采用正方形柵格表示法來建立環(huán)境模型。按照真實(shí)的地圖環(huán)境和機(jī)器人的大小比例，建立大小合適的正方形柵格地圖用于算法的研究，在這里我們將被控物體看成是點(diǎn)狀物體，它的移動(dòng)環(huán)境是二維平面，黑色格塊對(duì)應(yīng)柵格地圖中的障礙物，白色格塊是可以通行的自由格塊;將每一個(gè)正方形柵格與坐標(biāo)相對(duì)應(yīng)，坐標(biāo)可用P（x，y）表示，每個(gè)柵格都有對(duì)應(yīng)的屬性。

當(dāng)柵格的屬性為0時(shí)，柵格為自由柵格，可以通行;當(dāng)柵格的屬性為1時(shí)，柵格為障礙物柵格，不可以通行;當(dāng)柵格的屬性為2時(shí)，柵格表示路徑搜索的初始位置;當(dāng)柵格的屬性為3時(shí)，柵格表示路徑搜索的目標(biāo)位置。

柵格大小的選取影響著整個(gè)移動(dòng)機(jī)器人路徑搜索算法的效率，柵格如果選取得過大，相應(yīng)的計(jì)算量會(huì)變少，但得到的路徑長(zhǎng)度可能會(huì)變大;另一方面，柵格選取得過小，雖然搜索路徑的效率會(huì)提高，但是搜索時(shí)間會(huì)變長(zhǎng)，搜索過程緩慢。所以柵格大小的選取根據(jù)所處的環(huán)境來決定，柵格長(zhǎng)度選取為l=（r+R）+λ;其中，r是障礙物的半徑大小，R是機(jī)器人的半徑大小，λ是設(shè)定的安全距離。由以上條件可知，移動(dòng)機(jī)器人在復(fù)雜環(huán)境下路徑搜索算法的研究可轉(zhuǎn)化為通過在已得到的環(huán)境模型中的無障礙物的區(qū)域搜索，最終得到的一個(gè)連續(xù)路徑。

2 ?A*搜索算法的改進(jìn)

啟發(fā)式算法是路徑搜索算法中最常用的搜索算法，A*算法也屬于其中，啟發(fā)式搜索算法就是根據(jù)對(duì)柵格地圖中每一個(gè)柵格的相鄰柵格位置進(jìn)行搜索比較，從相鄰柵格中找到距離目標(biāo)點(diǎn)最近的柵格，再從這個(gè)柵格進(jìn)行搜索比較，直到搜索到目標(biāo)節(jié)點(diǎn)為止。然而在啟發(fā)式搜索中，對(duì)于柵格位置的評(píng)估是十分重要的，根據(jù)選取最佳搜索節(jié)點(diǎn)的策略不同，采用不同的估價(jià)函數(shù)有著不同的效果，其中A*搜索算法中的估價(jià)函數(shù)表示為：

傳統(tǒng)A*算法能夠有效地對(duì)目標(biāo)進(jìn)行全局路徑搜索，但是在較為復(fù)雜的環(huán)境中，A*算法優(yōu)化后得到的路徑冗余點(diǎn)較多、運(yùn)動(dòng)路線折線多、轉(zhuǎn)折次數(shù)多、轉(zhuǎn)折角度大，這些缺陷嚴(yán)重影響路徑搜索的效果，直接影響算法的執(zhí)行效率。為此，本文提出對(duì)傳統(tǒng)A*算法改進(jìn)的想法，并對(duì)考察節(jié)點(diǎn)數(shù)、花費(fèi)時(shí)間、路徑開銷和是否最優(yōu)四個(gè)方面進(jìn)行優(yōu)化改進(jìn)。在標(biāo)準(zhǔn)A*算法的基礎(chǔ)上增加父節(jié)點(diǎn)，防止走到死路，減少冗余點(diǎn)。該A*算法改進(jìn)成跳點(diǎn)搜索的方法進(jìn)行優(yōu)化，這種方法能夠減少搜索的節(jié)點(diǎn)和轉(zhuǎn)折次數(shù)。

本文對(duì)A*改進(jìn)并進(jìn)行路徑搜索的流程圖如圖1所示。

2.1 ?A*搜索算法流程

傳統(tǒng)A*搜索算法的搜索步驟如下：

（1）把起始節(jié)點(diǎn)看作是點(diǎn)A進(jìn)行搜索，建立一個(gè)開啟列表，將點(diǎn)A加入此列表。開啟列表存儲(chǔ)待搜索的節(jié)點(diǎn)。

（2）在節(jié)點(diǎn)A的可搜索方向進(jìn)行搜索，搜索所有可到達(dá)目標(biāo)節(jié)點(diǎn)的相鄰節(jié)點(diǎn)，將這些節(jié)點(diǎn)存儲(chǔ)到開啟列表中。

（3）節(jié)點(diǎn)A已經(jīng)搜索完畢，就從開啟列表中將其刪除，將節(jié)點(diǎn)A加入閉合列表。

（4）按照公式F=G+H計(jì)算A點(diǎn)所有周圍點(diǎn)的H值，選取開啟列表中H值最低的節(jié)點(diǎn)B，將此節(jié)點(diǎn)作為A之后搜尋到的節(jié)點(diǎn)，并加入閉合列表中。

（5）繼續(xù)從B節(jié)點(diǎn)開始搜索所有相鄰節(jié)點(diǎn)，除去閉合列表中的節(jié)點(diǎn)。

（6）如果存在B的相鄰節(jié)點(diǎn)不在開啟列表中，則將它們加入，如果節(jié)點(diǎn)B的相鄰節(jié)點(diǎn)都已經(jīng)在開啟列表中，并且存在G值低于B點(diǎn)G值的點(diǎn)，那么放棄B節(jié)點(diǎn)作為A的下一個(gè)節(jié)點(diǎn)。然后按照F值最低原則選擇開啟列表里其他節(jié)點(diǎn)作為A點(diǎn)的下一個(gè)節(jié)點(diǎn)。

（7）重復(fù)這個(gè)過程，直到目標(biāo)節(jié)點(diǎn)被添加進(jìn)關(guān)閉列表。

2.2 ?A*回溯算法

傳統(tǒng)的A*算法是通過將搜索路徑過程中的信息存儲(chǔ)起來，然后再從最后一個(gè)節(jié)點(diǎn)信息向第一個(gè)信息節(jié)點(diǎn)逆向提取，提取出的節(jié)點(diǎn)可形成一條路徑，即為搜索到的路徑。但是在多障礙物的環(huán)境下會(huì)出現(xiàn)死胡同現(xiàn)象，搜索過程中無法找到下一個(gè)最優(yōu)節(jié)點(diǎn)，搜索過程一直等待，無法進(jìn)行下去，形成死路，無法搜索到最優(yōu)路徑。算法的搜索效率變低，因此改進(jìn)的A*回溯算法是在原來的基礎(chǔ)上增加了父節(jié)點(diǎn)，避免走彎路，而且在較為復(fù)雜的環(huán)境中也能更好地進(jìn)行路徑搜索。從而達(dá)到提取最優(yōu)路徑的效果。

本文通過增加父指針對(duì)搜索步驟進(jìn)行改進(jìn)，如果當(dāng)前搜索到的下一個(gè)節(jié)點(diǎn)比當(dāng)前節(jié)點(diǎn)更優(yōu)時(shí)，就刪除當(dāng)前節(jié)點(diǎn)，將當(dāng)前節(jié)點(diǎn)加入閉合列表。然后父指針就指向該節(jié)點(diǎn)。搜索的過程不會(huì)改變。最終會(huì)通過閉合列表和父節(jié)點(diǎn)列表，根據(jù)父指針開始逆向搜索到開始節(jié)點(diǎn)，忽略冗余點(diǎn)，得到路徑。

在搜索節(jié)點(diǎn)的數(shù)目上、搜索時(shí)間上，增加父節(jié)點(diǎn)的A*回溯算法比標(biāo)準(zhǔn)A*算法有明顯的優(yōu)勢(shì)，A*回溯算法有效地避免了死路，有效節(jié)省了路徑開銷。

2.3 ?A*跳點(diǎn)搜索

在路徑優(yōu)化過程中，為了進(jìn)一步減少搜索的節(jié)點(diǎn)和冗余點(diǎn)，在A*算法搜索過的路徑節(jié)點(diǎn)中，選取跳點(diǎn)作為新的節(jié)點(diǎn)，將式（1）中的估價(jià)函數(shù)作為初始值進(jìn)行比較，根據(jù)代價(jià)函數(shù)的大小比較和不穿過障礙物為評(píng)價(jià)標(biāo)準(zhǔn)。如果選取的跳點(diǎn)的代價(jià)函數(shù)小于初始值并且沒有穿過障礙物，則選取這個(gè)跳點(diǎn)為新的路徑節(jié)點(diǎn)，將這些新的路徑節(jié)點(diǎn)連接起來就組成了新的路徑，僅包含開始節(jié)點(diǎn)、中間轉(zhuǎn)折點(diǎn)和目標(biāo)節(jié)點(diǎn)。

3 ?實(shí)驗(yàn)結(jié)果與分析

經(jīng)過改進(jìn)后的A*算法與標(biāo)準(zhǔn)A*算法的路徑搜索仿真如圖所示，圖2為傳統(tǒng)的A*算法路徑仿真圖，圖3為改進(jìn)后的A*算法路徑仿真圖。

由仿真圖的對(duì)比中可以看出改進(jìn)算法后搜索的路徑冗余點(diǎn)減少、運(yùn)動(dòng)路線折線減少、轉(zhuǎn)折次數(shù)變少、轉(zhuǎn)折角度更平滑。

4 ?結(jié) ?論

本文在A*算法的基礎(chǔ)上對(duì)移動(dòng)機(jī)器人的路徑搜索進(jìn)行研究，引入了父節(jié)點(diǎn)，對(duì)一些搜尋到死路節(jié)點(diǎn)時(shí)的情況進(jìn)行了優(yōu)化;而且通過A*回溯算法可以刪除多余的冗余點(diǎn)，縮短路徑搜索的時(shí)間。再進(jìn)一步通過跳點(diǎn)搜索的原理，將A*回溯算法搜索的路徑進(jìn)行優(yōu)化，進(jìn)一步減少擴(kuò)展節(jié)點(diǎn)，將整個(gè)搜索的路徑長(zhǎng)度縮短、減少轉(zhuǎn)折次數(shù)、縮小轉(zhuǎn)折角度、平滑搜索到的路徑，在一定情況下可以提高路徑搜索的效率，優(yōu)化路徑搜索的結(jié)果。

參考文獻(xiàn)：

[1] 柯星.動(dòng)態(tài)環(huán)境下多移動(dòng)機(jī)器人路徑規(guī)劃研究 [D].成都：電子科技大學(xué)，2013.

[2] 鄔再新，李艷宏，劉濤.多移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)的研究現(xiàn)狀與展望 [J].機(jī)械，2008（1）：1-3+16.

[3] 王洪斌，郝策，張平，等.基于A*算法和人工勢(shì)場(chǎng)法的移動(dòng)機(jī)器人路徑規(guī)劃 [J].中國機(jī)械工程，2019，30（20）：2489-2496.

[4] 王殿君.基于改進(jìn)A*算法的室內(nèi)移動(dòng)機(jī)器人路徑規(guī)劃 [J].清華大學(xué)學(xué)報(bào)（自然科學(xué)版），2012，52（8）：1085-1089.

[5] 紀(jì)海賓，師彩云.基于Origin的移動(dòng)機(jī)器人測(cè)距傳感器參數(shù)標(biāo)定 [J].現(xiàn)代信息科技，2020，4（9）：40-42+45.

作者簡(jiǎn)介：谷月（1996—），女，漢族，河北任丘人，碩士，研究方向：系統(tǒng)監(jiān)控與網(wǎng)絡(luò)管理技術(shù)。