1、迷宮機器人的回溯深度優先算法應用(圖文)    論文導讀：迷宮問題經典的算法是深度優先算法和廣度優先算法，深度優先算法是從迷宮的入口出發，順著某一方向向前探索，若能走通，則繼續前進，否則沿原路退回（回溯)，換一個方向再繼續探索，直到所有可能的通路都探索到為止，深度優先算法可以在未知迷宮中找到一條可行但不一定是最優的通路。考慮到實際物理系統內存容量和運算速度的限制以及以上算法的優缺點，帶回溯的深度優先算法具有占用內存空間少，對處理器的速度要求不高，不需要知道迷宮內部的具體結構的特點，因此適合于機器人在未知迷宮中進行路徑搜索。 關鍵詞：迷宮問題，機器人，深度

2、優先    0 引言 迷宮最短路徑問題是一個典型的搜索、遍歷問題，目前很多學者提出了一些新的迷宮路徑求解算法如如遺傳算法1、脈沖耦合神經網絡2 、蟻群算法3、反應擴散搜索4等，在迷宮最優路徑仿真搜索方面做出了一定的成績，但上述算法需要進行大規模的運算，對處理器的要求很高，因此只能應用于仿真層次，對于實際的物理系統來說實現起來是有困難的。 迷宮問題經典的算法是深度優先算法和廣度優先算法，深度優先算法是從迷宮的入口出發，順著某一方向向前探索，若能走通，則繼續前進，否則沿原路退回（回溯)，換一個方向再繼續探索，直到所有可能的通路都探索到為止，深度優先算法可以在

3、未知迷宮中找到一條可行但不一定是最優的通路。廣度優先搜索是從入口出發，離開入口后依次搜索與當前位置相鄰的單元格，然后分別從這些相鄰單元格出發依次訪問它們的鄰接格，依次類推直到找到迷宮出口，算法可以找到迷宮的最優路徑，但探索點會隨著探索的深入急劇增加，需要大量的內存空間用來保存探索過程的記錄。 考慮到實際物理系統內存容量和運算速度的限制以及以上算法的優缺點，帶回溯的深度優先算法具有占用內存空間少，對處理器的速度要求不高，不需要知道迷宮內部的具體結構的特點，因此適合于機器人在未知迷宮中進行路徑搜索。免費論文參考網。 1迷宮機器人結構描述 智能移動機器人技術是機器人研究領域的一個重要分支，智能移動機

4、器人是指機器人在完全未知的環境中，實時自主運動，是集環境感知、動態決策與規劃、行為控制與執行等功能于一體的具有高度自動化程度的智能化裝置。因此走迷宮機器人是在沒有人工干預的情況下，通過機器人自身的傳感器系統感知迷宮環境，并根據不同的迷宮環境做出不同的決策并驅動執行裝置執行相應的動作來完成走迷宮的過程的一種機器人。免費論文參考網。 1.1機械結構描述 機器人的移動方式有很多種，但大致可分為車輪式 和足步式兩種，車輪移動方式的大部分技術比較成熟， 控制也比較容易，而足步行走方式的控制要困難得多， 因此本文的迷宮機器人采用輪式移動機構，其機械結構如圖1所示：它有三個車輪，其中前輪為從動輪，為萬向自由

5、輪，后兩輪為相互獨立的驅動輪，固定不可轉向，并且每個輪子都有獨立的電氣驅動模塊和變速機構，車身的方向和速度依靠改變兩輪的速度來實現。 1.2傳感器系統 環境感知能力是移動機器人除了移動之外最為基本的一種能力，感知能力的高低直接決定了一個機器人的智能性高低，它的作用是建立合理的機器人感覺系統，以便機器人能夠建立起完整的信息獲取渠道。機器人要具備智能行為就必需依靠傳感器不斷感知外界環境，從而做出相應的決策行為。目前傳感器的種類繁多，功能越來越豐富，像超聲波傳感器、紅外傳感器、光電傳感等。傳感器系統是機器人很重要的 部分，選擇機器人傳感器完全取決于機器人的工作需要和應用特點，因此迷宮機器人具有如下傳

6、感器系統：其傳感器系統包括3個紅外傳感器和2兩個光電傳感器，3三個紅外傳感器位于機器人的左前右方（如圖1中箭頭3所示），探測距離是6cm，分別對機器人左前右三個方向的迷宮墻壁進行探測，以便機器人建立起迷宮障礙物的完整信息，光電傳感器1用來檢測是否進入一個新的迷宮格中，而傳感器2主要用來和1配合以識別機器人是否到達終點。 1.3 控制系統 控制系統主要包括單片機及其外圍電路以及電機驅動模塊、串行通訊模塊等，單片機采用了ATMEL公司的ATmega16微控制器，在16MHZ頻率下速度為16MIPS的8位RISC結構單片機，其內含硬件乘法器和16K的flash，支持ISP編程，運算速度比普通的單片機

7、要快的多，因此可以滿足系統的需要。 2 迷宮問題描述 迷宮問題是圖形學、圖論和數據結構等領域中廣為人知的一個經典問題，我們把迷宮簡化成如右圖2所示：圖中1表示障礙物，0表示通路，機器人從入口處進入，從出口出來就算成功的走出迷宮。 3算法仿真試驗 3.1算法描述如下： ：初始化，隨機生成符合要求的m行n列的迷宮maze（m，n），通過調整迷宮數組中0和1的個數比調節迷 宮的可行通路數量，0越多，則迷宮的可行路徑就越多，就越容 易找到出口。設定方向數組dir：規定搜索迷宮只能向上下左右四個方向搜索，對于正方形迷宮，設邊長為1個單位，因此可以設定方向數組dir（4，2）=1 0;0 1;0 -1;-

8、1 0。行進經過結點記錄數組jiedian（i，j）用來記錄機器人探索過的每個結點，如果機器人走過結點（i，j），則jiedian（i，j）=1，否則為0。走過路徑記錄數組way用來記錄機器人行走過程的可行路徑信息。 ：機器人開始行走，從當前結點開始向三個方向搜索，如果沒有障礙物（即該方向的迷宮壁為0）且不是終點并且沒有走過（即jiedian（i，j）=0），則把該結點記錄到jiedian中。 ：如果只有一個結點符合要求，則以該結點為起點繼續過程，同時把該結點記錄到way中，如果有兩個或兩個以上的結點，則從中隨機選擇一個結點為起點繼續過程，并把該結點記錄到way中。免費論文參考網。 ：如果三個

9、方向都有障礙物，則機器人進行回溯，退回上一個結點，選擇排除已經探索方向的其它方向繼續搜索，如果沒有可通路徑則繼續回溯直到回到起點，轉到，否則轉到繼續搜索直到找到終點，轉。 ：給出沒有可行路徑信息。 ：輸出可行路徑。 3.2實驗結果過程及結果： 為了驗證算法的有效性，我們隨機生成一個22*22規模的迷宮，應用深度優先算法進行迷宮路徑搜索，其仿真結果如3圖所示：圖中o表示迷宮的0，表示迷宮中的1，左上角為迷宮的入口，右下角為迷宮的出口，深色部分表示算法找到的可行迷宮路徑，從圖3中可以看到：深度優先算法可以在迷宮中找到一條可行路徑。 4 物理系統實現： 圖 3 深度優先算法找到的路徑示意圖機器人路徑

10、規劃問題可以分為兩種，一種是基于環境先驗完全信息的全局路徑規劃，另一種是基于傳感器信息的局部路徑規劃，后者環境是未知或者部分未知的。基于實際物理系統的特點，我們把該算法應用到我們研制的迷宮機器人上，在不影響算法正確性的情況下，我們采用圖4所示的簡化迷宮進行實驗：帶箭頭的白線是機器人實際所走路線圖，可以看到機器人從入口出發，按照帶回溯的深度優先算法行走，經過一定的時間后能夠順利的找到出口，完成了在未知迷宮中的行走過程，實驗證明了算法的有效性。 5結論： 迷宮問題是一個經典的遍歷問題，求解算法很多，但對于實際的物理系統，考慮到其運算速度和內存大小的局限，運用深度優先算法進行迷宮路徑的搜索是可行的，從仿真實驗和物理實驗都可以看出，深度優先算法是有效的。 參考文獻： 1 SU S,Tsuchiya K. Learning of a maze using a genetic algorithmc. IndustrialElectronics, Control and Instrumentation 1993, Proceedings of the IECON