IEEE電腦鼠迷宮路徑選擇及死區(qū)決策

IEEE電腦鼠路徑選擇及死區(qū)決策一、引言（一）IEEE電腦鼠走迷宮競(jìng)賽背景嵌入式系統(tǒng)融合了微電子、計(jì)算機(jī)軟\硬件、通信和電子工程等多種技術(shù)，廣泛應(yīng)用于航空、航天、儀器儀表、工業(yè)控制和3C（Computer、Communication、Consumer）等領(lǐng)域，是科技集成創(chuàng)新的主要手段。為了培養(yǎng)科技創(chuàng)性意識(shí)和動(dòng)手能力，全國(guó)各地在近幾年紛紛舉辦“電腦鼠走迷宮“邀請(qǐng)賽。電腦鼠英文名叫做MicroMouse，是使用嵌入式微控制器、傳感器和機(jī)電運(yùn)動(dòng)部件構(gòu)成的一種智能行走裝置（微型機(jī)器人）。電腦鼠要在指定的迷宮中比賽，在迷宮中探索以找出通往終點(diǎn)的路徑，并隨時(shí)掌握自身的位置信息，準(zhǔn)確獲取墻壁信息并做記錄，最終依靠記憶找出走出迷宮的最佳路徑，以最短的時(shí)間解開迷宮，贏得比賽。國(guó)際電工和電子工程學(xué)會(huì)（IEEE）每年都要舉辦一次國(guó)際性的電腦鼠走迷宮競(jìng)賽，自舉辦以來參加國(guó)踴躍，為此許多大學(xué)還開設(shè)了“電腦鼠原理和制作”選修課程。2007年和2008年，上海市計(jì)算機(jī)學(xué)會(huì)率先在國(guó)內(nèi)主辦了兩次IEEE標(biāo)準(zhǔn)電腦鼠走迷宮邀請(qǐng)賽（長(zhǎng)三角地區(qū)），有三十多所院校參加。2009年廣州致遠(yuǎn)電子有限公司贊助了全國(guó)“IEEE標(biāo)準(zhǔn)電腦鼠走迷宮”邀請(qǐng)賽，共邀請(qǐng)全國(guó)9個(gè)賽區(qū)的52所高校參賽，反響強(qiáng)烈。圖1所示為電腦鼠圖2所示為比賽迷宮 本文主要以MicroMouse615為平臺(tái)，介紹電腦鼠參賽的實(shí)現(xiàn)，對(duì)有些方面的基本算法提出改進(jìn)，并在此基礎(chǔ)上加上了一些自己的算法思想，比如說：用數(shù)學(xué)模型的方法提出了用改進(jìn)后的數(shù)字PID算法對(duì)行進(jìn)中的電腦鼠進(jìn)行狀態(tài)調(diào)整，進(jìn)入死區(qū)的電腦鼠的人工智能決策，參賽時(shí)迷宮搜索的易于實(shí)現(xiàn)的算法以及植入操作系統(tǒng)的思想。（二）競(jìng)賽平臺(tái)簡(jiǎn)介MicroMouse615平臺(tái)包含了微控制器、電機(jī)、紅外線傳感器、控制平臺(tái)。其中最重要的微控制器是LM3S615微控制器，如下圖3為L(zhǎng)M3S615的系統(tǒng)結(jié)構(gòu)圖。其中內(nèi)核用的是ARMCortex-M3,外圍還有存儲(chǔ)器、系統(tǒng)時(shí)鐘、定時(shí)器、輸入輸出端口、數(shù)模轉(zhuǎn)換器等等。ARMCortex-M3處理器為高性能、低成本的平臺(tái)提供了一個(gè)能夠滿足小存儲(chǔ)要求解決方案、簡(jiǎn)化管腳數(shù)、以及低功耗三方面要求的內(nèi)核，與此同時(shí)，它還提供了出色的計(jì)算性能和優(yōu)越的系統(tǒng)中斷響應(yīng)能力。其特性如下：1、緊湊的內(nèi)核2、Thumb-2指令集，在與8位和16位器件相關(guān)的存儲(chǔ)容量中，特別是在微控制器級(jí)應(yīng)用的幾千字節(jié)存儲(chǔ)量中，提供了ARM內(nèi)核所期望的高性能。3、優(yōu)越的中斷處理能力，通過執(zhí)行寄存器操作來實(shí)現(xiàn)，這些寄存器操作在處理硬件中斷時(shí)使用。4、存儲(chǔ)器保護(hù)單元（MPU），為復(fù)雜的應(yīng)用提供特權(quán)操作模式5、功能齊全的調(diào)試解決方案，包括：串行線JTAG調(diào)試端口（SWJ-DP）；Flash修補(bǔ)和斷點(diǎn)（FPB）單元，用于實(shí)現(xiàn)斷點(diǎn)操作；數(shù)據(jù)觀察點(diǎn)和觸發(fā)單元（DWT），用于執(zhí)行觀察點(diǎn)、觸發(fā)源和系統(tǒng)性能分析等操作；儀表跟蹤宏單元（ITM），用于支持Printf型調(diào)試。圖3MicroMouse615原理圖圖4LM3S615CPU結(jié)構(gòu)圖關(guān)于各個(gè)部件的接線圖如圖3，關(guān)于系統(tǒng)編程尤為重要；編程時(shí)主要注意引腳的鏈接和存儲(chǔ)器的地址映射等。在具體嵌入式編程方面，可以參照LM3S651微控制器數(shù)據(jù)手冊(cè)，其中提供了存儲(chǔ)器、串并口通信時(shí)序等全部信息。電機(jī)使用的是BA6845FS，它是步進(jìn)電機(jī)，最大輸出電流為1.0A。邏輯輸入允許三種輸出模式：前進(jìn)、反轉(zhuǎn)和節(jié)電模式。集成電路具有低輸出飽和電壓，能以低電壓驅(qū)動(dòng)電機(jī)。紅外傳感器使用的型號(hào)是IRM-8601S，該設(shè)備是一種小型紅外遙控器系統(tǒng)接收器，開發(fā)和設(shè)計(jì)利用最新IC技術(shù).PIN二極管前置放大器是組裝和引線框架，環(huán)氧包裝被設(shè)計(jì)成一個(gè)IR過濾器.解調(diào)輸出信號(hào)可直接由微處理器解碼?？刂婆_(tái)是使用ZLG7289B，ZLG7289B是廣州周立功單片機(jī)發(fā)展有限公司自行設(shè)計(jì)的數(shù)碼管顯示驅(qū)動(dòng)及鍵盤掃描管理芯片，可直接驅(qū)動(dòng)8位共陰式數(shù)碼管（或64只獨(dú)立LED），同時(shí)還可以掃描管理多達(dá)64只按鍵。ZLG7289B內(nèi)部含有顯示譯碼器，可直接接受BCD碼或16進(jìn)制碼，并同時(shí)具有2種譯碼方式。此外，還具有多種控制指令，如消隱﹑閃爍﹑左移﹑右移﹑段尋址等。ZLG7289B采用SPI串行總線與微控制器接口，僅占用少數(shù)幾根I/O口線。利用片選信號(hào)，多片ZLG7289B還可以并接在一起使用，能夠方便地實(shí)現(xiàn)多于8位的顯示或多于64只按鍵的應(yīng)用。ZLG7289B可廣泛地應(yīng)用于儀器儀表，工業(yè)控制器，條形顯示器，控制面板等領(lǐng)域。二、實(shí)時(shí)狀態(tài)采集及更新方法要想使電腦鼠具備智能選路的本領(lǐng)，必須使其具備記憶迷宮信息的能力，并且電腦鼠還需記憶當(dāng)前所在迷宮格和前進(jìn)方向的信息，這些信息將隨著電腦鼠在迷宮格中行走而不斷被刷新。用CurDir存儲(chǔ)當(dāng)前方向，用CurPosition[1][1]存儲(chǔ)當(dāng)前坐標(biāo)，用MazeShape[16][16]存儲(chǔ)每個(gè)迷宮格的形狀，用CurWall存儲(chǔ)當(dāng)前傳感器采集到迷宮格墻壁情況。信息采集算法的核心是確定何時(shí)刷新信息以及輸入?yún)?shù)。為此用三張表格來表示這三個(gè)刷新邏輯。當(dāng)迷宮是以類似于如圖5建立座標(biāo)時(shí)： Y（02）（12）（22）（01）（11）（21）（00）（10）X（20）X圖5以下是數(shù)據(jù)的更新方法：表1CurDir更新方法原始狀態(tài)NSWE左轉(zhuǎn)彎WESN右轉(zhuǎn)彎EWNS后轉(zhuǎn)彎SNEW其中轉(zhuǎn)彎項(xiàng)代表：準(zhǔn)備和剛轉(zhuǎn)完時(shí)的小車位置，且用于非連續(xù)轉(zhuǎn)彎。表2CurPosition更新方法原始狀態(tài)N(X,Y)S(X,Y)W(X,Y)E(X,Y)直走（X,Y+1）(X,Y-1)(X-1，Y)(X+1，Y)左轉(zhuǎn)彎（X,Y+1）(X,Y-1)(X-1，Y)(X+1，Y)右轉(zhuǎn)彎（X,Y+1）(X,Y-1)(X-1，Y)(X+1，Y)后轉(zhuǎn)彎（X,Y+1）(X,Y-1)(X-1，Y)(X+1，Y)其中轉(zhuǎn)彎項(xiàng)代表：準(zhǔn)備和剛轉(zhuǎn)完時(shí)的小車位置，且用于非連續(xù)轉(zhuǎn)彎。表3MazeShape[16][16]更新方法原始狀態(tài)參數(shù)N(X,Y)S(X,Y)W(X,Y)CurWallCurWallCurWallE(X,Y)CurWallMazeShape更新CurWall直接CurWallCurWall賦給順時(shí)針轉(zhuǎn)180°順時(shí)針轉(zhuǎn)90°MazeShape賦給MazeShape賦給MazeShape[x][y][x][y][x][y]CurWall逆時(shí)針轉(zhuǎn)90°賦給MazeShape[x][y]需要注意的是由上述三個(gè)刷新邏輯表可知，WallShape需要CurPosition作為參數(shù)，而CurPosition需要CurDir作為輸入?yún)?shù)來更新自身。因此當(dāng)需要同時(shí)刷新三個(gè)變量的兩個(gè)或三個(gè)時(shí)，應(yīng)先刷新CurDir再刷新CurPosition最后刷新WallShape。收集完迷宮狀態(tài)之后，就是怎么進(jìn)行電腦鼠的行進(jìn)過程，我們參考迷宮的整體狀態(tài)，可以設(shè)計(jì)程序如下：（其中等高法在下面介紹）voidobjectGoTo(int8x,int8y){uint8ucStep=1;int8cNBlock=0,cDirTemp;int8cX,cY;cX=GmcMouse.cX;cY=GmcMouse.cY;mapStepEdit(x,y);/*制作等高圖*//*根據(jù)等高值向目標(biāo)點(diǎn)運(yùn)動(dòng)，直到達(dá)到目的地*/while((cX!=x)||(cY!=y)){ucStep=GucMapStep[cX][cY];/*任選一個(gè)等高值比當(dāng)前自身等高值小的方向前進(jìn)*/if((GucMapBlock[cX][cY]&0x01)&&/*上方有路*/(GucMapStep[cX][cY+1]<ucStep)){/*上方等高值較小*/cDirTemp=UP;/*記錄方向*/if(cDirTemp==GucMouseDir){/*優(yōu)先選擇不需要轉(zhuǎn)彎的方向*/cNBlock++;/*前進(jìn)一個(gè)方格*/cY++;continue;/*跳過本次循環(huán)*/}}if((GucMapBlock[cX][cY]&0x02)&&(GucMapStep[cX+1][cY]<ucStep)){cDirTemp=RIGHT;if(cDirTemp==GucMouseDir){cNBlock++;cX++;continue;}}if((GucMapBlock[cX][cY]&0x04)&&(GucMapStep[cX][cY-1]<ucStep)){cDirTemp=DOWN;if(cDirTemp==GucMouseDir){cNBlock++;cY--;continue;}}if((GucMapBlock[cX][cY]&0x08)&&(GucMapStep[cX-1][cY]<ucStep)){cDirTemp=LEFT;if(cDirTemp==GucMouseDir){cNBlock++;cX--;continue;}}cDirTemp=(cDirTemp+4-GucMouseDir)%4;/*計(jì)算方向偏移量*/if(cNBlock){mouseGoahead(cNBlock);/*前進(jìn)cNBlock步*/}cNBlock=0;/*任務(wù)清零*//*控制電腦鼠轉(zhuǎn)彎*/switch(cDirTemp){case1:mouseTurnright();break;case2:mouseTurnback();break;case3:mouseTurnleft();break;default:break;}}if(cNBlock){/*判斷任務(wù)是否完成，否則繼續(xù)前進(jìn)*/mouseGoahead(cNBlock);}}三、迷宮算法的研究（一）傳統(tǒng)算法我們把電腦鼠的迷宮算法分為兩個(gè)層次，迷宮搜索算法和迷宮最優(yōu)路徑算法。迷宮搜索算法的目的是在沒有預(yù)知迷宮路徑的情況下從起點(diǎn)迷宮格搜索到終點(diǎn)迷宮格，再從終點(diǎn)迷宮格搜索到起點(diǎn)迷宮格，好的搜索算法要求以更短的時(shí)間搜索到更多的迷宮格，所以要盡量避免重復(fù)搜索已經(jīng)搜索過的地方。迷宮最短路徑算法要求根據(jù)已知的迷宮信息找出一條從入口到出口的最優(yōu)路徑，最優(yōu)路徑不僅要短而且要求彎道盡量少。在很多地方容易得知常見的迷宮搜索算法有：1.右手法則:以右邊為優(yōu)先的前進(jìn)方向,然后是直線方向、左邊方向。2.左手法則:以左邊為優(yōu)先的前進(jìn)方向,然后是直線方向、右邊方向。3.中左法則:以直線為優(yōu)先的前進(jìn)方向,然后是左邊方向、右邊方向4.中右法則:以直線為優(yōu)先的前進(jìn)方向,然后是右邊方向、左邊方向5.亂數(shù)法則:取隨機(jī)值作為前進(jìn)方向。6.向心法則:遇有交叉時(shí),以指向迷宮中心的方向?yàn)閮?yōu)先的前進(jìn)方向。本人傾向于向心算法+中右法則，即當(dāng)遇有交叉時(shí),以指向迷宮中心的方向?yàn)閮?yōu)先的前進(jìn)方向。但是當(dāng)向中心方向的路沒有時(shí)，利用中右法則。以直線為優(yōu)先的前進(jìn)方向,然后是右邊方向、左邊方向。經(jīng)典的最優(yōu)路徑算法有：1、深度優(yōu)先搜索(DFS) 從入口出發(fā)，順著某一方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路退回(回溯)，換一個(gè)方向再繼續(xù)探索．直至所有可能的通路都探索到為止。如果恰好某一步探索到出口，則就找到了從入口到出口的路徑。為了保證在任何位置上都能沿原路退回，防止死循環(huán)，需要使用堆棧來保存大量記錄。而要求解迷宮最短路徑，則必須用深度優(yōu)先搜索出所有到達(dá)出口的路徑，通過比較得到最短距離的路徑．這樣也必然要求增加數(shù)據(jù)空間來保存搜索過程中當(dāng)前最短路徑．增加了空間復(fù)雜度。2、廣度優(yōu)先搜索(BFS)從入口出發(fā)，離開入口后依次訪問與當(dāng)前位置鄰接的單元格(上下左右方向)，然后分別從這些相鄰單元格出發(fā)依次訪問它們的鄰接格，并使“先被訪問的單元格的鄰接格‘先于’后被訪問的單元格的鄰接格”被訪問，直至訪問到迷宮出口，則找到了迷宮問題的最優(yōu)解，即迷宮最短路徑。該算法的顯著特點(diǎn)是“層層推進(jìn)”，探索點(diǎn)會(huì)隨著探索的深入急劇增加，相應(yīng)地，需要大量的空間用來保存探索過程的記錄。空間復(fù)雜度大。但是上述兩種算法都比較抽象復(fù)雜,編程時(shí)由于牽涉到回溯、遞歸等較復(fù)雜的算法，實(shí)現(xiàn)起來容易出現(xiàn)問題,非常容易出錯(cuò)，尤其牽涉到復(fù)雜數(shù)據(jù)結(jié)構(gòu)棧(深度優(yōu)先搜索)、隊(duì)列(廣度優(yōu)先搜索)的操作,調(diào)試跟蹤比較麻煩，所以本人不認(rèn)為是一種很好的方法。（二）適于實(shí)踐的算法在比賽中，采用計(jì)時(shí)的方法計(jì)算成績(jī)，本人認(rèn)為用以上傳統(tǒng)方法選擇最優(yōu)路徑，是十分費(fèi)時(shí)的，而且實(shí)現(xiàn)起來不是很簡(jiǎn)便。實(shí)現(xiàn)電腦鼠的快速確定最優(yōu)路徑的算法應(yīng)該利用向心算法+中右法則來回遍歷出一部分的迷宮，再利用等高法求出相對(duì)于已遍歷出的迷宮狀態(tài)的最短路徑，我們把這條路徑稱之為最優(yōu)路徑。首先用上文所說的搜索迷宮算法（向心算法+中右法則），走到終點(diǎn)，然后從以終點(diǎn)為起點(diǎn)，以上一次的起點(diǎn)為終點(diǎn)再次利用向心算法+中右法則的算法走回去。這兩次走的路最好滿足以前走過的在之后的一次遍歷中不再重復(fù)，為了實(shí)現(xiàn)這樣的要求，可以在第一次從起點(diǎn)到終點(diǎn)的遍歷中，在走過的迷宮格上加上flag，標(biāo)志已走過，從此電腦鼠只走沒有阻礙和沒有標(biāo)志迷宮格，當(dāng)沒有阻礙迷宮格都是標(biāo)志過的，那也只能走以前走的路了。就這樣利用搜索迷宮算法+迷宮格限制條件就可以快速遍歷一部分迷宮格，并記錄迷宮格的狀況。將迷宮格的狀態(tài)存入MazeShape[16][16]中，然后回到終點(diǎn)利用等高法確定最優(yōu)路徑。等高法介紹：假設(shè)迷宮狀態(tài)如圖6所示，其中（##）代表的單元格表示此處有阻礙（這些狀態(tài)來源是在上一節(jié)的MazeShape[16][16]更新中給出）。假設(shè)圖中A代表起點(diǎn)，B代表終點(diǎn)，按照下圖用等高法來確定最優(yōu)路徑：######A######B################

圖6我們從A點(diǎn)出發(fā)，以此為第一個(gè)擴(kuò)展節(jié)點(diǎn)，與該擴(kuò)展節(jié)點(diǎn)相鄰并且可達(dá)的方格成為可行節(jié)點(diǎn)被加入到活節(jié)點(diǎn)隊(duì)列中，并將這些方格標(biāo)志為1，即從起始方格A到這些方格距離為1；接著從活動(dòng)隊(duì)列中取出隊(duì)首節(jié)點(diǎn)作為下一個(gè)擴(kuò)展節(jié)點(diǎn)，并將與當(dāng)前擴(kuò)展節(jié)點(diǎn)相鄰且為標(biāo)志過的節(jié)點(diǎn)標(biāo)志位2，并存入活動(dòng)隊(duì)列中。這一過程一直繼續(xù)到算法搜索到目標(biāo)方格B或活節(jié)點(diǎn)隊(duì)列為空為止。將圖6標(biāo)志如下：32##21####1A1##212####B##234##8######5678######678 圖7易知到達(dá)終點(diǎn)B時(shí)，最短距離為9;則可選擇出最優(yōu)路徑如圖8：######A######B################ 圖8到此為止，我們就選擇出了一條最優(yōu)路徑，電腦鼠就可以按照這條最有路徑向終點(diǎn)沖刺了。代碼如下：voidmapStepEdit(int8cX,int8cY){uint8n=0;/*GmcStack[]下標(biāo)*/uint8ucStep=1;/*等高值*/uint8ucStat=0;/*統(tǒng)計(jì)可前進(jìn)的方向數(shù)*/uint8i,j;GmcStack[n].cX=cX;/*起點(diǎn)X值入棧*/GmcStack[n].cY=cY;/*起點(diǎn)Y值入棧*/n++;/*初始化各坐標(biāo)等高值*/for(i=0;i<MAZETYPE;i++){for(j=0;j<MAZETYPE;j++){GucMapStep[i][j]=0xff;}}/*制作等高圖，直到堆棧中所有數(shù)據(jù)處理完畢*/while(n){GucMapStep[cX][cY]=ucStep++;/*填入等高值*//*對(duì)當(dāng)前坐標(biāo)格里可前進(jìn)的方向統(tǒng)計(jì)*/ucStat=0;if((GucMapBlock[cX][cY]&0x01)&&(GucMapStep[cX][cY+1]>(ucStep))){/*前方有路前方等高值大于計(jì)劃設(shè)定值*/ucStat++;/*可前進(jìn)方向數(shù)加1*/}if((GucMapBlock[cX][cY]&0x02)&&(GucMapStep[cX+1][cY]>(ucStep)))/*右方有路,右方等高值大于計(jì)劃設(shè)定值,可前進(jìn)方向數(shù)加1*/ {ucStat++;}if((GucMapBlock[cX][cY]&0x04)&&(GucMapStep[cX][cY-1]>(ucStep))){ucStat++;}if((GucMapBlock[cX][cY]&0x08)&&(GucMapStep[cX-1][cY]>(ucStep))){ucStat++;}/*沒有可前進(jìn)的方向，則跳轉(zhuǎn)到最近保存的分支點(diǎn)否則任選可前進(jìn)方向前進(jìn)*/if(ucStat==0){n--;cX=GmcStack[n].cX;cY=GmcStack[n].cY;ucStep=GucMapStep[cX][cY];}else{if(ucStat>1){/*有多個(gè)可前進(jìn)方向，保存坐標(biāo)*/GmcStack[n].cX=cX;/*橫坐標(biāo)X值入棧*/GmcStack[n].cY=cY;/*縱坐標(biāo)Y值入棧*/n++;}/*任意選擇一條可前進(jìn)的方向前進(jìn)*/if((GucMapBlock[cX][cY]&0x01)&&(GucMapStep[cX][cY+1]>(ucStep)))/*前方有路,前方等高值大于計(jì)劃設(shè)定值,修改坐標(biāo)*/{cY++;continue;}if((GucMapBlock[cX][cY]&0x02)&&(GucMapStep[cX+1][cY]>(ucStep)))/*右方有路右方等高值大于計(jì)劃設(shè)定值修改坐標(biāo)*/{cX++;continue;}if((GucMapBlock[cX][cY]&0x04)&&(GucMapStep[cX][cY-1]>(ucStep)))/*后方有路后方等高值大于計(jì)劃設(shè)定值修改坐標(biāo)*/{cY--;continue;}if((GucMapBlock[cX][cY]&0x08)&&(GucMapStep[cX-1][cY]>(ucStep)))/*左方有路左方等高值大于計(jì)劃設(shè)定值修改坐標(biāo)*/{cX--;continue;}}}}這種等高圖算法也叫洪泛法求最短路徑法。其實(shí)這個(gè)最優(yōu)路徑并不是最短路徑，因?yàn)椴皇撬械拿詫m信息都被電腦鼠收集到，我們只是在電腦鼠收集到的已有信息中找出最優(yōu)的路徑。我認(rèn)為這樣的做法是可取的，因?yàn)殡娔X鼠如果想得到所有的迷宮格信息，必然要全部遍歷迷宮，但是這樣做太花時(shí)間了，要走很多重復(fù)的路，并且電腦鼠遍歷運(yùn)行的時(shí)間越長(zhǎng)，很難保證它的偏差足夠小，就越容易出現(xiàn)不穩(wěn)定現(xiàn)象。所以我認(rèn)為在電腦鼠速度足夠快的情況下，最短路徑和最優(yōu)路徑所花時(shí)間沒什么區(qū)別，但大大節(jié)省了遍歷的時(shí)間和系統(tǒng)算法的復(fù)雜度，同時(shí)降低了電腦鼠的不穩(wěn)定性。 制作完等高圖，就要用等高圖作為最優(yōu)路徑選擇的基礎(chǔ)，以存儲(chǔ)在數(shù)組里面的等高值作為參照，以上面的思想作為依據(jù)開始讓電腦屬自主選擇路徑。（三）基于迷宮范圍已知時(shí)比賽的算法在網(wǎng)上我曾看見過一個(gè)臺(tái)灣的電腦鼠競(jìng)賽獲獎(jiǎng)的視頻，視頻里的電腦鼠跑得異?？欤⑶倚≤囈婚_始就好像就“認(rèn)識(shí)”路似的，直接就選擇了最優(yōu)的路徑，關(guān)于小車跑得快，可能是因?yàn)殡娔X鼠硬件過得去，電機(jī)驅(qū)動(dòng)和控制，轉(zhuǎn)彎算法調(diào)整得好。但是電腦鼠的路徑規(guī)劃給我很大的啟發(fā)。因?yàn)镮EEE電腦鼠競(jìng)賽是已知比賽迷宮圖的，盡管有很多張，我個(gè)人認(rèn)為光就比賽來說，我們可以用如下的方法，把電腦鼠對(duì)應(yīng)每個(gè)迷宮的最優(yōu)路徑存進(jìn)去（對(duì)于基于Cortex-M3內(nèi)核LM3S615來說，這點(diǎn)開銷是完全可以承受的）。例如2010年天津賽區(qū)的IEEE電腦鼠競(jìng)賽之前有九張圖，我們?cè)诖撕?jiǎn)單的取出兩個(gè)迷宮來說明：圖9比賽用的一二號(hào)迷宮圖我們可以讓電腦鼠先走一段迷宮探測(cè)迷宮開始的狀態(tài)，如圖一號(hào)迷宮在（0,4）處有出口，而二號(hào)迷宮在（0,2）處有出口，我們?cè)诒荣愔芯涂梢栽O(shè)置這樣的算法：小車開始出發(fā)如果探測(cè)到（0,2）格處有出口，我們立刻執(zhí)行存在微控制器中的2號(hào)路徑。否則執(zhí)行1號(hào)路徑。當(dāng)有很多迷宮圖時(shí)，基本思想一樣，就是先走一段路，當(dāng)電腦鼠徹底區(qū)分現(xiàn)在行走的到底是哪個(gè)迷宮時(shí)，用switch開關(guān)來控制選擇的最短路徑。雖然這種算法能很快的是電腦鼠到達(dá)終點(diǎn)，取得成績(jī)，但是這樣的算法只適用于比賽，卻沒有什么研究的價(jià)值。四、進(jìn)入死區(qū)的人工智能決策在比賽參觀了一次天津賽區(qū)的電腦鼠比賽中，我發(fā)現(xiàn)有些代表隊(duì)電腦鼠在行進(jìn)中狀態(tài)不好（路線不再迷宮跑道中間、行進(jìn)方向有偏差），常常會(huì)出現(xiàn)電腦鼠進(jìn)入一個(gè)死區(qū)（如圖10），首先左邊的傳感器探測(cè)到阻礙，于是電腦鼠右轉(zhuǎn)；但是右轉(zhuǎn)一定角度后右邊的傳感器也探測(cè)到阻礙，于是電腦鼠再左轉(zhuǎn)；左轉(zhuǎn)后右邊的傳感器又會(huì)探測(cè)到阻礙……此時(shí)電腦鼠就會(huì)困在墻角里出不來，選手被迫重新返回起點(diǎn)繼續(xù)開始，這樣會(huì)十分影響成績(jī)。其實(shí)遇到這種情況，我們是有辦法讓電腦鼠走出死區(qū)的。圖10方法是在程序運(yùn)行中，記下傳感器交替探測(cè)到阻礙的次數(shù)。并且關(guān)鍵是程序必須記住每一次探測(cè)到阻礙時(shí)前一次的探測(cè)狀態(tài)，并和當(dāng)前的探測(cè)狀態(tài)對(duì)比。如果狀態(tài)相反，就在交替總數(shù)上加1。如果這個(gè)交替總數(shù)的值大于程序中預(yù)先給定的閥值，那么就應(yīng)該令電腦鼠做一個(gè)向后轉(zhuǎn)的‘U’形彎。并且把交替計(jì)算器復(fù)位。圖10下面的圖11即為死區(qū)人工智能決策的流程圖，容易知道該決策的代碼實(shí)現(xiàn)其實(shí)也很簡(jiǎn)單，但是就是難在如何將該進(jìn)程融合在整個(gè)系統(tǒng)中來實(shí)現(xiàn)，我們可以用中斷前后臺(tái)來實(shí)現(xiàn)，也可以用引入操作系統(tǒng)，用進(jìn)程之間通信來實(shí)現(xiàn)。 圖11While(1){ if(兩個(gè)傳感器探測(cè)狀態(tài)不相同){ if(兩個(gè)傳感器探測(cè)狀態(tài)均不和原來自己的狀態(tài)相同){ Count加1；//交替次數(shù)加1 更新兩個(gè)傳感器自身old狀態(tài)為現(xiàn)在狀態(tài)； if(Count達(dá)到閥值){ Count復(fù)位為1； 執(zhí)行‘U’形轉(zhuǎn)彎；}}else//存在一個(gè)傳感器狀態(tài)不變，證明不存在交替了 count=1;} if(左右均有阻礙)then后轉(zhuǎn)； elseif(均無阻礙)then直走； elseif(狀態(tài)不同，上面判斷不是死區(qū)時(shí)，左邊沒有阻礙時(shí)) then左轉(zhuǎn) else//狀態(tài)不同，上面判斷不是死區(qū)時(shí)，右邊沒有阻礙時(shí) then右轉(zhuǎn)}本算法只適用于逃離死區(qū)，具體電腦鼠執(zhí)行算法很復(fù)雜，編寫代碼時(shí)想要加入這一功能時(shí)，可以參考這一算法。使用這一算法，可以實(shí)現(xiàn)人工智能決策，使電腦鼠能成功的逃離死區(qū)。五、算法的實(shí)現(xiàn)（一）、無操作系統(tǒng)的前后臺(tái)實(shí)現(xiàn)其實(shí)大多電腦鼠的操作都是基于無操作系統(tǒng)來實(shí)現(xiàn)的，簡(jiǎn)單地說就是軟件前后臺(tái)實(shí)現(xiàn)的關(guān)系，一個(gè)主函數(shù)和幾個(gè)中斷來實(shí)現(xiàn)電腦鼠的運(yùn)作，在周立功提供的源代碼里面，已經(jīng)有詳細(xì)的主函數(shù)與定時(shí)器中斷的關(guān)系。關(guān)于主函數(shù)：主函數(shù)執(zhí)行先走一步，然后用MazeSearch()函數(shù)在摸索中前進(jìn)，MazeSearch()提供墻壁信息之后電腦鼠繼續(xù)走。關(guān)于中斷服務(wù)序：其中的一部分有關(guān)于電機(jī)驅(qū)動(dòng)程序是這樣運(yùn)行的，首先初始程序設(shè)置定時(shí)器定時(shí)時(shí)間，定時(shí)時(shí)間到，定時(shí)器觸發(fā)中斷服務(wù)子程序，通過輸入驅(qū)動(dòng)步進(jìn)電機(jī)的時(shí)序狀態(tài)、步進(jìn)電機(jī)運(yùn)動(dòng)的方向來調(diào)節(jié)驅(qū)動(dòng)步進(jìn)電機(jī)的時(shí)序狀態(tài)和步進(jìn)電機(jī)運(yùn)動(dòng)的方向；所以在這里關(guān)鍵是定時(shí)時(shí)間的設(shè)定，在上面底層算法中已經(jīng)介紹了電機(jī)控制的方法，易知可以查表GuiAccelTable[GmLeft.iSpeed]來執(zhí)行TimerLoadSet(..)函數(shù)，GuiAccelTable關(guān)于表的計(jì)算在上面已經(jīng)詳細(xì)介紹。同理，傳感器驅(qū)動(dòng)也是如此，這里就不再介紹了，按照源碼改進(jìn)，我們是可以實(shí)現(xiàn)前后臺(tái)、無操作系統(tǒng)的電腦鼠正常運(yùn)行的。但是這樣，我們就是將ARM體系的處理器當(dāng)成準(zhǔn)單片機(jī)使用，有些大材小用，只能編出一些簡(jiǎn)單的電腦鼠軟件，因?yàn)闆]有操作系統(tǒng)，當(dāng)代碼的功能加強(qiáng)時(shí)，代碼的編寫難度會(huì)變得很大，比如上文我們提到的數(shù)字PID模型的決策算法。我們想利用時(shí)雖然可以將代碼嵌在中斷中，但是無疑加大了代碼的難度，并且代碼執(zhí)行的實(shí)時(shí)性不能保證，因?yàn)閿?shù)字PID算法的決策算法當(dāng)電腦鼠在直行過程中就要立即被調(diào)用，不然不能及時(shí)的調(diào)整電腦鼠的狀態(tài)，后果會(huì)出乎意料，這種多進(jìn)程的軟件實(shí)現(xiàn)最好是利用操作系統(tǒng)來輔助實(shí)現(xiàn)。（二）、基于μC/OS-Ⅱ多進(jìn)程的軟件設(shè)計(jì)一種好的電腦鼠軟件設(shè)計(jì)非常復(fù)雜，若像上文采用傳統(tǒng)的前后臺(tái)模式來管理程序會(huì)導(dǎo)致很大的開發(fā)難度，且程序不易修改。因此我們考慮在LM3S615上移植μC/OS-Ⅱ。作為一種嵌入式實(shí)時(shí)操作系統(tǒng)，μC/OS-Ⅱ提供了很多系統(tǒng)服務(wù)，例如信號(hào)量、互斥型信號(hào)量、事件標(biāo)志、消息郵箱、消息隊(duì)列、塊大小固定的內(nèi)存申請(qǐng)與釋放及時(shí)間管理等，基于RTOS編程，不僅使系統(tǒng)的實(shí)時(shí)性