Anchor Selection for SLAM Based on Graph Topology and Submodular Optimization

Chen, Y; Zhao, L; Zhang, Y; Huang, S; Dissanayake, G

Anchor Selection for SLAM Based on Graph Topology and Submodular Optimization

Chen, Y

Zhao, L

Zhang, Y Huang, S

Dissanayake, G

Permalink

Publisher:: IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
Publication Type:: Journal Article
Citation:: IEEE Transactions on Robotics, 2022, 38, (1), pp. 329-350
Issue Date:: 2022-01-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Download Accepted versionAdobe PDF (8.1 MB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Chen, Y https://orcid.org/0000-0003-2756-7050
dc.contributor.author	Zhao, L https://orcid.org/0000-0003-4063-8183
dc.contributor.author	Zhang, Y
dc.contributor.author	Huang, S https://orcid.org/0000-0002-6124-4178
dc.contributor.author	Dissanayake, G https://orcid.org/0000-0002-7992-0680
dc.date.accessioned	2023-03-09T05:14:58Z
dc.date.available	2023-03-09T05:14:58Z
dc.date.issued	2022-01-01
dc.identifier.citation	IEEE Transactions on Robotics, 2022, 38, (1), pp. 329-350
dc.identifier.issn	1552-3098
dc.identifier.issn	1941-0468
dc.identifier.uri	http://hdl.handle.net/10453/166812
dc.description.abstract	This article considers simultaneous localization and mapping (SLAM) problem for robots in situations where accurate estimates for some of the robot poses, termed anchors, are available. These may be acquired through external means, for example, by either stopping the robot at some previously known locations or pausing for a sufficient period of time to measure the robot poses with an external measurement system. The main contribution is an efficient algorithm for selecting a fixed number of anchors from a set of potential poses that minimizes estimated error in the SLAM solution. Based on a graph-topological connection between the D-optimality design metric and the tree-connectivity of the pose-graph, the anchor selection problem can be formulated approximately as a submatrix selection problem for reduced weighted Laplacian matrix, leading to a cardinality-constrained submodular maximization problem. Two greedy methods are presented to solve this submodular optimization problem with a performance guarantee. These methods are complemented by Cholesky decomposition, approximate minimum degree permutation, order reuse, and rank-1 update that exploit the sparseness of the weighted Laplacian matrix. We demonstrate the efficiency and effectiveness of the proposed techniques on public-domain datasets, Gazebo simulations, and real-world experiments.
dc.language	English
dc.publisher	IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
dc.relation	http://purl.org/au-research/grants/arc/DP200100982
dc.relation.ispartof	IEEE Transactions on Robotics
dc.relation.isbasedon	10.1109/TRO.2021.3078333
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	0801 Artificial Intelligence and Image Processing, 0906 Electrical and Electronic Engineering, 0913 Mechanical Engineering
dc.subject.classification	Industrial Engineering & Automation
dc.title	Anchor Selection for SLAM Based on Graph Topology and Submodular Optimization
dc.type	Journal Article
utslib.citation.volume	38
utslib.for	0801 Artificial Intelligence and Image Processing
utslib.for	0906 Electrical and Electronic Engineering
utslib.for	0913 Mechanical Engineering
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/Strength - RI - Robotics Institute
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Mechanical and Mechatronic Engineering
utslib.copyright.status	open_access	*
pubs.consider-herdc	false
dc.date.updated	2023-03-09T05:14:56Z
pubs.issue	1
pubs.publication-status	Published
pubs.volume	38
utslib.citation.issue	1

Abstract:

This article considers simultaneous localization and mapping (SLAM) problem for robots in situations where accurate estimates for some of the robot poses, termed anchors, are available. These may be acquired through external means, for example, by either stopping the robot at some previously known locations or pausing for a sufficient period of time to measure the robot poses with an external measurement system. The main contribution is an efficient algorithm for selecting a fixed number of anchors from a set of potential poses that minimizes estimated error in the SLAM solution. Based on a graph-topological connection between the D-optimality design metric and the tree-connectivity of the pose-graph, the anchor selection problem can be formulated approximately as a submatrix selection problem for reduced weighted Laplacian matrix, leading to a cardinality-constrained submodular maximization problem. Two greedy methods are presented to solve this submodular optimization problem with a performance guarantee. These methods are complemented by Cholesky decomposition, approximate minimum degree permutation, order reuse, and rank-1 update that exploit the sparseness of the weighted Laplacian matrix. We demonstrate the efficiency and effectiveness of the proposed techniques on public-domain datasets, Gazebo simulations, and real-world experiments.

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

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