應用於微型機器人自主導航之路徑規劃處理器設計與實現

Design and Implementation of A Path Planning Processor for Autonomous Navigation of Micro Robots

鍾杰(Chieh Chung)

指導教授 ： 楊家驤

國立臺灣大學/電機資訊學院/電子工程學研究所/碩士(2019年)

https://doi.org/10.6342/NTU201904283

摘要

自主行動之微型機器人已廣泛應用於各種場景並已改變人類生活方式，其自主導航與控制系統需要進行大量認知處理，才能讓機器人執行複雜任務。所需之認知處理包括路徑規劃與障礙物避讓，並需對動態環境進行即時反應。然而，受限於搭載電池的續航力，認知處理必須達到高速且節能。本論文透過演算法與硬體架構之綜合最佳化，提出一個應用於二維與三維空間即時自主導航之高效節能路徑規劃處理器。此處理器採用快速探索隨機樹 (RRT) 在高維度與高解析度的地圖進行路徑規劃，並使用雙樹生長策略、分支延伸、與平行擴展等技術降低運算複雜度與記憶體需求。在原本已搜尋之路徑的基礎上，採用修剪與重複利用等策略進行動態環境下的快速路徑重新規劃。所提出之處理器使用大量平行之處理引擎陣列，其硬體架構設計確保在低複雜度實現下仍具有高效能表現。所提出之路徑規畫處理器以 40nm製程實現，在 3.65mm^2 的晶片面積上整合 2M 邏輯閘。晶片可進行二維與三維的路徑規劃，僅需低於 1ms 與 10ms 的運算時間。操作於200MHz 時脈、供應電壓為 0.9V 時，針對一過去文獻支援之 100×100二維地圖，本研究所提出之處理器晶片消耗能量僅為 1.5µJ/task，在運算時間與能量消耗皆達到上千倍的提升。

關鍵字

路徑規劃 ； 自主機器人 ； 微型機器人 ； 自主導航 ； 取樣式演算法 ； 快速探索隨機樹 ； 數位積體電路

並列摘要

Autonomous micro robots have been utilized in a wide range of applications, changing how humans live. The autonomous navigation system contained in these robots requires a powerful cognition processor that allows complex tasks to be performed in real-time, while adapting to dynamically changing environments. In addition, the limited lifetime of the battery that provides power to the micro robot demands energy-efficient processing of path planning. This work presents an energy­-efficient path planning processor for real­-time autonomous 2D/3D navigation via algorithm­architecture optimization. The chip utilizes the rapidly­exploring random tree (RRT) algorithm to ensure efficient planning on maps that have an increased dimension and resolution. Hardware-­friendly techniques, including a dual­tree planning strategy, branch extension, and parallel expansion, are adopted to reduce both computational complexity and memory requirement. A prune-­and-­reuse strategy is also adopted in order to quickly respond to dynamic scenarios by reusing part of the previously generated path. An array of processing engines is designed as the core of the processor to enable parallel expansion, with the optimal number of processing engines determined through latency analysis. Low complexity implementation for operations in each processing engine are proposed to reduce hardware complexity while maintaining high performance. Fabricated in 40nm CMOS technology, the chip integrates 2M logic gates in an area of 3.65mm^2, supporting planning tasks on both 2D and 3D maps, with latencies of less than 1 and 10 ms, respectively. For a 100×100 2D map, the proposed processor dissipates 1.5µJ/tasks at a supply voltage of 0.9V and an operating frequency of 200MHz. Compared to prior design, improvements of three orders­-of-­magnitude are achieved in both latency and energy dissipation.

並列關鍵字

Path planning ； Autonomous robot ； Micro robot ； Autonomous navigation ； Sampling-­based algorithm ； Rapidly-­exploring random tree (RRT) ； Digital integrated circuits

參考文獻

[1] R. Bloss, “Mobile Hospital Robots Cure Numerous Logistic Needs,” Industrial Robot, vol. 38, no. 6, pp. 567–571, Oct. 2011.

[2] N. Mathew, S. L. Smith and S. L. Waslander, “Planning Paths for Package Delivery in Heterogeneous Multirobot Teams,” IEEE Transactions on Automation Science and Engineering, vol. 12, no. 4, pp. 1298–1308, Oct. 2015.

[3] N. Agmon, G. A. Kaminka and S. Kraus, “Multi-Robot Adversarial Patrolling: Facing a Full-Knowledge Opponent,” Journal of Artificial Intelligence Research, vol. 42, pp. 887–916, Dec. 2011.

[4] S. Witwicki, J. C. Castillo, J. Messias, J. Capitan, F. S. Melo, P. U. Lima and M. Veloso, “Autonomous Surveillance Robots: A Decision-Making Framework for Networked Multiagent Systems,” IEEE Robotics & Automation Magazine, vol. 24, no. 3, pp. 52–64, Sep. 2017.

[5] S. Thrun, S. Thayer, W. Whittaker, C. Baker, W. Burgard, D. Ferguson, D. Hahnal, M. Montemerlo, A. Morris, Z. Omohundro, C. Reverte and W. Whittaker, “Autonomous Exploration and Mapping of Abandoned Mines,” IEEE Robotics & Automation Magazine, vol. 11, no. 4, pp. 79–91, Dec. 2004.