Dynamic Detection of Topological Information from Grid-Based Generalized Voronoi Diagrams
Joint Authors
Yin, Quanjun
Qin, Long
Peng, Yong
Zha, Yabing
Source
Mathematical Problems in Engineering
Issue
Vol. 2013, Issue 2013 (31 Dec. 2013), pp.1-11, 11 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2013-11-25
Country of Publication
Egypt
No. of Pages
11
Main Subjects
Abstract EN
In the context of robotics, the grid-based Generalized Voronoi Diagrams (GVDs) are widely used by mobile robots to represent their surrounding area.
Current approaches for incrementally constructing GVDs mainly focus on providing metric skeletons of underlying grids, while the connectivity among GVD vertices and edges remains implicit, which makes high-level spatial reasoning tasks impractical.
In this paper, we present an algorithm named Dynamic Topology Detector (DTD) for extracting a GVD with topological information from a grid map.
Beyond the construction and reconstruction of a GVD on grids, DTD further extracts connectivity among the GVD edges and vertices.
DTD also provides efficient repair mechanism to treat with local changes, making it work well in dynamic environments.
Simulation tests in representative scenarios demonstrate that (1) compared with the static algorithms, DTD generally makes an order of magnitude improvement regarding computation times when working in dynamic environments; (2) with negligible extra computation, DTD detects topologies not computed by existing incremental algorithms.
We also demonstrate the usefulness of the resulting topological information for high-level path planning tasks.
American Psychological Association (APA)
Qin, Long& Yin, Quanjun& Zha, Yabing& Peng, Yong. 2013. Dynamic Detection of Topological Information from Grid-Based Generalized Voronoi Diagrams. Mathematical Problems in Engineering،Vol. 2013, no. 2013, pp.1-11.
https://search.emarefa.net/detail/BIM-1031895
Modern Language Association (MLA)
Qin, Long…[et al.]. Dynamic Detection of Topological Information from Grid-Based Generalized Voronoi Diagrams. Mathematical Problems in Engineering No. 2013 (2013), pp.1-11.
https://search.emarefa.net/detail/BIM-1031895
American Medical Association (AMA)
Qin, Long& Yin, Quanjun& Zha, Yabing& Peng, Yong. Dynamic Detection of Topological Information from Grid-Based Generalized Voronoi Diagrams. Mathematical Problems in Engineering. 2013. Vol. 2013, no. 2013, pp.1-11.
https://search.emarefa.net/detail/BIM-1031895
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1031895