一種電腦鼠走迷宮的算法

ID:37692014

大小:432.50 KB

頁數(shù):8頁

時間:2019-05-28

一種電腦鼠走迷宮的算法_第1頁
一種電腦鼠走迷宮的算法_第2頁
一種電腦鼠走迷宮的算法_第3頁
一種電腦鼠走迷宮的算法_第4頁
一種電腦鼠走迷宮的算法_第5頁
資源描述:

《一種電腦鼠走迷宮的算法》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、一種電腦鼠走迷宮的算法電腦鼠的英文名稱為Micromouse,實際上是一個由微處理器控制的,集感知、判斷、行走功能于一體,能夠自動尋找最佳路徑到達目的地的小型機器人。它可以在“迷宮”中自動感知并記憶迷宮地圖,通過一定的算法,尋找一條最佳路徑,以最快的速度到達目的地。1997年,在美國舉辦了第一屆電腦鼠競賽,隨后,電腦鼠競賽傳入歐洲,首屆歐洲電腦鼠競賽于1980年在倫敦舉辦,之后英國的電腦鼠比賽便由電子工程協(xié)會(IEE)主辦。1980年11月日本電腦鼠協(xié)會(JMA)在東京舉辦了第一屆競賽,此后,日本

2、每年都要舉辦一屆電腦鼠競賽。我國臺灣也于1986年10月舉辦了首屆電腦鼠比賽。現(xiàn)在國際電工和電子工程學會(IEEE)每年都要舉辦一次國際性的電腦鼠走迷宮競賽,各國選手報名踴躍,主要是大學生,為此部分大學還開設(shè)了“電腦鼠原理和制作”選修課程。由于電腦鼠要由參賽選手自己設(shè)計制作,不僅要求選手具有嵌入式系統(tǒng)應(yīng)用﹑傳感器﹑控制技術(shù)等多方面的知識、經(jīng)驗和實踐能力,還要求具有編寫尋找最佳路徑算法的能力。由于迷宮路徑設(shè)置是隨機的,因而競賽難度較大,極富挑戰(zhàn)性。這對培養(yǎng)和提高學生的創(chuàng)新精神和實踐能力,有著深遠的意

3、義。2007年5月—8月將舉辦由我國部分地區(qū)(上海及長三角地區(qū))參加的首屆電腦鼠邀請賽。1電腦鼠走迷宮的規(guī)則有關(guān)電腦鼠國際比賽的詳細規(guī)則,可參閱國際電工和電子工程學會(IEEE)的官方網(wǎng)站:http://www.eece.maine.edu/sc2006/2006MicromouseRules.pdf。迷宮的規(guī)格迷宮由256個方塊(單元)組成,每個方塊的大小為18厘米見方,排成16行×16列。迷宮的隔墻板沿方塊的四周布設(shè),形成迷宮通道。隔墻板高5厘米﹑厚1.2厘米,因此迷宮通道的實際寬度是16.8

4、厘米。隔墻板的兩個側(cè)面是白色的,頂部是紅色的。迷宮的地板由木質(zhì)材料做成,涂上沒有反光的黑漆。隔墻板的側(cè)面和頂部對紅外線有反射特性,而地板則對紅外線有吸收特性。競賽起始點可設(shè)在迷宮的任何一角,其三面要有隔墻;競賽的終點設(shè)在迷宮的中央,有四個方塊那么大小。圖一為一個實際的電腦鼠競賽用的迷宮照片。圖一電腦鼠競賽用的迷宮照片1.2電腦鼠的規(guī)格電腦鼠要求由參賽者自制,使用電源為能源,不能使用其它可燃物為能源。電腦鼠結(jié)構(gòu)高出隔墻部分的長寬幾何尺寸應(yīng)不大于25×25厘米,對高度沒有限制。一個完整的電腦鼠應(yīng)包含有

5、機身、電源、傳感器、微處理器、馬達及驅(qū)動等部分。電腦鼠的傳感器可分為三組,分別用來感知前、左、右三個方向是否已靠近宮壁,并將所獲得信息傳送給微處理器進行處理。微處理器要完成多種信息的處理,如路徑、迷宮地圖、行走距離、馬達控制等,并要能夠作出判斷。在馬達的控制下,電腦鼠能夠完成直行、轉(zhuǎn)彎、掉頭以及加減速等動作。通常采用左右獨立的馬達驅(qū)動和控制,以使微處理器的控制更加靈活。圖二為一個實際參加競賽的電腦鼠樣例照片。8圖二電腦鼠樣例照片。1.3競賽的規(guī)則電腦鼠的基本功能是從起點開始走到終點,這個過程稱為一

6、次“運行”,所花費的時間稱為“運行時間”。從終點回到起點所花費的時間不計算在運行時間內(nèi)。電腦鼠從第一次激活到每次運行開始,所花費的時間稱為“迷宮時間”。如果電腦鼠在比賽時需要手動輔助,這個動作稱為“碰觸”。競賽使用這三個參數(shù),即運行時間﹑迷宮時間和碰觸,從速度﹑求解迷宮的效率和電腦鼠可靠性三個方面來進行評分。電腦鼠的得分是通過計算每次運行的“排障時間”來衡量的。所謂排障時間是這樣計算的:先將迷宮時間的1/30加上一次運行時間,如果這次運行結(jié)束以后電腦鼠沒有被碰觸過,那么還要再減去10秒的獎勵時間,

7、這樣得到的就是排障時間。電腦鼠在迷宮中的停留或運行的總時間不可超過15分鐘,在限時內(nèi)允許運行多次,允許取其中最短的排障時間作為參賽的計分成績。當然,排障時間越短越好例如:一個電腦鼠在迷宮中運行時間為4分鐘(240秒)沒有碰觸過,迷宮時間使用了20秒,這次運行的排障時間就是:20秒+(240秒×1/30)-10秒=18秒。電腦鼠在迷宮通道內(nèi)行走時不能碰到隔墻板,遇到岔道口時要能夠自動作出方向選擇。本文規(guī)定:如果進入迷宮是為了進行探測和記憶,這次運行就稱為“試跑”;如果進入迷宮是根據(jù)先前的記憶和經(jīng)驗,

8、按照智能算法確定最佳路徑,并以最快的速度到達目的地,這次運行就稱為“沖刺”。1電腦鼠走迷宮的算法2.1 探測策略電腦鼠走迷宮可以采用全迷宮探索策略,即將迷宮的所有單元均搜索一次,從中找出最佳的行走路徑。這種策略需要有足夠的時間或探測次數(shù),但在IEEE競賽規(guī)則中每場競賽只有15分鐘的時間,因此是不可能的。另一種方法是部分迷宮探索策略,即在有限的時間或探測次數(shù)下,只探測迷宮的一部分,從中找出次最佳的路徑,顯然只能采用這種策略。電腦鼠在一巷道內(nèi)行走,如果最后無路可走,則該巷為死巷。電腦鼠

當前文檔最多預(yù)覽五頁,下載文檔查看全文

此文檔下載收益歸作者所有

當前文檔最多預(yù)覽五頁,下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學公式或PPT動畫的文件,查看預(yù)覽時可能會顯示錯亂或異常,文件下載后無此問題,請放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫負責整理代發(fā)布。如果您對本文檔版權(quán)有爭議請及時聯(lián)系客服。
3. 下載前請仔細閱讀文檔內(nèi)容,確認文檔內(nèi)容符合您的需求后進行下載,若出現(xiàn)內(nèi)容與標題不符可向本站投訴處理。
4. 下載文檔時可能由于網(wǎng)絡(luò)波動等原因無法下載或下載錯誤,付費完成后未能成功下載的用戶請聯(lián)系客服處理。
关闭