移動機器人混合式全遍歷覆蓋路徑規劃算法

陳 鵬， 李彩虹

(山東理工大學 計算機科學與技術學院， 山東 淄博 255091)

全遍歷覆蓋路徑規劃[1]是指在滿足某種性能評價指標最優或準優的前提下，尋找一條從起始點開始，且經過工作區域內所有可達點的路徑規劃.全遍歷覆蓋路徑規劃是一類特殊的路徑規劃，在許多領域都有著廣闊的應用前景，特別是很多家用場合，都要求移動機器人具備全區域覆蓋的能力.

按照對環境知識的了解，全遍歷覆蓋路徑規劃可分為環境已知和環境未知的路徑規劃.已知環境下的路徑規劃，多采用單元分解法[2-3]和模板模型法[4].單元分解法是將環境分解為梯形單元，機器人在梯形單元中做往返運動，并通過鄰接圖來表示從一個單元到另一個單元的轉移.缺點是單元分解過多致使重復率較高.模板模型法是根據覆蓋區域獲取的環境信息，與各個模板進行匹配來完成遍歷.缺點是對環境缺乏整體規劃，要求事先定義環境模型和模板記憶，對變化的環境很難處理.

對于環境未知情形下的路徑規劃，郝宗波[5]等提出了基于傳感器和柵格地圖的路徑規劃方法，適合簡單環境.Hsu[6]等采用離線規劃和在線避障方式來完成全遍歷，實現過程較為復雜.邱雪娜[7]等提出了基于生物激勵與滾動啟發式規則的路徑規劃，適合簡單環境，在復雜環境下出現了較多轉彎和重復.郭小勤[8]提出了可動態調節啟發式規則的滾動路徑規劃算法，有效減少轉彎次數，并解決了U型障礙物區域的連續遍歷問題.禹建麗[9]等在犁田式路徑規劃的基礎上，運用回溯法來解決遍歷過程中的盲區問題.

環境已知的路徑規劃方法不適用于環境未知的情形，而未知環境下的路徑規劃方法存在著重復率較高、系統開銷大等缺點.為提高工作效率，采用混合式的全遍歷覆蓋路徑規劃算法.利用滾動規劃把未知區域轉化為已知區域.于是，未知環境下的路徑規劃轉化為在已知區域內的路徑規劃，從而有效地提高工作效率.

1 實時環境信息

在未知環境下，移動機器人利用聲納傳感器探測環境信息，如障礙物位置等.在研究中所使用的移動機器人是利曼科技有限公司生產的先鋒機器人Pioneer3，先鋒機器人Pioneer3裝配有兩個聲納陣，前方、后方各有一個，每個聲納陣由8個聲納環組成，用于物體檢測、距離檢測和自動避障等.其聲納環分布如圖1所示.

圖1 聲納環結構

移動機器人裝載的聲納傳感器，可探測機器人位置360°范圍內的障礙物信息.此外，利用定位系統感知任意時刻的機器人位置Probot、目標柵格位置Pgoal(xg,yg)和障礙物位置Pobstacle(i)(i=1，…，n)等信息.

機器人的視野域Ssense定義為以機器人位置Probot為中心，以rsense為半徑的圓內.假定移動機器人的行進速度恒定，運動步長為ε，ε

1)障礙屬性Flag(x,y)

(1)

2)覆蓋屬性Visited(x,y)

Visited(x,y)=

(2)

3)關聯屬性Related(x,y)

Related(x,y)表示與柵格(x,y)相鄰的自由柵格的個數.

4)可選屬性Enabled(x,y)

Enabled(x,y)=

(3)

此外，還約定在柵格地圖中，用機器人位置Probot所在的柵格來標識機器人，用障礙物位置Pobstacle(i)(i=1，…，n)對應的柵格來標識障礙物.如圖2所示.

圖2 視野域示意圖

視野總域Ssensor定義為機器人在遍歷過程中，探測到的區域總和.機器人在路徑規劃時，可依據具體情形，選擇遍歷視野總域Ssensor內的任意自由柵格.機器人每行進一步，須實時探測、記錄視野域Ssense內的環境信息,并將新探測到的區域歸入視野總域Ssensor內.

2 全遍歷覆蓋路徑規劃算法

機器人在初始遍歷時，執行二叉樹搜索策略，直至相鄰柵格被全部遍歷.此時，由于沒有達到全遍歷覆蓋的要求，隨即執行目標柵格選取策略.待目標柵格確定后，執行兩點法搜索策略.機器人逐步移動至目標柵格位置，并重新執行二叉樹搜索策略，此后重復這個過程.在機器人移動過程中，一旦達到全遍歷覆蓋要求，路徑規劃立即終止.整個過程，就形成了有限狀態機(Finite State Machine,FSM)[10]的設計思路.下面就FSM實現、策略設計、評價指標做具體闡述.

2.1 全遍歷覆蓋路徑規劃的FSM實現

移動機器人的全遍歷覆蓋路徑規劃可通過FSM來實現，圖3是規劃算法的五狀態FSM實現圖.FSM包括五種狀態，還需要設計三種策略進行狀態之間的轉換，分別是二叉樹搜索策略、目標柵格選取策略和兩點法搜索策略.

當機器人周圍的相鄰柵格中，不存在還未被遍歷的自由柵格時，機器人須在視野總域Ssensor內，選取離當前機器人位置最近的、還未被遍歷的自由柵格，作為下一遍歷區域的起始柵格，我們稱該起始柵格為目標柵格.

五種狀態、三種策略作如下定義.

S1：初始狀態

S2：在機器人周圍的相鄰柵格中，還存在未被遍歷的自由柵格.

S3：在機器人周圍的相鄰柵格中，不存在還未被遍歷的自由柵格.

S4：目標柵格已確定時.

S5：結束狀態

F1：二叉樹搜索策略

F2：目標柵格選取策略

F3：兩點法搜索策略

移動機器人的全遍歷覆蓋過程何時結束，需依據具體環境和實際工作要求來決定.這里為了仿真實驗的需要，假定遍歷覆蓋率達到99%，全遍歷覆蓋過程結束. 全遍歷覆蓋路徑規劃的FSM實現如圖3所示.

圖3 全遍歷覆蓋路徑規劃的FSM實現

2.2 全遍歷覆蓋路徑規劃的策略設計

2.2.1 二叉樹搜索策略F1

機器人處于S2時，執行F1.該狀態的目標是搜索與機器人相鄰的自由柵格，找出其中關聯柵格數最大的柵格，并遍歷該柵格.值得指出的是，機器人每前進一步，須實時更新環境信息，并檢測在機器人的相鄰柵格中是否還存在未被訪問的自由柵格.若存在，則重復F1.若不存在，機器人隨即跳轉至S3.

為滿足二叉樹搜索策略的需要，為所有柵格賦予四種屬性：障礙屬性Flag(x,y)、遍歷屬性Visited(x,y)、關聯屬性Related(x,y)、可選屬性Enabled(x,y).這樣，二叉樹搜索策略選取柵格須符合：障礙屬性值Flag(x,y)為1、遍歷屬性值Visited(x,y)為0、關聯屬性值Related(x,y)最大、可選屬性值Enabled(x,y)為1.

二叉樹搜索策略，涉及到了關聯柵格數的計算問題.根據待研究柵格在柵格區域的位置不同，柵格區域可劃分為三種模型：四格型、六格型和九格型.通過轉化，任意柵格區域均符合三種模型，如圖4所示.為此，本文僅對三種模型進行研究.

(a)四格型 (b)六格型 (c)九格型圖4 柵格區域模型示意圖

1)若采用數組結構存儲各柵格的關聯柵格信息，假定數組名為A.以柵格i為例，則有：

(1)當柵格i為自由柵格時

a)四格型

A{i}.Related=A{1}.Flag+A{2}.Flag

+A{3}.Flag

(4)

b)六格型

A{i}.Related=A{1}.Flag+

A{2}.Flag+

A{3}.Flag+

A{4}.Flag+

A{5}.Flag

(5)

c)九格型

A{i}.Related=A{1}.Flag+

A{2}.Flag+

A{3}.Flag+

A{4}.Flag+

A{5}.Flag+

A{6}.Flag+

A{7}.Flag+

A{8}.Flag

(6)

此處，若柵格i的相鄰柵格中有障礙物柵格，則障礙物柵格的障礙屬性值Flag為0，因此，柵格i的關聯屬性值不受影響，A{i}.Related能夠真實反映柵格i關聯柵格的實際個數.

(2)當柵格i為障礙柵格時

A{i}.Related=0

(7)

2)若柵格i為機器人柵格，求所有相鄰柵格的最大關聯柵格數，則有：

a)四格型

A{i}.maxrelated=

max(A{1}.Related,

A{2}.Related,

A{3}.Related)

(8)

b)六格型

A{i}.maxrelated=

max(A{1}.Related,

A{2}.Related,

A{3}.Related,

A{4}.Related,

A{5}.Related)

(9)

c)九格型

A{i}.maxrelated=

max(A{1}.Related,

A{2}.Related,

A{3}.Related,

A{4}.Related,

A{5}.Related,

A{6}.Related,

A{7}.Related,

A{8}.Related)

(10)

通過比較，得到柵格i的最大關聯柵格數A{i}.maxrelated，記錄最大關聯柵格數對應的柵格編號j.緊接著，移動機器人前進至柵格j，并實時更新環境信息.

2.2.2 目標柵格選取策略F2

機器人處于S3時，為使機器人離開已遍歷完區域，到未遍歷區域繼續遍歷，需選取一個目標柵格，即在視野總域Ssensor內，選取離機器人柵格最近的可選柵格，并且要求該柵格還未被遍歷過.待目標柵格確定后，機器人隨即跳轉至S4.

假設任意柵格與機器人位置Probot(xr,yr)之間的距離用Distance表示，則目標柵格須符合：障礙屬性值Flag(x,y)為1、遍歷屬性值Visited(x,y)為0、可選屬性值Enabled(x,y)為1、Distance值最小.

若用柵格的中心點坐標來標識柵格位置，則待選柵格Pi(xi,yi)(i=1，…，m，m為符合目標柵格選取條件的柵格總數)與機器人位置Probot(xr,yr)之間的距離Distance(i)可表示為

(i=1，…，m)

(11)

求Distance(i)的最小值：

Distance=min(Distance(i))

i=1,…,m

(12)

通過比較，得到待選柵格與機器人位置之間的距離最小值Distance，并記錄該最小值對應的柵格編號k、柵格中心點坐標Pk(xk,yk).

2.2.3 兩點法搜索策略F3

目標柵格確定后，機器人立即從當前位置，移動到目標柵格位置.在向目標柵格移動過程中，若已達到全遍歷覆蓋要求，則終止整個遍歷過程.若到達目標柵格后，還未達到全遍歷覆蓋要求，機器人隨即跳轉至S2.

兩點法搜索策略簡述為移動機器人向目標柵格直線移動時，若遇到障礙物，就改變方向、移動到沒有障礙物的位置，并再次確定目標柵格的方向、感知障礙物信息.如此反復，直至到達目標柵格[11].兩點法搜索策略示意圖如圖5所示.

圖5 兩點法搜索過程示意圖

由圖5可知，A為起始點，B為目標柵格，起始點A與目標柵格B之間的線段AB上有障礙物.此時，首先向上偏轉角度θ，得到的線段AB1上仍有障礙物，再以線段AB為基準，向下偏轉角度θ，得到的線段AB2上也有障礙物，再從線段AB1開始向上偏轉角度θ….如此反復，當偏轉到線段ABi時，ABi上沒有障礙物，得到一點C，以此類推得到另一點D，直至到達目標柵格B，整個搜索過程停止.

2.3 評價指標

遍歷結束后，須引入“評價指標”對遍歷結果進行評價.本文采用遍歷覆蓋率和遍歷重疊率作為評價指標.假設S表示整個工作空間，SΩ表示可達區域的面積，Shc表示已遍歷的面積，Scc表示重復遍歷的面積.

1)遍歷覆蓋率：遍歷完成后，已遍歷面積與可達區域面積的百分比.

Jhc=(Shc/SΩ)×100%

(13)

2)遍歷重疊率：所有重復遍歷面積之和與可達區域面積的百分比.

Jcc=(Scc/SΩ)×100%

(14)

為了盡可能地減少遍歷盲區，不可避免地就會產生一定程度的重疊.顯然，重疊率越小越好，但受系統誤差、控制精度以及環境等諸多因素的影響，重疊區域不可能太小.但若機器人的性能較高，則遍歷重疊率可控制在較小的范圍內，遍歷效率大幅提高，遍歷效果趨于理想.

3 仿真實驗

利用以上設計的全遍歷覆蓋路徑規劃算法，對移動機器人在障礙物稀疏程度不同的環境下進行仿真.程序運行前，設定覆蓋率達到99%時，遍歷結束.仿真結果如圖6所示.

仿真結果表明，移動機器人在無障礙環境、障礙稀疏環境、障礙密集環境下，都能有效地躲避障礙物，高效地完成全遍歷覆蓋任務，遍歷重復率也被控制在可接受的范圍內.

(a)無障礙環境

(b)障礙稀疏環境

(c) 障礙密集環境

圖6 遍歷效果圖

4 結束語

本文針對移動機器人在未知環境下的全遍歷覆蓋任務，提出了滾動規劃與搜索策略相結合的一種混合式全遍歷覆蓋路徑規劃算法，并進行仿真實驗.結果表明，算法具有以下特點：能在無障礙環境、障礙稀疏環境、障礙密集環境下，完成全遍歷覆蓋路徑規劃任務；能覆蓋工作區域的幾乎全部區域，遍歷覆蓋率高；移動機器人重復遍歷的柵格較少，重復率較低.從整體來看，遍歷覆蓋率較高，遍歷重復率較低，因此遍歷效率較高.

移動機器人根據全遍歷覆蓋路徑規劃算法，能夠高效地完成全遍歷覆蓋任務，但也存在一些不足之處，如尚不能保證遍歷路徑長度絕對最短等，這些問題將是今后研究的課題.

[1]邱燕，儀垂杰.小麥精播機器人路徑規劃研究[D].青島:青島理工大學，2011.

[2]徐美清,孫晨亮.移動機器人路徑規劃方法研究[J].科教信息，2012(35):60-61.

[3]顧國昌,張巧榮.移動機器人分層路徑規劃方法研究[J].哈爾濱工程大學學報，2011,22(5):31-32.

[4]田春穎,劉瑜,馮申坤,等.基于柵格地圖的移動機器人完全遍歷算法—矩形分解法[J].機械工程學報，2004,40(10):56-61.

[5]郝宗波,洪柄榕,黃慶成.基于柵格地圖的機器人覆蓋路徑規劃研究[J].計算機應用研究，2007,24(10):56-58.

[6]Hsu S M,Lin C L,Yang M Y.On the complete coverage path planning for mobile robots[J].Intelligent and Robotic System，2013，7(1):1-19.

[7]邱雪娜,劉士榮,宋加濤.不確定動態環境下移動機器人的完全遍歷路徑規劃[J].機器人，2006,28(6):586-592.

[8]郭小勤.未知環境下移動機器人遍歷路徑規劃[J].計算機工程與設計，2010,31(1):172-174.

[9]禹建麗,徐亮.室內自主機器人的路徑規劃[J].中原工學院學報，2010,21(3):1-3.

[10]張崢煒.基于生物啟發的群機器人系統群體搭建機制研究[D].濟南：山東大學,2012.

[11]李彩虹,張子間.基于兩點法的機器人路徑規劃[J].山東理工大學學報:自然科學報，2005,19(1):17-20.