解迷宮演算法實現於視覺自動導引車

本論文為了考量成本而使用只有單顆鏡頭做為外界感測器的自動導引車，並提出改良的迷宮演算法針對模擬的倉儲空間進行地圖製作，在行駛過程中一併將地圖紀錄下來。作為紀錄倉儲空間地圖的機器人，僅由單顆鏡頭作為感測器的實驗難度相較於多感測器提升不少，因此將場地簡化為只有特徵點與行走線，當鏡頭行駛至特徵點位置時，利用OpenCV相關函式庫對影像畫面進行預先處理之後進行色彩判定，判定特徵點與岔路之後，由演算法紀錄該特徵點資料並計算下一步動作，這個判定會直至該導引車至少走過所有特徵點方可停止。在記錄地圖的演算法上選擇使用了特雷莫演算法(Trémaux algorithm)，並移除掉迷宮演算法特有的隨機性質，給與演算法固定性的決策計算方式，在有尚未行駛的路段不會結束，使得導引車能夠行駛地圖所有路段並繪製出完成地圖。本論文的軟體系統使用機器人操作系統(Robot Operating System, ROS)，機器人操作系統容易整合多種功能，並且使用多執行緒的方式進行個別功能演算，讓自動導引車可使用視覺進行直走判定、轉彎判定、回轉判定的行動模式，最後記錄所有經過的特徵點並製作地圖。

關鍵字

自動導引車；迷宮演算法；特雷莫演算法；機器人操作系統

並列摘要

This thesis consider to the cost by using only single camera for sensor, and propose a modified maze-solving algorithm to mapping warehouse space by traveling whole map. As a robot that records the map of the warehouse space, the difficulty of using single camera as a sensor is much higher than multiple sensors, so the area is simplified to only feature points and walking lines, when the vehicle travels to the feature point, the image will be pre-processed by using OpenCV and color determination, after determining the feature point and the walking lines, the feature point data is recorded by the algorithm and calculate the next move, the movement will stop when vehicle has traveled through at least all feature points. In this thesis, I choose Trémaux algorithm for calculate and removes the stochastic of the maze-solving algorithm, giving the algorithm decision-making calculation method, ensure that all lines have been traveled, and recorded all feature points data. This thesis also using Robot Operating System (ROS), which is easy to control multiple functions and uses multi-threaded to perform individual function calculations, so that the automated guid vehicle can use camera to control the action modes of forward , turning right or left, and turn backward, and finally record all the passing feature points and create a map.