A Shortest Path Finding Time-Based Accelerator Core with Built-in Gravity Control and Buffer Zone for Smooth 3-D Navigation

Luke R. Everson; Jeehwan Song; Sachin S. Sapatnekar; Chris H. Kim

doi:10.1109/LSSC.2020.2995051

A Shortest Path Finding Time-Based Accelerator Core with Built-in Gravity Control and Buffer Zone for Smooth 3-D Navigation

Luke R. Everson, Jeehwan Song, Sachin S. Sapatnekar, Chris H. Kim

Electrical and Computer Engineering

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

A mixed-signal time-based 65-nm application specific integrated circuit is developed for solving shortest-path problems in 3-D. Previous path planning ASICs have been restricted to 2-D maps due to computational complexity or physical architecture limitations. Our time-based, asynchronous, one-shot architecture has been coupled with a novel dual axis interleaving strategy to solve the multidimensional shortest path problem in a simple, energy efficient manner. Additional features include circuit-based solutions for obstacle blockage avoidance and gravity. The efficacy of the proposed ASIC is evaluated on a drone navigation application, 3-D Voronoi diagrams, and a physical optics experiment. The chip is twice as energy efficient as prior 2-D work while containing 5\times more vertices and 7.5\times additional edge connections.

Original language	English (US)
Article number	9097891
Pages (from-to)	66-69
Number of pages	4
Journal	IEEE Solid-State Circuits Letters
Volume	3
DOIs	https://doi.org/10.1109/LSSC.2020.2995051
State	Published - 2020

Bibliographical note

Funding Information:
Manuscript received October 23, 2019; revised January 19, 2020 and April 2, 2020; accepted April 30, 2020. Date of publication May 21, 2020; date of current version June 12, 2020. This work was supported in part by the National Science Foundation under Award CCF-1763761. This article was approved by Associate Editor Lluca Benini. This work was supported in part by the National Science Foundation under Award CCF-1763761. (Corresponding author: Luke R. Everson.) The authors are with the Electrical and Computer Engineering Department, University of Minnesota, Minneapolis, MI 55455 USA (e-mail: [email protected]). Digital Object Identifier 10.1109/LSSC.2020.2995051 Fig. 1. Prior work of path planning chips targeted at 3-D, but falls short in that they do not fully compute the third dimensions due to computational limitations [3] or limited connectivity [4].

Publisher Copyright:
© 2018 IEEE.

Keywords

A algorithm
graph computing
graphs
single-source shortest path
time-domain computing
time-to-digital converter

Publisher link

10.1109/LSSC.2020.2995051

Find It

Find It at U of M Libraries

Cite this

@article{30802bf74fa44ecb9522a721d0dc1a8a,

title = "A Shortest Path Finding Time-Based Accelerator Core with Built-in Gravity Control and Buffer Zone for Smooth 3-D Navigation",

abstract = "A mixed-signal time-based 65-nm application specific integrated circuit is developed for solving shortest-path problems in 3-D. Previous path planning ASICs have been restricted to 2-D maps due to computational complexity or physical architecture limitations. Our time-based, asynchronous, one-shot architecture has been coupled with a novel dual axis interleaving strategy to solve the multidimensional shortest path problem in a simple, energy efficient manner. Additional features include circuit-based solutions for obstacle blockage avoidance and gravity. The efficacy of the proposed ASIC is evaluated on a drone navigation application, 3-D Voronoi diagrams, and a physical optics experiment. The chip is twice as energy efficient as prior 2-D work while containing 5\times more vertices and 7.5\times additional edge connections.",

keywords = "A algorithm, graph computing, graphs, single-source shortest path, time-domain computing, time-to-digital converter",

author = "Everson, {Luke R.} and Jeehwan Song and Sapatnekar, {Sachin S.} and Kim, {Chris H.}",

note = "Funding Information: Manuscript received October 23, 2019; revised January 19, 2020 and April 2, 2020; accepted April 30, 2020. Date of publication May 21, 2020; date of current version June 12, 2020. This work was supported in part by the National Science Foundation under Award CCF-1763761. This article was approved by Associate Editor Lluca Benini. This work was supported in part by the National Science Foundation under Award CCF-1763761. (Corresponding author: Luke R. Everson.) The authors are with the Electrical and Computer Engineering Department, University of Minnesota, Minneapolis, MI 55455 USA (e-mail: [email protected]). Digital Object Identifier 10.1109/LSSC.2020.2995051 Fig. 1. Prior work of path planning chips targeted at 3-D, but falls short in that they do not fully compute the third dimensions due to computational limitations [3] or limited connectivity [4]. Publisher Copyright: {\textcopyright} 2018 IEEE.",

year = "2020",

doi = "10.1109/LSSC.2020.2995051",

language = "English (US)",

volume = "3",

pages = "66--69",

journal = "IEEE Solid-State Circuits Letters",

issn = "2573-9603",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

TY - JOUR

T1 - A Shortest Path Finding Time-Based Accelerator Core with Built-in Gravity Control and Buffer Zone for Smooth 3-D Navigation

AU - Everson, Luke R.

AU - Song, Jeehwan

AU - Sapatnekar, Sachin S.

AU - Kim, Chris H.

N1 - Funding Information: Manuscript received October 23, 2019; revised January 19, 2020 and April 2, 2020; accepted April 30, 2020. Date of publication May 21, 2020; date of current version June 12, 2020. This work was supported in part by the National Science Foundation under Award CCF-1763761. This article was approved by Associate Editor Lluca Benini. This work was supported in part by the National Science Foundation under Award CCF-1763761. (Corresponding author: Luke R. Everson.) The authors are with the Electrical and Computer Engineering Department, University of Minnesota, Minneapolis, MI 55455 USA (e-mail: [email protected]). Digital Object Identifier 10.1109/LSSC.2020.2995051 Fig. 1. Prior work of path planning chips targeted at 3-D, but falls short in that they do not fully compute the third dimensions due to computational limitations [3] or limited connectivity [4]. Publisher Copyright: © 2018 IEEE.

PY - 2020

Y1 - 2020

N2 - A mixed-signal time-based 65-nm application specific integrated circuit is developed for solving shortest-path problems in 3-D. Previous path planning ASICs have been restricted to 2-D maps due to computational complexity or physical architecture limitations. Our time-based, asynchronous, one-shot architecture has been coupled with a novel dual axis interleaving strategy to solve the multidimensional shortest path problem in a simple, energy efficient manner. Additional features include circuit-based solutions for obstacle blockage avoidance and gravity. The efficacy of the proposed ASIC is evaluated on a drone navigation application, 3-D Voronoi diagrams, and a physical optics experiment. The chip is twice as energy efficient as prior 2-D work while containing 5\times more vertices and 7.5\times additional edge connections.

AB - A mixed-signal time-based 65-nm application specific integrated circuit is developed for solving shortest-path problems in 3-D. Previous path planning ASICs have been restricted to 2-D maps due to computational complexity or physical architecture limitations. Our time-based, asynchronous, one-shot architecture has been coupled with a novel dual axis interleaving strategy to solve the multidimensional shortest path problem in a simple, energy efficient manner. Additional features include circuit-based solutions for obstacle blockage avoidance and gravity. The efficacy of the proposed ASIC is evaluated on a drone navigation application, 3-D Voronoi diagrams, and a physical optics experiment. The chip is twice as energy efficient as prior 2-D work while containing 5\times more vertices and 7.5\times additional edge connections.

KW - A algorithm

KW - graph computing

KW - graphs

KW - single-source shortest path

KW - time-domain computing

KW - time-to-digital converter

UR - http://www.scopus.com/inward/record.url?scp=85085741130&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85085741130&partnerID=8YFLogxK

U2 - 10.1109/LSSC.2020.2995051

DO - 10.1109/LSSC.2020.2995051

M3 - Article

AN - SCOPUS:85085741130

SN - 2573-9603

VL - 3

SP - 66

EP - 69

JO - IEEE Solid-State Circuits Letters

JF - IEEE Solid-State Circuits Letters

M1 - 9097891

ER -

A Shortest Path Finding Time-Based Accelerator Core with Built-in Gravity Control and Buffer Zone for Smooth 3-D Navigation

Abstract

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this