Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Haynes, Paul; Alboul, Lyuba; Penders, Jacques (2012)
Publisher: Elsevier
Journal: Journal of Discrete Algorithms
Languages: English
Types: Article
Subjects: 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
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [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).
    • [11] Howard, A., Mataric, M. J., Sukhatme, G. S.: Localization for mobile robot teams: A distributed MLE approach. In Experimental Robotics VIII, ser. Advanced Robotics Series, 146-166, (2002).
    • [12] Rekleitis, I., Dudek, G., and Milios, E. : Multi-robot collaboration for robust exploration, Annals of Mathematics and Artificial Intelligence, Vol. 31, pp. 7-40, (2001).
    • [13] Ludwig, L., Gini, M.: Robotic Swarm Dispersion Using Wireless Intensity Signals. In: Distributed Autonomous Robotic Systems 7, pages 135-144. Springer Japan, 2007.
    • [14] Mesbahi, M., Egerstedt, M., Graph Theoretical Methods in Multiagent Networks. Princeton University Press, 2010.
    • [15] Rekleitis, I., Dudek, G., and Milios, E. : Multi-robot collaboration for robust exploration, Annals of Mathematics and Artificial Intelligence, Vol. 31, pp. 7-40, (2001).
    • [16] Kurazume, K. R., Hirose, S.: An experimental study of a cooperative positioning system. Autonomous Robots, 8(1):4352, 2000.
    • [17] Vlassis, N., Papakonstantinou, G., and Tsanakas, P.: Robot Map Building by Kohonen's Self-Organizing Neural Networks. In Proc. 1st Mobinet Symposium on Robotics for Health, (1997).
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article