基于改進(jìn)A＊算法的AGV轉(zhuǎn)運(yùn)機(jī)器人路徑規(guī)劃研究

石英托 陳 華 張連新 孫鵬飛 裴 培 李代楊

（中國工程物理研究院機(jī)械制造工藝研究所，四川 綿陽 621900）

隨著科學(xué)技術(shù)的發(fā)展，智能存儲(chǔ)等手段層出不窮，如AGV全向車等實(shí)現(xiàn)我國舟山港的無人化，南京晨光集團(tuán)裝配過程中各工位間智能轉(zhuǎn)運(yùn)等。機(jī)器人正逐步替代人工，成為自動(dòng)化生產(chǎn)與運(yùn)輸領(lǐng)域的生力軍。在執(zhí)行某些轉(zhuǎn)運(yùn)任務(wù)時(shí)，需要操作人員完成某些特定工序，與機(jī)器人共享工作空間。由于人的誤操作、機(jī)器人故障等意外，機(jī)器人可能會(huì)與人發(fā)生碰撞，對(duì)人員的安全產(chǎn)生威脅。因此如何保證人與機(jī)器人的安全交互是AGV機(jī)器人廣泛應(yīng)用于自動(dòng)化運(yùn)輸需首要關(guān)注的問題。

機(jī)器人路徑規(guī)劃提供了一種解決方案。路徑規(guī)劃包含兩個(gè)層次，一是避障，控制機(jī)器人能自主避開障礙物；二是最優(yōu)，按照需求規(guī)劃出路徑最短或耗費(fèi)最少的路徑。國內(nèi)外常用的路徑規(guī)劃算法包括Dijkstra算法[1]、A*算法[2]、動(dòng)態(tài)規(guī)劃算法[3]、遺傳算法[4-5]和人工勢(shì)場(chǎng)法[6]等。Geetha S等[7]將蟻群算法與遺傳算法相結(jié)合，在多目標(biāo)路徑規(guī)劃中得到了很好的效果；王志中等[8]提出了基于改進(jìn)粒子群算法的機(jī)器人路徑規(guī)劃方法，改進(jìn)算法規(guī)劃的路徑在長度、平滑度和規(guī)劃時(shí)間上均具有優(yōu)勢(shì)。相比其他算法，A*算法簡單，易實(shí)現(xiàn)，便于機(jī)器人避碰路徑規(guī)劃，但在障礙較多、環(huán)境復(fù)雜的情況下計(jì)算迭代次數(shù)較多，影響其計(jì)算的實(shí)時(shí)性。

本文的研究基于筆者單位在研的某產(chǎn)品高效裝配生產(chǎn)線項(xiàng)目，旨在提出一種改進(jìn)的A*路徑規(guī)劃算法，應(yīng)用于AGV轉(zhuǎn)運(yùn)機(jī)器人運(yùn)動(dòng)控制中，當(dāng)檢測(cè)到運(yùn)動(dòng)路線上出現(xiàn)障礙物后，能夠?qū)崟r(shí)規(guī)劃運(yùn)動(dòng)路徑，實(shí)現(xiàn)AGV機(jī)器人主動(dòng)避碰，從而在不影響轉(zhuǎn)運(yùn)效率的前提下，提高AGV機(jī)器人應(yīng)用的安全性。其主體架構(gòu)為：首先對(duì)AGV機(jī)器人和運(yùn)動(dòng)障礙進(jìn)行分析，建立機(jī)器人運(yùn)動(dòng)交互環(huán)境模型；隨后對(duì)傳統(tǒng)A*算法進(jìn)行分析，提出一種改進(jìn)的A*路徑規(guī)劃算法；接著對(duì)改進(jìn)后的算法進(jìn)行Matlab仿真驗(yàn)證；最后對(duì)文章進(jìn)行總結(jié)。

1 環(huán)境建模

圖1為某產(chǎn)品高效裝配生產(chǎn)線分配了裝配、倉儲(chǔ)等區(qū)域。為節(jié)省人力，提高轉(zhuǎn)運(yùn)效率，不同區(qū)域間產(chǎn)品及工裝的轉(zhuǎn)運(yùn)就依靠AGV轉(zhuǎn)運(yùn)機(jī)器人實(shí)現(xiàn)。

圖1 高效裝配生產(chǎn)線示意圖

AGV轉(zhuǎn)運(yùn)機(jī)器人上裝有導(dǎo)航模塊，能夠?qū)\(yùn)動(dòng)環(huán)境進(jìn)行實(shí)時(shí)掃描，通過控制器計(jì)算與處理，將環(huán)境信息轉(zhuǎn)化為計(jì)算機(jī)可識(shí)別的數(shù)據(jù)，進(jìn)而建立AGV運(yùn)動(dòng)交互環(huán)境模型。

基于環(huán)境信息的建模方法有很多，常用的有拓?fù)鋱D法、柵格法和導(dǎo)航網(wǎng)絡(luò)[9]等。本文采用柵格法進(jìn)行環(huán)境建模，其優(yōu)勢(shì)在于：

（1）利用規(guī)則長方形包絡(luò)障礙物來近似建模，雖然擴(kuò)大了障礙域，所規(guī)劃的路徑并非最短無碰撞路徑，但實(shí)則增大了安全距離，提高了安全性。

（2）柵格法對(duì)隨機(jī)障礙域的表述準(zhǔn)確，不易產(chǎn)生失真等情況，適用于現(xiàn)場(chǎng)復(fù)雜環(huán)境描述。

（3）柵格法對(duì)障礙域的描述相對(duì)簡化，從而提高路徑規(guī)劃的效率。

AGV機(jī)器人在廠區(qū)內(nèi)工作環(huán)境相對(duì)復(fù)雜，運(yùn)動(dòng)路徑上可能出現(xiàn)雜物、操作人員等。AGV導(dǎo)航模塊對(duì)這些障礙進(jìn)行實(shí)時(shí)掃描與識(shí)別，將其外形、位置等信息反饋給主控模塊用于構(gòu)建環(huán)境模型。

基于上述分析，得到AGV機(jī)器人運(yùn)動(dòng)交互環(huán)境建模如圖2所示。其中1（左）為起點(diǎn)，2（右）為終點(diǎn)，黑色部分包含環(huán)境障礙和邊界，同視為障礙。

圖2 AGV機(jī)器人運(yùn)動(dòng)交互環(huán)境建模

2 路徑規(guī)劃算法研究

2.1 A＊算法原理

A*算法是廣泛用于尋路和圖遍歷的計(jì)算機(jī)算法，由于其具有較好的性能和準(zhǔn)確性，經(jīng)常被使用在最短路徑求解中，是一種啟發(fā)式搜索算法。其成本估計(jì)函數(shù)為

式中：f(n)代表從起始節(jié)點(diǎn)經(jīng)由當(dāng)前節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的成本估計(jì)，g(n)代表從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)n的實(shí)際成本，h(n)代表從當(dāng)前節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的最佳路徑的估計(jì)成本。

A*算法步驟為：

（1）將起點(diǎn)S加到OPEN表中。

（2）判斷OPEN表是否為空，若為空，則算法結(jié)束，無法找到路徑，否則進(jìn)入下一步。

（3）從OPEN表中找到f(n)最小的節(jié)點(diǎn)N，添加到CLOSE表中，并判斷該節(jié)點(diǎn)是否為目標(biāo)節(jié)點(diǎn)E，若為目標(biāo)節(jié)點(diǎn)E，算法結(jié)束，否則進(jìn)入下一步。

（4）找到節(jié)點(diǎn)N的所有相鄰節(jié)點(diǎn)Xi（i≤k，k為與節(jié)點(diǎn)N相鄰的全部節(jié)點(diǎn)個(gè)數(shù)）。若Xi不在OPEN表中也不在CLOSE表中，計(jì)算f(Xi)并加入OPEN表中；若Xi在OPEN表中，但是f(Xi)比OPEN表中估計(jì)值小，更新OPEN表中的估計(jì)值，并按從小到大排序；若Xi在CLOSE表中，則忽略該點(diǎn)。

（5）重復(fù)步驟2到步驟4，直到目標(biāo)點(diǎn)E在CLOSE表中，表明已找到最優(yōu)路徑，或OPEN表為空，算法結(jié)束。

在運(yùn)行此算法之后，目標(biāo)節(jié)點(diǎn)將指向其前導(dǎo)節(jié)點(diǎn)，依此類推，直到某個(gè)節(jié)點(diǎn)的前導(dǎo)是開始節(jié)點(diǎn)，就可以得到最短路徑序列。

區(qū)別于Dijkstra算法，A*算法用了一個(gè)啟發(fā)函數(shù)h(n)，使算法利用啟發(fā)信息朝著某個(gè)確定的方向搜索，所以其訪問的節(jié)點(diǎn)比Dijkstra算法少得多，能快速地導(dǎo)向目標(biāo)結(jié)點(diǎn)，訪問到目標(biāo)節(jié)點(diǎn)后算法停止。

2.2 A＊算法不足

A*算法原理簡單，使用靈活，因此在現(xiàn)代路徑規(guī)劃領(lǐng)域應(yīng)用廣泛。但通過對(duì)其計(jì)算過程的分析，可知其存在一定的不足：朝著某個(gè)確定的方向搜索，能快速地導(dǎo)向目標(biāo)結(jié)點(diǎn)。h(n)越小，A*算法需要擴(kuò)展的點(diǎn)越多，運(yùn)行速度越

（1）啟發(fā)函數(shù)的選取對(duì)算法的影響。啟發(fā)函數(shù)可以影響A*算法的運(yùn)行，使算法利用啟發(fā)信息慢，此時(shí)算法運(yùn)行效率較低；h(n)選取過大時(shí)，算法不一定能找到最佳路徑，運(yùn)行質(zhì)量較差。

（2）OPEN表對(duì)存儲(chǔ)空間的占用。當(dāng)?shù)貓D較大、路徑較為發(fā)展時(shí)，OPEN表中會(huì)保存大量待考察的點(diǎn)，對(duì)存儲(chǔ)空間大量占用，使算法在表中插入、排序等操作變慢，影響運(yùn)算效率。

（3）OPEN表中對(duì)成本估計(jì)f(n)的排序運(yùn)算。隨著算法深入，OPEN表中節(jié)點(diǎn)數(shù)持續(xù)增加，每次迭代運(yùn)算都要對(duì)表中各節(jié)點(diǎn)f(n)進(jìn)行計(jì)算和排序，導(dǎo)致運(yùn)算效率下降。

2.3 A＊算法改進(jìn)

結(jié)合2.2小節(jié)對(duì)A*算法不足的分析，提出對(duì)A*算法進(jìn)行改進(jìn)。

2.3.1 啟發(fā)函數(shù)h(n)的選取

在A*算法的估價(jià)函數(shù)中，節(jié)點(diǎn)的g(n)值是實(shí)際值，而其h(n)值 是估值，h(n)選擇得越合理，那么f(n)的值就越接近真實(shí)值，A*算法的效率就會(huì)越高。實(shí)際計(jì)算時(shí)常采用曼哈頓距離、對(duì)角線距離和歐幾里得距離等[10-11]作為啟發(fā)函數(shù)。曼哈頓距離代表標(biāo)準(zhǔn)坐標(biāo)系上絕對(duì)軸距總和；對(duì)角線距離相比曼哈頓距離，考慮了沿對(duì)角線移動(dòng)的情況；歐幾里得距離特點(diǎn)是“兩點(diǎn)一線”，為兩點(diǎn)之間的最短距離。圖3可以對(duì)3種距離進(jìn)行清晰地表述：

圖3 3種距離示意圖

圖中A為起點(diǎn)，B為終點(diǎn)，黑色實(shí)線為各自距離。對(duì)比3種距離，曼哈頓距離運(yùn)算簡單，尋徑的效率高，但尋徑的質(zhì)量較低；歐幾里德距離最短，易求得最短路徑，但計(jì)算涉及平方和開方運(yùn)算，求解效率低；對(duì)角線距離作為啟發(fā)函數(shù)，在進(jìn)行估值運(yùn)算時(shí)與最優(yōu)路徑的估值誤差不大，同時(shí)計(jì)算相對(duì)簡化，因此本文采用對(duì)角線距離啟發(fā)函數(shù)。具體計(jì)算過程如下：

式中：c表示在地圖中水平或豎直移動(dòng)一步的代價(jià)，按對(duì)角線移動(dòng)的代價(jià)則為由式（2）～（4）即可計(jì)算得到對(duì)角線距離的代價(jià)估值 。

2.3.2 OPEN表中節(jié)點(diǎn)數(shù)目優(yōu)化管理

在A*算法進(jìn)行路徑搜索過程中，每向目標(biāo)方向擴(kuò)展一次節(jié)點(diǎn)，就要對(duì)相鄰點(diǎn)f(n)進(jìn)行計(jì)算，并在OPEN表中進(jìn)行排序，導(dǎo)致算法擴(kuò)展速度越來越慢。而實(shí)際上一些早期加入的和估值很大的節(jié)點(diǎn)就因不再需要而成為計(jì)算負(fù)擔(dān)?；诖耍疚奶岢鰧?duì)OPEN表中節(jié)點(diǎn)數(shù)量進(jìn)行管理與優(yōu)化。當(dāng)OPEN表中的節(jié)點(diǎn)數(shù)達(dá)到一定值時(shí)，刪除最早加入的估值較大的節(jié)點(diǎn)，使算法在后續(xù)運(yùn)行過程中，OPEN表中節(jié)點(diǎn)數(shù)量維持恒定，這樣就提高了算法運(yùn)行后期的計(jì)算效率。

對(duì)OPEN表中節(jié)點(diǎn)數(shù)量進(jìn)行優(yōu)化管理后，在同樣的條件下進(jìn)行對(duì)比發(fā)現(xiàn)，運(yùn)算效率得到了提高，同時(shí)擴(kuò)展的節(jié)點(diǎn)并沒有減少，因此仍能夠得到與原算法相同的路徑搜索結(jié)果。

3 仿真驗(yàn)證

改進(jìn)A*算法在路徑搜索中的效果需要通過試驗(yàn)進(jìn)行驗(yàn)證。本文中擬在Matlab環(huán)境中進(jìn)行驗(yàn)證。

仿真試驗(yàn)的軟硬件環(huán)境如下：

軟件：Windows 7旗艦版 64位，Matlab R2015b（x86）；

硬件：CPU Intel Core i5-7500@ 3.40 GHz，內(nèi)存8 G。

仿真實(shí)驗(yàn)采用20×20方格，網(wǎng)格間隔0.2 m的區(qū)域進(jìn)行，建立的環(huán)境模型如圖2所示。隨后分別對(duì)無障礙和不同障礙情況下算法的路徑規(guī)劃效果進(jìn)行仿真驗(yàn)證。仿真結(jié)果如圖4所示：

圖4 不同環(huán)境路徑規(guī)劃結(jié)果

路徑規(guī)劃結(jié)果中，網(wǎng)格變淺灰表示每次迭代運(yùn)算過程中，該點(diǎn)被加入了OPEN表中，網(wǎng)格變深灰表示該點(diǎn)為淺灰點(diǎn)的相鄰待考察點(diǎn)；最終形成的黑色細(xì)線路線即為路徑搜索結(jié)果。

下面對(duì)路徑搜索效率進(jìn)行比較，結(jié)果如表1所示。通過對(duì)仿真試驗(yàn)結(jié)果進(jìn)行分析，可以得出：

表1 路徑規(guī)劃效率比較

（1）改進(jìn)A*算法與A*算法路徑規(guī)劃結(jié)果一致，都能利用啟發(fā)信息，朝著目標(biāo)節(jié)點(diǎn)方向進(jìn)行路徑搜索，從而快速導(dǎo)向至目標(biāo)節(jié)點(diǎn)，同時(shí)都能夠規(guī)避障礙，規(guī)劃出合理路線。

（2）在路徑規(guī)劃效率方面。當(dāng)環(huán)境較為簡單，運(yùn)動(dòng)路線上沒有障礙時(shí)，所規(guī)劃的運(yùn)動(dòng)路徑較為簡單，OPEN表中數(shù)量較少，算法改進(jìn)后效率提升不明顯；當(dāng)環(huán)境較為復(fù)雜，運(yùn)動(dòng)路線上出現(xiàn)障礙時(shí)，在路徑規(guī)劃迭代運(yùn)算過程中，OPEN表中數(shù)量逐漸增加，算法改進(jìn)后效率提升較為明顯；且當(dāng)運(yùn)動(dòng)路線上障礙越復(fù)雜時(shí)，算法改進(jìn)后效率提升更加明顯。

4 結(jié)語

本文針對(duì)提高AGV轉(zhuǎn)運(yùn)機(jī)器人在高效裝配生產(chǎn)線項(xiàng)目應(yīng)用中的安全性，提出了一種改進(jìn)A*路徑規(guī)劃算法，應(yīng)用于機(jī)器人運(yùn)動(dòng)控制中，能夠在不影響轉(zhuǎn)運(yùn)效率的前提下，實(shí)現(xiàn)機(jī)器人主動(dòng)避碰。通過仿真試驗(yàn)，得出改進(jìn)A*算法與A*算法路徑規(guī)劃一致，都能利用啟發(fā)信息，快速導(dǎo)向至目標(biāo)節(jié)點(diǎn)；算法改進(jìn)后，路徑規(guī)劃效率得到提升，且當(dāng)運(yùn)動(dòng)路線上障礙越復(fù)雜，效率提升越明顯。因此，可認(rèn)為改進(jìn)A*算法能夠規(guī)劃路線，實(shí)現(xiàn)AGV機(jī)器人主動(dòng)避障。