Complete Coverage Path Planning for a Mobile Robot in an Unknown Indoor Environment

[[abstract]]同時定位與環境地圖建立 (Simultaneous Localization And Mapping, SLAM) 是機器人研究中一個很重要的議題。然而，SLAM 需要在搭配有能力探索環境且決定機器人移動方向的機器人導航演算法之後才能展現其成效。本論文的主旨是開發出能夠建構障礙物地圖和實現環境之全域覆蓋路徑規劃的機器人導航系統。在這項研究中，我們使用 Pioneer-3DX 移動式機器人，並搭配 Microsoft Robotics Developer Studio 操控其感測器與致動器以實現機器人的自動導航。將感測器導入機器人平台的主要目的是為了防止機器人的碰撞和建構障礙物地圖，基於成本低廉且易普及化，我們選擇使用超音波聲納感測器。雖然超音波聲納感測器的用途是測量距離，但測量結果卻很容易受到聲納反射的干擾。為此，我們建立了倒感測器過濾模型，並和霍夫變換與倒感測器模型配合使用，成功自含有雜訊的聲納偵測資料中建構出準確的障礙物地圖。另外，我們提出了啟發式的探索方法來實現環境之全域覆蓋路徑規劃。在進行實際環境的實驗測試後，也證實了我們的方法是有效的。[[abstract]]Simultaneous localization and mapping (SLAM) is an important research topic in robotics. However, a successful SLAM algorithm will rely on a robot navigation algorithm which explores the environment and determines the next moving direction. The subject of this thesis is to develop such a robot navigation system for obstacle map construction and complete-coverage path planning. In this study, we use the Pioneer-3DX mobile-robot platform and the Microsoft Robotics Developer Studio to control sensors and actuators to accomplish automatic navigation. The main purpose of introducing sensors into the mobile-robot platform is to achieve both collision avoidance and obstacle map construction. The ultrasonic sensors are adopted because of its low cost and high popularity. Although an ultrasonic sonar sensor device is designed to provide distance information, incorrect distance measure can be easily induced by reflection. The incorrect distance measurement usually leads to misestimate of obstacles. Therefore, we proposed inverse sensor filter models which can be used with the Hough transform and inverse sensor models to construct accurate obstacle maps from noisy sonar sensory data. Also, we proposed a heuristic exploration method for accomplishing complete-coverage path planning. Real experiments have been conducted to test the proposed methods and the results show that our methods are promising.[[note]]碩