Dynamic graph-based search in unknown environments

HAYNES, Paul, ALBOUL, Lyuba and PENDERS, Jacques (2012). Dynamic graph-based search in unknown environments. Journal of Discrete Algorithms, 12, 2-13.

PDF (Preprint submission)
elsarticle-template-num.pdf - Submitted Version

Download (788kB) | Preview
Link to published version:: 10.1016/j.jda.2011.06.004


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.nH) time complexity, where nH is the number of vertices of the discovered environment and 1 <= k <= nH. A maximum bound on the length of the resulting walk is given.

Item Type: Article
Research Institute, Centre or Group: Materials and Engineering Research Institute > Centre for Automation and Robotics Research > Mobile Machine and Vision Laboratory
Identification Number: 10.1016/j.jda.2011.06.004
Depositing User: Jacques Penders
Date Deposited: 27 Sep 2011 15:45
Last Modified: 19 Aug 2015 16:34
URI: http://shura.shu.ac.uk/id/eprint/3876

Actions (login required)

View Item View Item


Downloads per month over past year

View more statistics