Algorithms for Rapidly Dispersing Robot Swarms in Unknown Environments

Preprint English OPEN
Hsiang, Tien-Ruey ; Arkin, Esther M. ; Bender, Michael ; Fekete, Sandor P. ; Mitchell, Joseph S. B. (2002)
  • Subject: I.2.9 | Computer Science - Robotics

We develop and analyze algorithms for dispersing a swarm of primitive robots in an unknown environment, R. The primary objective is to minimize the makespan, that is, the time to fill the entire region. An environment is composed of pixels that form a connected subset of the integer grid. There is at most one robot per pixel and robots move horizontally or vertically at unit speed. Robots enter R by means of k>=1 door pixels Robots are primitive finite automata, only having local communication, local sensors, and a constant-sized memory. We first give algorithms for the single-door case (i.e., k=1), analyzing the algorithms both theoretically and experimentally. We prove that our algorithms have optimal makespan 2A-1, where A is the area of R. We next give an algorithm for the multi-door case (k>1), based on a wall-following version of the leader-follower strategy. We prove that our strategy is O(log(k+1))-competitive, and that this bound is tight for our strategy and other related strategies.
  • References (30)
    30 references, page 1 of 3

    1. B. Awerbuch, M. Betke, R. L. Rivest, and M. Singh. Piecemeal graph exploration by a mobile robot. In Proc. 8th Annual ACM Conference on Computational Learning Theory, pages 321-328, 1995.

    2. T. Balch. http://www.teambots.org.

    3. T. Balch and R. C. Arkin. Behavior-based formation control for multi-robot teams. IEEE Transactions on Robotics and Automation, 14(6):926-939, 1998.

    4. M. A. Batalin and G. S. Sukhatme. Multi-robot dynamic coverage of a planar bounded environment. Technical report, Robotic Embedded Systems Laboratory, University of Southern California, 2002.

    5. M. A. Batalin and G. S. Sukhatme. Spreading out: A local approach to multirobot coverage. In H. Asama, T. Arai, T. Fukuda, and T. Hasegawa, editors, Proc. 6th International Symposium on Distributed Autonomous Robotic Systems, Fukuoka, Japan, 2002. Springer-Verlag.

    6. O. B. Bayazit, J.-M. Lien, and N. M. Amato. Better flocking behaviors using rule-based roadmaps. In Proc. 5th International Workshop on Algorithmic Foundations of Robotics, 2002.

    7. M. A. Bender, A. FernĀ“andez, D. Ron, A. Sahai, and S. Vadhan. The power of a pebble: Exploring and mapping directed graphs. Information and Computation, 176:1-21, 2002.

    8. M. A. Bender and D. Slonim. The power of team exploration: Two robots can learn unlabeled directed graphs. In Proc. 35th Annual Symposium on Foundations of Computer Science, pages 75-85, 1994.

    9. A. M. Bruckstein, C. L. Mallows, and I. A. Wagner. Probabilistic pursuits on the grid. American Mathematical Monthly, 104(4):323-343, 1997.

    10. X. Deng and C. H. Papadimitriou. Exploring an unknown graph. In Proc. 31st Annual Symposium on Foundations of Computer Science, pages 356-361, 1990.

  • Metrics
    No metrics available
Share - Bookmark