IEEE標(biāo)準(zhǔn)電腦鼠算法的探索與研究

師建軍

[摘 要] 介紹了IEEE標(biāo)準(zhǔn)電腦鼠搜尋最優(yōu)路徑的構(gòu)思和實(shí)現(xiàn)方法，結(jié)合相關(guān)的軟、硬件設(shè)計(jì)，使電腦鼠能在多條路徑中選擇最優(yōu)路徑到達(dá)終點(diǎn)。

[關(guān) 鍵 詞] 最優(yōu)路徑；電腦鼠；算法

[中圖分類號(hào)] G433 [文獻(xiàn)標(biāo)志碼] A [文章編號(hào)] 2096-0603（2016）24-0161-01

一、電腦鼠概述

電腦鼠的英文名稱為Micromouse，實(shí)際上是一個(gè)由微處理器控制的，集感知、判斷、行走功能于一體，能夠自動(dòng)尋找最佳路徑到達(dá)目的地的小型機(jī)器人。它可以在“迷宮”中自動(dòng)感知并記憶迷宮地圖，通過(guò)一定的算法，尋找一條最佳路徑，以最快的速度到達(dá)目的地。1997年，在美國(guó)舉辦了第一屆電腦鼠競(jìng)賽，隨后，電腦鼠競(jìng)賽傳入歐洲，首屆歐洲電腦鼠競(jìng)賽于1980年在倫敦舉辦，之后英國(guó)的電腦鼠比賽便由電子工程協(xié)會(huì)（IEE）主辦。1980年11月日本電腦鼠協(xié)會(huì)（JMA）在東京舉辦了第一屆競(jìng)賽，此后，日本每年都要舉辦一屆電腦鼠競(jìng)賽。我國(guó)臺(tái)灣也于1986年10月舉辦了首屆電腦鼠比賽。現(xiàn)在國(guó)際電工和電子工程學(xué)會(huì)（IEEE）每年都要舉辦一次國(guó)際性的電腦鼠走迷宮競(jìng)賽，各國(guó)選手報(bào)名踴躍，主要是大學(xué)生，為此部分大學(xué)還開(kāi)設(shè)了“電腦鼠原理和制作”選修課程。

由于電腦鼠要由參賽選手自己設(shè)計(jì)制作，不僅要求選手具有嵌入式系統(tǒng)應(yīng)用、傳感器、控制技術(shù)等多方面的知識(shí)、經(jīng)驗(yàn)和實(shí)踐能力，還要求具有編寫尋找最佳路徑算法的能力。由于迷宮路徑設(shè)置是隨機(jī)的，因而競(jìng)賽難度較大，極富挑戰(zhàn)性。這對(duì)培養(yǎng)和提高學(xué)生的創(chuàng)新精神和實(shí)踐能力有著深遠(yuǎn)的意義。

二、算法研究

電腦鼠在第一次進(jìn)入迷宮時(shí)，可以采用全迷宮搜索策略，即將迷宮的所有單元均搜索一次，從中找出最佳的行走路徑。這種策略需要有足夠的時(shí)間，在IEEE競(jìng)賽規(guī)則中每場(chǎng)競(jìng)賽只有規(guī)定的很短時(shí)間，因此，保證電腦鼠順利走完全程是比較困難的。另一種方法是部分迷宮搜索策略，即在有限的時(shí)間內(nèi)，只搜索迷宮的一部分，從中找出最佳的路徑。

假如電腦鼠在行走的過(guò)程中，進(jìn)入一條前、左、右都有障礙的道路，則必須掉頭，回到最近的支路，再次選擇新的道路進(jìn)行搜索，直至找到終點(diǎn)。除此之外，電腦鼠在任一單元內(nèi)，可能的行走方向最多只有三個(gè)（前、左、右），如果有兩個(gè)或兩個(gè)以上的可能行走方向，稱為交叉，遇有交叉時(shí)，由于有多個(gè)可以行走的方向，在行走方向的選擇上，通常情況下，有以下幾種選擇法則，迷宮搜索流程圖如右圖所示。

右手法則：以右邊為優(yōu)先的前進(jìn)方向，然后是直線方向、左邊方向。

左手法則：以左邊為優(yōu)先的前進(jìn)方向，然后是直線方向、右邊方向。

中左法則：以前面為優(yōu)先的前進(jìn)方向，然后是左邊方向、右邊方向。

中右法則：以前面為優(yōu)先的前進(jìn)方向，然后是右邊方向、左邊方向。

中心法則：由于終點(diǎn)在迷宮的中心，遇有交叉時(shí)，以向迷宮中心的方向?yàn)閮?yōu)先的前進(jìn)方向。

三、算法選擇

在整個(gè)電腦鼠比賽的過(guò)程中，要求電腦鼠要在沒(méi)有觸碰，或者觸碰次數(shù)盡量少的情況下，以最短的時(shí)間完成由起點(diǎn)到終點(diǎn)的沖刺。因此，路徑的選擇至關(guān)重要，步數(shù)少的路徑，是最佳路徑的條件之一，但不是唯一條件。

在比賽過(guò)程中，由于比賽的迷宮是未知的，所以我們?cè)谶x擇電腦鼠的算法時(shí)，就勢(shì)必要綜合考慮運(yùn)行時(shí)間和支路的情況等。若遇到十字路口多迷宮，如果我們只是單純地選擇右手法則或者左手法則，則電腦鼠在經(jīng)過(guò)多個(gè)連續(xù)的十字路口，或者其中的一個(gè)十字路口時(shí)，就有可能會(huì)進(jìn)入死循環(huán)，因?yàn)橛沂址▌t或者左右法則，最終會(huì)讓電腦鼠走一個(gè)閉合的環(huán)形路徑，要想避免，就必須在程序中另外調(diào)用子程序來(lái)解決這個(gè)問(wèn)題。但如果我們選擇的算法是中心法則，則可以有效地避免上述問(wèn)題的出現(xiàn)，而且節(jié)省電腦鼠在迷宮中的運(yùn)行時(shí)間。

四、直接到指定坐標(biāo)程序設(shè)計(jì)

該程序的目的是讓電腦鼠能夠以最短路徑前進(jìn)到指定坐標(biāo)點(diǎn)，當(dāng)然該功能實(shí)現(xiàn)的前提是目的地是電腦鼠已經(jīng)走過(guò)且記錄下來(lái)的方格。設(shè)計(jì)該程序的步驟如下：

1.制作以目的地為起點(diǎn)的等高圖。

2.檢查電腦鼠是否已達(dá)到目的地，如果是則跳到第7步，否則繼續(xù)順序執(zhí)行。

3.獲取當(dāng)前坐標(biāo)的等高值。

4.尋找比當(dāng)前坐標(biāo)等高值小的支路方向，且優(yōu)先選擇不需要轉(zhuǎn)彎的方向前進(jìn)。如果選擇的方向是正前方，則前進(jìn)步數(shù)cNBlock加一并返回第2步，否則繼續(xù)執(zhí)行。

5.前進(jìn)cNBlock步，并清零cNBlock。

6.根據(jù)目標(biāo)方向控制電腦鼠轉(zhuǎn)彎，完成后返回第2步。

7.控制電腦鼠前進(jìn)cNBlock，任務(wù)完成后程序結(jié)束。