陳 鵬， 李彩虹

(山東理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 山東 淄博 255091)

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

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

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

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

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

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

圖1 聲納環(huán)結(jié)構(gòu)

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

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

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

(1)

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

Visited(x,y)=

(2)

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

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

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

Enabled(x,y)=

(3)

此外，還約定在柵格地圖中，用機(jī)器人位置Probot所在的柵格來(lái)標(biāo)識(shí)機(jī)器人，用障礙物位置Pobstacle(i)(i=1，…，n)對(duì)應(yīng)的柵格來(lái)標(biāo)識(shí)障礙物.如圖2所示.

圖2 視野域示意圖

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

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

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

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

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

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

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

S1：初始狀態(tài)

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

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

S4：目標(biāo)柵格已確定時(shí).

S5：結(jié)束狀態(tài)

F1：二叉樹(shù)搜索策略

F2：目標(biāo)柵格選取策略

F3：兩點(diǎn)法搜索策略

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

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

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

2.2.1 二叉樹(shù)搜索策略F1

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

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

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

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

1)若采用數(shù)組結(jié)構(gòu)存儲(chǔ)各柵格的關(guān)聯(lián)柵格信息，假定數(shù)組名為A.以柵格i為例，則有：

(1)當(dāng)柵格i為自由柵格時(shí)

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的關(guān)聯(lián)屬性值不受影響，A{i}.Related能夠真實(shí)反映柵格i關(guān)聯(lián)柵格的實(shí)際個(gè)數(shù).

(2)當(dāng)柵格i為障礙柵格時(shí)

A{i}.Related=0

(7)

2)若柵格i為機(jī)器人柵格，求所有相鄰柵格的最大關(guān)聯(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)

通過(guò)比較，得到柵格i的最大關(guān)聯(lián)柵格數(shù)A{i}.maxrelated，記錄最大關(guān)聯(lián)柵格數(shù)對(duì)應(yīng)的柵格編號(hào)j.緊接著，移動(dòng)機(jī)器人前進(jìn)至柵格j，并實(shí)時(shí)更新環(huán)境信息.

2.2.2 目標(biāo)柵格選取策略F2

機(jī)器人處于S3時(shí)，為使機(jī)器人離開(kāi)已遍歷完區(qū)域，到未遍歷區(qū)域繼續(xù)遍歷，需選取一個(gè)目標(biāo)柵格，即在視野總域Ssensor內(nèi)，選取離機(jī)器人柵格最近的可選柵格，并且要求該柵格還未被遍歷過(guò).待目標(biāo)柵格確定后，機(jī)器人隨即跳轉(zhuǎn)至S4.

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

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

(i=1，…，m)

(11)

求Distance(i)的最小值：

Distance=min(Distance(i))

i=1,…,m

(12)

通過(guò)比較，得到待選柵格與機(jī)器人位置之間的距離最小值Distance，并記錄該最小值對(duì)應(yīng)的柵格編號(hào)k、柵格中心點(diǎn)坐標(biāo)Pk(xk,yk).

2.2.3 兩點(diǎn)法搜索策略F3

目標(biāo)柵格確定后，機(jī)器人立即從當(dāng)前位置，移動(dòng)到目標(biāo)柵格位置.在向目標(biāo)柵格移動(dòng)過(guò)程中，若已達(dá)到全遍歷覆蓋要求，則終止整個(gè)遍歷過(guò)程.若到達(dá)目標(biāo)柵格后，還未達(dá)到全遍歷覆蓋要求，機(jī)器人隨即跳轉(zhuǎn)至S2.

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

圖5 兩點(diǎn)法搜索過(guò)程示意圖

由圖5可知，A為起始點(diǎn)，B為目標(biāo)柵格，起始點(diǎn)A與目標(biāo)柵格B之間的線段AB上有障礙物.此時(shí)，首先向上偏轉(zhuǎn)角度θ，得到的線段AB1上仍有障礙物，再以線段AB為基準(zhǔn)，向下偏轉(zhuǎn)角度θ，得到的線段AB2上也有障礙物，再?gòu)木€段AB1開(kāi)始向上偏轉(zhuǎn)角度θ….如此反復(fù)，當(dāng)偏轉(zhuǎn)到線段ABi時(shí)，ABi上沒(méi)有障礙物，得到一點(diǎn)C，以此類推得到另一點(diǎn)D，直至到達(dá)目標(biāo)柵格B，整個(gè)搜索過(guò)程停止.

2.3 評(píng)價(jià)指標(biāo)

遍歷結(jié)束后，須引入“評(píng)價(jià)指標(biāo)”對(duì)遍歷結(jié)果進(jìn)行評(píng)價(jià).本文采用遍歷覆蓋率和遍歷重疊率作為評(píng)價(jià)指標(biāo).假設(shè)S表示整個(gè)工作空間，SΩ表示可達(dá)區(qū)域的面積，Shc表示已遍歷的面積，Scc表示重復(fù)遍歷的面積.

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

Jhc=(Shc/SΩ)×100%

(13)

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

Jcc=(Scc/SΩ)×100%

(14)

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

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

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

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

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

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

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

圖6 遍歷效果圖

4 結(jié)束語(yǔ)

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

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

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

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

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

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

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

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

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

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

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