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

陳 鵬， 李彩虹

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

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

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

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

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

1 實時環(huán)境信息

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

圖1 聲納環(huán)結構

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

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

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

(1)

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

Visited(x,y)=

(2)

3)關聯(lián)屬性Related(x,y)

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

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

Enabled(x,y)=

(3)

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

圖2 視野域示意圖

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

2 全遍歷覆蓋路徑規(guī)劃算法

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

2.1 全遍歷覆蓋路徑規(guī)劃的FSM實現(xiàn)

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

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

五種狀態(tài)、三種策略作如下定義.

S1：初始狀態(tài)

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

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

S4：目標柵格已確定時.

S5：結束狀態(tài)

F1：二叉樹搜索策略

F2：目標柵格選取策略

F3：兩點法搜索策略

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

圖3 全遍歷覆蓋路徑規(guī)劃的FSM實現(xiàn)

2.2 全遍歷覆蓋路徑規(guī)劃的策略設計

2.2.1 二叉樹搜索策略F1

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

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

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

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

1)若采用數(shù)組結構存儲各柵格的關聯(lián)柵格信息，假定數(shù)組名為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的關聯(lián)屬性值不受影響，A{i}.Related能夠真實反映柵格i關聯(lián)柵格的實際個數(shù).

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

A{i}.Related=0

(7)

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

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的最大關聯(lián)柵格數(shù)A{i}.maxrelated，記錄最大關聯(lián)柵格數(shù)對應的柵格編號j.緊接著，移動機器人前進至柵格j，并實時更新環(huán)境信息.

2.2.2 目標柵格選取策略F2

機器人處于S3時，為使機器人離開已遍歷完區(qū)域，到未遍歷區(qū)域繼續(xù)遍歷，需選取一個目標柵格，即在視野總域Ssensor內(nèi)，選取離機器人柵格最近的可選柵格，并且要求該柵格還未被遍歷過.待目標柵格確定后，機器人隨即跳轉至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為符合目標柵格選取條件的柵格總數(shù))與機器人位置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.

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

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

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

2.3 評價指標

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

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

Jhc=(Shc/SΩ)×100%

(13)

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

Jcc=(Scc/SΩ)×100%

(14)

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

3 仿真實驗

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

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

(a)無障礙環(huán)境

(b)障礙稀疏環(huán)境

(c) 障礙密集環(huán)境

圖6 遍歷效果圖

4 結束語

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

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

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

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

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

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

[5]郝宗波,洪柄榕,黃慶成.基于柵格地圖的機器人覆蓋路徑規(guī)劃研究[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]邱雪娜,劉士榮,宋加濤.不確定動態(tài)環(huán)境下移動機器人的完全遍歷路徑規(guī)劃[J].機器人，2006,28(6):586-592.

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

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

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

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