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.

[img]
Preview
PDF (Preprint submission) - Submitted Version
Download (769kB) | Preview
    Link to published version:: 10.1016/j.jda.2011.06.004

    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: Materials and Engineering Research Institute > Centre for Robotics and Automation > Mobile Machine and Vision Laboratory
    Identification Number: 10.1016/j.jda.2011.06.004
    Depositing User: Jacques Penders
    Date Deposited: 27 Sep 2011 16:45
    Last Modified: 21 Sep 2012 13:56
    URI: http://shura.shu.ac.uk/id/eprint/3876

    Actions (login required)

    View Item

    Downloads

    Downloads per month over past year

    View more statistics