Efficient nearest-neighbor computation for GPU-based motion planning

Jia Pan; Christian Lauterbach; Dinesh Manocha

doi:10.1109/IROS.2010.5651449

Efficient nearest-neighbor computation for GPU-based motion planning

Jia Pan
, Christian Lauterbach
, Dinesh Manocha

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

45 Citations (Scopus)

Abstract

We present a novel k-nearest neighbor search algorithm (KNNS) for proximity computation in motion planning algorithm that exploits the computational capabilities of many-core GPUs. Our approach uses locality sensitive hashing and cuckoo hashing to construct an efficient KNNS algorithm that has linear space and time complexity and exploits the multiple cores and data parallelism effectively. In practice, we see magnitude improvement in speed and scalability over prior GPU-based KNNS algorithm. On some benchmarks, our KNNS algorithm improves the performance of overall planner by 20-40 times for CPU-based planner and up to 2 times for GPU-based planner. ©2010 IEEE.

Original language	English
Title of host publication	IEEE/RSJ 2010 International Conference on Intelligent Robots and Systems, IROS 2010 - Conference Proceedings
Pages	2243-2248
DOIs	https://doi.org/10.1109/IROS.2010.5651449
Publication status	Published - 2010
Externally published	Yes
Event	23rd IEEE/RSJ 2010 International Conference on Intelligent Robots and Systems, IROS 2010 - Taipei, Taiwan, China Duration: 18 Oct 2010 → 22 Oct 2010

Conference

Conference	23rd IEEE/RSJ 2010 International Conference on Intelligent Robots and Systems, IROS 2010
Place	Taiwan, China
City	Taipei
Period	18/10/10 → 22/10/10

Access Output

10.1109/IROS.2010.5651449

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@inproceedings{c9b9344a6f63453d86bb957d342f791a,

title = "Efficient nearest-neighbor computation for GPU-based motion planning",

abstract = "We present a novel k-nearest neighbor search algorithm (KNNS) for proximity computation in motion planning algorithm that exploits the computational capabilities of many-core GPUs. Our approach uses locality sensitive hashing and cuckoo hashing to construct an efficient KNNS algorithm that has linear space and time complexity and exploits the multiple cores and data parallelism effectively. In practice, we see magnitude improvement in speed and scalability over prior GPU-based KNNS algorithm. On some benchmarks, our KNNS algorithm improves the performance of overall planner by 20-40 times for CPU-based planner and up to 2 times for GPU-based planner. {\textcopyright}2010 IEEE.",

author = "Jia Pan and Christian Lauterbach and Dinesh Manocha",

year = "2010",

doi = "10.1109/IROS.2010.5651449",

language = "English",

isbn = "9781424466757",

pages = "2243--2248",

booktitle = "IEEE/RSJ 2010 International Conference on Intelligent Robots and Systems, IROS 2010 - Conference Proceedings",

note = "23rd IEEE/RSJ 2010 International Conference on Intelligent Robots and Systems, IROS 2010 ; Conference date: 18-10-2010 Through 22-10-2010",

}

Pan, J, Lauterbach, C & Manocha, D 2010, Efficient nearest-neighbor computation for GPU-based motion planning. in IEEE/RSJ 2010 International Conference on Intelligent Robots and Systems, IROS 2010 - Conference Proceedings., 5651449, pp. 2243-2248, 23rd IEEE/RSJ 2010 International Conference on Intelligent Robots and Systems, IROS 2010, Taipei, Taiwan, China, 18/10/10. https://doi.org/10.1109/IROS.2010.5651449

Efficient nearest-neighbor computation for GPU-based motion planning. / Pan, Jia; Lauterbach, Christian; Manocha, Dinesh.
IEEE/RSJ 2010 International Conference on Intelligent Robots and Systems, IROS 2010 - Conference Proceedings. 2010. p. 2243-2248 5651449.

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Efficient nearest-neighbor computation for GPU-based motion planning

AU - Pan, Jia

AU - Lauterbach, Christian

AU - Manocha, Dinesh

PY - 2010

Y1 - 2010

N2 - We present a novel k-nearest neighbor search algorithm (KNNS) for proximity computation in motion planning algorithm that exploits the computational capabilities of many-core GPUs. Our approach uses locality sensitive hashing and cuckoo hashing to construct an efficient KNNS algorithm that has linear space and time complexity and exploits the multiple cores and data parallelism effectively. In practice, we see magnitude improvement in speed and scalability over prior GPU-based KNNS algorithm. On some benchmarks, our KNNS algorithm improves the performance of overall planner by 20-40 times for CPU-based planner and up to 2 times for GPU-based planner. ©2010 IEEE.

AB - We present a novel k-nearest neighbor search algorithm (KNNS) for proximity computation in motion planning algorithm that exploits the computational capabilities of many-core GPUs. Our approach uses locality sensitive hashing and cuckoo hashing to construct an efficient KNNS algorithm that has linear space and time complexity and exploits the multiple cores and data parallelism effectively. In practice, we see magnitude improvement in speed and scalability over prior GPU-based KNNS algorithm. On some benchmarks, our KNNS algorithm improves the performance of overall planner by 20-40 times for CPU-based planner and up to 2 times for GPU-based planner. ©2010 IEEE.

UR - https://www.scopus.com/pages/publications/78651473585

UR - https://www.scopus.com/pages/publications/78651473585#tab=impact

U2 - 10.1109/IROS.2010.5651449

DO - 10.1109/IROS.2010.5651449

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9781424466757

SP - 2243

EP - 2248

BT - IEEE/RSJ 2010 International Conference on Intelligent Robots and Systems, IROS 2010 - Conference Proceedings

T2 - 23rd IEEE/RSJ 2010 International Conference on Intelligent Robots and Systems, IROS 2010

Y2 - 18 October 2010 through 22 October 2010

ER -

Efficient nearest-neighbor computation for GPU-based motion planning

Abstract

Conference

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this