A scalable sampling-based optimal path planning approach via search space reduction

Lu, W; Liu, D

A scalable sampling-based optimal path planning approach via search space reduction

Lu, W

Liu, D

Permalink

Publication Type:: Journal Article
Citation:: IEEE Access, 2019, 7 pp. 153921 - 153935
Issue Date:: 2019-01-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Published VersionAdobe PDF (2.3 MB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Lu, W https://orcid.org/0000-0003-1677-3633	en_US
dc.contributor.author	Liu, D https://orcid.org/0000-0002-1581-5582	en_US
dc.date.issued	2019-01-01	en_US
dc.identifier.citation	IEEE Access, 2019, 7 pp. 153921 - 153935	en_US
dc.identifier.uri	http://hdl.handle.net/10453/137865
dc.description.abstract	© 2013 IEEE. Many sampling strategies in Sampling-Based Planning (SBP) often consider goal and obstacle population and may however become less efficient in large and cluttered 3D environments with a goal distanced away. This paper presents a search-space-Reduced optimal SBP approach (RSBP) for a rigid body. This reduced space is found by a sparse search tree, which is enabled by a Metric Function (MF) built on a neural network. The offline-learnt MF estimates the minimum traveling cost between any two nodes in a fixed small workspace with various obstacles. It allows connections of two sparse nodes without path planning, where the connections represent the traveling costs (not paths). It is proven that the asymptotic optimality is preserved in the RSBP (assuming a zero-error MF) and the optimality degeneration is bounded (assuming a bounded-error MF). The computational complexity during planning is shown linear to the Lebesgue measure of the entire search space (assuming the same sampling density across environments). Numerical simulations have shown that in tested large and cluttered environments the RSBP is at least as fast as the bidirectional fast marching tree∗ and informed rapidly exploring random tree∗, with planned paths of similar optimality. The results also have shown the RSBP's improved scalability to large environments and enhanced efficiency in dealing with narrow passages.	en_US
dc.relation	http://purl.org/au-research/grants/arc/LP150100935
dc.relation.ispartof	IEEE Access	en_US
dc.relation.isbasedon	10.1109/ACCESS.2019.2948976	en_US
dc.rights	info:eu-repo/semantics/openAccess
dc.title	A scalable sampling-based optimal path planning approach via search space reduction	en_US
dc.type	Journal Article
utslib.citation.volume	7	en_US
utslib.for	0801 Artificial Intelligence and Image Processing	en_US
utslib.for	0906 Electrical and Electronic Engineering	en_US
utslib.for	08 Information and Computing Sciences	en_US
utslib.for	09 Engineering	en_US
utslib.for	10 Technology	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Mechanical and Mechatronic Engineering
pubs.organisational-group	/University of Technology Sydney/Strength - CAS - Centre for Autonomous Systems
utslib.copyright.status	open_access	*
pubs.publication-status	Published	en_US
pubs.volume	7	en_US

Abstract:

© 2013 IEEE. Many sampling strategies in Sampling-Based Planning (SBP) often consider goal and obstacle population and may however become less efficient in large and cluttered 3D environments with a goal distanced away. This paper presents a search-space-Reduced optimal SBP approach (RSBP) for a rigid body. This reduced space is found by a sparse search tree, which is enabled by a Metric Function (MF) built on a neural network. The offline-learnt MF estimates the minimum traveling cost between any two nodes in a fixed small workspace with various obstacles. It allows connections of two sparse nodes without path planning, where the connections represent the traveling costs (not paths). It is proven that the asymptotic optimality is preserved in the RSBP (assuming a zero-error MF) and the optimality degeneration is bounded (assuming a bounded-error MF). The computational complexity during planning is shown linear to the Lebesgue measure of the entire search space (assuming the same sampling density across environments). Numerical simulations have shown that in tested large and cluttered environments the RSBP is at least as fast as the bidirectional fast marching tree∗ and informed rapidly exploring random tree∗, with planned paths of similar optimality. The results also have shown the RSBP's improved scalability to large environments and enhanced efficiency in dealing with narrow passages.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/137865