自走式機器人之路徑規划

Abstract

線上路徑規劃(on-lie path planning)是在自走式機器人內建立環境模型，以特定的 方法或演算法(algorithm) 快速的尋找到能完成所負任務的路徑，并且將路徑資料下 傳給自走式機器人；并依據機器人上感測資訊在必要時修改環境模型，并重新規劃其 路徑。 根據上面的論述，我們提出了象限法(quadrant method) 及改良式Gilles演算法(en- hance of Gilles Aigorithm)做為自走式機器人之路徑規劃的演算法。改良式Gilles 演算法是將Gilles演算法中的格子產生方式做一修改：以環境模型中障礙物的安全邊 際為產生格子的方法；而使格子的形狀為不等尺雨之矩形，這種修改使尋找路徑的記 憶(memory)需求減少，并且加快將路徑尋找的速度。由於起點與終點可指示出最有利 的路徑尋找方向，使用象限法可使尋找路徑的空間只局限於某一象限內，所以可以節 省在其余象限所尋找路徑的時間。為配合改良式Gilles演算法及使運動軌慫規劃能有 較圓滑性的路徑；我們也解決了起點或終點落在障礙物區(obstacle region) 時的問 題：取前置量法(predictor method)，使得路徑規劃不會產生錯誤。此種路徑規劃方 式可廣泛的適用於不同導引(guideness) 方式的自走式機器人。 另外我們設計了一個監督器來監督盄上路徑規劃、自走式機器人的運動軌慫、自走式 機器人上的超音波感測器對環境障礙物的描敘與修改環境模型及路徑再規劃的判斷。 監督器做超音波感測器對環境劂物的描敘方法是采用bit-mapping 的方法，這種方法 可以將環境障礙物作一般性的描敘，并且用來修改監督器內的環境模式。 本論文最后也用一些情錶來做模擬，所模擬的結果可以印證我們所提出的理論。