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)
elsarticle-template-num.pdf - Submitted Version

Download (788kB) | Preview
Link to published version:: https://doi.org/10.1016/j.jda.2011.06.004
Related URLs:

    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 > Centre for Automation and Robotics Research > Mobile Machine and 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: http://shura.shu.ac.uk/id/eprint/3876

    Actions (login required)

    View Item View Item

    Downloads

    Downloads per month over past year

    View more statistics