Some previous studies of the adaptiveness of communication for coordination have found communication beneficial, others have not. We claim that this results from the lack of a systematic examination of important variables such as communication range, sensory range, and environmental conditions. We present an extensive series of simulations exploring how these parameters effect the utility of communication for coordination in the multi-agent territory exploration (MATE( n)) task. MATE(n) requires agents to visit all checkpoints in the environment in as little time as possible; n agents must be at a checkpoint simultaneously for it to be counted “visited.” A comparison of the absolute performance of communicating and non-communicating agents on MATE(n) (i.e., performance without regard to cost) finds that communication can be beneficial. A subsequent analysis of the results establishes constraints on the cost of communication for it to provide relative performance benefit (i.e., absolute performance scaled by cost).
Ackley, D., & Littman, M. (1991). Altruism in the evolution of communication. In R. Brooks & P. Maes (Eds.), Artificial life IV: Proceedings of the Fourth Workshop on Artificial Life (pp. 40—48). Cambridge, MA: MIT Press.
2.
Applegate, D., Cook, W., Dash, S., & Rohe, A. (2002). Solution of a min-max vehicle routing problem . INFORMS Journal on Computing, 14, 132—143.
3.
Balch, T., & Arkin, R. (1993). Avoiding the past: a simple but effective strategy for reactive navigation. In Proceedings of the 1993 IEEE International Conference on Robotics and Automation, Atlanta, GA (pp. 678—685). Los Alamitos CA: IEEE Computer Society Press.
4.
Bugera, V. (2004). Properties of no-depot min-max 2-traveling-salesmen problem. In S. Butenko, R. Murphey, & P. Pardalos (Eds.), Recent developments in cooperative control and optimization (pp. 45—60). Norwell, MA: Kluwer Academic Publishers.
5.
Cangelosi, A., Riga, T., Giolito, B., & Marocco, D. (2004). Language emergence and grounding in sensorimotor agents and robots. In First International Workshop on Emergence and Evolution of Linguistic Communication, Kanazawa, Japan, May/June 2004 .
6.
Capaldi, E.A., & Dyer, F.C. (1999). The role of orientation flights on homing performance in honeybees. The Journal of Experimental Biology, 202, 1655—1666.
7.
Clement, B.J., & Barrett, A.C. (2003). Continual coordination through shared activities . In Proceedings of the Second International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS `03), Melbourne, Australia (pp. 57—64). New York: ACM Press.
8.
Cooper, R., DeJong, D.V., Forsythe, R., & Ross, T.W. (1992). Communication in coordination games. The Quarterly Journal of Economics, 107, 739—771.
9.
Cormen, T.T., Leiserson, C.E., & Rivest, R.L. (1990). Introduction to algorithms. Cambridge, MA: MIT Press.
10.
Dornhaus, A., & Chittka, L. (2004). Why do honey bees dance?Behavioral Ecology and Sociobiology, 55, 396—401.
11.
Emerson, S., & Boyd, S. (1999). Mating vocalizations of female frogs: control and evolution mechanisms. Brain, Behavior and Evolution, 53, 187—197.
12.
Estlin, T., Rabideau, G., Mutz, D., & Chien, S. (2000). Using continuous planning techniques to coordinate multiple rovers. Electronic Transactions onArtificial Intelligence , 4, 45—57.
13.
Gavish, B., & Srikanth, K. (1986). An optimal solution method for large-scale multiple traveling salesmen problems. Operations Research, 34, 698—717.
14.
Gervasi, V., & Prencipe, G. (2004). Coordination without communication: The case of the flocking problem. DiscreteApplied Mathematics, 143, 203—223.
Grim, P., Kokalis, T., Tafti, A., & Kilb, N. (2002). Evolution of communication with a spatialized genetic algorithm. Evolution ofCommunication, 3, 105—134.
17.
Johnson, D.S., & McGeoch, L.A. (1997). The traveling salesman problem: A case study in local optimization. In E. H. L. Aarts & J. K. Lenstra (Eds.), Local search in combinatorial optimization (pp. 215—310). Hoboken, NJ: John-Wiley and Sons, Ltd.
18.
Levin, M. (1995). The evolution of understanding: A genetic algorithm model of the evolution of communication. BioSystems, 35, 167—178.
19.
MacLennan, B. (1991). Synthetic ethology: An approach to the study of communication. In C. G. Langton, C. Taylor, J. D. Farmer, & S. Rasmussen (Eds.), Artificial life II: Proceedings of the Second Workshop on Artificial Life (pp. 631—658). Redwood City, CA: Addison-Wesley.
20.
Marocco, D., Cangelosi, A., & Nolfi, S. (2003). The emergence of communication in evolutionary robots. Philosophical Transactions: Mathematical, Physical and Engineering Sciences, 361, 2397—2421.
21.
McLister, J. (2001). Physical factors affecting the cost and efficiency of sound production in the treefrog Hyla versicolor. Journal ofExperimental Biology, 204, 69—80.
22.
Menzel, R., Geiger, K., Joerges, J., Müller, U., & Chittka, L. (1998). Bees travel novel homeward routes by integrating separately acquired vector memories. Animal Behavior, 55, 139—152.
23.
Miller, J.H., Butts, C.T., & Rode, D. (2002). Communication and cooperation. Journal of Economic Behavior and Organization, 47, 179—195.
24.
Miller, J.H., & Moser, S. (2003). Communication and coordination. Working Paper 03-03-019, Santa Fe Institute, Santa Fe, New Mexico.
25.
Montemanni, R., Gambardella, L., Rizzoli, A., & Donati, A. (2003). A new algorithm for a dynamic vehicle routing problem based on ant colony system. In Second International Workshop on Freight Transportation and Logistics, Sicily, Italy, May 2003.
26.
Nicholson, D.J., Judd, S.P.D., Cartwright, B.A., & Collett, T.S. (1999). Learning walks and landmark guidance in wood ants (Formica rufa). The Journal ofExperimental Biology, 202, 1831—1838.
27.
Noble, J. (1999). Cooperation, conflict and the evolution of communication . Adaptive Behavior, 7, 349—370.
28.
Noble, J., & Cliff, D. (1996). On simulating the evolution of communication. In P. Maes (Ed.), Proceedings of the Fourth International Conference on Simulation of Adaptive Behavior (pp. 608—617). Cambridge, MA: MIT Press.
29.
Parker, L.E., Kannan, B., Tang, F., & Bailey, M. (2004). Tightly-coupled navigation assistance in heterogeneous multi-robot teams. In Proceedings of IEEE International Conference on Intelligent Robots and Systems (IROS). Los Alamitos, CA: IEEE Computer Society Press.
30.
Rabideau, G., Estlin, T., Chien, S., & Barrett, A. (1999). Working together: Centralized command sequence generation for cooperating rovers. In Proceedings of the IEEE Aerospace Conference (IAC), Rabideau, Aspen, CO, March 1999.
31.
Reynolds, C.W. (1987). Flocks, herds, and schools: A distributed behavioral model. Computer Graphics, 21, 25—34.
32.
Schermerhorn, P., & Scheutz, M. (2005). The effect of environmental structure on the utility of communication in hive-based swarms. In IEEE Swarm Intelligence Symposium 2005 (pp. 440—443). Los Alamitos, CA: IEEE Computer Society Press.
33.
Scheutz, M., & Andronache, V. (2004). Architectural mechanisms for dynamic changes of behavior selection strategies in behavior-based systems . IEEE Transactions of System, Man, and Cybernetics Part B , 34, 2377—2395.
34.
Scheutz, M., & Schermerhorn, P. (2003). Many is more but not too many: Dimensions of cooperation of agents with and without predictive capabilities. In Proceedings of IEEE/ WIC IAT-2003 (pp. 378—384). Los Alamitos, CA: IEEE Computer Society Press.
35.
Scheutz, M., & Schermerhorn, P. (2005). Predicting population dynamics and evolutionary trajectories based on performance evaluations in alife simulations. In Proceedings of GECCO 2005 (pp. 35—42). New York: ACM Press .
36.
Shen, J-X., Xu, Z-M., & Hankes, E. (1998). Direct homing behavior in the ant Tetramorium caespitum (Formicidae, Myrmicinae). Animal Behavior, 55, 1443—1450.
37.
Tang, F., & Parker, L.E. (2005). Asymtre: Automated synthesis of multi-robot task solutions through software reconfiguration. In Proceedings of 2005 IEEE International Conference on Robotics and Automation (ICRA) (pp. 1501— 1508). Los Alamitos, CA: IEEE Computer Society Press.
38.
Thompson, P.M., & Psaraftis, H.N. (1993). Cyclic transfer algorithms for multivehicle routing and scheduling problems. Operations Research, 41, 935—946.
39.
Wang, H., & Xue, D. (2002). An intelligent zone-based delivery scheduling approach. Computers in Industry, 48, 109— 125.
40.
Werger, B.B. (1999). Cooperation without deliberation: a minimal behavior-based approach to multi-robot teams. Artificial Intelligence, 110, 293—320.
