基于單元分解法的移動機器人遍歷路徑規劃

陳逸懷，朱 博

（1.天津職業技術師范大學信息技術工程學院，天津 300222；2.溫州城市大學，浙江 溫州 325027；3.天津職業技術師范大學 機電工程研究所，天津 300222）

基于單元分解法的移動機器人遍歷路徑規劃

陳逸懷1，2，朱 博3

（1.天津職業技術師范大學信息技術工程學院，天津 300222；2.溫州城市大學，浙江 溫州 325027；3.天津職業技術師范大學 機電工程研究所，天津 300222）

針對移動機器人遍歷路徑規劃問題，利用boustrophedon單元分解法建立環境模型，將環境地圖分割成若干子區域，每個子區域設一個基點，子區域與基點一一對應。提出了一種領域法，通過搜索基點，即可找到該子區域以及確定該子區域是否被遍歷到。首先進行第一層遍歷路徑規劃，遍歷完成后，搜索地圖模型基點，確定是否存在未遍歷到的基點，該基點即代表其子區域。尋找到后進行第二層局部區域遍歷。

移動機器人；遍歷路徑規劃；單元分解法；鄰域法

路徑規劃是機器人領域中的核心問題，也是機器人學中研究人工智能的一個重要方面。移動機器人的路徑規劃即給定機器人工作環境信息，按照某種優化指標，從起始點和目標點規劃出一條與環境障礙物無碰撞的路徑[1]。它是機器人執行各種任務的基礎，放映了機器人在運動過程中與周圍環境的交互能力。

機器人路徑規劃主要分為兩種：一種是傳統意義上的點到點的路徑規劃；另一種是遍歷路徑規劃。遍歷路徑規劃是一種特殊的路徑規劃，要求機器人尋找一條走遍工作空間內所有可達區域的連續路徑，并保證所規劃路徑的合理性和最優性[2]。完全遍歷路徑規劃比傳統的點對點路徑規劃更復雜。

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

1 環境建模

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

圖1 單元分解法環境地圖模型

當機器人到達另外一條公共邊時即完成了一個區域的遍歷。利用機器人的往復運動方式實現單元區域的完全遍歷。

2 鄰域遍歷路徑規劃算法思想

環境地圖運用單元分解法，將其劃分成若干個子區域，每個子區域對應著唯一的基點，其基點即代表這個子區域。在整個交錯網絡上搜索基點，一旦所有基點都被搜索到，則代表所有子區域被遍歷到，這樣整個環境地圖就被遍歷到。如果某個或幾個基點未被搜索到，即意味著該基點對應的子區域未被遍歷到。于是，完全遍歷路徑規劃問題就轉換成為了在環境地圖模型中的交錯網絡上尋找一條路徑來遍歷所有基點的問題。

我們把每個子區域的基點設為每個區域的右下角。如此設置的原因是：我們第一層遍歷路徑規劃是在環境地圖上從左向右遍歷，當移動機器人到達地圖的最右端，找不到與其相鄰的子區域時，機器人停止，進行全地圖掃描，判斷是否有基點未被遍歷到。如果有，機器人會移動到此基點，將子區域從右向左遍歷。將基點設置在子區域的右下角，可使機器人移動到此基點的路徑變短，遍歷路徑規劃的重復率降低，節省時間，提高效率。

移動機器人運動，主要分為兩種，一種是在子區域中的遍歷路徑規劃；另一種為子區域與子區域之間的路徑規劃，即機器人所在位置移動至另一個子區域的基點的點到點路徑規劃。

圖2 鄰域法示意圖

以下是鄰域法基本思想：

步驟1：子區域遍歷路徑規劃，移動機器人從起始點點出發，設定機器人每一步長與機器人的大小。機器人從左向右將當前子區域遍歷，直至遍歷完該子區域，如圖 2（a）所示。

步驟2：判斷機器人此時所在結束點位置，尋找其相鄰子區域。重復步驟1，遍歷其相鄰子區域。

步驟3：重復步驟2，直至機器人找不到鄰域，如圖2(（b）所示。進行全局掃描，判斷是否有基點未被遍歷到。如果沒有，結束掃描；如果有，繼續執行步驟4。

步驟4：機器人掃描到未遍歷到的基點，判斷哪個基點與機器人當前位置最近，機器人移動至最近的基點，從右向左遍歷該子區域，直至遍歷完成，如圖 2（c）所示。

步驟5：掃描環境地圖，重復步驟4與步驟5，直至遍歷完所有基點，即將環境地圖遍歷完成，如圖2（d）所示。

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

圖3 鄰域法流程圖

3 結束語

本文提出的鄰域法是針對靜態障礙物環境中的路徑規劃問題，采用單元分解法進行環境建模。通過掃描基點，判定地圖是否被完全遍歷到，然后通過判別機器人掃描完當前子區域所在位置，決定下一子區域的掃描。下一步再針對復雜環境下的移動機器人遍歷路徑規劃問題，對該方法進一步進行優化。

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

[2]劉 奎.移動機器人完全遍歷系統研究[D].南京:東南大學碩士論文，2006.

[3]李開生，張慧慧，費仁元，等.國外服務機器人的發展動態和前景[J].制造業自動化，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]張赤斌，王興松.基于蟻群算法的完全遍歷路徑規劃研究[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－），男，本科，高級講師，研究領域：移動機器人路徑規劃；朱 博（1988－），男，碩士，研究領域：移動機器人路徑規劃。