A Two-Stage Path Planning Engine for Robot Navigation System

Yu En Hsu, Yen Chin Liao, Hsie Chia Chang

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


This paper presents a two-stage path planning architecture, realized by using a general-purpose CPU as a global planner and a proposed path planning engine as a local planner, solving a path planning problem hierarchically. By the use of heterogeneity, the hardware-software cooperation architecture can take advantages of both hardware and software approach and achieve both generalization and hardware-acceleration. The proposed path planning engine is based on A∗ algorithm, several hardware-friendly optimization techniques are applied or proposed to reduce the time complexity of searching. The coefficient modification avoids the usage of square root hardware. Then, the priority list reordering fully utilizes the memory bandwidth. Finally, we optimized the critical path and achieved 333MHz operating frequency.The proposed system is established and verified in Xilinx PYNQ-Z2 platform using ARM A9 processor as global planner and FPGA as local planner. Moreover, the proposed path planning engine is implemented in TSMC 40nm CMOS process and integrated 296.1k logic gates in 0.28mm2 chip area. It achieves 9.6μs/task latency and 0.16μJ/task energy consumption in 2D and 27.6μs/task latency and 0.48μJ/task energy consumption in 3D.

Original languageEnglish
Title of host publicationProceedings - 34th IEEE International System-on-Chip Conference, SOCC 2021
EditorsGang Qu, Jinjun Xiong, Danella Zhao, Venki Muthukumar, Md Farhadur Reza, Ramalingam Sridhar
PublisherIEEE Computer Society
Number of pages6
ISBN (Electronic)9781665429313
StatePublished - 2021
Event34th IEEE International System-on-Chip Conference, SOCC 2021 - Virtual, Online, United States
Duration: 14 Sep 202117 Sep 2021

Publication series

NameInternational System on Chip Conference
ISSN (Print)2164-1676
ISSN (Electronic)2164-1706


Conference34th IEEE International System-on-Chip Conference, SOCC 2021
Country/TerritoryUnited States
CityVirtual, Online


  • A
  • algorithm
  • heterogeneous architecture
  • path planning
  • robot navigation


Dive into the research topics of 'A Two-Stage Path Planning Engine for Robot Navigation System'. Together they form a unique fingerprint.

Cite this