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

王藝寧　蔣涵　王博　于娜

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

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

中圖分類號(hào)：TP36 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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電腦鼠為研究對(duì)象，以電腦鼠走迷宮比賽為背景。電腦鼠車體采用四輪驅(qū)動(dòng)結(jié)構(gòu)，內(nèi)核控制器采用32位ARM Cortex-M3 STM32，控制和檢測(cè)紅外傳感器；微控制器根據(jù)檢測(cè)到的傳感信號(hào)，控制電機(jī)驅(qū)動(dòng)電路，調(diào)整行走，按照載入搜索算法進(jìn)行迷宮的探測(cè)，尋找最短路徑，最終實(shí)現(xiàn)從起點(diǎn)到終點(diǎn)的沖刺。

1 電腦鼠硬件研究

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

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

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

2.1 探測(cè)策略

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

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

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

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

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

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

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

2.2 等高圖的制作

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

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

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

2.3 沖刺

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

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

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

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

3 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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

[4] 張新誼.一種電腦鼠走迷宮的算法[J].單片機(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.