基于柵格的簡單全覆蓋路徑規(guī)劃

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

關(guān)鍵詞：清潔機器人；路徑規(guī)劃；深度優(yōu)先遍歷搜索；全區(qū)域覆蓋

中圖分類號：TP24 文獻(xiàn)標(biāo)識碼：A 文章編號：1674-7712 （2012） 14-0047-02

一、引言

移動機器人的研究始于60年代末期。所謂移動機器人，就是一種具有高度自規(guī)劃、自組織、自適應(yīng)能力，適合于在復(fù)雜的非結(jié)構(gòu)環(huán)境中工作的機器人。

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

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

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

三、算法

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

Step1：機器人對房間的環(huán)境進(jìn)行測量。這里機器人可通過沿房間內(nèi)壁環(huán)繞房間一周，記錄房間大小。

Step2：對房間進(jìn)行柵格化；

Step3：對柵格后的格子進(jìn)行編碼；

Step4：隨機選取幾種情況下的障礙物跟房屋的構(gòu)造關(guān)系，并作出相應(yīng)的圖；

Step5：應(yīng)用深度優(yōu)先遍歷算法求出路徑，計算路徑長度和重復(fù)率。

四、實驗

按照深度優(yōu)先遍歷算法設(shè)計路徑，通過編程實現(xiàn)，得出以下九種情況在兩種算法中得到的路徑、路徑長度和重復(fù)率：