電腦鼠走迷宮智能算法的研究與優(yōu)化

王藝寧　蔣涵　王博　于娜

摘 要：電腦鼠（Micromouse）是智能機電鼠的簡稱，實際上是一個由微處理器控制的，集感知、判斷、行走功能于一體，能夠自動尋找最佳路徑到達目的地的微型機器人。該文簡要分析了電腦鼠的硬件組成和工作原理，在此基礎(chǔ)上重點對電腦鼠軟件部分的探測策略模塊、等高圖制作模塊、沖刺模塊進行了分析研究與優(yōu)化，并通過大量實驗進行了驗證。實驗結(jié)果表明優(yōu)化后的算法能夠在一定程度上有效地提高電腦鼠走迷宮的運行速度、減少電腦鼠的搜索時間。

關(guān)鍵詞：電腦鼠 嵌入式系統(tǒng) 智能算法 搜索法則

中圖分類號：TP36 文獻標識碼：A 文章編號：1674-098X（2015）11（b）-0129-03

Abstract：Micromouse （computer mouse） is the abbreviation of the intelligent electrical mouse. It is actually a micro robot which is controlled by the microprocessor with abilities to perceive、judge and walk， which is capable of finding the best path to reach the destination automatically. In this paper， the hardware and working principle of the micromouse are briefly analyzed， and the key part of this paper is to analyze and optimize the search strategy module， the contour map-module drawn module and the module of sprint of the software， and verified these through a lot of experiments .The experimental results show that the optimized algorithm can effectively improve the running speed of the micromouse and reduce the searching time of the micromouse.

Key Words：Embedded System；Micromouse；Intelligent Algorithm；Search strategy

該文以TQD-Micromouse-JZ電腦鼠為研究對象，以電腦鼠走迷宮比賽為背景。電腦鼠車體采用四輪驅(qū)動結(jié)構(gòu)，內(nèi)核控制器采用32位ARM Cortex-M3 STM32，控制和檢測紅外傳感器；微控制器根據(jù)檢測到的傳感信號，控制電機驅(qū)動電路，調(diào)整行走，按照載入搜索算法進行迷宮的探測，尋找最短路徑，最終實現(xiàn)從起點到終點的沖刺。

1 電腦鼠硬件研究

該部分主要研究的是TQD-Micromouse-JZ電腦鼠的硬件設(shè)計，針對電源模塊、微控制器單元模塊、傳感器模塊和直流電機控制模塊[1]四個模塊進行研究。其中ARM Cortex-M3 STM32內(nèi)核控制器是電腦鼠的核心，通過檢測傳感器信號，結(jié)合載入的搜索算法，控制直流電機，從而實現(xiàn)電腦鼠在迷宮中的行走。

2 電腦鼠軟件研究與優(yōu)化

電腦鼠的軟件部分主要用來檢測迷宮環(huán)境，傳送控制信號給相應(yīng)的硬件模塊，對在迷宮中行走的電腦鼠進行制導(dǎo)與導(dǎo)航[2]。軟件部分分為相對方向與絕對方向的轉(zhuǎn)換模塊、墻壁資料存儲模塊、探測策略模塊、等高圖制作模塊、沖刺模塊、轉(zhuǎn)彎模塊。該文主要對探測策略模塊、等高圖制作模塊、沖刺模塊進行了分析研究與優(yōu)化，并通過大量實驗進行了驗證。

2.1 探測策略

電腦鼠走迷宮可以采用全迷宮探測策略或部分迷宮探測策略，從中找出最佳的路徑。在時間有限的情況下只能選擇后者。做此種處理的電腦鼠要時刻掌握自己的位置及姿態(tài)，記錄所有訪問過的方塊四周是否有墻壁，記憶曾經(jīng)搜索過的路徑。

2.1.1 現(xiàn)有搜索法則

現(xiàn)有基礎(chǔ)搜索法則有左手法則、右手法則、中左法則和中右法則，中心法則由以上基礎(chǔ)法則按照一定的規(guī)則有機組合起來，隨時根據(jù)電腦鼠與迷宮終點的相對位置智能的選擇最有效的基礎(chǔ)法則，使得電腦鼠搜索方向始終以目標點所在方向為最優(yōu)方向。

根據(jù)比賽規(guī)則，電腦鼠首先從起點出發(fā)，找到目標點后回到起點準備第一次沖刺。在實際試驗中發(fā)現(xiàn)，電腦鼠使用中心法則搜索到目標點后根據(jù)已知的迷宮信息計算出一條最短路回到起點，但是由于電腦鼠采用部分迷宮搜索策略，往往這條路不是最優(yōu)路徑。根據(jù)比賽規(guī)則，電腦鼠比賽成績=迷宮時間/30+運行時間-獎勵時間[3]，所以，要盡可能找到更優(yōu)路徑來減小運行時間。

2.1.2 中心法則優(yōu)化

為了提高迷宮搜索的有效性，對中心法則進行優(yōu)化，電腦鼠從目標點回到起點時再繼續(xù)搜索其他路徑，同樣采用最高效的中心法則，以起點或電腦鼠搜索到的第一個分支節(jié)點為中心進行搜索。為了驗證優(yōu)化后算法的性能，該文搭建如圖1所示的迷宮，分別以4個頂點為起點模擬完整的比賽。電腦鼠的搜索結(jié)果如圖1所示。

記錄4組成功完成且無觸碰實驗的實驗數(shù)據(jù)，如表1所示。通過實驗數(shù)據(jù)不難發(fā)現(xiàn)，當(dāng)二次搜索的路徑為更優(yōu)路徑時（A，B為出發(fā)點），優(yōu)化后的算法能顯著提高比賽成績；當(dāng)二次搜索路徑?jīng)]有更優(yōu)時（C，D為出發(fā)點），雖然會延長搜索時間，但對比賽成績影響不大。

2.2 等高圖的制作

經(jīng)過有限次的探測后，已經(jīng)可以得到部分或大部分描述迷宮圖線路的二維表，其中可能包含了若干條可以到達終點的路徑，為了尋找到達終點的路徑，需要制作等高圖[4]。

由于電腦鼠在轉(zhuǎn)彎和直行時，走相等的步數(shù)時間代價是不同的，不能單純的用步數(shù)來確定等高值，因此，對轉(zhuǎn)彎加權(quán)制作等高圖對最優(yōu)路徑的選擇更有效。

由于電腦鼠轉(zhuǎn)彎需要花費較長時間，所以，要對拐彎次數(shù)（90°的轉(zhuǎn)彎為一次，180°的轉(zhuǎn)彎為二次）加權(quán)后加到步數(shù)中得到加權(quán)步數(shù)，因此，拐彎權(quán)重是一個對結(jié)果有重要影響的參數(shù)，要結(jié)合電腦鼠的結(jié)構(gòu)和試跑確定。根據(jù)上文所得數(shù)據(jù)可計算出該電腦鼠在搜索過程中轉(zhuǎn)彎權(quán)值為1.0。

2.3 沖刺

電腦鼠從起點開始，根據(jù)等高圖信息直接調(diào)用行進函數(shù)，控制電腦鼠走完記錄好的步數(shù)。在沖刺階段可以通過調(diào)整不同步數(shù)的直道前進速度，實現(xiàn)電腦鼠的變速沖刺，既節(jié)省了時間，又能保證電腦鼠前進的穩(wěn)定性。

根據(jù)比賽規(guī)則，要不斷刷新運行時間來提高比賽成績，但是由于電腦鼠運行速度越快越不穩(wěn)定，越容易發(fā)生碰撞，因此，可以先用保守速度沖刺完成比賽，在實驗中發(fā)現(xiàn)，當(dāng)速度為160時，電腦鼠能穩(wěn)定運行，沖刺成功率幾乎為100%，平均沖刺時間為13.5 s。因此，選用160為保守沖刺速度，再通過實驗確定后續(xù)沖刺速度。用節(jié)省的時間（T）來顯示多次沖刺的優(yōu)勢。（Ti=（13.5-Si）-（13.5×2×1/30））

根據(jù)表2實驗結(jié)果，并綜合考慮節(jié)省時間和電腦鼠沖刺成功率，將第2次沖刺速度確定為200，平均沖刺時間為10.2 s。以此為基礎(chǔ)進行實驗確定第3次沖刺速度。（Ti=（10.2-Si）-（（13.5+10.2）×2×1/30））

根據(jù)表3實驗結(jié)果，當(dāng)?shù)?次的沖刺速度低于220時，不能刷新成績，所以沖刺是沒有意義的，綜合考慮電腦鼠沖刺成功率，將3次沖刺速度確定為235，平均沖刺時間為7.9s。

3 結(jié)語

通過不斷地實驗對電腦鼠走迷宮智能算法進行優(yōu)化，并進行反復(fù)驗證，實驗結(jié)果表明，優(yōu)化后的算法能夠在一定程度上有效地提高電腦鼠走迷宮的運行速度、減少電腦鼠的搜索時間。但由于筆者研究能力有限，對電腦鼠走迷宮智能算法的優(yōu)化方法的學(xué)習(xí)和實踐還處于初級階段，今后還需進一步深入學(xué)習(xí)、研究和實踐。

參考文獻

[1] 付秀偉，張驊.基于ARM—M3的電腦鼠硬件設(shè)計[J].吉林化工學(xué)院學(xué)報，2012，29（1）：47-49.

[2] 祝學(xué)云，況迎輝，楊海波.“基于LM3S615的電腦鼠實踐”研討班課程建設(shè)[J].電氣電子教學(xué)學(xué)報，2011（4）：25-26.

[3] IEEE國際電工和電子工程學(xué)會.IEEE電腦鼠（迷宮）競賽規(guī)則和介紹—嵌入之夢[Z].

[4] 張新誼.一種電腦鼠走迷宮的算法[J].單片機與嵌入式系統(tǒng)應(yīng)用，2007（5）：84-85.

[5] 蔣雄，任化龍，馬忠麗.基于ARM的電腦鼠走迷宮的研究[J].現(xiàn)代電子技術(shù)，2011（8）：14-16.

[6] UK Micromouse Championship.UK Micromouse Hampion-ship Rules.UK Mieromouse Championship，2006.