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

IEEE電腦鼠路徑選擇及死區(qū)決策一、引言（一）IEEE電腦鼠走迷宮競賽背景嵌入式系統(tǒng)融合了微電子、計算機(jī)軟\硬件、通信和電子工程等多種技術(shù)，廣泛應(yīng)用于航空、航天、儀器儀表、工業(yè)控制和3C（Computer、Communication、Consumer）等領(lǐng)域，是科技集成創(chuàng)新的主要手段。為了培養(yǎng)科技創(chuàng)性意識和動手能力，全國各地在近幾年紛紛舉辦“電腦鼠走迷宮“邀請賽。電腦鼠英文名叫做MicroMouse，是使用嵌入式微控制器、傳感器和機(jī)電運(yùn)動部件構(gòu)成的一種智能行走裝置（微型機(jī)器人）。電腦鼠要在指定的迷宮中比賽，在迷宮中探索以找出通往終點(diǎn)的路徑，并隨時掌握自身的位置信息，準(zhǔn)確獲取墻壁信息并做記錄，最終依靠記憶找出走出迷宮的最佳路徑，以最短的時間解開迷宮，贏得比賽。國際電工和電子工程學(xué)會（IEEE）每年都要舉辦一次國際性的電腦鼠走迷宮競賽，自舉辦以來參加國踴躍，為此許多大學(xué)還開設(shè)了“電腦鼠原理和制作”選修課程。2007年和2008年，上海市計算機(jī)學(xué)會率先在國內(nèi)主辦了兩次IEEE標(biāo)準(zhǔn)電腦鼠走迷宮邀請賽（長三角地區(qū)），有三十多所院校參加。2009年廣州致遠(yuǎn)電子有限公司贊助了全國“IEEE標(biāo)準(zhǔn)電腦鼠走迷宮”邀請賽，共邀請全國9個賽區(qū)的52所高校參賽，反響強(qiáng)烈。圖1所示為電腦鼠圖2所示為比賽迷宮 本文主要以MicroMouse615為平臺，介紹電腦鼠參賽的實(shí)現(xiàn)，對有些方面的基本算法提出改進(jìn)，并在此基礎(chǔ)上加上了一些自己的算法思想，比如說：用數(shù)學(xué)模型的方法提出了用改進(jìn)后的數(shù)字PID算法對行進(jìn)中的電腦鼠進(jìn)行狀態(tài)調(diào)整，進(jìn)入死區(qū)的電腦鼠的人工智能決策，參賽時迷宮搜索的易于實(shí)現(xiàn)的算法以及植入操作系統(tǒng)的思想。（二）競賽平臺簡介MicroMouse615平臺包含了微控制器、電機(jī)、紅外線傳感器、控制平臺。其中最重要的微控制器是LM3S615微控制器，如下圖3為LM3S615的系統(tǒng)結(jié)構(gòu)圖。其中內(nèi)核用的是ARMCortex-M3,外圍還有存儲器、系統(tǒng)時鐘、定時器、輸入輸出端口、數(shù)模轉(zhuǎn)換器等等。ARMCortex-M3處理器為高性能、低成本的平臺提供了一個能夠滿足小存儲要求解決方案、簡化管腳數(shù)、以及低功耗三方面要求的內(nèi)核，與此同時，它還提供了出色的計算性能和優(yōu)越的系統(tǒng)中斷響應(yīng)能力。其特性如下：1、緊湊的內(nèi)核2、Thumb-2指令集，在與8位和16位器件相關(guān)的存儲容量中，特別是在微控制器級應(yīng)用的幾千字節(jié)存儲量中，提供了ARM內(nèi)核所期望的高性能。3、優(yōu)越的中斷處理能力，通過執(zhí)行寄存器操作來實(shí)現(xiàn)，這些寄存器操作在處理硬件中斷時使用。4、存儲器保護(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)于各個部件的接線圖如圖3，關(guān)于系統(tǒng)編程尤為重要；編程時主要注意引腳的鏈接和存儲器的地址映射等。在具體嵌入式編程方面，可以參照LM3S651微控制器數(shù)據(jù)手冊，其中提供了存儲器、串并口通信時序等全部信息。電機(jī)使用的是BA6845FS，它是步進(jìn)電機(jī)，最大輸出電流為1.0A。邏輯輸入允許三種輸出模式：前進(jìn)、反轉(zhuǎn)和節(jié)電模式。集成電路具有低輸出飽和電壓，能以低電壓驅(qū)動電機(jī)。紅外傳感器使用的型號是IRM-8601S，該設(shè)備是一種小型紅外遙控器系統(tǒng)接收器，開發(fā)和設(shè)計利用最新IC技術(shù).PIN二極管前置放大器是組裝和引線框架，環(huán)氧包裝被設(shè)計成一個IR過濾器.解調(diào)輸出信號可直接由微處理器解碼?？刂婆_是使用ZLG7289B，ZLG7289B是廣州周立功單片機(jī)發(fā)展有限公司自行設(shè)計的數(shù)碼管顯示驅(qū)動及鍵盤掃描管理芯片，可直接驅(qū)動8位共陰式數(shù)碼管（或64只獨(dú)立LED），同時還可以掃描管理多達(dá)64只按鍵。ZLG7289B內(nèi)部含有顯示譯碼器，可直接接受BCD碼或16進(jìn)制碼，并同時具有2種譯碼方式。此外，還具有多種控制指令，如消隱﹑閃爍﹑左移﹑右移﹑段尋址等。ZLG7289B采用SPI串行總線與微控制器接口，僅占用少數(shù)幾根I/O口線。利用片選信號，多片ZLG7289B還可以并接在一起使用，能夠方便地實(shí)現(xiàn)多于8位的顯示或多于64只按鍵的應(yīng)用。ZLG7289B可廣泛地應(yīng)用于儀器儀表，工業(yè)控制器，條形顯示器，控制面板等領(lǐng)域。二、實(shí)時狀態(tài)采集及更新方法要想使電腦鼠具備智能選路的本領(lǐng)，必須使其具備記憶迷宮信息的能力，并且電腦鼠還需記憶當(dāng)前所在迷宮格和前進(jìn)方向的信息，這些信息將隨著電腦鼠在迷宮格中行走而不斷被刷新。用CurDir存儲當(dāng)前方向，用CurPosition[1][1]存儲當(dāng)前坐標(biāo)，用MazeShape[16][16]存儲每個迷宮格的形狀，用CurWall存儲當(dāng)前傳感器采集到迷宮格墻壁情況。信息采集算法的核心是確定何時刷新信息以及輸入?yún)?shù)。為此用三張表格來表示這三個刷新邏輯。當(dāng)迷宮是以類似于如圖5建立座標(biāo)時： 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)完時的小車位置，且用于非連續(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)完時的小車位置，且用于非連續(xù)轉(zhuǎn)彎。表3MazeShape[16][16]更新方法原始狀態(tài)參數(shù)N(X,Y)S(X,Y)W(X,Y)CurWallCurWallCurWallE(X,Y)CurWallMazeShape更新CurWall直接CurWallCurWall賦給順時針轉(zhuǎn)180°順時針轉(zhuǎn)90°MazeShape賦給MazeShape賦給MazeShape[x][y][x][y][x][y]CurWall逆時針轉(zhuǎn)90°賦給MazeShape[x][y]需要注意的是由上述三個刷新邏輯表可知，WallShape需要CurPosition作為參數(shù)，而CurPosition需要CurDir作為輸入?yún)?shù)來更新自身。因此當(dāng)需要同時刷新三個變量的兩個或三個時，應(yīng)先刷新CurDir再刷新CurPosition最后刷新WallShape。收集完迷宮狀態(tài)之后，就是怎么進(jìn)行電腦鼠的行進(jìn)過程，我們參考迷宮的整體狀態(tài)，可以設(shè)計程序如下：（其中等高法在下面介紹）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á)到目的地*/while((cX!=x)||(cY!=y)){ucStep=GucMapStep[cX][cY];/*任選一個等高值比當(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)一個方格*/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;/*計算方向偏移量*/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)算法我們把電腦鼠的迷宮算法分為兩個層次，迷宮搜索算法和迷宮最優(yōu)路徑算法。迷宮搜索算法的目的是在沒有預(yù)知迷宮路徑的情況下從起點(diǎn)迷宮格搜索到終點(diǎn)迷宮格，再從終點(diǎn)迷宮格搜索到起點(diǎn)迷宮格，好的搜索算法要求以更短的時間搜索到更多的迷宮格，所以要盡量避免重復(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.向心法則:遇有交叉時,以指向迷宮中心的方向?yàn)閮?yōu)先的前進(jìn)方向。本人傾向于向心算法+中右法則，即當(dāng)遇有交叉時,以指向迷宮中心的方向?yàn)閮?yōu)先的前進(jìn)方向。但是當(dāng)向中心方向的路沒有時，利用中右法則。以直線為優(yōu)先的前進(jìn)方向,然后是右邊方向、左邊方向。經(jīng)典的最優(yōu)路徑算法有：1、深度優(yōu)先搜索(DFS) 從入口出發(fā)，順著某一方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路退回(回溯)，換一個方向再繼續(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)會隨著探索的深入急劇增加，相應(yīng)地，需要大量的空間用來保存探索過程的記錄。空間復(fù)雜度大。但是上述兩種算法都比較抽象復(fù)雜,編程時由于牽涉到回溯、遞歸等較復(fù)雜的算法，實(shí)現(xiàn)起來容易出現(xiàn)問題,非常容易出錯，尤其牽涉到復(fù)雜數(shù)據(jù)結(jié)構(gòu)棧(深度優(yōu)先搜索)、隊列(廣度優(yōu)先搜索)的操作,調(diào)試跟蹤比較麻煩，所以本人不認(rèn)為是一種很好的方法。（二）適于實(shí)踐的算法在比賽中，采用計時的方法計算成績，本人認(rèn)為用以上傳統(tǒng)方法選擇最優(yōu)路徑，是十分費(fèi)時的，而且實(shí)現(xiàn)起來不是很簡便。實(shí)現(xiàn)電腦鼠的快速確定最優(yōu)路徑的算法應(yīng)該利用向心算法+中右法則來回遍歷出一部分的迷宮，再利用等高法求出相對于已遍歷出的迷宮狀態(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ā)，以此為第一個擴(kuò)展節(jié)點(diǎn)，與該擴(kuò)展節(jié)點(diǎn)相鄰并且可達(dá)的方格成為可行節(jié)點(diǎn)被加入到活節(jié)點(diǎn)隊列中，并將這些方格標(biāo)志為1，即從起始方格A到這些方格距離為1；接著從活動隊列中取出隊首節(jié)點(diǎn)作為下一個擴(kuò)展節(jié)點(diǎn)，并將與當(dāng)前擴(kuò)展節(jié)點(diǎn)相鄰且為標(biāo)志過的節(jié)點(diǎn)標(biāo)志位2，并存入活動隊列中。這一過程一直繼續(xù)到算法搜索到目標(biāo)方格B或活節(jié)點(diǎn)隊列為空為止。將圖6標(biāo)志如下：32##21####1A1##212####B##234##8######5678######678 圖7易知到達(dá)終點(diǎn)B時，最短距離為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ì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++;/*填入等高值*//*對當(dāng)前坐標(biāo)格里可前進(jìn)的方向統(tǒng)計*/ucStat=0;if((GucMapBlock[cX][cY]&0x01)&&(GucMapStep[cX][cY+1]>(ucStep))){/*前方有路前方等高值大于計劃設(shè)定值*/ucStat++;/*可前進(jìn)方向數(shù)加1*/}if((GucMapBlock[cX][cY]&0x02)&&(GucMapStep[cX+1][cY]>(ucStep)))/*右方有路,右方等高值大于計劃設(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){/*有多個可前進(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)))/*前方有路,前方等高值大于計劃設(shè)定值,修改坐標(biāo)*/{cY++;continue;}if((GucMapBlock[cX][cY]&0x02)&&(GucMapStep[cX+1][cY]>(ucStep)))/*右方有路右方等高值大于計劃設(shè)定值修改坐標(biāo)*/{cX++;continue;}if((GucMapBlock[cX][cY]&0x04)&&(GucMapStep[cX][cY-1]>(ucStep)))/*后方有路后方等高值大于計劃設(shè)定值修改坐標(biāo)*/{cY--;continue;}if((GucMapBlock[cX][cY]&0x08)&&(GucMapStep[cX-1][cY]>(ucStep)))/*左方有路左方等高值大于計劃設(shè)定值修改坐標(biāo)*/{cX--;continue;}}}}這種等高圖算法也叫洪泛法求最短路徑法。其實(shí)這個最優(yōu)路徑并不是最短路徑，因?yàn)椴皇撬械拿詫m信息都被電腦鼠收集到，我們只是在電腦鼠收集到的已有信息中找出最優(yōu)的路徑。我認(rèn)為這樣的做法是可取的，因?yàn)殡娔X鼠如果想得到所有的迷宮格信息，必然要全部遍歷迷宮，但是這樣做太花時間了，要走很多重復(fù)的路，并且電腦鼠遍歷運(yùn)行的時間越長，很難保證它的偏差足夠小，就越容易出現(xiàn)不穩(wěn)定現(xiàn)象。所以我認(rèn)為在電腦鼠速度足夠快的情況下，最短路徑和最優(yōu)路徑所花時間沒什么區(qū)別，但大大節(jié)省了遍歷的時間和系統(tǒng)算法的復(fù)雜度，同時降低了電腦鼠的不穩(wěn)定性。 制作完等高圖，就要用等高圖作為最優(yōu)路徑選擇的基礎(chǔ)，以存儲在數(shù)組里面的等高值作為參照，以上面的思想作為依據(jù)開始讓電腦屬自主選擇路徑。（三）基于迷宮范圍已知時比賽的算法在網(wǎng)上我曾看見過一個臺灣的電腦鼠競賽獲獎的視頻，視頻里的電腦鼠跑得異常快，并且小車一開始就好像就“認(rèn)識”路似的，直接就選擇了最優(yōu)的路徑，關(guān)于小車跑得快，可能是因?yàn)殡娔X鼠硬件過得去，電機(jī)驅(qū)動和控制，轉(zhuǎn)彎算法調(diào)整得好。但是電腦鼠的路徑規(guī)劃給我很大的啟發(fā)。因?yàn)镮EEE電腦鼠競賽是已知比賽迷宮圖的，盡管有很多張，我個人認(rèn)為光就比賽來說，我們可以用如下的方法，把電腦鼠對應(yīng)每個迷宮的最優(yōu)路徑存進(jìn)去（對于基于Cortex-M3內(nèi)核LM3S615來說，這點(diǎn)開銷是完全可以承受的）。例如2010年天津賽區(qū)的IEEE電腦鼠競賽之前有九張圖，我們在此簡單的取出兩個迷宮來說明：圖9比賽用的一二號迷宮圖我們可以讓電腦鼠先走一段迷宮探測迷宮開始的狀態(tài)，如圖一號迷宮在（0,4）處有出口，而二號迷宮在（0,2）處有出口，我們在比賽中就可以設(shè)置這樣的算法：小車開始出發(fā)如果探測到（0,2）格處有出口，我們立刻執(zhí)行存在微控制器中的2號路徑。否則執(zhí)行1號路徑。當(dāng)有很多迷宮圖時，基本思想一樣，就是先走一段路，當(dāng)電腦鼠徹底區(qū)分現(xiàn)在行走的到底是哪個迷宮時，用switch開關(guān)來控制選擇的最短路徑。雖然這種算法能很快的是電腦鼠到達(dá)終點(diǎn)，取得成績，但是這樣的算法只適用于比賽，卻沒有什么研究的價值。四、進(jìn)入死區(qū)的人工智能決策在比賽參觀了一次天津賽區(qū)的電腦鼠比賽中，我發(fā)現(xiàn)有些代表隊電腦鼠在行進(jìn)中狀態(tài)不好（路線不再迷宮跑道中間、行進(jìn)方向有偏差），常常會出現(xiàn)電腦鼠進(jìn)入一個死區(qū)（如圖10），首先左邊的傳感器探測到阻礙，于是電腦鼠右轉(zhuǎn)；但是右轉(zhuǎn)一定角度后右邊的傳感器也探測到阻礙，于是電腦鼠再左轉(zhuǎn)；左轉(zhuǎn)后右邊的傳感器又會探測到阻礙……此時電腦鼠就會困在墻角里出不來，選手被迫重新返回起點(diǎn)繼續(xù)開始，這樣會十分影響成績。其實(shí)遇到這種情況，我們是有辦法讓電腦鼠走出死區(qū)的。圖10方法是在程序運(yùn)行中，記下傳感器交替探測到阻礙的次數(shù)。并且關(guān)鍵是程序必須記住每一次探測到阻礙時前一次的探測狀態(tài)，并和當(dāng)前的探測狀態(tài)對比。如果狀態(tài)相反，就在交替總數(shù)上加1。如果這個交替總數(shù)的值大于程序中預(yù)先給定的閥值，那么就應(yīng)該令電腦鼠做一個向后轉(zhuǎn)的‘U’形彎。并且把交替計算器復(fù)位。圖10下面的圖11即為死區(qū)人工智能決策的流程圖，容易知道該決策的代碼實(shí)現(xiàn)其實(shí)也很簡單，但是就是難在如何將該進(jìn)程融合在整個系統(tǒng)中來實(shí)現(xiàn)，我們可以用中斷前后臺來實(shí)現(xiàn)，也可以用引入操作系統(tǒng)，用進(jìn)程之間通信來實(shí)現(xiàn)。 圖11While(1){ if(兩個傳感器探測狀態(tài)不相同){ if(兩個傳感器探測狀態(tài)均不和原來自己的狀態(tài)相同){ Count加1；//交替次數(shù)加1 更新兩個傳感器自身old狀態(tài)為現(xiàn)在狀態(tài)； if(Count達(dá)到閥值){ Count復(fù)位為1； 執(zhí)行‘U’形轉(zhuǎn)彎；}}else//存在一個傳感器狀態(tài)不變，證明不存在交替了 count=1;} if(左右均有阻礙)then后轉(zhuǎn)； elseif(均無阻礙)then直走； elseif(狀態(tài)不同，上面判斷不是死區(qū)時，左邊沒有阻礙時) then左轉(zhuǎn) else//狀態(tài)不同，上面判斷不是死區(qū)時，右邊沒有阻礙時 then右轉(zhuǎn)}本算法只適用于逃離死區(qū)，具體電腦鼠執(zhí)行算法很復(fù)雜，編寫代碼時想要加入這一功能時，可以參考這一算法。使用這一算法，可以實(shí)現(xiàn)人工智能決策，使電腦鼠能成功的逃離死區(qū)。五、算法的實(shí)現(xiàn)（一）、無操作系統(tǒng)的前后臺實(shí)現(xiàn)其實(shí)大多電腦鼠的操作都是基于無操作系統(tǒng)來實(shí)現(xiàn)的，簡單地說就是軟件前后臺實(shí)現(xiàn)的關(guān)系，一個主函數(shù)和幾個中斷來實(shí)現(xiàn)電腦鼠的運(yùn)作，在周立功提供的源代碼里面，已經(jīng)有詳細(xì)的主函數(shù)與定時器中斷的關(guān)系。關(guān)于主函數(shù)：主函數(shù)執(zhí)行先走一步，然后用MazeSearch()函數(shù)在摸索中前進(jìn)，MazeSearch()提供墻壁信息之后電腦鼠繼續(xù)走。關(guān)于中斷服務(wù)序：其中的一部分有關(guān)于電機(jī)驅(qū)動程序是這樣運(yùn)行的，首先初始程序設(shè)置定時器定時時間，定時時間到，定時器觸發(fā)中斷服務(wù)子程序，通過輸入驅(qū)動步進(jìn)電機(jī)的時序狀態(tài)、步進(jìn)電機(jī)運(yùn)動的方向來調(diào)節(jié)驅(qū)動步進(jìn)電機(jī)的時序狀態(tài)和步進(jìn)電機(jī)運(yùn)動的方向；所以在這里關(guān)鍵是定時時間的設(shè)定，在上面底層算法中已經(jīng)介紹了電機(jī)控制的方法，易知可以查表GuiAccelTable[GmLeft.iSpeed]來執(zhí)行TimerLoadSet(..)函數(shù)，GuiAccelTable關(guān)于表的計算在上面已經(jīng)詳細(xì)介紹。同理，傳感器驅(qū)動也是如此，這里就不再介紹了，按照源碼改進(jìn)，我們是可以實(shí)現(xiàn)前后臺、無操作系統(tǒng)的電腦鼠正常運(yùn)行的。但是這樣，我們就是將ARM體系的處理器當(dāng)成準(zhǔn)單片機(jī)使用，有些大材小用，只能編出一些簡單的電腦鼠軟件，因?yàn)闆]有操作系統(tǒng)，當(dāng)代碼的功能加強(qiáng)時，代碼的編寫難度會變得很大，比如上文我們提到的數(shù)字PID模型的決策算法。我們想利用時雖然可以將代碼嵌在中斷中，但是無疑加大了代碼的難度，并且代碼執(zhí)行的實(shí)時性不能保證，因?yàn)閿?shù)字PID算法的決策算法當(dāng)電腦鼠在直行過程中就要立即被調(diào)用，不然不能及時的調(diào)整電腦鼠的狀態(tài)，后果會出乎意料，這種多進(jìn)程的軟件實(shí)現(xiàn)最好是利用操作系統(tǒng)來輔助實(shí)現(xiàn)。（二）、基于μC/OS-Ⅱ多進(jìn)程的軟件設(shè)計一種好的電腦鼠軟件設(shè)計非常復(fù)雜，若像上文采用傳統(tǒng)的前后臺模式來管理程序會導(dǎo)致很大的開發(fā)難度，且程序不易修改。因此我們考慮在LM3S615上移植μC/OS-Ⅱ。作為一種嵌入式實(shí)時操作系統(tǒng)，μC/OS-Ⅱ提供了很多系統(tǒng)服務(wù)，例如信號量、互斥型信號量、事件標(biāo)志、消息郵箱、消息隊列、塊大小固定的內(nèi)存申請與釋放及時間管理等，基于RTOS編程，不僅使系統(tǒng)的實(shí)時性