HAYNES, Paul, ALBOUL, Lyuba and PENDERS, Jacques (2012). Dynamic graph-based search in unknown environments. Journal of Discrete Algorithms, 12, 2-13.
![]()
|
PDF
SpecialIssuePaper_subm.pdf - Accepted Version Download (889kB) | Preview |
Abstract
A novel graph-based approach to search in unknown environments is presented. A virtual geometric structure is imposed on the environment represented in computer memory by a graph. Algorithms use this representation to coordinate a team of robots (or entities). Local discovery of environmental features cause dynamic expansion of the graph resulting in global exploration of the unknown environment. The algorithm is shown to have $O(k \cdot n_{H})$ time complexity, where $n_{H}$ is the number of vertices of the discovered environment and $1 \leq k <n_{H}$. A maximum bound on the length of the resulting walk $\Omega$ is given.
Item Type: | Article |
---|---|
Research Institute, Centre or Group - Does NOT include content added after October 2018: | Materials and Engineering Research Institute > Modelling Research Centre > Microsystems and Machine Vision Laboratory |
Identification Number: | https://doi.org/10.1016/j.jda.2011.06.004 |
Page Range: | 2-13 |
Depositing User: | Lyuba Alboul |
Date Deposited: | 12 Aug 2011 09:29 |
Last Modified: | 18 Mar 2021 06:15 |
URI: | https://shura.shu.ac.uk/id/eprint/3755 |
Actions (login required)
![]() |
View Item |
Downloads
Downloads per month over past year