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) - Submitted Version |
Download (769kB) | Preview
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.
|Research Institute, Centre or Group:||Materials and Engineering Research Institute > Centre for Robotics and Automation > Mobile Machine and Vision Laboratory|
|Depositing User:||Jacques Penders|
|Date Deposited:||27 Sep 2011 16:45|
|Last Modified:||21 Sep 2012 13:56|
Actions (login required)
Downloads per month over past year