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.

Preview

PDF (Preprint submission) elsarticle-template-num.pdf - Submitted Version Download (788kB) | 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.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 - 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:	Jacques Penders
Date Deposited:	27 Sep 2011 15:45
Last Modified:	18 Mar 2021 06:10
URI:	https://shura.shu.ac.uk/id/eprint/3876

Actions (login required)

View Item

Downloads

Publication Metrics