謝坤霖，李宗根，代宇航，周 敏，曾晟珂

(1.西華大學西華學院， 四川 成都 610039； 2.西華大學計算機與軟件工程學院， 四川 成都 610039)

隨著科學技術(shù)的高速發(fā)展，智能化控制也成為當下家庭對家電選擇的一個重要考慮因素。智能掃地機器人成為了目前比較受歡迎的一類機器人。一般來說，將完成清掃、吸塵、擦地工作的機器人，統(tǒng)一歸為掃地機器人[1]，它融合了機器人、傳感器和人工智能等技術(shù)[2]。當前市面上的掃地機器人雖已能完成掃地的基本任務，但依舊無法完全像人力勞動者一樣，還存在清掃區(qū)域不全、對不規(guī)則物體無法完全躲避、路徑重復率高和效率低等問題[3-4]。基于此，本文對智能掃地機器人的路徑規(guī)劃提出了一種新方案，通過建立恰當?shù)幕竟ぷ髁鞒腆w系、構(gòu)造合理的評價函數(shù)以及利用傳感器設立沿邊清掃機制等，來實現(xiàn)整體清掃工作的高覆蓋率和低重復率。

1 基本路徑規(guī)劃方案

1.1 路徑規(guī)劃的衡量指標

作為評價智能掃地機器人優(yōu)劣的關(guān)鍵技術(shù)之一的路徑規(guī)劃是學者研究的重點之一。點與點的路徑規(guī)劃，其效果是時間最短、路程最短，但覆蓋率低；全遍歷路徑規(guī)劃實現(xiàn)的是全區(qū)域覆蓋且無碰撞，但其在時間與路程方面則無法做到效果良好[5]。換言之，路徑規(guī)劃是一種滿足時間、路程和覆蓋率等約束條件下的優(yōu)化問題，無法在每個方面都做到最佳，只能對現(xiàn)有路徑規(guī)劃進行改進從而體現(xiàn)其綜合優(yōu)勢。路徑規(guī)劃的衡量指標主要有3個。

1)覆蓋率。覆蓋率C是指機器人完成清掃時實際清掃面積與任務區(qū)域總面積的比值[6]。機器人在覆蓋率方面的最優(yōu)要求是實現(xiàn)環(huán)境全遍歷的清掃，但根據(jù)簡單約束條件下的約束方程可知，在實現(xiàn)覆蓋率最優(yōu)的條件下(即C趨近于1)，必定是其他條件的最低實現(xiàn)。用S1表示實際清掃面積，S表示任務總區(qū)域面積，則覆蓋率可表示為

(1)

2)重復率。重復率R是衡量一個數(shù)量性狀在同一個體多次度量值之間的相關(guān)程度的參數(shù)。本文指機器人完成清掃時重復清掃面積與任務總區(qū)域面積的比值[7]。與重復率相關(guān)度最高的衡量指標應屬覆蓋率，在保證覆蓋率最優(yōu)的條件下，極大可能會破壞重復率的設置，因此在衡量重復率指標時須結(jié)合覆蓋率列出約束方程。用S2表示完成清掃時重復清掃面積，S表示任務總區(qū)域面積，則重復率可表示為

(2)

3)付出的代價。掃地機器人付出的代價是指其在運行時的各種消耗，主要指時耗與能耗。智能掃地機器人的時效性是評價機器人工作優(yōu)劣的一項重要指標，通過優(yōu)化路徑規(guī)劃方案的細節(jié)，可以合理減少清掃時間。另一個重要指標是能量的消耗，由于不同的掃地機器人電池不同，能量總量也就不同，在規(guī)劃路徑、規(guī)定掃地任務的同時需要考慮到能量的消耗是否足夠，這是設計機器人的重要考量參數(shù)。本文主要從路徑規(guī)劃著手，來盡量降低能量消耗。

總言之，一般來說應首先對覆蓋率和重復率進行考量，因為將這2個指標優(yōu)化后，機器人的時耗與能耗自然也會相應降低；故本文更側(cè)重于對覆蓋率和重復率的直接優(yōu)化，使掃地機器人路徑規(guī)劃的各項指標達到更優(yōu)水平。

1.2 建立基本路徑規(guī)劃方案

面對家庭掃地機器人出現(xiàn)的清掃覆蓋率不高、清掃重復率高、時間效率低等問題[8]，本文提出一種有效的路徑規(guī)劃方案：通過柵格法建立一個二維柵格地圖[9-10]，再將整個柵格地圖劃分為矩形子區(qū)域，并在各分區(qū)內(nèi)逐個進行全覆蓋的清掃，以達到掃地機器人基本的清掃目的?；镜那鍜吡鞒倘鐖D1所示。

圖1 基本的清掃流程

1.2.1 構(gòu)建柵格地圖

W.E.Howden提出的柵格法常用于移動機器人的地圖建模，基于柵格法建立二維空間模型，可以使掃地機器人在障礙物較少區(qū)域中的路徑規(guī)劃變得更加簡單[11-13]。由于現(xiàn)實中的障礙物多是不規(guī)則或零散分布的，故先利用膨脹原理將未占滿柵格的不規(guī)則障礙物做膨脹處理并將零散分布的障礙物隱藏，其后再對不規(guī)則和零散分布的障礙物的尋路方法進行單獨討論。

如圖2所示，將掃地機器人需要清潔的區(qū)域表示成二維的平面工作空間，并將整個工作區(qū)域劃分成M×N個邊長為S的柵格，S是單位長度，其中白色柵格代表無障礙區(qū)、黑色柵格代表障礙物[4，14-15]。在程序中建立地圖時，將白色柵格所代表的無障礙自由區(qū)域用0表示，黑色柵格所代表的障礙物用1表示。值得注意的是，單位柵格的邊長取圖1 基本的清掃流程值，較為理想的柵格長度是機器人的直徑。

1.2.2 劃分矩形子區(qū)域

在建立二維空間柵格地圖后，整體上地形復雜、障礙物分布毫無規(guī)律，使掃地機器人清掃起來會產(chǎn)生清掃效率低、清掃時間長、重復率高等問題。將一個問題劃分為子問題往往能使問題更簡化[2]，故本文采用將整個工作區(qū)域劃分為子區(qū)域的方案?；跂鸥穹ǖ奶匦?，將各區(qū)域劃分為矩形最為理想，且矩形子區(qū)域有便于用坐標標識、方便實現(xiàn)等優(yōu)勢。分區(qū)的好壞直接決定了內(nèi)置模板的數(shù)量以及清掃的效率。最理想的情況是使分區(qū)內(nèi)沒有障礙物，內(nèi)置模板的形式便能夠大大減少，清掃效率也會隨之提升?；诖?，本文對傳統(tǒng)的分區(qū)算法提出了一些改進。

圖2 柵格化地圖

分區(qū)的方法須滿足3個原則：1)以左上角為原點，對柵格地圖建立X，Y坐標軸；2)將相鄰物體邊界橫坐標值X或縱坐標值Y相同的邊界添加一條分割線[16]；3)優(yōu)先在非矩形物體周圍的區(qū)域添加分割線，分割線要使矩形子區(qū)域面積最大化，如圖3所示。對于物體1#、2#和3#的右邊界具有相同橫坐標2S，添加分割線作為1號區(qū)域和2號區(qū)域的右邊界；對于中間的物體6#和4#，它們的左邊界具有相同的橫坐標5S，添加分割線作為3號區(qū)域的右邊界；對于左下方的物體3#的上邊界和物體6#的下邊界，它們具有相同的縱坐標10S，添加分割線作為4號區(qū)域的上邊界；對于上方物體4#和5#的下邊界，它們具有相同的縱坐標3S，添加分割線作為6號區(qū)域的下邊界；對于中間的物體6#上半部分的下邊界和右邊物體7#的上邊界，它們具有相同的縱坐標6S，添加紅色分割線作為7號區(qū)域的下邊界；在原則2)的分割線都劃分完成后，再對非矩形黑塊周圍按照矩形最大化進行劃分得到5號區(qū)域的右邊界、8號區(qū)域的下邊界、9號區(qū)域的左邊界。通過合并所有的自由子區(qū)域，得到一個完整的柵格地圖。通過該方法劃分為多個自由子區(qū)域可以減少掃地機器人因清掃路徑過多而產(chǎn)生的錯誤，提高清掃的效率和準確性[17-19]。

1.2.3 子區(qū)域內(nèi)的遍歷方法

類似于分解法，把一個復雜問題分解成多個簡單問題。在劃分好各個子區(qū)域后，需要對各子區(qū)域內(nèi)的路徑進行規(guī)劃[2，4]。得益于區(qū)域的理想劃分，大部分無障礙物子區(qū)域用模板法即可高效解決，并且本文中的模板法讓掃地機器人只存在一種轉(zhuǎn)向方式，在一定程度上能降低掃地機器人清掃路徑的重復率。其中，最主要的工作是建立恰當?shù)钠鹬裹c和往返遍歷規(guī)則。規(guī)則制定得越恰當整體效率將越高。

圖3 柵格化地圖的分區(qū)結(jié)果

首先確定各自由子區(qū)域的工作起點和終點位置。規(guī)則如下：將自由子區(qū)域的起點定義在橫坐標值縱坐標值最小的節(jié)點(Xmin，Ymin)處，清掃終點的坐標由規(guī)則式(3) 確定。

if (Xmax-Xmin)<(Ymax-Ymin){

if (Xmax-Xmin=2KS(K=1，2，3，…))，(X，Y)=(Xmax，Ymin)；

else if (Xmax-Xmin=(2K+1)S(K=0，1，2，3，…))，(X，Y)=(Xmax，Ymax)；

}

if (Xmax-Xmin)>(Ymax-Ymin){

if (Ymax-Ymin=2KS(K=1，2，3，…))，(X，Y)=(Xmin，Ymax)；

else if (Ymax-Ymin=(2K+1)S(K=0，1，2，3，…))，(X，Y)=(Xmax，Ymax)；

}

(3)

如圖4所示，綠色柵格代表掃地機器人的出發(fā)點，紅色柵格代表掃地機器人的終點，掃地機器人須從起點開始清掃，到終點結(jié)束，從而完成單個自由子區(qū)域的清掃。該起終選取規(guī)則可以減少機器人轉(zhuǎn)向次數(shù)。完成這些清掃動作還需要引入往返機制，參照函數(shù)為式(4)。

F(X)={X=1，Turn∪X=0，Go}

(4)

圖4 子區(qū)域內(nèi)的遍歷方法2改進的路徑規(guī)劃方案

接著掃地機器人從綠色柵格出發(fā)，沿著四周的墻壁、黑色障礙物的邊界或者劃分好的由分割線構(gòu)成的各個區(qū)域的邊界，以直線運動的方式進行清掃。利用類似于氣味遺留的算法，在掃地機器人完全通過一個柵格后，將上一個柵格標為0.01，代表已經(jīng)通過路徑，避免區(qū)域內(nèi)遍歷地圖時重復清掃該柵格，并與0代表的未通過路徑和1代表的墻壁、黑色障礙物、分割線等區(qū)別。具體的轉(zhuǎn)向規(guī)則為：在一個子區(qū)域內(nèi)，當掃地機器人碰到1時，立即向左邊或右邊相鄰且未被清掃的自由柵格0轉(zhuǎn)向，并進入到該自由柵格中。在掃地機器人完成上述操作后，它會繼續(xù)完成一次轉(zhuǎn)向，轉(zhuǎn)向方向為上次轉(zhuǎn)向方向。例如掃地機器人在自由子區(qū)域1清掃時，在碰到物體2#的上邊界，它立即向行進方向的左方向轉(zhuǎn)動進入到下一個自由柵格，之后它將立即左轉(zhuǎn)進入再下一個自由柵格繼續(xù)直線運動，直到到達綠色柵格。在清掃完一個自由子區(qū)域后進入下個自由子區(qū)域繼續(xù)從綠色柵格到紅色柵格的清掃，直到清掃完所有的自由子區(qū)域，具體的子區(qū)域遍歷路線如圖4所示。由于本文對柵格地圖采取多個矩形自由子區(qū)域的劃分和沿最長直線路線的清掃方式，讓掃地機器人只存在一種轉(zhuǎn)向方式，在一定程度上降低了掃地機器人清掃的重復率，提高了時間效率[2]。

2 改進的路徑規(guī)劃方案

2.1 基于啟發(fā)式矩形子區(qū)域間的遍歷方法

矩形子區(qū)域間的路徑規(guī)劃問題是研究一組對象如何在有限的區(qū)域內(nèi)彼此盡量不重疊的優(yōu)化布局問題[20]。它的研究具有廣泛的應用價值，但作為NP難問題，很難準確地解決這一問題。

2.1.1 矩形子區(qū)域間遍歷順序的確定方法

矩形子區(qū)域間遍歷順序的確定依靠于圖的相關(guān)遍歷算法。深度優(yōu)先遍歷是遍歷圖中最重要的方法，它適用于無向圖和有向圖。將各分區(qū)抽出10個節(jié)點相連形成一個無向節(jié)點圖，如圖5所示。

圖5 區(qū)域間節(jié)點圖

利用深度優(yōu)先算法很容易對節(jié)點圖進行遍歷并得到多解，但這些解的效率往往參差不齊[3]。例如經(jīng)過節(jié)點A3時存在重復路徑、拐角的選取問題。不考慮這些問題很可能產(chǎn)生一些不必要的重復路徑。這時需要引入適當?shù)脑u價函數(shù)來對解進行篩選，使路徑整體規(guī)劃效率達到較優(yōu)的目的。評價函數(shù)直接影響著解的效率，但是評價函數(shù)的選取往往是比較困難的，并且沒有絕對的好壞；所以只能在保證評價函數(shù)的選擇要達到對模型的高度適應的前提下對所使用的評價函數(shù)進行較優(yōu)擇取。深度優(yōu)先算法將啟發(fā)信息引入搜索過程，并對周邊的每個搜索位置進行評價，得到評價條件的最優(yōu)位置，再把搜索到的位置作為基點進行搜索指導，以搜索到目標點，這樣可以顯著提高路徑搜索的效率。

深度優(yōu)先算法在路徑搜索中采用評價函數(shù)F(n)對節(jié)點n進行評價，F(xiàn)(n)的表達式為

F(n)=G(n)+K(n)

(5)

式中：G(n)為起始點距當前位置的實際路徑長度；K(n)為機器人轉(zhuǎn)向角度和。設起始點為(xg，yg)，當前位置為(xi，yi)，則G(n)可表示為

(6)

設第i次轉(zhuǎn)角的消耗為wi，則轉(zhuǎn)向角度和K(n)可表示為

(7)

對該函數(shù)的各項做加權(quán)處理，使G(n)的權(quán)重最大，作為第一原則，以此保證整體效率較高；使K(n)的權(quán)重第二大，作為第二原則，能夠在一定程度上降低重復率。

如圖5所示，由于A3節(jié)點的存在，該圖沒有只遍歷1遍的解，且滿足G(n)最優(yōu)的解也有多個，主要是在經(jīng)過A3、A7節(jié)點時存在不同選擇，但G(n)+K(n)對解做出進一步篩選，同時滿足這2個條件的最優(yōu)解路徑是A10→A7→A6→A5→A3→A1→A3→A2→A3→A4→A9→A8。另外，若規(guī)定了不同的起點也會得到不同的解，這里本文采用A10為起點的最優(yōu)解。

2.1.2 子區(qū)域間銜接路徑的規(guī)劃方法

選定好子區(qū)域間遍歷順序后，需要給出銜接路徑的規(guī)劃方法。

首先對銜接路徑的長度進行最優(yōu)化。利用傳統(tǒng)的A*算法可以方便地規(guī)劃出最短路徑，但是需要對一些特殊情況做一些特殊討論，以降低重復率[21]。對于相鄰子區(qū)域的轉(zhuǎn)移，可以進行直接規(guī)劃，但本文給出的地圖中有多處需要經(jīng)過其他子區(qū)域來進行轉(zhuǎn)移。如果按照從一個子區(qū)域終點到另一個子區(qū)域起點的方式來進行轉(zhuǎn)移，會產(chǎn)生多且不必要的重復路徑。對于這種情況需要使用程序進行識別歸類。例如A3→A1→A3→A2這一轉(zhuǎn)移過程，應直接對A1→A2進行規(guī)劃。

接著引入啟發(fā)函數(shù)，篩除冗余無用解。在實際規(guī)劃中往往存在多解的情況，并且這些解的實際效率卻并不一定都是最優(yōu)，而傳統(tǒng)的A*算法可能對這些解一視同仁[4]。如圖6，A1→A3→A2這一過程，路徑代價是一樣的，轉(zhuǎn)角代價卻不一樣，這很可能會在整個地圖中增添一些不必要的功耗和時間代價。基于此，需要引入轉(zhuǎn)向角度和對解做進一步的約束。用于子區(qū)域間銜接路徑規(guī)劃的評價函數(shù)F(n)的表達式為

F(n)=G(n)+K(n)+H(n)

(8)

式中：G(n)為起始點距當前位置的實際路徑長度；K(n)為機器人轉(zhuǎn)向角度和；H(n)為當前位置距終點的最佳路徑的估計距離。仍然是G(n)的權(quán)重最大，K(n)的權(quán)重第二大。G(n)、K(n)的形式與上節(jié)一致。啟發(fā)函數(shù)H(n)的引入使當前位置每次都會優(yōu)先向終點方向進行移動，以達到先篩除冗余的無用解的目的。H(n)越復雜，約束條件越多，時間成本就越高；但降低H(n)的值，即如果減少約束條件，并不一定能得到最優(yōu)路徑，當H(n)=0時，便意味著正在進行盲目搜索。

圖6 最短路徑的多解示意圖

常用的啟發(fā)函數(shù)如下。

1)曼哈頓距離。標準的估計函數(shù)為曼哈頓距離，即在南北方向上2點之間的距離和東西方向的距離。

3)歐氏距離。如果一個單元可以以任意角度而非柵格方向移動，那么可以使用歐氏距離。

如圖1所示，與對照組比較，TGF組HLFs細胞α-SMA、ColI蛋白表達水平升高，差異有統(tǒng)計學意義(P＜0.01);與TGF組比較，Tβ4中劑量組及高劑量組HLFs細胞α-SMA、ColI蛋白表達水平降低，差異有統(tǒng)計學意義(P＜0.05或P＜0.01);提示中劑量(10 mg/L)及高劑量(100 mg/L)Tβ4對TGF-β1誘導 HLFs細胞 α-SMA、ColI蛋白表達有顯著抑制作用。

設柵格地圖中曼哈頓距離為Hh(n)，則有

Hh(n)=|xn-xg|+|yn-yg|

(9)

設柵格地圖中對角線距離為Hd(n)，則有

(10)

將Hh(n)和Hd(n)合并，并且簡化可得

h(n)=W·[Hh(n)+Hd(n)]

(11)

因而，可得到完整的H(n)表達式，為

(12)

2.2 改進子區(qū)域內(nèi)的遍歷方法

2.2.1 多障礙物子區(qū)域內(nèi)的遍歷方法

當障礙物較多時，需要啟用路徑搜索功能[1]。目前大多數(shù)掃地機器人采用的是隨機碰撞的尋路方式，即隨機覆蓋法，其普遍存在清掃效率低且在復雜地形下很難達到各方面高效的理想目標[22]。本文利用深度優(yōu)先搜索算法保證了掃地機器人在障礙物較多的環(huán)境下能快速、精準地達到高覆蓋率，但同時產(chǎn)生的重復率較高的問題很難完全解決。通過設置合理的評價函數(shù)以控制多種情況下的深度優(yōu)先行為，能在一定程度上減少重復率[1]。評價函數(shù)有以下特點：當目標太低時，可以得到最短路徑，但是速度會慢；當目標太高時，可以放棄最短路徑，但是確保路徑搜索算法運行得更快[22]。在這一點上，必須在運行效率和路徑選取之間進行權(quán)衡[23]。

從這個例子不難看出，將H(n)取一個較為中間的值最為妥當。深度優(yōu)先算法的內(nèi)部內(nèi)容是在每個節(jié)點上計算。當H(n)與G(n)完全匹配時，F(xiàn)(n)的值不會沿該路徑變化。不在正確路徑上的所有節(jié)點的F(n)值均大于正確路徑上的F(n)值。一般情況下，能夠保證路徑長度和運行時間可以達到較為均衡的狀態(tài)，并且解不會偏離最短路徑[25]。

2.2.2 不規(guī)則障礙物區(qū)域的路徑規(guī)劃方法

在區(qū)域銜接時若遇到不規(guī)則障礙物區(qū)域，應該對膨脹處理后的不規(guī)則的障礙物邊緣進行規(guī)劃清理。針對不規(guī)則障礙物，在分區(qū)銜接的路徑規(guī)劃中，需要運用傳感器對不規(guī)則障礙物的邊進行探測，控制機器人與障礙物之間的距離，以使其沿不規(guī)則障礙物的邊清掃。

在沿邊搜索時，需要利用傳感器來采集環(huán)境信息，路徑規(guī)劃規(guī)則需在環(huán)境信息模型的基礎(chǔ)上針對障礙物來尋求一系列行為動作。對在沿邊行進的多條路徑中的不同地形的評估，可以使用評估代價的算法來計算一條初始路徑[26-28]。

例如，定義低幅度路面不平的代價是1，大幅度

(a)

(b)

(c)

路面不平的代價是2，路線曲折的代價是3，路徑狹窄的代價是4，那么程序會考慮通過3個低幅度不平的路段來避免通過一個路線曲折的路段。通過把路段通過的難易程度進行量化來計算初始路徑，可以使用更少的時間規(guī)劃，且可以更快地找到一條路徑使其接近于精確啟發(fā)函數(shù)的效果[29]。一旦找到一條路徑，物體就可以開始移動，當多余的CPU時間是可用的時候，也可以用更細致的階梯式移動代價去計算更好的路徑。在RobotBASIC中能模擬出帶有傳感器的機器人，可實現(xiàn)機器人對不規(guī)則障礙物進行沿邊遍歷，效果如圖8所示。

圖8 對不規(guī)則障礙物的沿邊清掃示意圖

3 測試

如圖9所示的全遍歷路徑規(guī)劃圖，深藍色的圓為整個清掃過程的起點，深藍色的勾為整個清掃過程的終點。該圖一共有16×12個柵格，黑色的障礙物區(qū)域約占50個柵格，自由柵格一共142個。其中，重復遍歷的柵格為45個，重復率約31%，覆蓋率近100%。本文所設的地圖較小、柵格數(shù)量較少，且障礙物較為緊湊，便于示意。在實際中，柵格的數(shù)量會大大增加，覆蓋率也會隨之減少。如圖10所示，將地圖倍增后，重復率降為18%?？偟膩碚f，該算法可將重復率控制在10%～18%的范圍內(nèi)。傳統(tǒng)算法與改進算法路徑規(guī)劃的覆蓋率和重復率對比如表1所示。

圖9 全遍歷路徑規(guī)劃圖

圖10 全遍歷路徑重復率示意圖

遍歷方式覆蓋率/%重復率/%傳統(tǒng)規(guī)劃算法90～94>20改進規(guī)劃算法> 9910～18

另外，在實際工作中，掃地機器人的轉(zhuǎn)向也會影響清掃效率。在該算法中，由于增加了對角度的約束，減少了轉(zhuǎn)向角度和，在一定程度上提高了整體的清掃效率[2]。

綜上，改進后的算法在整體的清掃覆蓋率、重復率和效率上都有不同程度的提高。

4 結(jié)束語

經(jīng)過對掃地機器人路徑規(guī)劃的探討，發(fā)現(xiàn)不管是使用哪一種規(guī)劃路徑的方法，都會出現(xiàn)一定的重復，只能通過不斷優(yōu)化整體方案來逐漸降低重復率。本文提出的方案在覆蓋率和重復率上表現(xiàn)較為突出，且總體時耗、能耗也相應略有降低。在面對不規(guī)則障礙物時，由于機器人本身的直徑大小會使其在清掃不規(guī)則障礙物周身時出現(xiàn)一定的盲區(qū)，導致該部分區(qū)域無法清潔。接下來可以從以下幾方面來考慮改進：改進地圖分區(qū)方式；改進復雜環(huán)境下掃地機器人的尋路算法；對機器人的機器形態(tài)、運動方式、運動和轉(zhuǎn)向能耗進行優(yōu)化等。