自動化無線行動感測器佈署之免碰撞路徑規劃機制設計

Abstract

由於行動機器人的發明，人只要透過遙控機器人，就能利用身上的攝影機、雷達、壓力等感測器進行環境檢測，但若要佈署大量感測器，路徑規劃就相當重要，良好的路徑規劃機制必須免於碰撞發生並且能夠在移動上節省電力消耗，如此一來，使感測器監測可以達到最大效率。 本篇論文中，我們研究重點在於行動感測器佈署過程中的路徑規劃，目的為了能夠藉由感測器探索或是測量周圍的環境，我們提出Collision-free Moving Algorithm(以下簡稱CFMA)，使得行動感測器可以安全的到達目標。CFMA將行動感測器之間的碰撞關係轉成牴觸圖 (conflict graph) ，並利用著色問題的概念設計演算法，可讓行動感測器在佈署過程中能夠免於碰撞，由於CFMA在感測器移動時間差距大得到的結果不夠好，因此為了優化路徑規畫的移動時間，我們將原來的CFMA改良成Collision-free Moving Algorithm-Weight (以下簡稱CFMA-W) 。效能評估的結果顯示我們的CFMA在規畫路徑的計算時間、總移動時間、成功佈署率以及物理移動耗能都優於其他的機制。另外，我們在論文中證明了CFMA解決的問題是NP-complete(NPC)，也證明改良後的CFMA-W規劃路徑的問題是NP-hard。

Recent advances in robotics have enabled automated mobile sensors deployment. In these settings, several mobile robots, each equipped with cameras or other sensors, are deployed to realize a smart sensing environment. For a successful deployment of mobile robots, a multi-robot path planning should be carefully designed and implemented. A good multi-robot path planning needs to ensure that the generated paths are not only collision-free, but also optimized with minimum path length, minimum reaching time and minimum power consumption. In this thesis, we address the path planning problem for mobile sensors deployment. We target on smart sensing/monitoring systems and propose a Collision-free Moving Algorithm (CFMA) to ensure all the robots to reach the goals safely. We first maps the collision relationship between sensors into a conflict graph and reduces the k-coloring problem to our path planning problem, then propose the CFMA to achieve a collision-free deployment. Our performance results show that the proposed approaches outperform other mechanisms in terms of computation time, total moving time, sensor reachability, and total energy consumption.