王溫鑫

（仰恩大學(xué) 工程技術(shù)學(xué)院，福建泉州，362000）

0 引言

谷物干燥是谷物收獲后需要處理的重要步驟，不僅保證了谷物的品質(zhì)而且能夠提高谷物的出谷率。因氣候原因，谷物可能由于沒有曬干達(dá)不到安全水分的要求，導(dǎo)致其產(chǎn)量受到損失，因此對谷物進(jìn)行翻曬使其充分干燥，將損失降低到最低點(diǎn)是谷物生產(chǎn)、豐收的重要保障。目前谷物翻曬主要有兩種方式：一是人工翻曬，該方案不僅勞動(dòng)強(qiáng)度大且易受天氣的影響；二是使用大型機(jī)械設(shè)備進(jìn)行烘干，該方法成本高且產(chǎn)生的廢氣會(huì)對空氣造成一定的污染。因此為了減少翻曬勞動(dòng)力和降低干燥成本，研發(fā)一款小型自動(dòng)翻曬谷物機(jī)器人是非常有價(jià)值的。隨著精準(zhǔn)農(nóng)業(yè)的大力推廣，全覆蓋路徑規(guī)劃是翻曬谷物機(jī)器人對谷物進(jìn)行全面均勻翻曬的研究重點(diǎn)。在國外，Khan A 等人利用在線牛耕分解法對未知工作空間進(jìn)行區(qū)域劃分，并利用所提出的雙向鄰近搜索算法，使用回溯技術(shù)完成區(qū)域全覆蓋[1]；Hong 等人利用啟發(fā)式模板規(guī)則并結(jié)合貪心準(zhǔn)則的回溯機(jī)制實(shí)現(xiàn)區(qū)域全覆蓋[2]；Ma 等人提出一種高精度定位、低分辨率柵格建模方法，并利用生物激勵(lì)網(wǎng)絡(luò)實(shí)現(xiàn)移動(dòng)機(jī)器人的全覆蓋路徑規(guī)劃[3]。在國內(nèi)，聶楊利用無標(biāo)識(shí)工作區(qū)域的邊界建立和識(shí)別方法，引導(dǎo)機(jī)器人完成草坪邊界信息的采集，然后將A*算法與往復(fù)式算法相結(jié)合實(shí)現(xiàn)割草機(jī)器人的全區(qū)域覆蓋路徑規(guī)劃[4]；李楷提出一種起始點(diǎn)方向優(yōu)先的局部區(qū)域覆蓋算法，然后結(jié)合改進(jìn)的theta*算法進(jìn)行子區(qū)域間的銜接，實(shí)現(xiàn)全覆蓋路徑規(guī)劃[5]；周琳娜等人提出利用牛耕分解法對環(huán)境地圖進(jìn)行劃分，然后將生物激勵(lì)神經(jīng)網(wǎng)絡(luò)算法與深度優(yōu)先算法相結(jié)合完成作業(yè)區(qū)域全覆蓋[6]。

為了使谷物機(jī)器人對谷物實(shí)現(xiàn)全面的均勻翻曬，提高谷物翻曬效率。本文提出一種基于改進(jìn)A*算法的全覆蓋路徑規(guī)劃方法。首先，設(shè)計(jì)了面向谷物翻曬機(jī)器人的環(huán)境建模方法和區(qū)域劃分策略。接著根據(jù)谷物機(jī)器人的作業(yè)能量消耗與實(shí)際需求，利用沿長邊行走的弓子型往返式路徑規(guī)劃方法，實(shí)現(xiàn)子區(qū)域全覆蓋。其次，通過貪婪算法與距離公式相結(jié)合的方式，對下一個(gè)子區(qū)域的起點(diǎn)進(jìn)行選擇。然后，利用優(yōu)化后的A*算法和Bezier 曲線（B-A*）實(shí)現(xiàn)區(qū)域銜接，通過仿真分析可知，B-A*算法可減少節(jié)點(diǎn)搜索時(shí)間，規(guī)劃出的路徑更加平滑、安全。最后，利用上述全覆蓋路徑規(guī)劃策略進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明該方案可實(shí)現(xiàn)全覆蓋，說明了該方案的有效性和可行性。

1 翻曬谷物機(jī)器人全覆蓋路徑規(guī)劃性能指標(biāo)

翻曬谷物機(jī)器人全覆蓋路徑規(guī)劃并不是點(diǎn)到點(diǎn)的路徑規(guī)劃，而是通過點(diǎn)到線，再從線到面，最終將規(guī)定區(qū)域內(nèi)所有的空白區(qū)域全部覆蓋完畢。本文對翻曬谷物機(jī)器人的全覆蓋路徑性能指標(biāo)主要有以下幾方面：

（1）機(jī)器人能夠避開行走過程中的所有障礙物，并遍歷完工作區(qū)域內(nèi)的其他所有地方。

（2）為了利于實(shí)際機(jī)器人的行駛，應(yīng)盡量使用直線、曲線這樣的運(yùn)動(dòng)軌跡。

（3）翻曬谷物機(jī)器人應(yīng)當(dāng)盡量減少整個(gè)遍歷過程中的能量消耗。

全覆蓋路徑規(guī)劃的含義可由以上幾個(gè)方面的指標(biāo)所體現(xiàn)，覆蓋率越高，機(jī)器人轉(zhuǎn)彎次數(shù)越少、能量消耗越低越能體現(xiàn)算法的優(yōu)越性。全覆蓋路徑規(guī)劃算法還有一個(gè)重要指標(biāo)為重復(fù)率，由于本文是針對翻曬谷物機(jī)器人對谷物進(jìn)行翻曬作業(yè)，可在機(jī)器人行駛過程中對谷物進(jìn)行重復(fù)翻曬，因此本文不考慮重復(fù)率這一指標(biāo)。

2 翻曬谷物機(jī)器人全覆蓋路徑規(guī)劃

2.1 環(huán)境建模

本文利用柵格法[7～8]創(chuàng)建作業(yè)環(huán)境模型，單位柵格長度為機(jī)器人的尺寸大小。在柵格法中，每個(gè)柵格都會(huì)通過一個(gè)值來衡量該柵格的可行率，一般來說，使用0 來代表可行柵格，即機(jī)器人可通過該柵格區(qū)域；使用1 來代表障礙柵格，即機(jī)器人不可移動(dòng)的區(qū)域。由于本文研究的是全覆蓋路徑規(guī)劃算法，所以柵格也需要記錄自身是否已經(jīng)被機(jī)器人所覆蓋的信息。根據(jù)柵格是否已覆蓋，又可將柵格劃分為已覆蓋柵格和未覆蓋柵格。根據(jù)以上信息的組合后，柵格有以下三種狀態(tài)：可通行并未覆蓋區(qū)域、可通行但已覆蓋區(qū)域、障礙物，具體的數(shù)字編碼情況如表1 所示。根據(jù)柵格法，對環(huán)境進(jìn)行相應(yīng)的建模，結(jié)果如圖1 所示。空白柵格代表可通行區(qū)域，黑色柵格代表障礙物。

圖1 環(huán)境地圖柵格化

表1 柵格數(shù)字編碼情況

2.2 區(qū)域分割

區(qū)域分割是將作業(yè)環(huán)境根據(jù)障礙物分布情況，利用相關(guān)算法將工作環(huán)境劃分為多個(gè)子區(qū)域，使得各個(gè)子區(qū)域內(nèi)不再包含障礙物。傳統(tǒng)區(qū)域分割法是梯形分解法[9～11]，牛耕分解法[12]在梯形分解法基礎(chǔ)上進(jìn)行相應(yīng)的改進(jìn)，該方法通過一條垂直線從左到右按照平移方向掃過具有多邊形障礙物的區(qū)域，每遇到障礙物頂點(diǎn)可上下延伸的臨界點(diǎn)進(jìn)行分割，最終作業(yè)環(huán)境被分割成多個(gè)不含障礙物的子區(qū)域，其示意圖如圖2 所示。相比梯形分解法，該方法產(chǎn)生更少的子區(qū)域，可減少機(jī)器人作業(yè)時(shí)對地圖環(huán)境的分解時(shí)間，提高機(jī)器人的工作效率，因此本文采用牛耕分解法作為區(qū)域劃分方法，進(jìn)而為后續(xù)機(jī)器人進(jìn)行全覆蓋路徑規(guī)劃做準(zhǔn)備。

圖2 牛耕分解法示意圖

2.3 子區(qū)域內(nèi)部遍歷算法

利用牛耕分解法對環(huán)境地圖進(jìn)行分區(qū)后，關(guān)鍵步驟是完成對子區(qū)域內(nèi)部的遍歷。針對內(nèi)部區(qū)域遍歷主要有往返式弓子形和螺旋式路徑規(guī)劃，基于同一區(qū)域，文獻(xiàn)[13]對兩種路徑規(guī)劃方法在路徑長度和轉(zhuǎn)彎次數(shù)兩方面進(jìn)行實(shí)驗(yàn)對比，發(fā)現(xiàn)弓子形路徑更優(yōu)。另外針對往返式弓子型路徑規(guī)劃，需要對谷物機(jī)器人的行走方向進(jìn)行確定。在同一區(qū)域，機(jī)器人分別沿著長邊和短邊行走，發(fā)現(xiàn)直線行駛距離以及轉(zhuǎn)彎次數(shù)各不相同，這將導(dǎo)致其在區(qū)域內(nèi)的行走軌跡以及對整個(gè)區(qū)域覆蓋所消耗的能量也會(huì)產(chǎn)生一定的差異，文獻(xiàn)[14]討論了機(jī)器人在相同區(qū)域內(nèi)，分別沿著不同方向進(jìn)行弓子形路徑規(guī)劃行走軌跡，發(fā)現(xiàn)沿長邊行走機(jī)器人的轉(zhuǎn)彎次數(shù)較少，能量消耗較小，因此本文選用沿長邊行走的往返式弓子形遍歷規(guī)則實(shí)現(xiàn)對子區(qū)域的全覆蓋。

2.4 子區(qū)域銜接起點(diǎn)的選擇

當(dāng)完成對谷物翻曬場劃分為一系列簡單的無障礙子區(qū)域，并對當(dāng)前的子區(qū)域完成全覆蓋后，需要規(guī)劃出一條路徑對下一個(gè)子區(qū)域進(jìn)行銜接，然后結(jié)合弓子型路徑完成對下一個(gè)子區(qū)域進(jìn)行順序覆蓋。在進(jìn)行區(qū)域銜接路徑規(guī)劃時(shí)，需要尋找到下一個(gè)區(qū)域的起點(diǎn)。為了減少內(nèi)存的消耗以及搜索時(shí)間，對于起點(diǎn)的選取，本文在算法程序中：

（1）只記錄區(qū)域在進(jìn)行劃分過程中，與障礙物、區(qū)域邊界交點(diǎn)所產(chǎn)生的頂點(diǎn)信息。通過這種方式可減少起點(diǎn)的數(shù)量，進(jìn)而減少完成整體全覆蓋路徑規(guī)劃所需要的時(shí)間。

（2）下一個(gè)區(qū)域的起點(diǎn)與上一個(gè)區(qū)域的終點(diǎn)之間的距離應(yīng)最小，這樣可減少谷物機(jī)器人行走的路徑長度，降低消耗的能量。

為此針對如何選取下一個(gè)區(qū)域的起始點(diǎn)，本文利用貪婪算法與曼哈頓距離公式相結(jié)合的方式，以曼哈頓距離公式作為貪婪算法的選擇策略，每次選取與當(dāng)前位置最近的區(qū)域頂點(diǎn)作為下一個(gè)區(qū)域的起點(diǎn)，算法描述如下：

其中，tn表示當(dāng)前區(qū)域的終點(diǎn)，n表示下一個(gè)區(qū)域的起點(diǎn)。則所有可選擇的起點(diǎn)可表示為：

式中，nmin為選擇出的下一個(gè)覆蓋區(qū)域的起點(diǎn)。

2.5 子區(qū)域銜接路徑規(guī)劃

2.5.1 傳統(tǒng)A*算法

翻曬谷物機(jī)器人的全覆蓋路徑算法即機(jī)器人從起始點(diǎn)出發(fā)，通過對翻曬環(huán)境進(jìn)行區(qū)域劃分、進(jìn)行子區(qū)域全覆蓋、對下一個(gè)子區(qū)域的起點(diǎn)進(jìn)行選取、建立子區(qū)域間的路徑銜接最終完成整個(gè)工作環(huán)境的全覆蓋路徑規(guī)劃。本文選擇以當(dāng)前區(qū)域的終點(diǎn)為起點(diǎn)，以下一個(gè)區(qū)域的起點(diǎn)為目標(biāo)點(diǎn)利用A*算法[15～17]實(shí)現(xiàn)區(qū)域銜接路徑規(guī)劃。另外A*算法也可作為在整個(gè)環(huán)境地圖中避障算法。

A*算法是利用啟發(fā)式函數(shù)來進(jìn)行搜索路徑，主要通過代價(jià)函數(shù)進(jìn)行路徑規(guī)劃，從起點(diǎn)位置向附近的子節(jié)點(diǎn)進(jìn)行擴(kuò)展，評價(jià)函數(shù)根據(jù)子節(jié)點(diǎn)距離代價(jià)值最小的節(jié)點(diǎn)選為下一父節(jié)點(diǎn)，重復(fù)此過程直到完成路徑規(guī)劃，生成最終路徑。

啟發(fā)式函數(shù)的一般表達(dá)式為：

式中，F(xiàn)（n） 表示從起始點(diǎn)經(jīng)過任意節(jié)點(diǎn)n到達(dá)目標(biāo)點(diǎn)的總代價(jià)值，g（n） 為從起始點(diǎn)到任意節(jié)點(diǎn)n的實(shí)際距離評估值，h（n） 為從任意節(jié)點(diǎn)n到達(dá)目標(biāo)點(diǎn)的估計(jì)值。

根據(jù)對傳統(tǒng)A*算法進(jìn)行尋路過程的研究發(fā)現(xiàn)，若將該算法直接應(yīng)用于實(shí)際中的翻曬谷物機(jī)器人進(jìn)行全覆蓋路徑規(guī)劃，其還存在一定的缺陷，需要對其進(jìn)行優(yōu)化，以便更好地完成任務(wù)。本文將從以下兩個(gè)關(guān)鍵問題對傳統(tǒng)A*算法進(jìn)行優(yōu)化和改進(jìn)：

①從A*算法的啟發(fā)函數(shù)來看，g（n） 為定值，因此對其進(jìn)行修改所起到的作用不明顯。估計(jì)函數(shù)h（n） 才是啟發(fā)函數(shù)的靈魂所在，因此估計(jì)函數(shù)的優(yōu)劣會(huì)決定A*算法能否高效、準(zhǔn)確地判斷出下一個(gè)節(jié)點(diǎn)。在傳統(tǒng)的A*算法進(jìn)行節(jié)點(diǎn)搜索的過程中，會(huì)搜索大量不必要的節(jié)點(diǎn)，導(dǎo)致搜索時(shí)間變長，增加計(jì)算量，使路徑規(guī)劃效率變低。

②平滑度差。傳統(tǒng)A*算法的節(jié)點(diǎn)搜索方向僅限于柵格之間的相交位置，使得規(guī)劃出來的路徑轉(zhuǎn)折點(diǎn)多，搜索方向易受到谷物機(jī)器人轉(zhuǎn)彎半徑的影響，不利于實(shí)際機(jī)器人的行駛，另外實(shí)際中多次轉(zhuǎn)彎的代價(jià)會(huì)影響谷物機(jī)器人的運(yùn)行效率。

2.5.2 改進(jìn)A*算法

傳統(tǒng)的A*算法在節(jié)點(diǎn)搜索的過程中會(huì)產(chǎn)生大量的不必要節(jié)點(diǎn)，從而導(dǎo)致搜索時(shí)間長，路徑規(guī)劃效率低。為了使算法在搜索的過程中，能夠盡快地朝向目標(biāo)點(diǎn)前進(jìn)，本文對估價(jià)函數(shù)h（n）進(jìn)行優(yōu)化和改進(jìn)，該函數(shù)對于A*算法的運(yùn)行速度有著非常重要的影響，現(xiàn)對估價(jià)函數(shù)h（n） 和代價(jià)函數(shù)g（n）之間的關(guān)系對A*算法的影響進(jìn)行討論：

①當(dāng)h（n） = 0時(shí)，只有g(shù)（n）起作用，A*算法將會(huì)演變?yōu)镈ijkstra 算法，該算法是一種盲目式搜索算法，因此會(huì)擴(kuò)展更多無用節(jié)點(diǎn)，搜索效率低。

②當(dāng)h（n） ＜g（n）時(shí)，此時(shí)可找到一條最短路徑，但隨著搜索不斷地向終點(diǎn)靠近，h（n）不斷地減少，此時(shí)會(huì)使得A*算法搜索擴(kuò)展的節(jié)點(diǎn)變多，搜索時(shí)間變長，導(dǎo)致機(jī)器人尋徑效率變低。

③當(dāng)h（n） =g（n）時(shí)，A*算法將會(huì)僅僅尋找最佳路徑上的節(jié)點(diǎn)，不會(huì)擴(kuò)展別的任何節(jié)點(diǎn)，此時(shí)運(yùn)行速度最快。

④當(dāng)h（n） ＞g（n）時(shí)，此種狀態(tài)會(huì)比②時(shí)的速度快，搜索節(jié)點(diǎn)減小，運(yùn)行效率變高，但不能保證搜索得到最優(yōu)路徑。

⑤當(dāng)h（n） ＞＞g（n）時(shí)，此時(shí)只有h（n） 起作用，該算法演變?yōu)锽FS 算法，該算法是一種啟發(fā)式搜索算法，利用啟發(fā)函數(shù)使得擴(kuò)展節(jié)點(diǎn)變少，搜索效率高，但不一定能搜索到最短路徑。

因此在設(shè)計(jì)估價(jià)函數(shù)時(shí)，應(yīng)保證g（n） 和h（n） 最好能在同一個(gè)數(shù)量級，避免出現(xiàn)極端情況的出現(xiàn)。

本文選用歐幾里得距離公式作為估價(jià)函數(shù)，A*算法在傳統(tǒng)的估計(jì)函數(shù)的影響下，只會(huì)單一地進(jìn)行往返搜索生成大量的搜索節(jié)點(diǎn)，而在實(shí)際情況中當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)之間的距離一定會(huì)大于實(shí)際路徑的消耗值，因此需要加快當(dāng)前節(jié)點(diǎn)向目標(biāo)節(jié)點(diǎn)的收斂速度，即增大估價(jià)函數(shù)h（n） 的權(quán)重。該權(quán)值的選擇應(yīng)滿足當(dāng)h（n） 較大時(shí)，當(dāng)前節(jié)點(diǎn)遠(yuǎn)離目標(biāo)點(diǎn)，應(yīng)增大權(quán)重，此時(shí)A*算法能盡快地向目標(biāo)點(diǎn)擴(kuò)展，搜索速度會(huì)較快，當(dāng)h（n） 較小時(shí)，也即擴(kuò)展節(jié)點(diǎn)接近目標(biāo)點(diǎn)，權(quán)重應(yīng)減小，此時(shí)A*算法更傾向于搜索最優(yōu)路徑。因此本文引入以指數(shù)形式的權(quán)重因子h（n）e對傳統(tǒng)A*算法的表達(dá)式進(jìn)行改進(jìn)，公式修改為：

h（n）估計(jì)值應(yīng)始終大于0，eh（n）的圖像如圖3 所示，從圖中可知，當(dāng)h（n） 減小時(shí)，eh（n）也在不斷地減小，當(dāng)h（n）等于0，也即當(dāng)前節(jié)點(diǎn)到達(dá)目標(biāo)點(diǎn)時(shí)，eh（n）為1，整體不發(fā)生改變，符合上述改變權(quán)值的要求。

圖3 h（ n）e 變化圖像

2.5.3 貝塞爾曲線優(yōu)化

A*算法本身存在著許多的不足：在柵格環(huán)境下A*算法規(guī)劃出的路徑往往存在許多的轉(zhuǎn)折點(diǎn)，累積轉(zhuǎn)折角度大，在后期應(yīng)用于實(shí)際谷物機(jī)器人中時(shí)會(huì)不利于機(jī)器人的行駛，存在過多轉(zhuǎn)彎現(xiàn)象，運(yùn)行效率低等問題。于是本文在對改進(jìn)后A*算法規(guī)劃出的路徑進(jìn)行平滑處理，減少因路徑轉(zhuǎn)折點(diǎn)過多而降低機(jī)器人工作效率。

Bezier 曲 線[18]由 伯 恩 斯 坦 多 項(xiàng) 式（Bernstein polynomial）演化而來，其受曲線上控制點(diǎn)數(shù)目的影響。伯恩斯坦多項(xiàng)式的第n階項(xiàng)有如下形式：

其中i= 0,1,… ,n，而：

一般伯恩斯坦多項(xiàng)式可以表示為：

其中，βi為伯恩斯坦系數(shù)。當(dāng)伯恩斯坦系數(shù)是二維平面中的一系列固定點(diǎn)時(shí)，伯恩斯坦多項(xiàng)式就演變成為Bezier 曲線。

將Bezier 曲線與A*算法（B-A*）相結(jié)合，A*算法生成路徑點(diǎn)的總控制點(diǎn)個(gè)數(shù)為n+ 1，βi伯恩斯坦系數(shù)為A*算法生成的第i個(gè)路徑點(diǎn)Pi，其中i= 0,1,… ,n。則通過公式 （7）計(jì)算可得B0…Bn，即可得到平滑后的曲線路徑。

根據(jù)Bezier 曲線的性質(zhì)可知，規(guī)劃所得曲線路徑不會(huì)與控制點(diǎn)連接而成的多邊形外部障礙物發(fā)生碰撞，但會(huì)有與內(nèi)部障礙物發(fā)生碰撞的可能，在實(shí)際工作中該種情況會(huì)使谷物機(jī)器人陷入工作死區(qū)對自身造成一定的損壞，所以需對Bezier 曲線進(jìn)行一定的優(yōu)化。對Bezier 曲線進(jìn)行優(yōu)化的思想，是將兩個(gè)相鄰節(jié)點(diǎn)中插入一定的點(diǎn)，將插入的點(diǎn)共同作為控制點(diǎn)，以此增加控制點(diǎn)的數(shù)量。合適的控制點(diǎn)會(huì)使得曲線接近拐點(diǎn)，以此盡量向規(guī)劃的路徑上靠攏，進(jìn)而增大與障礙物之間的距離，躲避障礙物。增多控制點(diǎn)思想的偽代碼如下：

for i=1:1:pointnum-1

%pointnum 所需插入點(diǎn)的個(gè)數(shù)

D（ai+i,:）=（（B - C）./pointnum*i ）+ C;

%B 和 C 為相鄰控制點(diǎn)，D 所分控制點(diǎn)坐標(biāo)

end

ai=ai+pointnums;

2.6 仿真實(shí)驗(yàn)

2.6.1 改進(jìn)A*算法對比分析

在翻曬谷物時(shí)，一般會(huì)盡可能地選取寬敞且障礙物較少的場地進(jìn)行翻曬，為了驗(yàn)證A*算法作為從當(dāng)前區(qū)域到下一個(gè)區(qū)域銜接路徑規(guī)劃算法的有效性，隨機(jī)在柵格環(huán)境中選定起始點(diǎn)與目標(biāo)點(diǎn)。改進(jìn)的A*算法主要是減少擴(kuò)展節(jié)點(diǎn)，縮短節(jié)點(diǎn)搜索時(shí)間，沒有對路徑長度進(jìn)行改進(jìn)。因此本文以15×15 和30×30 兩個(gè)不同柵格大小的障礙物地圖作為仿真實(shí)驗(yàn)環(huán)境，通過Matlab 軟件分別對Dijkstra 算法、A*算法以及改進(jìn)的A*算法進(jìn)行實(shí)驗(yàn)對比分析，仿真結(jié)果如圖4所示。

圖4 15×15 環(huán)境地圖仿真圖

圖4 中，黑色柵格代表障礙物，白色柵格代表可通行柵格，灰色柵格代表所搜索的節(jié)點(diǎn)，五角星代表起點(diǎn)，圓圈代表終點(diǎn)，從起點(diǎn)到終點(diǎn)的線段為規(guī)劃出的路徑。從圖中可以看到通過三種方法都能成功地從起始點(diǎn)搜索出一條路徑達(dá)到目標(biāo)點(diǎn)，但改進(jìn)的A*算法相對于Dijstra 算法和標(biāo)準(zhǔn)A*算法搜索節(jié)點(diǎn)大大減少，從表2 中也可以看到，改進(jìn)后的A*算法在尋路時(shí)間和遍歷節(jié)點(diǎn)數(shù)的性能指標(biāo)上都得到了很大的提升。為了進(jìn)一步驗(yàn)證改進(jìn)A*算法的有效性，擴(kuò)大地圖環(huán)境，以30×30 環(huán)境地圖再次進(jìn)行仿真實(shí)驗(yàn)，結(jié)果如圖5 所示，從仿真結(jié)果與表3 都能再一次看到經(jīng)過改進(jìn)后的A*算法性能更優(yōu)，達(dá)到實(shí)驗(yàn)要求。

表3 30×30柵格地圖環(huán)境

2.6.2 路徑平滑對比分析

通過Bezier 曲線對30×30 環(huán)境地圖下改進(jìn)A*算法規(guī)劃出的路徑進(jìn)行平滑處理，得到圖6 仿真圖，其中Bezier曲線中的控制點(diǎn)即為最優(yōu)路徑中的節(jié)點(diǎn)，虛線曲線為通過改進(jìn)A*算法所規(guī)劃出的最優(yōu)路徑經(jīng)過平滑優(yōu)化后的曲線，從圖中可以看到，在對節(jié)點(diǎn)進(jìn)行Bezier 曲線優(yōu)化時(shí)，①和②處能觸碰到障礙物，在實(shí)際工作中該種情況會(huì)使谷物機(jī)器人對自身造成一定的損壞，所以需對Bezier 曲線進(jìn)行一定的優(yōu)化。

圖6 改進(jìn)A*算法Bezier 曲線優(yōu)化處理

對上述經(jīng)過Bezier 曲線平滑后的路徑再次通過增加控制點(diǎn)的方式進(jìn)行優(yōu)化，在本次實(shí)驗(yàn)中將相鄰的兩個(gè)控制點(diǎn)增加3 個(gè)點(diǎn)再次進(jìn)行平滑處理得到如圖7 仿真圖，圖7（a）和圖7（b）中的圓圈構(gòu)成的曲線為圖6 中①和②所示經(jīng)過平滑后的曲線，從圖中可以看出，該曲線能一定程度地躲避障礙物，避免了實(shí)際谷物機(jī)器人在工作過程中觸碰到障礙物，減少了對自身的損壞。圖7（c）為完整的平滑曲線圖，通過對曲線進(jìn)行優(yōu)化處理，路徑更加順暢，使得谷物機(jī)器人在實(shí)際工作中移動(dòng)得更加流暢，仿真結(jié)果表明了本算法對路徑平滑的可行性和有效性。

圖7 優(yōu)化Bezier 曲線對改進(jìn)A*算法平滑處理

2.6.3 全覆蓋路徑規(guī)劃仿真實(shí)驗(yàn)

前面詳細(xì)介紹了翻曬谷物機(jī)器人基于柵格地圖的全覆蓋路徑規(guī)劃基本步驟，要想完成一個(gè)完整的區(qū)域全覆蓋，首先需要對工作環(huán)境地圖進(jìn)行建模，然后在有障礙物的區(qū)域根據(jù)障礙物頂點(diǎn)進(jìn)行區(qū)域劃分得到多個(gè)子區(qū)域，其次對子區(qū)域設(shè)計(jì)遍歷算法，最終根據(jù)區(qū)域銜接路徑規(guī)劃完成整個(gè)工作區(qū)域的全覆蓋。下面以30×30 障礙物環(huán)境地圖進(jìn)行全覆蓋路徑規(guī)劃仿真，以此驗(yàn)證本文設(shè)計(jì)的全覆蓋路徑規(guī)劃的可行性和有效性，仿真結(jié)果如下。圖8 為通過牛耕分解法對30×30 環(huán)境地圖下進(jìn)行區(qū)域劃分的結(jié)果圖。通過仿真圖可知，該地圖被分成①～⑥6 個(gè)子區(qū)域，驗(yàn)證了牛耕分解法的有效性。

圖8 30×30 牛耕分解結(jié)果圖

接下來對子區(qū)域分別進(jìn)行弓子型區(qū)域覆蓋，仿真結(jié)果如圖9 所示。其中五角星表示機(jī)器人的起始點(diǎn)，實(shí)心圓圈表示當(dāng)前區(qū)域的終點(diǎn)，空心圓圈表示下一個(gè)子區(qū)域起點(diǎn)。直線表示子區(qū)域內(nèi)進(jìn)行往返式弓子型路徑，曲線表示區(qū)域間的銜接路徑。從 30×30 全覆蓋路徑規(guī)劃仿真圖中可以看出，經(jīng)過本文設(shè)計(jì)的算法策略均可以實(shí)現(xiàn)柵格地圖的100%覆蓋，驗(yàn)證了本文提出的全覆蓋路徑規(guī)劃算法是可行且有效的。

圖9 30×30 全覆蓋路徑規(guī)劃仿真實(shí)驗(yàn)

3 總結(jié)

本文提出一種改進(jìn)A*算法的全覆蓋路徑規(guī)劃方案，利用柵格法、牛耕分解法、貪婪算法與曼哈頓距離結(jié)合策略、往返式弓子型遍歷方法和A*算法分別對機(jī)器人工作環(huán)境建模、子區(qū)域劃分、子區(qū)域起點(diǎn)選擇、子區(qū)域內(nèi)部遍歷以及子區(qū)域銜接路徑規(guī)劃進(jìn)行求解，實(shí)現(xiàn)整個(gè)機(jī)器人對場地的全覆蓋翻曬。同時(shí)對傳統(tǒng)A*算法和Bezier 曲線進(jìn)行改進(jìn)，在相同仿真環(huán)境下，改進(jìn)后的B-A*算法使得搜索節(jié)點(diǎn)時(shí)間縮短，路徑平滑、安全。通過以上策略對環(huán)境地圖進(jìn)行全覆蓋仿真分析，實(shí)驗(yàn)結(jié)果表明本文提出的方法可完成100%的覆蓋，表明該方案具有一定的有效性和可適用性。