陳逸懷，朱 博

（1.天津職業(yè)技術(shù)師范大學(xué)信息技術(shù)工程學(xué)院，天津 300222；2.溫州城市大學(xué)，浙江 溫州 325027；3.天津職業(yè)技術(shù)師范大學(xué) 機(jī)電工程研究所，天津 300222）

基于單元分解法的移動(dòng)機(jī)器人遍歷路徑規(guī)劃

陳逸懷1，2，朱 博3

（1.天津職業(yè)技術(shù)師范大學(xué)信息技術(shù)工程學(xué)院，天津 300222；2.溫州城市大學(xué)，浙江 溫州 325027；3.天津職業(yè)技術(shù)師范大學(xué) 機(jī)電工程研究所，天津 300222）

針對(duì)移動(dòng)機(jī)器人遍歷路徑規(guī)劃問題，利用boustrophedon單元分解法建立環(huán)境模型，將環(huán)境地圖分割成若干子區(qū)域，每個(gè)子區(qū)域設(shè)一個(gè)基點(diǎn)，子區(qū)域與基點(diǎn)一一對(duì)應(yīng)。提出了一種領(lǐng)域法，通過搜索基點(diǎn)，即可找到該子區(qū)域以及確定該子區(qū)域是否被遍歷到。首先進(jìn)行第一層遍歷路徑規(guī)劃，遍歷完成后，搜索地圖模型基點(diǎn)，確定是否存在未遍歷到的基點(diǎn)，該基點(diǎn)即代表其子區(qū)域。尋找到后進(jìn)行第二層局部區(qū)域遍歷。

移動(dòng)機(jī)器人；遍歷路徑規(guī)劃；單元分解法；鄰域法

路徑規(guī)劃是機(jī)器人領(lǐng)域中的核心問題，也是機(jī)器人學(xué)中研究人工智能的一個(gè)重要方面。移動(dòng)機(jī)器人的路徑規(guī)劃即給定機(jī)器人工作環(huán)境信息，按照某種優(yōu)化指標(biāo)，從起始點(diǎn)和目標(biāo)點(diǎn)規(guī)劃出一條與環(huán)境障礙物無碰撞的路徑[1]。它是機(jī)器人執(zhí)行各種任務(wù)的基礎(chǔ)，放映了機(jī)器人在運(yùn)動(dòng)過程中與周圍環(huán)境的交互能力。

機(jī)器人路徑規(guī)劃主要分為兩種：一種是傳統(tǒng)意義上的點(diǎn)到點(diǎn)的路徑規(guī)劃；另一種是遍歷路徑規(guī)劃。遍歷路徑規(guī)劃是一種特殊的路徑規(guī)劃，要求機(jī)器人尋找一條走遍工作空間內(nèi)所有可達(dá)區(qū)域的連續(xù)路徑，并保證所規(guī)劃路徑的合理性和最優(yōu)性[2]。完全遍歷路徑規(guī)劃比傳統(tǒng)的點(diǎn)對(duì)點(diǎn)路徑規(guī)劃更復(fù)雜。

隨著商用和家用機(jī)器人的產(chǎn)業(yè)化進(jìn)程推進(jìn)，完全遍歷路徑規(guī)劃的研究受到越來越多的關(guān)注與重視，如清潔機(jī)器人、自動(dòng)收割機(jī)、割草機(jī)、自主吸塵器等[3～4]。研究完全遍歷路徑規(guī)劃的主要有模板模型法[5]、單元分解法[6]、神經(jīng)網(wǎng)絡(luò)和其他混合方法。Boustrophedon單元分解法是一種精確單元分解法[7]，基于這種分解思想的單元具有以下特點(diǎn)：單元必有兩條邊是平行的，而其他邊是障礙物的邊界或者環(huán)境的邊界[8]。

1 環(huán)境建模

本文的環(huán)境地圖模型采用單元分解法表示，利用單元分解法把整個(gè)環(huán)境劃分成若干個(gè)子區(qū)域。Boustrophedon單元分解法是將一條垂直于絕對(duì)坐標(biāo)X軸的虛擬掃描線從地圖的左邊掃描到右邊，通過判斷掃描線的連通性變化來生成子區(qū)域。如圖1所示，掃描線從圖1的左下角的起始點(diǎn)開始掃描，首先遍歷圖中1區(qū)，當(dāng)掃描線經(jīng)過障礙物Ⅰ時(shí)，連通性發(fā)生變化，產(chǎn)生子區(qū)域2和3。如此劃分下去，將地圖經(jīng)行boustrophedon單元分解后，可以分解為若干子區(qū)域和障礙物區(qū)。

圖1 單元分解法環(huán)境地圖模型

當(dāng)機(jī)器人到達(dá)另外一條公共邊時(shí)即完成了一個(gè)區(qū)域的遍歷。利用機(jī)器人的往復(fù)運(yùn)動(dòng)方式實(shí)現(xiàn)單元區(qū)域的完全遍歷。

2 鄰域遍歷路徑規(guī)劃算法思想

環(huán)境地圖運(yùn)用單元分解法，將其劃分成若干個(gè)子區(qū)域，每個(gè)子區(qū)域?qū)?yīng)著唯一的基點(diǎn)，其基點(diǎn)即代表這個(gè)子區(qū)域。在整個(gè)交錯(cuò)網(wǎng)絡(luò)上搜索基點(diǎn)，一旦所有基點(diǎn)都被搜索到，則代表所有子區(qū)域被遍歷到，這樣整個(gè)環(huán)境地圖就被遍歷到。如果某個(gè)或幾個(gè)基點(diǎn)未被搜索到，即意味著該基點(diǎn)對(duì)應(yīng)的子區(qū)域未被遍歷到。于是，完全遍歷路徑規(guī)劃問題就轉(zhuǎn)換成為了在環(huán)境地圖模型中的交錯(cuò)網(wǎng)絡(luò)上尋找一條路徑來遍歷所有基點(diǎn)的問題。

我們把每個(gè)子區(qū)域的基點(diǎn)設(shè)為每個(gè)區(qū)域的右下角。如此設(shè)置的原因是：我們第一層遍歷路徑規(guī)劃是在環(huán)境地圖上從左向右遍歷，當(dāng)移動(dòng)機(jī)器人到達(dá)地圖的最右端，找不到與其相鄰的子區(qū)域時(shí)，機(jī)器人停止，進(jìn)行全地圖掃描，判斷是否有基點(diǎn)未被遍歷到。如果有，機(jī)器人會(huì)移動(dòng)到此基點(diǎn)，將子區(qū)域從右向左遍歷。將基點(diǎn)設(shè)置在子區(qū)域的右下角，可使機(jī)器人移動(dòng)到此基點(diǎn)的路徑變短，遍歷路徑規(guī)劃的重復(fù)率降低，節(jié)省時(shí)間，提高效率。

移動(dòng)機(jī)器人運(yùn)動(dòng)，主要分為兩種，一種是在子區(qū)域中的遍歷路徑規(guī)劃；另一種為子區(qū)域與子區(qū)域之間的路徑規(guī)劃，即機(jī)器人所在位置移動(dòng)至另一個(gè)子區(qū)域的基點(diǎn)的點(diǎn)到點(diǎn)路徑規(guī)劃。

圖2 鄰域法示意圖

以下是鄰域法基本思想：

步驟1：子區(qū)域遍歷路徑規(guī)劃，移動(dòng)機(jī)器人從起始點(diǎn)點(diǎn)出發(fā)，設(shè)定機(jī)器人每一步長與機(jī)器人的大小。機(jī)器人從左向右將當(dāng)前子區(qū)域遍歷，直至遍歷完該子區(qū)域，如圖 2（a）所示。

步驟2：判斷機(jī)器人此時(shí)所在結(jié)束點(diǎn)位置，尋找其相鄰子區(qū)域。重復(fù)步驟1，遍歷其相鄰子區(qū)域。

步驟3：重復(fù)步驟2，直至機(jī)器人找不到鄰域，如圖2(（b）所示。進(jìn)行全局掃描，判斷是否有基點(diǎn)未被遍歷到。如果沒有，結(jié)束掃描；如果有，繼續(xù)執(zhí)行步驟4。

步驟4：機(jī)器人掃描到未遍歷到的基點(diǎn)，判斷哪個(gè)基點(diǎn)與機(jī)器人當(dāng)前位置最近，機(jī)器人移動(dòng)至最近的基點(diǎn)，從右向左遍歷該子區(qū)域，直至遍歷完成，如圖 2（c）所示。

步驟5：掃描環(huán)境地圖，重復(fù)步驟4與步驟5，直至遍歷完所有基點(diǎn)，即將環(huán)境地圖遍歷完成，如圖2（d）所示。

圖3為上述流程的流程簡圖。

圖3 鄰域法流程圖

3 結(jié)束語

本文提出的鄰域法是針對(duì)靜態(tài)障礙物環(huán)境中的路徑規(guī)劃問題，采用單元分解法進(jìn)行環(huán)境建模。通過掃描基點(diǎn)，判定地圖是否被完全遍歷到，然后通過判別機(jī)器人掃描完當(dāng)前子區(qū)域所在位置，決定下一子區(qū)域的掃描。下一步再針對(duì)復(fù)雜環(huán)境下的移動(dòng)機(jī)器人遍歷路徑規(guī)劃問題，對(duì)該方法進(jìn)一步進(jìn)行優(yōu)化。

[1]李開生，張慧慧，費(fèi)仁元，等.具有遍歷特性的移動(dòng)機(jī)器人規(guī)劃方法的研究[J].機(jī)器人，2001，23(6):486-492.

[2]劉 奎.移動(dòng)機(jī)器人完全遍歷系統(tǒng)研究[D].南京:東南大學(xué)碩士論文，2006.

[3]李開生，張慧慧，費(fèi)仁元，等.國外服務(wù)機(jī)器人的發(fā)展動(dòng)態(tài)和前景[J].制造業(yè)自動(dòng)化，2000，22(6)：1-4.

[4]The definition of service robot in the questionnaire of the international federation of Robotics(IFR)for their yearly study of world wide robotstatistics，1998.

[5]de Carvalho R N D,Vidal H A,Vieira P,etal.Complete Coverage Path Planning and Guidance for Cleaning Robots[C]//Proc.of the IEEE International Symposium on Industrial Electronics.Guimaraes：IEEE，1997：677-682.

[6]A car EU,ChosetH.RobustSensor-based Coverage ofUnstructured Environments[C]//Proceedings of the 2001IEEE/RSJ on IntelligentRobotsand Systems.Maui：IEEE，2001：61-68.

[7]ChosetH,Lee JY.Sensor-based Construction of Retract-like Structure for a Planar Rod Robot[J].IEEE Transactions on Roboticsand Automation，2001，17(4)：435-449.

[8]張赤斌，王興松.基于蟻群算法的完全遍歷路徑規(guī)劃研究[J].中國機(jī)械工程，2008，19(16):1945-1949.

Comp lete Coverage Path Planning ofMobile Robotbased on Partition of Unity Method

CHEN Yi-huai1，2，ZHU Bo3
（1.Tianjin University of Technology and Education，Tianjin 300222，China；2.City University ofWenzhou,Wenzhou Zhejiang 325000，China；3.Institute ofMechatronics Engineering，Tianjin University of Technology and Education，Tianjin 300222，China)

We focused on the problem of the complete coverage path planning ofmobile robot.The environmentmodel which is based on Boustrophedon partition of unitymethod can divided the environmentalmap into some sub domain.Each sub domain only has one homologues basis point.We proposed a method which is based on Neighborhood algorithm to traverse path planning.We can estimatewhether the sub domain is completely traversed by searching the basis points.First,we traverse the basalpath planning.Second,we search the basis point in the environmentalmap and confirm whether themissing basis point is existed.The basis pointwe found is the representative of its sub domain.Third,we traverse the second layerofsub domain if they areexisted.

mobile robot；complete coverage path planning,；boustrophedon partition of unity method；neighborhood algorithm

TP242

B

1672-545X（2014）04-0148-02

2014-01-05

陳逸懷（1973－），男，本科，高級(jí)講師，研究領(lǐng)域：移動(dòng)機(jī)器人路徑規(guī)劃；朱 博（1988－），男，碩士，研究領(lǐng)域：移動(dòng)機(jī)器人路徑規(guī)劃。