February 11, 2019
EECS Doctoral Dissertations

Efficient Computing for Autonomous Navigation using Algorithm-and-Hardware Co-design

Zhengdong Zhang, MIT
  • Speaker
  • Abstract
  • Exclusive Content

Zhengdong Zhang  is a PhD candidate in the department of Electrical Engineering and Computer Science working with Prof. Vivienne Sze. He received the B.S. in Computer Science in 2011 from Tsinghua University, Beijing, China. He received the M.S. degree in Computer Science from Massachusetts Institute of Technology, Cambridge in 2014. Between 2011 and 2012 he worked in Microsoft Research Asia, Beijing, China, as an Assistant Researcher. He is pursuing the Ph.D. degree under the supervision of Prof. Vivienne Sze. His research interest spans the area of sparsity, low-rank matrix recovery, symmetry/regularity of textures, 3D computer vision, computational photography, robotics, localization and mapping, autonomous exploration. His current research focuses on the design of energy-efficient vision and robotics system.

Autonomous navigation of drones and robots require several key functions, such as visual perception, localization, mapping, and path planning. The state-of-the-art algorithms for these functions typically have high computational complexity and require powerful computers to provide real-time throughput. As a result, deploying them in miniature robots and drones with limited battery and computation power can be challenging.

This thesis proposes various forms of algorithm and hardware co-design that enable these algorithms to be computed on embedded platforms that can be mounted on small drones and vehicles. The defense will focus on one of the tasks, robotic exploration, which studies how to rapidly reduce environment uncertainty and shorten the exploration time. Unfortunately, principled algorithms based on rigorous information-theoretic metrics, such as maximizing Shannon mutual information along the exploration path, are computationally extremely demanding.

We first show a novel algorithm called Fast computation of Shannon Mutual Information (FSMI) that computes the Shannon mutual information between perspective range measurements and the environment, which is a widely used principled objective to guide the search for efficient exploration trajectories. The FSMI algorithm avoids the numerical integration in the previously known algorithm. It also introduces a few approximation techniques, such as Gaussian truncation and tabulation of computation. As a result, FSMI is three orders of magnitude faster than the previous state-of-the-art algorithm for the computation of Shannon mutual information.

Second, we extend the FSMI algorithm to compute the mutual information in a compressed 3D environment represented by OctoMap. Instead of uncompressing the input first and then running the FSMI algorithm, the new algorithm directly performs computation on the compressed input that has a significantly shorter length, leading to an order of magnitude acceleration of FSMI computation in a typical 3D environment.

Finally, we present an FPGA architecture designed for the FSMI algorithm. The design consists of a novel memory banking method that increases the bandwidth of the memory so that multiple FSMI cores can run in parallel while maintaining high utilization. A novel arbiter is proposed to resolve the memory read conflicts between multiple cores within one clock cycle. The final design on FPGA achieves more than 100x higher throughput compared with a CPU while consuming less than 1/10 of the power.

This content is restricted to our MIG members and members of the MIT community. Login below, or contact us for more information about our partner programs.

Login