More Web Proxy on the site http://driver.im/

research-article

Accelerating RRT Motion Planning Using TCAM

Authors:

Yinhe HanAuthors Info & Claims

GLSVLSI '20: Proceedings of the 2020 on Great Lakes Symposium on VLSI

Pages 481 - 486

https://doi.org/10.1145/3386263.3406948

Published: 07 September 2020 Publication History

Abstract

Real-time motion planning is important for robot movement. In motion planning, path search and collision detection are two performance bottlenecks. In this paper, we adopt a range-based matching scheme with ternary content-addressable memories (TCAMs) to accelerate the processes of both nearest neighbor search and collision detection. In our approach, the nearest node search and collision detection can be both processed in a few TCAM lookup cycles. The evaluation shows that the TCAM-based accelerator is 236× faster than CPU for motion planning tasks. It is 5.4× faster and at least 8.8× more energy-efficient than a state-of-the-art dedicated ASIC-based accelerator.

Supplementary Material

MP4 File (3386263.3406948.mp4)

Presentation video

Download
46.14 MB

References

[1]

J. Pan, C. Lauterbach and D. Manocha, "g-Planner: Real-time motion planning and global navigation using GPUs," in AAAI, 2010.

[2]

J. Bialkowski, S. Karaman and E. Frazzoli, "Massively parallelizing the RRT and the RRT?," in IROS, 2011.

[3]

J. Pan and D. Manocha, "GPU-based parallel collision detection for fast motion planning," IJRR, 31(2): 187--200, 2012.

Digital Library

[4]

A. Hermann, F. Drews, J. Bauer, S. Klemm, A. Roennau, and R. Dillmann, "Unified GPU voxel collision detection for mobile manipulation planning," IROS, 2014.

[5]

S. Murray, W. Floyd-Jones, Y. Qi, D. Sorin and G. Konidaris, "The microarchitecture of a real-time robot motion planning accelerator," in MICRO, 2016.

[6]

S. Lian, Y. Han, X. Chen, Y. Wang and H. Xiao, "Dadu-P: a scalable accelerator for robot motion planning in a dynamic environment," in DAC, 2018.

[7]

S. Xiao, A. Postula, and N. Bergmann, "Optimal random sampling based path planning on FPGAs," in FPL, 2016.

[8]

S. Xiao, N. Bergmann and A. Postula, "Parallel RRT* architecture design for motion planning," in FPL, 2017.

[9]

L. E. Kavraki, P. Svestka, J. C. Latombe and M. H. Overmars, "Probabilistic roadmaps for path planning in high-dimensional con?guration spaces," TRA, 12(4):566--580, 1996.

[10]

S. M. LaValle. "Rapidly-exploring random trees: A new tool for path planning." Report 1998.

[11]

S. Karaman and E. Frazzoli, "Sampling-based algorithms for optimal motion planning," IJRR, 30(7): 846--894, 2011.

Digital Library

[12]

A. B.-Barr, Y. Harchol, D. Hay and Y. H.-Or, "Encoding short ranges in TCAM without expansion: efficient algorithm and applications," IEEE/ACM Transactions On Networking, 26(2):835--850, 2018.

Digital Library

[13]

M. Chang et al., "A 3T1R Nonvolatile TCAM Using MLC ReRAM for Frequent-Off Instant-On Filters in IoT and Big-Data Processing," in IEEE Journal of Solid-State Circuits, vol. 52, no. 6, pp. 1664--1679, June 2017.

[14]

P. Leven and S. Hutchinson, "A framework for real-time path planning in changing environments," IJRR, 21(12):999--1030, 2002.

[15]

J. D. Gammell, S. S. Srinivasa, and T. D. Barfoot, "Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic," in IROS, 2014.

[16]

J. D. Gammell, S. S. Srinivasa and T. D. Barfoot, "Batch Informed Trees (BIT*): Sampling-based optimal planning via the heuristically guided search of implicit random geometric graphs," in ICRA, 2015.

[17]

K. Hauser, "Lazy collision checking in asymptotically-optimal motion planning," in ICRA, 2015.

[18]

V. Ravikumar and R. N. Mahapatra, "TCAM architecture for IP lookup using prefix properties," Micro, IEEE, 24(2):60--69, 2004.

Digital Library

[19]

J. Ritter. "An Efficient Bounding Sphere," in Graphics Gems, Academic Press: 301--303, 1990.

[20]

G. Bergen, "Efficient Collision Detection of Complex Deformable Models using AABB Trees," Journal of Graphics Tools, 2(4):1--13, 1997.

Digital Library

[21]

S. Gottschalk, M. C. Lin, D. Manocha, "OBB-Tree: A Hierarchical Structure for Rapid Interference Detection," in SIGGRAPH, 1996.

[22]

I. A. Sucan, M. Moll and L. E. Kavraki, "The Open Motion Planning Library," in IEEE Robotics & Automation Magazine, 19(4):72--82, 2012.

[23]

R. Alterovitz, S. Patil, and A. Derbakova. "Rapidly-exploring roadmaps: Weighing exploration vs. refinement in optimal motion planning," in ICRA, 2011.

Cited By

Huang LGong YSui YZang XYuan B(2024)MOPED: Efficient Motion Planning Engine with Flexible Dimension Support2024 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA57654.2024.00043(483-497)Online publication date: 2-Mar-2024
https://doi.org/10.1109/HPCA57654.2024.00043
Yang YChen XHan Y(2023)Dadu-RBD: Robot Rigid Body Dynamics Accelerator with Multifunctional PipelinesProceedings of the 56th Annual IEEE/ACM International Symposium on Microarchitecture10.1145/3613424.3614298(297-309)Online publication date: 28-Oct-2023
https://dl.acm.org/doi/10.1145/3613424.3614298

Index Terms

Accelerating RRT Motion Planning Using TCAM
1. Hardware
  1. Integrated circuits
    1. Reconfigurable logic and FPGAs
      1. Hardware accelerators

Recommendations

Energy-Efficient Realtime Motion Planning
ISCA '23: Proceedings of the 50th Annual International Symposium on Computer Architecture

Motion planning is a fundamental problem in autonomous robotics with real-time and low-energy requirements for safe navigation through a dynamic environment. More than 90% of computation time in motion planning is spent on collision detection between ...
Motion-Driven Action-Based Planning
ICTAI '13: Proceedings of the 2013 IEEE 25th International Conference on Tools with Artificial Intelligence

Achievement of robotic goals generally needs both plan synthesis and plan execution through physical motions. Costs of actions in robotic tasks are generally motiondependent. Generally there are many action-based plans for achieving a goal and usually ...
AM-RRT*: An Automatic Robot Motion Planning Algorithm Based on RRT
Neural Information Processing
Abstract
Motion planning is a very important part of robot technology, where the quality of planning directly affects the energy consumption and safety of robots. Focusing on the shortcomings of traditional RRT methods such as long, unsmooth paths, and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

GLSVLSI '20: Proceedings of the 2020 on Great Lakes Symposium on VLSI

September 2020

597 pages

ISBN:9781450379441

DOI:10.1145/3386263

General Chairs:
Tinoosh Mohsenin
University of Maryland, Baltimore County, USA
,
Weisheng Zhao
Beihang University, China
,
Program Chairs:
Yiran Chen
Duke University, USA
,
Onur Mutlu
ETH Zurich, Switzerland

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 September 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GLSVLSI '20

GLSVLSI '20: Great Lakes Symposium on VLSI 2020

September 7 - 9, 2020

Virtual Event, China

Acceptance Rates

Overall Acceptance Rate 312 of 1,156 submissions, 27%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
193
Total Downloads

Downloads (Last 12 months)24
Downloads (Last 6 weeks)4

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Huang LGong YSui YZang XYuan B(2024)MOPED: Efficient Motion Planning Engine with Flexible Dimension Support2024 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA57654.2024.00043(483-497)Online publication date: 2-Mar-2024
https://doi.org/10.1109/HPCA57654.2024.00043
Yang YChen XHan Y(2023)Dadu-RBD: Robot Rigid Body Dynamics Accelerator with Multifunctional PipelinesProceedings of the 56th Annual IEEE/ACM International Symposium on Microarchitecture10.1145/3613424.3614298(297-309)Online publication date: 28-Oct-2023
https://dl.acm.org/doi/10.1145/3613424.3614298

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents