Task inference and distributed task management in the Centibots robotic system

ABSTRACT

We describe the Centibots system, a very large scale distributed robotic system, consisting of more than 100 robots, that has been successfully deployed in large, unknown indoor environments, over extended periods of time (i.e., durations corresponding to several power cycles). Unlike most multiagent systems, the set of tasks about which teams must collaborate is not given a priori. We first describe a task inference algorithm that identifies potential team commitments that collectively balance constraints such as reachability, sensor coverage, and communication access. We then describe a dispatch algorithm for task distribution and management that assigns resources depending on either task density or replacement requirements stemming from failures or power shortages. The targeted deployment environments are expected to lack a supporting communication infrastructure; robots manage their own network and reason about the concomitant localization constraints necessary to maintain team communication. Finally, we present quantitative results in terms of a "search and rescue problem" and discuss the team-oriented aspects of the system in the context of prevailing theories of multiagent collaboration.

REFERENCES

• 1: Ronald C. Arkin, An Behavior-based Robotics, MIT Press, Cambridge, MA, 1998
• 2: Jérôme Barraquand , Bruno Langlois , Jean-Claude Latombe, Robot motion planning with many degrees of freedom and dynamic constraints, The fifth international symposium on Robotics research, p.435-444, February 1991
• 3: Maxim A. Batalin and Gaurav S. Sukhatmen. Coverage, exploration, and deployment by a mobile robot and communication network. Telecommunication Systems, Special Issue on Wireless Sensor Networks, 26(2):181--196, 2004.
• 4: W. Keith Edwards, Core Jini, Prentice Hall PTR, Upper Saddle River, NJ, 1999
• 5: Barbara J. Grosz , Sarit Kraus, Collaborative plans for complex group action, Artificial Intelligence, v.86 n.2, p.269-357, Oct. 1996 [doi>10.1016/0004-3702(95)00103-4]
• 6: Andrew Howard, Maja J. Mataric, and Gaurav Sukhatme. An incremental self-deployment algorithm for mobile sensor networks.
• 7: Andrew Howard, Lynne E. Parker, and Gaurav S. Sukhatme. The sdr experience: Experiments with a large-scale heterogenous mobile robot team (extended abstract). In 9th International Symposium on Experimental Robotics 2004, Singapore, Jun 2004.
• 8: Boyoon Jung , Gaurav S. Sukhatme, Tracking Targets Using Multiple Robots: The Effect of Environment Occlusion, Autonomous Robots, v.13 n.3, p.191-205, November 2002 [doi>10.1023/A:1020598107671]
• 9: James Kennedy , Russell C. Eberhart, Swarm intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 10: K. Ko, B. Stewart, D. Fox. K. Konolige, and B. Limketkai. A practical, decision-theoretic approach to multi-robot mapping and exploration. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, 2003.
• 11: Kurt Konolige. A gradient method for realtime robot control. In Proceedings of IROS, 2000.
• 12: Kurt Konolige, Karen Myers, Enrique Ruspini, and Alessandro Saffiotti. The saphira architecture: A design for autonomy. Journal of Experimental and Theoretical AI, 1996.
• 13: Victor Lesser , Milind Tambe , Charles L. Ortiz, Distributed Sensor Networks: A Multiagent Perspective, Kluwer Academic Publishers, Norwell, MA, 2003
• 14: R. G. Ogier, F. L. Templin, and M. G. Lewis. Topology dissemination based on reverse-path forwarding, February 2004. IETF RFC 3684 (Experimental).
• 15: Charles L. Ortiz, Jr. , Eric Hsu, Structured negotiation, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 3, July 15-19, 2002, Bologna, Italy [doi>10.1145/545056.545102]
• 16: C. L. Ortiz, A. Agno, P. Berry, and R. Vincent. Multilevel adaptation in teams of unmanned air and ground vehicles. In Proceedings of the First AIAA Unmanned Aerospace Vehicles, Systems, Technologies and Operations Conference and Workshop, 2002.
• 17: David V. Pynadath , Milind Tambe, An Automated Teamwork Infrastructure for Heterogeneous Software Agents and Humans, Autonomous Agents and Multi-Agent Systems, v.7 n.1-2, p.71-100, July-September 2003 [doi>10.1023/A:1024176820874]
• 18: A. Saffiotti, E. H. Ruspini, and K. Konolige. Integrating reactivity and goal-directedness in a fuzzy controller. In Proceedings of the 2nd Fuzzy-IEEE Conference, 1993.
• 19: A. Saffiotti, N. B. Zumel, and E. H. Ruspini. Multirobot team coordination using desirabilities. In In Proc. of the 6th Int. Conf on Intelligent Autonomous Systems (IAS), July 2000.
• 20: Régis Vincent , Pauline Berry , Andrew Agno , Charlie Ortiz , David Wilkins, Teambotica: a robotic framework for integrated teaming, tasking, networking, and control, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860841]
• 21: D. E. Wilkins, T. Lee, and P. Berry. Interactive execution monitoring of agent teams. Journal of Artificial Intelligence Research, 18:217--261, March 2003.
• 22: O. Yadgar, S. Kraus, and C. Ortiz. Scaling up distributed sensor networks: cooperative large-scale mobile-agent organizations, pages 185--218. Kluwer publishing, 2003.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.9 Robotics

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

General Terms:
Algorithms, Experimentation, Management, Performance

Keywords:
autonomous robots and robot teams, mobile agents, teamwork