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.;
  • 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 o... View more
  • 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.

    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.

  • Related Organizations (4)
  • Metrics
Share - Bookmark