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 - Accepted Version
Download (868kB) | 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 \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: 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: Lyuba Alboul
    Date Deposited: 12 Aug 2011 10:29
    Last Modified: 13 Mar 2013 10:56
    URI: http://shura.shu.ac.uk/id/eprint/3755

    Actions (login required)

    View Item


    Downloads per month over past year

    View more statistics