運用基於次梯度演算法的信號源探測控制室內導航

Abstract

自動化載具在近期是一項熱門且應用廣泛的議題，諸如：室內環境探勘、搜救和運輸。自動化載具的研究多在未知環境中探勘和追蹤目標物。目標物位置分為兩種：已知和未知。相較於被廣泛的研究的前者，後者更符合實際應用。為達到無法使用GPS和未建立無線信標系統的未知室內應用，和避免「即時定位與地圖建構」（SLAM）系統相同的位置窮舉法。假設情境中的目標物能發出無線訊號，讓行動載具依據無線訊號品質追蹤到目標物，進而達到如室內運送、呼叫行動載具和災難後救援等應用，這樣的問題屬於信號源追蹤控制。 本篇論文提出一個基於次梯度演算法的信號源追蹤控制，主要目標是讓行動載具能根據目標物所發送的訊號強度移動至該目標物的位置。為了避免傳統極值尋找法（ES）基於諧波訊號控制造成行動載具的位置震盪，本文引進通常用於電腦領域的最佳化方法：次梯度演算法，並修改成用於行動載具的路徑規劃方法。在訊號場中，有一個常見的問題是訊號延遲，並造成訊號梯度估測上的失準。因此在本方法中，行動載具在「移動」和「等候」兩種狀態間切換以兼具追蹤任務和次梯度的正確運算。 本文中主要的挑戰是未知的訊號場。在未知的訊號場中，行動載具只能依據目前的進行方向，判斷該方向上的梯度。同一位置其他方向的梯度則未知，使得行動載具無法判斷在目前位置的最大訊號梯度方向為何，造成次梯度演算法的失敗。因此提出一項搜尋演算法，使行動載具在不同方向間切換，並分析這樣的多次一維最佳化設計會等效於多維度的最佳化設計。最後則分析解釋牛頓法不適用的理由。 在實際情境中，由於環境會有障礙物，因此行動載具的避障功能是必要的設計。依此，本文提出一懲罰項，為行動載具和障礙物間距離的函數。當行動載具接近障礙物時，行動載具的速度會因為懲罰項而有所抑制，達到該行進方向上的避障，當應用於多次一維搜尋演算法後，則達成多維度環境中的避障。雖然訊號場在本文中假設未知，本文尚分析次梯度演算法的應用於無線傳播模型時的收斂性，以證明提出方法適用於實際情境。模擬和實驗結果顯示，在目標物一定的環境限制下，行動載具可以依據訊號強度追蹤到訊號源。

Autonomous vehicle is a key technology that has been widely researched in recent decade and has many applications such as indoor navigation, rescue and transportation. The works of autonomous vehicle usually focus on navigation in an indoor environment or target tracking. There are two kinds of targets: (1) targets that positions have been detected by range sensors or locating systems and (2) targets that positions are unknown. Comparing to the former targets that have been researched wildly, the latter meet real scenario. In order to reach the unknown indoor navigation that GPS is denied and wireless beacon system has not been built, and avoid the same situation of exhaustive position tracking provided by Simultaneous Localization and Mapping (SLAM) technique, assume the target in the scenario is capable of broadcasting wireless signal. Mobile vehicles can track the target based on signal quality of the electromagnetic wave received, and then reach the applications such as indoor transportation, rescue, and mobile vehicle summation. This kind of problem is called source seeking. This thesis proposes a signal source tracking control algorithm based on subgradient. The main purpose is to steer the mobile vehicle to the position of the target according to strength of signal received from targets. In order to avoid position oscillation of vehicle caused by sinusoidal probe signal used in traditional Extremum Seeking (ES), an optimization method called subgradient method used in computer science is used and modified for mobile vehicle path planning. In signal field, a common problem is signal delay which causes failure of computing gradient of signal strength. Mobile vehicle is designed to switch between moving state and pausing state to accomplish both tracking task and subgradient computation. The major challenge of the problem is the unknown signal field. Mobile robot can only estimate subgradient in the corresponding moving direction, while subgradient in other direction at same position remains unknown. This make the mobile robot lose its judgment of choosing the direction with largest subgradient at the position, thus subgradient method failed. So, a searching algorithm making mobile vehicle switch alternately is raised by the proposed method. Effectiveness of the algorithm that combines multiple one-dimensional optimizations to multi-dimensional optimization is also analyzed as well. The reason why the other common optimization method, Newton’s method, failed is also analyzed in the end of this part. In real scenario, there may be obstacles in the environment, so a design with obstacle avoidance feature of mobile vehicle is necessary. Thus, a punish term which is a function of the distance from obstacles measured by the onboard range sensors, is added into the computation of subgradient. When the mobile vehicle is approaching obstacles, punish term inhibit the translational velocity of the mobile vehicle to reach obstacle avoidance in the moving direction. If the design is applied to multiple one-dimensional searching algorithm, obstacle avoidance in multi-dimensional environment is completed. Although the signal field is assumed to be unknown, convergence of subgradient method applied on radio propagation model is analyzed to show applicability of the proposed method in real situation. Simulation and experimental results show that with certain constrains of the target, the vehicle mobile can track the signal source based on the proposed method.