勇闖未知領域 電腦鼠的迷宮探索策略

迷宮探索一直是人類喜愛的挑戰之一，而有一種微型車輛的導航機器人，專門被設計用來探索迷宮，並會定期舉辦相關競賽，這就是電腦鼠 (Micromouse) 競賽。參賽者必須設計能夠自主導航的機器車，在未知迷宮中利用感測器蒐集環境資訊，建立地圖，並尋找通往終點的最佳路徑。本文介紹電腦鼠競賽的起源與規則，說明其常用的感測技術與定位方式，並探討迷宮探索策略。此外，也介紹高速競賽中常見的最速路徑規劃與運動控制技術。透過電腦鼠競賽，不僅能瞭解機器人如何在未知環境中做出決策，也能一窺導航系統與智慧物流背後的路徑規劃原理。

撰文｜穿山甲

無止盡的好奇心，以及想要瞭解所處世界的慾望，一直激盪著人類的靈魂，促使著許多探險家前仆後繼，儘管感到恐懼也甘願冒巨大風險探索未知領域。自古以來，迷宮就是人們最喜愛探索的項目之一。無論是地底溶穴、水下岩洞、遊樂園裡的迷宮花園，還是神話中的米諾陶洛斯迷宮，抑或紙本遊戲中的迷宮題目，迷宮都讓人如此深深著迷，考驗著人們的方向感與探索未知環境的能力。然而迷宮往往過於龐大，單純人為探索往往過於耗費心力。人們開始將目標轉向機器人，思考著若裝上感測器與電機，使用預先設計好的演算法，能否正確地找到出口？

電腦鼠的迷宮探索策略

為此，工程師設計了一項經典的電腦鼠（Micromouse，又稱機械鼠）競賽。參賽者必須打造一隻能夠自主思考的「電腦老鼠」，讓它能在未知迷宮中一邊探索環境、一邊記錄走過的路線，根據不斷更新的資訊做出決策，期望以最快速度完成挑戰。這項競賽最早於1977年由《IEEE Spectrum》國際期刊提出構想，並於1979年舉辦第一次競賽。此後，逐漸受到全球工程師與學生的歡迎，並在世界各地發展成為重要的機器人競賽項目。

競賽除了考驗參賽者對機構、電路與程式的瞭解外，電腦鼠探索迷宮的策略也很重要。已知迷宮與未知迷宮的路徑搜尋方式會有所不同。迷宮的資訊可能來自於前幾次探索後，所繪製的地圖，抑或於賽前公布。假使已經知道迷宮的全貌，可以先將迷宮的所有死路填滿，這樣可以留下較少的岔路，以便更容易找到路徑，如圖1(a)所示。另一種方法，則可以將迷宮的所有路徑看作一組具有彈性的橡膠，抓住起點與終點往兩側拉扯。迷宮的路徑就會出現在逐漸遠離的兩端點間，此時再去比對原始路徑，即可找到迷宮的最短路徑，如圖1(b)所示。

然而，一般的賽事通常無法事先知曉迷宮全貌，拉伸迷宮法也難以程式化。最原始的方法就是隨機選擇岔路行進。雖然是隨機選擇，但時間一久總是可以抵達終點。但在爭分奪秒的實際賽事中，此法顯然效率過低。另一個簡單的策略就是摸著牆走，可以想像自己身處於迷宮之中，伸出你的右手或左手全程放在牆面行進，遇到岔路依然貼著牆移動。這種方法的優點是執行方法簡單，不需要建立地圖，就能抵達終點，如圖2(a)所示。然而，這個方法僅限於起點與終點的牆有相連的情況。假使終點設定在迷宮中央，且起點與終點的牆是斷開的，就有可能走不到終點，如圖2(b)所示。此外，亦不能保證能找到最短路徑，在複雜迷宮中甚至會繞行許多不必要的路線，增加探索時間。

如果想要加快速度，可以讓電腦鼠隨機深入一條路徑，經過岔路隨機選擇方向，直到遭遇死路後返回上一個岔路，嘗試另一條路徑。這種方法被稱作深度優先探索 (Depth-First Search, DFS)，執行上耗費的記憶體較少，能快速探查路徑，但不保證找到的路徑是最短的。與之相對的方法叫廣度優先探索 (Breadth-First Search, BFS)，將迷宮的每層岔路依序探索，找完第一層，再往第二層，再前進第三層，以此類推。雖然這個方法可以找到最短路徑，但電腦鼠無法瞬間移動，來回探索會花費很多時間，所以通常要針對路徑的特性設定權重，例如距離或方向。一種廣泛使用的方法，被稱為泛洪填充 (Flood Fill) 演算法。它的概念可以想像成往迷宮倒水，水會沿著每一條可通行的道路逐漸向外擴散，距離終點越近的位置數值越小，距離越遠數值越大。數字填完後，只要比較相鄰格子的數值，始終朝著數值較小的方向走，就能找到最短路徑，如圖3(a) 所示。

除了Flood Fill之外，Dijkstra演算法與A star (A*) 演算法也是常見的路徑規劃方法。Dijkstra的核心概念，是從起點開始逐步計算到每一個位置的最小累積成本，但此法會朝向四面八方計算。相較之下，A*可視為Dijkstra的改良版本。除了考慮從起點走到目前位置所累積的成本之外，還會估計目前位置距離終點還有多遠，也就是預估走剩餘路徑的成本，優先搜尋那些最有希望接近終點的路徑，因此通常能以更少的搜尋步驟找到相同的最佳解，搜尋效率較高，如圖3(b) 所示。A*演算法也廣泛應用於遊戲中，用以搜尋怪物或行進中可自動繞過路障。

最短與最快路徑之爭

在計算得分方面，除了比較誰可以最快抵達終點外，迷宮探索時間也會計算在內。倘若行進間發生碰撞，需要人為移回正確路徑時，則會視不同程度疊加上時間，最終以使用最短時間的隊伍獲勝。不同的賽事規則可能會不一樣，有些還會要求電腦鼠自行返回起點，或只看從迷宮起點到終點的運動時間。因為看的是時間，則有可能讓最短路徑與最短時間路徑不重合。因為走直線的速度會比轉彎來得快，轉彎也需要做適度的運動控制才不至於翻車，因此轉彎的次數越少則越有利。此外，轉彎的方式與角度也很重要，例如原本需要轉兩個90度的路徑，可以改以斜向路徑通過，這種方法時常可以將連續彎道變成直線前進，以爭取更短時間，如圖4(a)(b) 所示。轉彎角度與次數，以及加速時間等參數所付出的成本，都可以作為判斷最佳路徑的依據。在運動控制方面，因為電腦鼠的速度都很快，這反而容易讓電腦鼠行進間微微飄起，使輪子的抓地力變差。這部分可以依靠修改電腦鼠的結構、配重，抑或製造吸力，使輪子跟地面貼得更緊，以減少運動時的漂移。

電腦鼠從辨識周遭環境、建立地圖，到計算最佳路徑與高速運動控制，每一個環節都考驗著參賽者對系統整合能力的理解。其中所使用的許多技術並不只存在於競賽之中，今日的自駕車、倉儲搬運機器人、無人機導航系統，甚至工廠中的自主移動機器人，都面臨著類似的定位、導航與路徑規劃問題。可以說，這項看似簡單的迷宮解謎問題，其實裡面蘊含著智慧機器人技術的縮影。

參考文獻

1. S. Mishra and P. Bande, “Maze Solving Algorithms for Micro Mouse,” 2008 IEEE International Conference on Signal Image Technology and Internet Based Systems, Bali, Indonesia, pp. 86-–93, 2008.
2. M. Nadour and L. Cherroun, “Using Flood-fill Algorithms for an Autonomous Mobile Robot Maze Navigation,” International Journal of System Assurance Engineering and Management, vol. 13, 546–555, 2022.
3. A. Narendran, A. Hothri, H. Saga, and A. Sahay, “MazeSolver: Exploring Algorithmic Solutions for Maze Navigation,” 2024 15th International Conference on Computing Communication and Networking Technologies, Kamand, India, pp. 1–8, 2024.
4. X. Liu and D. Gong, “A Cstudy of A-star Algorithms for Search and Rescue in Perfect Maze,” 2011 International Conference on Electric Information and Control Engineering, Wuhan, 2011, pp. 24–27, 2011.