# An Efficient Global Localization Method for Indoor Environment Using Geometry Features

****
###### A thesis submitted to Institute of Electrical and Control Engineering, National Chiao Tung University in partial fulfillment of the requirements for the degree of master of science in electrical and control engineering January 2021

碩士畢業論文，此論文主要的目的為加速自主移動式機器人全域定位的過程。

[電子全文（未開放）](https://etd.lib.nctu.edu.tw/cgi-bin/gs32/tugsweb.cgi/ccd=VlQrTc/record?r1=1&h1=0)

****
# Abstract
       全域定位對於安全的移動式機器人自主導航系統相當重要，不管應用於初始化或是機器人發生迷航的狀況，都有助於提升其穩定性，避免機器人處在危險的狀態。而在室內環境，由於缺乏GPS的絕對座標，因此需要利用其他感測器對環境進行識別，去找出機器人自身在預先建構之地圖上的最有可能的位姿。現今常見的方法是利用影像建立數據庫，並將最新的影像進行匹配，然而此方法較容易受到視角的限制。另一類的方法是使用測距儀所產生的掃描點對地圖進行匹配，找出匹配分數最高的位置，此類方法雖然較為穩定，但計算量較大。

       在本篇論文中，我們提出一個結合地圖幾何特徵與像素精準掃描匹配的快速全域定位方法，加速了整體全域定位的過程。我們的完整地圖由眾多子圖構建而成，在定位的過程中，藉由匹配子圖與與當前掃描數據的幾何特徵，來尋找出機器人最有可能位在的子圖，並對此子圖執行像素精準掃描匹配來完成全域定位的目的。我們的方法大幅度的減少了候選位姿的數量，以達到加速的目的。此外我們也對匹配地圖以及掃描數據進行處理，使得像素精準掃描匹配的最終定位過程更加快速。本篇論文所提出的方法同時在模擬環境以及現實環境完成驗證。

# Motivation
       對於周遭環境的辨識與偵測一直都是機器人系統中非常重要的一個議題，機器人可以藉由感知系統去獲得現實環境中的資訊，對於自主移動的機器人更是不可或缺的一部分，安全可靠的機器人自主導航必須建構在其對於環境的了解，而機器人定位的實現，則是導航最根本的條件。

       移動式機器人定位問題，也稱之為位姿估計，主要的目的就是去尋找機器人基於已知環境的位置，利用感測器當前的資訊，與過去累積的數據進行匹配以分析出當下最有可能的位置。普遍來說機器人的定位問題可以分成兩種，位置追蹤以及全域定位。位置追蹤也可以稱為區域定位，我們假設機器人前一刻的位姿是已知的，可以根據上個位置以及里程計數據，結合感測器的感知資訊，去推測出機器人當前的位姿。全域定位則沒有任何的先驗資訊，機器人可能在環境中的任何位置，所以無法利用上述位置追蹤的方法，只能藉由當下感測器獲得的訊息，分析出機器人最有可能所在的位置。

       相對於區域定位，全域定位受到的關注則沒有那麼多，相關的研究也較少。然而，當機器人在現實的環境中行走，是有可能遇到各種外在的突發狀況，造成機器人的迷航，迷航的發生對於自主移動的機器人是相當危險的。目前即使再好的位置追蹤方法，在複雜及動態的環境下或是遭到外力移動，都是難以避免其發生的，因此失效回復，也就是全域定位，對於移動式機器人是相當重要也是必要的。若是在室外環境，即使發生迷航，因為有GPS，所以可以利用此為參考來進行復原；但如果在室內，沒有GPS訊號就讓此問題變得更加困難。此外，除了失效回復，初始位姿估計對於移動式機器人也有一定的需求。雖然大部分的商用機器人皆有充電站作為參考，然而機器人若不在站點啟動，則此時機器人對於自己的位置則會一無所知，此時就需要全域定位，去尋找當前最有可能的位置，讓機器人可以順利的開始去執行任務。

       影像是當前常見用來進行全域定位或是迴環檢測(loop closure detection)的數據來源，其優點為成本低，且其計算量並不大，配合一些穩定的特徵擷取方法，使其具有一定的成效。若使用人造的特徵，如QR code等，其實現則更加的容易。然而影像本身有視角的限制，若新進來的影像與先前的觀測角度不同，則難以達成迴環檢測，此外，若有動態物體在前方，會使得達成目標的難度會更高，亮度的不同，也會造成額外的影響。近年來由於Lidar (光學雷達)技術的不斷進步，使得機器人能夠獲得夠準確的周遭環境距離資訊。雖然面對動態環境，Lidar也會受到一定的干擾，但相對於影像，就沒有這麼大的影響，其容忍度更高，且也沒有視角的問題。然而相對於相機，其成本較高，若應用於全域定位，將新的資訊與數據庫即地圖進行匹配，由於沒有任何初始假設，要找到最有可能的位置，如果使用暴力搜尋，也就是遍歷地圖上的所有位姿，那其計算量則十分巨大，但優點為找到的位置一定是地圖上的最優解。因此，若能夠降低其計算量，又能夠穩定的找到最佳解，那麼利用Lidar進行全域定位不失為一種可行的方案。

# Contribution
       本研究主要目的為加速機器人在室內環境的全域定位，並保有一定穩定性，在本篇論文中，我們提供了一個完整的全域定位架構，從預處理到完成最後的精準定位。而在我們提出的方法中，全域的地圖由眾多子圖所構成，利用室內環境的建築特性，提取子圖的幾何特徵，並在定位時與新的掃描資訊進行特徵匹配，以獲得機器人最有可能位在之子圖，我們利用此種方式快速的減少候選位姿的數量進而加速整體流程。此外，我們藉由將地圖膨脹以及對感測器原始數據的處理，使得在進行像素準確掃描匹配的過程中對於佔據分數的計算能夠優化，結合分支定界搜索法，更進一步的加速了全域定位。

# System Architecture
       本研究所提出的全域定位總體架構如上圖所示。主要的流程為:
1. 預處理，建構資料庫
2. 進行全域定位時，選出與最新數據匹配的子圖
3. 根據上一個步驟選出的子圖執行掃描匹配，找出最有可能的位姿。

       右上方的資料庫，會在預處理的時候完成，即SLAM的建圖過程以及後續特徵提取的部分，因此，資料庫會包含眾多子圖的本身的資訊，如長、寬、解析度以及各柵格的佔據機率等，同時也會將個子圖特徵提取的資訊保存下來。
新數據的部分則根據感測器本身以及使用者需求去做調整，若感測器本身解析度較低或是掃描範圍較小，則可以在定位的當下建構出小子圖再去執行全域定位，多累積一些數據，會增加其可靠度，避免收斂在區域最大值；若本身感測器較好，解析度較高且視角可能是剛好360度，則可以直接將單一幀的掃描進行匹配。

       關於掃描匹配，則是再找出了最有可能位在的子圖後，去執行像素準確的掃描匹配，去找哪一個位姿在在佔據地圖上所獲得的分數最高，得到的位姿，即全域定位的結果。

# Experiment
Simulation test
[](https://www.youtube.com/watch?v=aQsTNJOpZwg&ab_channel=%E6%9E%97%E6%94%BF%E7%A2%A9 "Simulation test")

ITRI lab test
[](https://www.youtube.com/watch?v=L6dfcSJ4iY0&feature=youtu.be&ab_channel=%E6%9E%97%E6%94%BF%E7%A2%A9 "ITRI lab test")

# Conclusion
       本篇論文提出一個結合佔據柵格地圖幾何特徵與像素精準掃描匹配快速且穩定的全域定位方法，在執行完成即時建圖後，利用眾多子圖以及其個別的直線特徵建構出完整的資料庫，並在執行全域定位的過程中，藉由匹配子圖與與當前最新掃描數據的幾何特徵，依據相似度來排序出機器人最有當前可能位在的子圖，並依序對各子圖執行像素精準掃描匹配來完成全域定位的目的，這個方法幅度的減少了候選位姿的數量，加速了整體全域定位的過程，而我們也在真實以及模擬環境中完成驗證。同時我們也對匹配地圖以及掃描數據進行處理，優化了整體的佔據分數，結合分支定界演算法的特性，藉由設置更高的初始最佳分數，使得像素精準掃描匹配的最終定位過程更加快速。而在複雜或是動態的環境之中，若是感測器沒有被遮擋太多，且依然能掃描到環境中大體的架構，則我們的方法依舊能找出與之前類似的環境特徵，對於整體流程不會有太大的影響。

       此篇論文提出的方法最主要可以再改進的部分為特徵提取，因為即使在方方正正的室內環境內，再加上了人為的擺設或裝飾後，原本的直線架構很容易找不到，未來如果能夠使用更穩定的特徵擷取方法，或許能夠使得整體更加穩定。此外，若是能結合其他感測器如相機等來濾除動態物體，則也能夠更進一步提升系統的穩定性。