In the world of living creatures, simple-minded animals often cooperate to achieve common goals with amazing performance. One can consider this idea in the context of robotics, and suggest models for programming goal-oriented behavior into the members of a group of simple robots lacking global supervision. This can be done by controlling the local interactions between the robot agents, to have them jointly carry out a given mission. As a test case we analyze the problem of many simple robots cooperating to clean the dirty floor of a non-convex region inZ2, using the dirt on the floor as the main means of inter-robot communication.
Acar, E.U., Zhang, Y., Choset, H., Schervish, M., Costa, A.G., Melamud, R., Lean, D.C. and Gravelin, A. (2001). Path Planning for Robotic Demining and Development of a Test Platform. Proceedings of International Conference on Field and Service Robotics, Helsinki, Finland. 161—168.
2.
Adler, F.R. and Gordon, D.M. (1992). Information collection and spread by networks of partolling agents. The American Naturalist, 140(3): 373—400.
3.
Alami, R., Fleury, S., Herrb, M., Ingrand, F. and Robert, F. (1997). Multi-Robot Cooperation in the Martha Project . IEEE Robotics and Automation Magazine, 5(1): 36—47.
4.
Arai, T., Ogata, H. and Suzuki, T. (1989). Collision Avoidance Among Multiple Robots Using Virtual Impedance. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, 479—485.
5.
Arkin, R.C. (1990). Integrating Behavioral, Perceptual, and World Knowledge in Reactive Navigation. Robotics and Autonomous Systems, 6: 105—122.
6.
Arkin, R.C. and Balch, T. (1997). AuRA: Principles and Practice in Review. Journal of Experimental and Theoretical Artificial Intelligence, 9(2—3): 175—188.
7.
Arkin, R.C. and Balch, T. (1998). Cooperative multi-agent Robotic Systems. Artificial Intelligence and Mobile Robots. MIT/ AAAI Press: Cambridge, MA.
8.
Baeza-Yates, R. and Schott, R. (1995). Parallel Searching in the Plane. ComputationalGeometry, 5 :143—154.
9.
Balch, T. and Arkin, R. (1998). Behavior-Based Formation Control for Multi-Robot Teams. IEEE Transactions on Robotics and Automation, 14(6):926—939.
10.
Batalin, M.A. and Sukhatme, G.S. (2002). Spreading Out: A Local Approach to Multi-Robot Coverage. In Proceedings of 6th International Symposium on Distributed Autonomous Robotics Systems, Fukuoka, Japan.
11.
Benda, M., Jagannathan, V. and Dodhiawalla, R. (1985). On Optimal Cooperation of Knowledge Sources. Technical Report BCS-G2010-28, Boeing AI Center.
12.
Beni, G. and Wang, J. (1991). Theoretical Problems for the Realization of Distributed Robotic Systems. In Proceedings of 1991 IEEE Internal Conference on Robotics and Automation, Sacramento, CA, 1914—1920.
13.
Braitenberg, V. (1984). Vehicles. MIT Press, Cambridge, MA.
14.
Brooks, R.A. (1986). A Robust Layered Control System for a Mobile Robot . IEEE Journal of Robotics and Automation, RA-2(1): 14—23.
15.
Brooks, R.A. (1990). Elephants Don't Play Chess. In Designing Autonomous Agents, P. Maes (ed.) MIT press/Elsevier, Cambridge, MA; 3—15.
16.
Bruckstein, A.M. (1993). Why the Ant Trails Look So Straight and Nice. The Mathematical Intelligencer, 15(2): 59—62.
17.
Bruckstein, A.M., Mallows, C.L. and Wagner, I.A. (1994). Probabilistic Pursuits on the Integer Grid. Technical report CIS-9411, Center for Intelligent Systems, Technion , Haifa.
18.
Butler, Z., Rizzi, A. and Hollis, R. (2001). Distributed Coverage of Rectilinear Environments . In Proceedings of the Workshop on the Algorithmic Foundations of Robotics.
19.
Candea, C., Hu, H., Iocchi, L., Nardi, D. and Piaggio, M. (2001). Coordinating in Multi-Agent RoboCup Teams. Robotics and Autonomous Systems, 36(2—3): 67—86.
20.
Chevallier, D. and Payandeh, S. (2000). On Kinematic Geometry of Multi-Agent Manipulating System Based on the Contact Force Information. In Proceedings of 6th International Conference on Intelligent Autonomous Systems (IAS-6), 188—195.
21.
Conner, D.C., Greenfield, A., Atkar, P.N., Rizzi, A. and Choset, H. (2005). Paint Deposition Modeling for Trajectory Planning on Automotive Surfaces. IEEE Transactions on AutomationScience and Engineering, 2(4): 381—392.
22.
Deneubourg, J., Goss, S., Sandini, G., Ferrari, F. and Dario, P. (1990). Self-Organizing Collection and Transport of Objects in Unpredictable Environments. In Proceedings of Japan-U.S.A. Symposium on Flexible Automation, Kyoto, Japan, 1093—1098.
23.
Dias, M.B. and Stentz, A. (2001). A Market Approach to Multirobot Coordination. Technical Report, CMU-RI-TR-01-26, Robotics Institute, Carnegie Mellon University.
24.
Do-Carmo, M.P. (1976). Differential Geometry of Curves and Surfaces. Prentice-Hall: New Jersey.
25.
Drogoul, A. and Ferber, J. (1992). From Tom Thumb to the Dockers: Some Experiments With Foraging Robots. In Proceedings of the Second International Conference on Simulation of Adaptive Behavior, Honolulu, Hawaii, 451— 459.
26.
Dudek, G., Jenkin, M.R.M., Milios, E. and Wilkes, D. (1996). A taxonomy for multi-agent robotics. Autonomous Robots Journal, 3(4): 375—397.
27.
Ferrari, C., Pagello, E., Ota, J., and Arai, T. (1998). Multirobot Motion Coordination in Space and Time . Robotics and Autonomous Systems, 25: 219—229.
28.
Fredslund, J. and Mataric, M.J. (2001). Robot Formations Using Only Local Sensing and Control. In Proceedings of the International Symposium on Computational Intelligence in Robotics and Automation (IEEE CIRA 2001) , Banff, Alberta, Canada, 308—313.
29.
Gerkey, B.P. and Mataric, M.J. (2002). Sold! Market Methods for Multi-Robot Control. IEEE Transactions on Robotics and Automation, Special Issue on Multi-robotSystems, 18(5): 758—768.
30.
Golfarelli, M., Maio, D. and Rizzi, S. (1997). A Task-Swap Negotiation Protocol Based on the Contract Net Paradigm. Technical Report, 005-97, CSITE (Research Center For Informatics And Telecommunication Systems, associated with the University of Bologna, Italy).
31.
Gordon, D.M. (1995). The expandable network of ant exploration. Animal Behaviour, 50: 372—378.
32.
Gordon, N., Wagner, I.A. and Bruckstein, A.M. (2003). Discrete Bee Dance Algorithms for Pattern Formation on a Grid. In Proceedings of IEEE International Conference on Intelligent Agent Technology (IAT03), 545—549.
33.
Haynes, T. and Sen, S. (1986). Evolving Behavioral Strategies in Predators and Prey. In Adaptation and Learning in Multi-AgentSystems, Weiss G. and Sen S. eds. 113—126.
34.
Hedberg, S. (1995). Robots Cleaning Up Hazardous Waste. AI Expert, 10(5): 20—24.
35.
Held, M. (1991). On the Computational Geometry of Pocket Machining. Lecture Notes in Computer Science. Springer-Verlag, New York, NY.
36.
Henrich, D. (1994). Space Efficient Region Filling in Raster Graphics . The Visual Computer, 10: 205—215.
37.
Itai, A., Papadimitriou, C.H., and Szwarefiter, J.L. (1982). Hamilton Paths in Grid Graphs. SIAM Journal of Computing, 11: 676—686.
38.
Koenig, S. and Szymanski, B. (1999). Value-update rules for real-time search. In Proceedings of the National Conference on Artificial Intelligence, 718—724.
39.
Koenig, S. and Liu, Y. (2001). Terrain Coverage with Ant Robots: A Simulation Study. In Proceedings of 5th International Conference on Autonomous Agents 2001, Montreal, Quebec, Canada, 600—607.
40.
Koenig, S., Szymanski, B. and Liu, Y. (2001). Efficient and inefficient ant coverage methods. Annals of Mathematics andArtificial Intelligence, 31: 41—76.
41.
Latimer, D., Srinivasa, S., Lee-Shue, V., Sonne, S., Choset, H. and Hurst, A. (2002). Toward Sensor Based Coverage with Robot Teams . In Proceedings of The International Society for Optical Engineering (SPIE), 4573: 1—9, Mobile Robots XVI.
42.
LaValle, S.M., Lin, D., Guibas, L.J., Latombe, J.C. and Motwani, R. (1997). Finding an Unpredictable Target in a Workspace with Obstacles. In Proceedings of the 1997 IEEE International Conference on Robotics and Automation (ICRA-97), 737—742.
43.
Levi, S. (1992). Artificial Life — the Quest for a New Creation . Penguin, New York, NY.
44.
Lumelsky, V.J. and Harinarayan, K.R. (1997). Decentralized Motion Planning for Multiple Mobile Robots: The Cocktail Party Model. Autonomous Robots, 4(1): 121—136.
45.
MacKenzie, D., Arkin, R., and Cameron, J. (1997). Multiagent Mission Specification and Execution . Autonomous Robots, 4(1): 29—52.
46.
Mataric, M.J. (1992). Designing Emergent Behaviors: From Local Interactions to Collective Intelligence. In Proceedings of the Second International Conference on Simulation of Adaptive Behavior. Meyer, J., Roitblat, H. and Wilson, S. (eds). MIT Press: Honolulu, Hawaii; 432—441.
47.
Mataric, M.J. (1994). Interaction and Intelligent Behavior. PhD Thesis , Massachusetts Institute of Technology.
48.
Min, T.W. and Yin, H.K. (1998). A Decentralized Approach for Cooperative Sweeping by Multiple Mobile Robots. In Proceedings of 1998 IEEE/RSJ International Conference on Intelligent Robots and Systems, 1: 380—385.
49.
Neubauer, W. (1993). Locomotion with Articulated Legs in Pipes or Ducts . Robotics and Autonomous Systems, 11: 163—169.
50.
Pagello, E., D'Angelo, A., Montesello, F., Garelli, F. and Ferrari, C. (1999). Cooperative Behaviors in Multi-Robot Systems Through Implicit Communication. Robotics and Autonomous Systems, 29(1): 65—77.
51.
Pagello, E., D'Angelo, A., Ferrari, C., Polesel, R., Rosati, R. and Speranzon, A. (2003). Emergent Behaviors of a Robot Team Performing Cooperative Tasks. Advanced Robotics, 17(1): 3—19.
52.
Parker, L.E. (1998). ALLIANCE: An Architecture for Fault-Tolerant Multi-Robot Cooperation. IEEE Transactions on Robotics and Automation , 14(2): 220—240.
53.
Parker, L.E. and Touzet, C. (2000). Multi-Robot Learning in a Cooperative Observation Task. Distributed Autonomous RoboticSystems, 4: 391—401.
54.
Polycarpou, M., Yang, Y. and Passino, K. (2001). A Cooperative Search Framework for Distributed Agents. In Proceedings of the 2001 IEEE International Symposium on Intelligent Control, Mexico City, Mexico. IEEE: New Jersey, 1—6.
55.
Premvuti, S. and Yuta, S. (1990). Consideration on the Cooperation of Multiple Autonomous Mobile Robots. In Proceedings of the IEEE International Workshop of Intelligent Robots and Systems, Tsuchiura, Japan, 59—63.
56.
Rabideau, G., Estlin, T., Chien, T. and Barrett, A. (1999). A Comparison of Coordinated Planning Methods for Cooperating Rovers. In Proceedings of the American Institute of Aeronautics and Astronautics (AIAA) Space Technology Conference .
57.
Rekleitis, I.M., Dudek, G. and Milios, E. (2003). Experiments in Free-Space Triangulation Using Cooperative Localization. In Proceedings of IEEE/RSJ/GI International Conference on Intelligent Robots and Systems (IROS), 2: 1777— 1782.
58.
Rekleitisy, I., Lee-Shuey, V., Peng Newz, A. and Choset, H. (2004). Limited Communication, Multi-Robot Team Based Coverage. In Proceedings of the 2004 IEEE International Conference on Robotics and Automation, New Orleans, LA , 3462—3468.
59.
Russell, R.A. (1993). Mobile Robot Guidance Using a Short-Lived Heat Trail. Robotica, 11: 427—431.
60.
Sen, S., Sekaran, M., Hale, J. (1994). Learning to Coordinate Without Sharing Information . In Proceedings of American Association for Artifical Intelligence1994, 426—431.
61.
Shoham, Y. and Tennenholtz, M. (1995). On Social Laws for Artificial Agent Societies: Off Line Design. Artificial Intelligence, 73(1—2): 231—252.
62.
Simon H.A. (1981). The Sciences of the Artificial. Second Edition. MIT Press, Cambridge, MA.
63.
Smith, R. (1980). The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver. IEEE Transactions on Computers, C-29(12): 1104— 1113.
64.
Steels, L. (1990). Cooperation Between Distributed Agents Through Self-Organization. Decentralized A.I. In Proceedings of the first European Workshop on Modeling Autonomous Agents in Multi-Agents world, DeMazeau, Y., Muller J. P. (eds). 175—196.
65.
Stone, P. and Veloso, M. (1999). Task Decomposition, Dynamic Role Assignment, and Low-Bandwidth Communication for Real-Time Strategic Teamwork. Artificial Intelligence, 110(2): 241—273.
66.
Svennebring, J. and Koenig, S. (2004). Building Terrain-Covering Ant Robots: A Feasibility Study. Autonomous Robots, 16(3): 313—332.
67.
Svestka, P. and Overmars, M.H. (1998). Coordinated Path Planning for Multiple Robots . Robotics and Autonomous Systems, 23(3): 125—152.
68.
Thayer, S.M., Dias, M.B., Digney, B.L., Stentz, A., Nabbe, B. and Hebert, M. (2000). Distributed Robotic Mapping of Extreme Environments . In Proceedings of SPIE, 4195, Mobile Robots XV and Telemanipulator and Telepresence Technologies VII.
69.
Wagner, I.A. and Bruckstein, A.M. (1994). Row Straightening via Local Interactions. Technical report CIS-9406, Center for Intelligent Systems, Technion, Haifa.
70.
Wagner, I.A. and Bruckstein, A.M. (1997). Cooperative Cleaners: A Case of Distributed Ant-Robotics. In Communications, Computation, Control, and Signal Processing: A Tribute to Thomas Kailath. Kluwer Academic Publishers: The Netherlands; 289—308.
71.
Wagner, I.A. and Bruckstein, A.M. (2000). ANTS: agents, networks, trees and subgraphs. Future Generation Computer Systems Journal , 16(8): 915—926.
72.
Wagner, I.A. and Bruckstein, A.M. (2001). From Ants to A(ge)nts: A Special Issue on Ant—Robotics. Annals of Mathematics and Artificial Intelligence, Special Issue on Ant Robotics, 31(1—4): 1—6.
73.
Wagner, I.A., Lindenbaum, M. and Bruckstein, A.M. (1998). Efficiently Searching a Graph by a Smell-Oriented Vertex Process. Annals of Mathematics andArtificial Intelligence, 24: 211—223.
74.
Wang, P.K.C. (1989). Navigation Strategies for Multiple Autonomous Mobile Robots. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 486—493.
75.
Wellman, M.P. and Wurman, P.R. (1998). Market-Aware Agents for a Multiagent World. Robotics and Autonomous Systems, 24: 115—125.
76.
Yamashita, A., Fukuchi, M., Ota, J., Arai, T. and Asama, H. (2000). Motion Planning for Cooperative Transportation of a Large Object by Multiple Mobile Robots in a 3D Environment. In Proceedings of IEEE International Conference on Robotics and Automation , 3144—3151.
77.
Yanovski, V., Wagner, I.A. and Bruckstein, A.M. (2001). Vertex-ants-walk: a robust method for efficient exploration of faulty graphs. Annals of Mathematics andArtificial Intelligence, 31(1—4): 99—112.
78.
Yanovski, V., Wagner, I.A. and Bruckstein, A.M. (2003). A distributed ant algorithm for efficiently patrolling a network. Algorithmica, 37: 165—186.
79.
Zlot, R., Stentz, A., Dias, M.B. and Thayer, S. (2002). MultiRobot Exploration Controlled By A Market Economy. In Proceedings of the IEEE International Conference on Robotics and Automation, 3016—3023.
