Dynamic graph-based search in unknown environments

Article English OPEN
Haynes, Paul ; Alboul, Lyuba ; Penders, Jacques (2012)
  • Publisher: Elsevier
  • Journal: Journal of Discrete Algorithms, volume 12, pages 2-13 (issn: 1570-8667)
  • Related identifiers: doi: 10.1016/j.jda.2011.06.004
  • Subject: Theoretical Computer Science | Computational Theory and Mathematics | Discrete Mathematics and Combinatorics

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.
  • References (17)
    17 references, page 1 of 2

    [1] Alboul, L. S., Abdul-Rahman, H., Haynes, P. S., Penders, J., An approach to multi-robot site exploration based on principles of selforganization,Intelligent Robotics and Applications - Third International Conference, ICIRA 2010, Shanghai, China, November 10-12, 2010. Proceedings, Part II, LNCS 6425, pp. 717-729, Springer, 2010.

    [2] Haynes, P. S., Alboul, L. S., 2011. Hamiltonian Walks in Embedded Planar Graphs, In preparation.

    [3] Alboul, L. and Echeveria, G. and Rodrigues, M., 2004. Curvature criteria to fit curves to discrete data. EWCG 19th European Workshop on Computational Geometry.

    [4] Baker, B. S, 1994. Approximation algorithms for NP-complete problems on planar graphs. Journal of the Association for Computing Machinery, 41:1, pp. 153-180.

    [5] Tutte, W. T., 1956. A theorem on planar graphs. Transactions of American Mathematical Society, 82, pp. 99-116.

    [6] Tutte, W. T., 1977. Bridges and Hamiltonian circuits in planar graphs. Aequationes Mathematica, 15, pp. 1-33.

    [7] Gerkey, B., Mataric, M., Multi-robot task allocation: Analyzing the complexity and optimality of key architectures. In: Proc. of the IEEE International Conference on Robotics and Automation (ICRA) (2003).

    [8] Bailey, T.; Durrant-Whyte, H., Simultaneous localization and mapping (SLAM): part II,. IEEE Robotics and Automation Magazine, V.13(3), pp. 108-117.

    [9] Dieter Fox, Wolfram Burgard, Hannes Kruppa, and Sebastian Thrun, A probabilistic approach to collaborative multi-robot localization. Autonomous Robots, 8(3):325-344, 2000.

    [10] Fox, D., Ko, J., Konolige, K., Limketkai, B., Schulz, and D., Stewart, B.: Distributed Multirobot Exploration and Mapping. Proceedings of the IEEE, Vol. 94, No. 7, pp. 1325-1339, (2006).

  • Metrics
    No metrics available
Share - Bookmark