一種電腦鼠走迷宮的算法.doc

一種電腦鼠走迷宮的算法電腦鼠的英文名稱為Micromouse，實際上是一個由微處理器控制的，集感知、判斷、行走功能于一體，能夠自動尋找最佳路徑到達目的地的小型機器人。它可以在“迷宮”中自動感知并記憶迷宮地圖，通過一定的算法，尋找一條最佳路徑，以最快的速度到達目的地。1997年，在美國舉辦了第一屆電腦鼠競賽，隨后，電腦鼠競賽傳入歐洲，首屆歐洲電腦鼠競賽于1980年在倫敦舉辦，之后英國的電腦鼠比賽便由電子工程協(xié)會（IEE）主辦。1980年11月日本電腦鼠協(xié)會（JMA）在東京舉辦了第一屆競賽，此后，日本每年都要舉辦一屆電腦鼠競賽。我國臺灣也于1986年10月舉辦了首屆電腦鼠比賽?，F(xiàn)在國際電工和電子工程學(xué)會（IEEE）每年都要舉辦一次國際性的電腦鼠走迷宮競賽，各國選手報名踴躍，主要是大學(xué)生，為此部分大學(xué)還開設(shè)了“電腦鼠原理和制作”選修課程。由于電腦鼠要由參賽選手自己設(shè)計制作，不僅要求選手具有嵌入式系統(tǒng)應(yīng)用傳感器控制技術(shù)等多方面的知識、經(jīng)驗和實踐能力，還要求具有編寫尋找最佳路徑算法的能力。由于迷宮路徑設(shè)置是隨機的，因而競賽難度較大，極富挑戰(zhàn)性。這對培養(yǎng)和提高學(xué)生的創(chuàng)新精神和實踐能力，有著深遠的意義。2007年5月 8月將舉辦由我國部分地區(qū)（上海及長三角地區(qū)）參加的首屆電腦鼠邀請賽。1 電腦鼠走迷宮的規(guī)則有關(guān)電腦鼠國際比賽的詳細規(guī)則，可參閱國際電工和電子工程學(xué)會（IEEE）的官方網(wǎng)站：/sc2006/2006MicromouseRules.pdf 。迷宮的規(guī)格迷宮由256個方塊（單元）組成，每個方塊的大小為18厘米見方，排成16行16列。迷宮的隔墻板沿方塊的四周布設(shè)，形成迷宮通道。隔墻板高5厘米厚1.2厘米，因此迷宮通道的實際寬度是16.8厘米。隔墻板的兩個側(cè)面是白色的，頂部是紅色的。迷宮的地板由木質(zhì)材料做成，涂上沒有反光的黑漆。隔墻板的側(cè)面和頂部對紅外線有反射特性，而地板則對紅外線有吸收特性。競賽起始點可設(shè)在迷宮的任何一角，其三面要有隔墻；競賽的終點設(shè)在迷宮的中央，有四個方塊那么大小。圖一為一個實際的電腦鼠競賽用的迷宮照片。圖一 電腦鼠競賽用的迷宮照片1.2 電腦鼠的規(guī)格電腦鼠要求由參賽者自制，使用電源為能源，不能使用其它可燃物為能源。電腦鼠結(jié)構(gòu)高出隔墻部分的長寬幾何尺寸應(yīng)不大于2525厘米，對高度沒有限制。一個完整的電腦鼠應(yīng)包含有機身、電源、傳感器、微處理器、馬達及驅(qū)動等部分。電腦鼠的傳感器可分為三組，分別用來感知前、左、右三個方向是否已靠近宮壁，并將所獲得信息傳送給微處理器進行處理。微處理器要完成多種信息的處理，如路徑、迷宮地圖、行走距離、馬達控制等，并要能夠作出判斷。在馬達的控制下，電腦鼠能夠完成直行、轉(zhuǎn)彎、掉頭以及加減速等動作。通常采用左右獨立的馬達驅(qū)動和控制，以使微處理器的控制更加靈活。圖二為一個實際參加競賽的電腦鼠樣例照片。圖二 電腦鼠樣例照片。1.3 競賽的規(guī)則電腦鼠的基本功能是從起點開始走到終點，這個過程稱為一次“運行”，所花費的時間稱為“運行時間”。從終點回到起點所花費的時間不計算在運行時間內(nèi)。電腦鼠從第一次激活到每次運行開始，所花費的時間稱為“迷宮時間”。如果電腦鼠在比賽時需要手動輔助，這個動作稱為“碰觸”。競賽使用這三個參數(shù)，即運行時間迷宮時間和碰觸，從速度求解迷宮的效率和電腦鼠可靠性三個方面來進行評分。電腦鼠的得分是通過計算每次運行的“排障時間”來衡量的。所謂排障時間是這樣計算的：先將迷宮時間的1/30加上一次運行時間，如果這次運行結(jié)束以后電腦鼠沒有被碰觸過，那么還要再減去10秒的獎勵時間，這樣得到的就是排障時間。電腦鼠在迷宮中的停留或運行的總時間不可超過15分鐘，在限時內(nèi)允許運行多次，允許取其中最短的排障時間作為參賽的計分成績。當(dāng)然，排障時間越短越好例如：一個電腦鼠在迷宮中運行時間為4分鐘（240秒）沒有碰觸過，迷宮時間使用了20秒，這次運行的排障時間就是：20秒+（240秒1/30） 10秒 = 18秒。電腦鼠在迷宮通道內(nèi)行走時不能碰到隔墻板，遇到岔道口時要能夠自動作出方向選擇。本文規(guī)定：如果進入迷宮是為了進行探測和記憶，這次運行就稱為“試跑”；如果進入迷宮是根據(jù)先前的記憶和經(jīng)驗，按照智能算法確定最佳路徑，并以最快的速度到達目的地，這次運行就稱為“沖刺”。2 電腦鼠走迷宮的算法2.1探測策略電腦鼠走迷宮可以采用全迷宮探索策略，即將迷宮的所有單元均搜索一次，從中找出最佳的行走路徑。這種策略需要有足夠的時間或探測次數(shù)，但在IEEE競賽規(guī)則中每場競賽只有15分鐘的時間，因此是不可能的。另一種方法是部分迷宮探索策略，即在有限的時間或探測次數(shù)下，只探測迷宮的一部分，從中找出次最佳的路徑，顯然只能采用這種策略。電腦鼠在一巷道內(nèi)行走，如果最后無路可走，則該巷為死巷。電腦鼠在任一單元內(nèi)，可能的行走方向最多只有三個（前、左、右），如果有二個或二個以上的可能行走方向，稱為交叉，遇有交叉時，由于有多個可以行走的方向，在行走方向的選擇上，可有下面的幾種選擇法則： 右手法則：遇有交叉時，以右邊為優(yōu)先的前進方向，然后是直線方向、左邊方向。 左手法則：遇有交叉時，以左邊為優(yōu)先的前進方向，然后是直線方向、右邊方向。 中左法則：遇有交叉時，以直線為優(yōu)先的前進方向，然后是左邊方向、右邊方向。與此類似的還有中右法則。 亂數(shù)法則：遇有交叉時，取隨機值作為前進方向。 向心法則：由于終點在迷宮的中心，遇有交叉時，以向迷宮中心的方向為優(yōu)先的前進方向。2.2標(biāo)記為了記憶迷宮的詳細信息，需要對迷宮單元的位置進行線路標(biāo)記。全迷宮共有1616個單元組成，可采用二維坐標(biāo)方式標(biāo)記，即用每個單元的XY坐標(biāo)表示，如起點可標(biāo)記為（0，0），終點為（7，7）。此外，還需要對迷宮單元的可行進方向進行標(biāo)記，可采用絕對方位或相對方位二種方式。絕對方位：這是一種與電腦鼠行進方向無關(guān)的標(biāo)記方式，以一個四位的二進制數(shù)，分別表示“東”“西”“南”和“北”四個方向。以1表示允許行進（無墻壁），0表示不允許行進（有墻壁）。相對方位：這是一種與電腦鼠行進方向有關(guān)的標(biāo)記方式，以一個三位的二進制數(shù)即可實現(xiàn)標(biāo)記，分別表示“前”“左”“右”， 以1表示允許（無墻壁），0表示不允許（有墻壁）。2.3阻斷在電腦鼠試跑過程中或在最后沖刺時，需要對部分路徑進行“阻斷”，即在發(fā)現(xiàn)某條路徑是死路（只有入口而無出口）時，在該路徑的入口處（一般是交叉點）設(shè)置標(biāo)記，即將入口的線路標(biāo)記由1改為0。2.4試跑試跑是獲得迷宮地圖（各單元路線標(biāo)記）的唯一方法，因而應(yīng)在規(guī)則允許的情況下，盡可能多的獲得迷宮信息，為最后的沖刺準(zhǔn)備盡可能多的信息。在試跑過程中，要對經(jīng)過的單元進行線路標(biāo)記，同時還要選擇一個合適的探測策略。下面以1/4迷宮為例進行說明。假設(shè)迷宮圖布局如圖三所示，共有88=64個單元，起點在左下角（Start），終點在右上角（End）。選用一個88的矩陣map保存迷宮地圖信息，矩陣的每個元素為1個字節(jié)，高4位表示探測到的可行進路徑，以絕對方位標(biāo)記，次序為“北”“東”“西”“南”。低4位記錄自起點的交叉點的個數(shù)。探測策略采用右手法則，在初始狀態(tài)，矩陣map各元素的值均為FFH，00H表示死巷。圖三1/4迷宮在探測過程中，如果下一個可行進的單元已經(jīng)探測過（對應(yīng)的矩陣元素值非00H或非FFH），只有在發(fā)現(xiàn)死巷時，才對map中的數(shù)據(jù)進行修改。對于其它情況，無論探測結(jié)果與矩陣中對應(yīng)元素存儲的信息是否一致，均不修改存儲的信息。對于復(fù)雜的迷宮，往往不能僅使用一種探測策略，而要綜合考慮，如增加向心法則。當(dāng)發(fā)現(xiàn)交叉點時，應(yīng)將該單元坐標(biāo)和線路特征保存（如入棧），再分析可行的下一個單元是否已經(jīng)探測過，如果均未探測過，則根據(jù)探測策略，選擇一方向進行探測。如果部分單元已經(jīng)探測，則選擇未被探測的單元進行探測。遇有死巷，應(yīng)返回最近的交叉點，同時將死巷阻斷，修改入口單元的相應(yīng)數(shù)值。圖四為首次探測時電腦鼠的行走路線示意，電腦鼠在探測過程中，將獲得行走過的各單元的線路特征，表一為電腦鼠探測到（5，0）單元時的二維表（以十六進制表示，高4位為線路標(biāo)記，低4位為交叉點數(shù)）。圖四首次探測行走路線7FFHFFHFFHFFHFFHFFHFFHend6FFHFFHFFHFFHFFHFFHFFHFFH530H50HFFHFFHFFHFFHFFHFFH490H90HFFHFFHFFHFFHFFHFFH390HD1HFFHFFHFFHFFHFFHFFH290H90HFFHFFHFFHFFHFFHFFH190HB2HFFHFFHFFHFFHFFHFFH080HC0H60H60H60H60HFFHFFH01234567表一探測到（5，0）時的map二維表從圖四可以看出，該巷為一死巷，當(dāng)電腦鼠探測到（7，0）時，發(fā)現(xiàn)是死巷，將按原路返回到最近的交叉點（1，1），進行阻斷，即將向“南”修改為不可行，并修改交叉點的數(shù)據(jù)，由原值B2H改為90H，死巷中的數(shù)據(jù)全寫零，并繼續(xù)完成探測，最后得表二。7FFHFFHFFHFFHFFHFFHFFHend6FFHFFHFFHFFHFFHFFHFFHB0H530H50HFFHFFHFFHFFHFFHB0H490H90HFFHFFHFFHFFHFFH90H390HD1HFFHFFHFFHFFHFFH90H290H90HFFHFFHFFHFFHFFHA2H190HC0H60H60H60H60H60H90H080H00H00H00H00H00H00H00H01234567表二執(zhí)行阻斷后的二維表根據(jù)IEEE電腦鼠競賽規(guī)定，當(dāng)電腦鼠到達終點后，可進行返回探測，從而獲得更多的迷宮地圖信息。圖五為返回探測時的行走路徑。在返回探測中，未發(fā)現(xiàn)死巷，返回起點，探測后的結(jié)果如表三。圖五返回時的探測路徑750H60H60H60H60H60H30Hend6C0H60H70HFFHFFHFFHC0HB4H530H50HD2HFFHFFHFFHFFHB3H490H90HC0H60H30HFFHFFH90H390HD1H60H71HA0HFFHFFH90H290H90HFFHFFHFFHFFHFFHA2H190HC0H60H60H60H60H60H90H080H00H00H00H00H00H00H00H01234567表三返回探測后的二維表圖六第二次探測路徑第二次探測如圖六，在（3，3）和（2，5）分別執(zhí)行阻斷，將獲得二維表四750H60H60H60H60H60H30Hend6C0H60H70H72H60H30HC0HB4H530H50H90H00H00HD3HHHHB3H490H90HC0H60H30H90HHHH90H390HD1H60H30HA0H90HHHH90H290H90HHHH00H00HC0H60HA2H190HC0H60H60H60H60H60H90H080H00H00H00H00H00H00H00H01234567表四第二次探測后的二維表2.5數(shù)據(jù)補全由于不可能將所有的單元均探測到，在有了一定的數(shù)據(jù)基礎(chǔ)上，就可以實現(xiàn)數(shù)據(jù)補全了。數(shù)據(jù)補全，就是對未探測到的單元，通過周圍已有的相數(shù)據(jù)，可進行補充的一種方法。方法是尋找單元數(shù)據(jù)為FFH的單元，如果該單元的“東”“西”“南”“北”四個相鄰的單元均為非00H或FFH，分析“東”“西”和“南”“北”四個單元的二組數(shù)據(jù)，看是否有指向該單元的可行方向，如果有，在該方向是相通的，可對數(shù)據(jù)進行大膽的假設(shè)。對照表四，（6，5）是未探測過的，其值為FFH，分析與之相鄰的（5，5）（7，5）和（6，6）（6，4）二組數(shù)據(jù)，（6，4）的數(shù)據(jù)為FFH，放棄在南北方向上的補全，考慮東西方向，（5，5）向東是可行的，（7，5）向西是可行的，因而可以大膽設(shè)想，（6，5）是東西可行的，數(shù)據(jù)可設(shè)為60H，將60H填入表四，就得到補全后的表五。750H60H60H60H60H60H30Hend6C0H60H70H72H60H30HC0HB4H530H50H90H00H00HD3H60HB3H490H90HC0H60H30H90HHHH90H390HD1H60H30HA0H90HHHH90H290H90HHHH00H00HC0H60HA2H190HC0H60H60H60H60H60H90H080H00H00H00H00H00H00H00H01234567表五補全后的二維表2.6等高表經(jīng)過有限次的探測、阻斷與補全后，已經(jīng)可以得到描述迷宮圖線路的二維表，雖然不是全部，但已經(jīng)是部分或大部分，其中可能包含了若干條可以到達終點的路徑，為了尋找到達終點的路徑，需要制作等高表。等高表是指已探測的各單元距離起點的步數(shù)（一個單元為一步），起點的步數(shù)為0，表六為通過表五所獲得的等高表。等高值以十進制數(shù)表示。19202122232425281817161718192627561520212247141312211938910112218292324171101112131415160表六等高表2.7可行路徑在等高表中，可行路徑上任一單元到起點的步數(shù)都是已知的，按從大到小的次序，可以返回起點。按從小到大的次序，可到達終點，這樣的可行路徑可能不止一個，而是多個。可行路徑的查找，從起點開始，在允許前進的方向上，按比當(dāng)前等高值高1的方向前進，直到終點。有時可能會遇到下一單元的等高值小于當(dāng)前值（如（6，2）點）或比當(dāng)前值高1以上的情況，如果當(dāng)前單元不是交叉點，可以不予理會，進入下一個單元，按等高值增加的方向查找。如果是交叉點，則要進行趨勢分析，找出等高值就增加的方向。舍棄等高值減少的方向。圖七 是根據(jù)表六得到的所有可行路徑，共有A、B、C、D四條。圖七所有的可行路徑2.8可行路徑的步數(shù)可行路徑的步數(shù)，指由起點到達終點，所經(jīng)過的單元數(shù)，可由等高表計算得出。線路A：由（0，0）到（7，4），19步，（7，4）到（7，5）1步，（7，5）到（7，6）1步，（7，6）到（7，7），28-27=1步。總計=19+1+1+1=22步。線路B：由（0，0）到（6，2），24步，（6，2）到（7，2）1步，（7，2）到（7，4）,19-17=2步，（7，4）到（7，5），1步, （7，5）