Hardware-Software Co-Design for Path Planning by Drones

This work consists of two main components: designing a hardware-software co-design, MT⁺, for adapting the Mikami-Tabuchi algorithm for on-board path planning by drones in a 3D environment; and development of a specialized custom hardware accelerator CDU, as a part of MT⁺, for parallel collision detection. Collision detection is a performance bottleneck in path planning. MT⁺ reduces the delay in path planning without using any heuristic. A comparative analysis between the state-of-the-art path planning algorithm A∗ and Mikami-Tabuchi is performed to show that Mikami-Tabuchi is faster than A∗ in typical real-world environments. In custom-generated environments, path planning using Mikami-Tabuchi shows a latency improvement of 1.7× across varying average sizes of obstacles and 2.7× across varying obstacle density over state-of-the-art path planning algorithm, A∗. Further, the experiments show that the co-design achieves speedups over a full software implementation on CPU, averaging between 10% to 60% across different densities and sizes of obstacles. CDU area and power overheads are negligible against a conventional single-core processor.