基于柵格的簡單全覆蓋路徑規劃

摘要：對柵格化后的區域進行編碼，對障礙區域進行標記，利用深度優先遍歷搜索算法來制定清潔機器人的全區域路徑規劃。利用C語言編程進行實驗，結果表明，此方法既避免了機器人判斷障礙物所需要進行的復雜計算，也十分有效的完成了機器人進行全區域覆蓋的清掃工作。

關鍵詞：清潔機器人；路徑規劃；深度優先遍歷搜索；全區域覆蓋

中圖分類號：TP24 文獻標識碼：A 文章編號：1674-7712 （2012） 14-0047-02

一、引言

移動機器人的研究始于60年代末期。所謂移動機器人，就是一種具有高度自規劃、自組織、自適應能力，適合于在復雜的非結構環境中工作的機器人。

我國從20 世紀90 年代開始進行智能掃地清潔機器人的技術跟蹤研究，但由于環境的特殊性和清潔機器人自身的特點，國內智能掃地機器人的智能水平較低，目前仍處于初級研究階段，許多關鍵技術如定位、環境建模、路徑規劃、傳感器等都有待進一步解決。

室內地面清潔是一項枯燥乏味的重復性勞動，傳統吸塵器工作時不僅需要人的參與，而且操作安放不便、清潔效率低、效果差，實現清潔作業自動化與智能化是高效高質清潔的有效途徑。智能掃地機器人是將移動機器人技術和吸塵器技術有機結合起來以實現室內環境半自主或自主清潔的一種環保、健康、智能型的服務性機器人。

目前國內外在清潔機器人方面的研究還有許多關鍵技術問題需要解決和提高，其中路徑規劃就是重要的關鍵技術之一，也是移動機器人為實現高智能化而必須解決的問題。機器人可以通過機身上的各種傳感器，通信器等裝置來獲取所處環境的信息，根據機器人所感知的環境，按照某種優化指標，在起始點和目標點規劃出一條與場景中障礙物不發生碰撞的路徑。而另一方面，對于地面清潔機器人而言，不僅需要設計從起點到終點的運行路徑，更需要機器人能將整個環境區域遍歷，以達到清掃整個室內地面的要求。

三、算法

由于廣度優先遍歷算法所得路徑中很多鄰接點之間，清潔機器人并不能直接到達，若采用回溯法到達鄰接點將會造成行進路徑重復，不僅增加了路徑長度，而且重復率很高，不能達到高效、節能的目的。因此，本文選擇深度優先遍歷算法對房間進行搜索。

Step1：機器人對房間的環境進行測量。這里機器人可通過沿房間內壁環繞房間一周，記錄房間大小。

Step2：對房間進行柵格化；

Step3：對柵格后的格子進行編碼；

Step4：隨機選取幾種情況下的障礙物跟房屋的構造關系，并作出相應的圖；

Step5：應用深度優先遍歷算法求出路徑，計算路徑長度和重復率。

四、實驗

按照深度優先遍歷算法設計路徑，通過編程實現，得出以下九種情況在兩種算法中得到的路徑、路徑長度和重復率：