Advanced Search

Journal Navigation

Journal Home

Subscriptions

Archive

Contact Us

Table of Contents

CiteULike is a free service for managing and discovering scholarly references - click here to get started.

Sign In to gain access to subscriptions and/or personal tools.
Adaptive Behavior
This Article
Right arrow Abstract Freely available
Right arrow Free Full Text (Free PDF) Free
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Right arrow Citation Map
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to Saved Citations
Right arrow Download to citation manager
Right arrowRequest Permissions
Right arrow Request Reprints
Right arrow Add to My Marked Citations
Citing Articles
Right arrow Citing Articles via Google Scholar
Right arrow Citing Articles via Scopus
Google Scholar
Right arrow Articles by Schermerhorn, P.
Right arrow Articles by Scheutz, M.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Complore   Add to Connotea   Add to Del.icio.us   Add to Digg   Add to Reddit   Add to Technorati   Add to Twitter  
What's this?

Investigating the Adaptiveness of Communication in Multi-Agent Behavior Coordination

Paul Schermerhorn

Cognitive Science Program and School of Informatics, Indiana University, Bloomington, IN 47406, USA, pscherme{at}indiana.edu

Matthias Scheutz

Cognitive Science Program and School of Informatics, Indiana University, Bloomington, IN 47406, USA, mscheutz{at}cse.nd.edu

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).

Key Words: communicating agents • behavior coordination • cost tradeoffs

References

  • 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.
  • Applegate, D., Cook, W., Dash, S., & Rohe, A. (2002). Solution of a min-max vehicle routing problem. INFORMS Journal on Computing, 14, 132—143.[Abstract/Free Full Text]
  • 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.
  • 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.
  • 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.
  • 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.[Abstract]
  • 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.
  • Cooper, R., DeJong, D.V., Forsythe, R., & Ross, T.W. (1992). Communication in coordination games. The Quarterly Journal of Economics, 107, 739—771.[CrossRef]
  • Cormen, T.T., Leiserson, C.E., & Rivest, R.L. (1990). Introduction to algorithms. Cambridge, MA: MIT Press.
  • Dornhaus, A., & Chittka, L. (2004). Why do honey bees dance? Behavioral Ecology and Sociobiology, 55, 396—401.
  • Emerson, S., & Boyd, S. (1999). Mating vocalizations of female frogs: control and evolution mechanisms. Brain, Behavior and Evolution, 53, 187—197.[CrossRef][Web of Science][Medline] [Order article via Infotrieve]
  • Estlin, T., Rabideau, G., Mutz, D., & Chien, S. (2000). Using continuous planning techniques to coordinate multiple rovers. Electronic Transactions on Artificial Intelligence, 4, 45—57.
  • Gavish, B., & Srikanth, K. (1986). An optimal solution method for large-scale multiple traveling salesmen problems. Operations Research, 34, 698—717.[Abstract/Free Full Text]
  • Gervasi, V., & Prencipe, G. (2004). Coordination without communication: The case of the flocking problem. Discrete Applied Mathematics, 143, 203—223.
  • Golden, B., Bodin, L., Doyle, T., & Stewart, W., Jr., (1980). Approximate traveling salesman algorithms. Operations Research, 28, 694—711.[Abstract/Free Full Text]
  • Grim, P., Kokalis, T., Tafti, A., & Kilb, N. (2002). Evolution of communication with a spatialized genetic algorithm. Evolution of Communication, 3, 105—134.
  • 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.
  • Levin, M. (1995). The evolution of understanding: A genetic algorithm model of the evolution of communication. BioSystems, 35, 167—178.[CrossRef][Web of Science][Medline] [Order article via Infotrieve]
  • 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.
  • Marocco, D., Cangelosi, A., & Nolfi, S. (2003). The emergence of communication in evolutionary robots. Philosophical Transactions: Mathematical, Physical and Engineering Sciences, 361, 2397—2421.[CrossRef]
  • McLister, J. (2001). Physical factors affecting the cost and efficiency of sound production in the treefrog Hyla versicolor. Journal of Experimental Biology, 204, 69—80.
  • 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.[CrossRef][Web of Science][Medline] [Order article via Infotrieve]
  • Miller, J.H., Butts, C.T., & Rode, D. (2002). Communication and cooperation. Journal of Economic Behavior and Organization, 47, 179—195.[CrossRef]
  • Miller, J.H., & Moser, S. (2003). Communication and coordination. Working Paper 03-03-019, Santa Fe Institute, Santa Fe, New Mexico.
  • 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.
  • 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 of Experimental Biology, 202, 1831—1838.
  • Noble, J. (1999). Cooperation, conflict and the evolution of communication. Adaptive Behavior, 7, 349—370.[Abstract/Free Full Text]
  • 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.
  • 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.
  • 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.
  • Reynolds, C.W. (1987). Flocks, herds, and schools: A distributed behavioral model. Computer Graphics, 21, 25—34.[CrossRef]
  • 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.
  • 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.[CrossRef]
  • 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.
  • 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.
  • Shen, J-X., Xu, Z-M., & Hankes, E. (1998). Direct homing behavior in the ant Tetramorium caespitum (Formicidae, Myrmicinae). Animal Behavior, 55, 1443—1450.[CrossRef][Web of Science][Medline] [Order article via Infotrieve]
  • 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.
  • Thompson, P.M., & Psaraftis, H.N. (1993). Cyclic transfer algorithms for multivehicle routing and scheduling problems. Operations Research, 41, 935—946.[Abstract/Free Full Text]
  • Wang, H., & Xue, D. (2002). An intelligent zone-based delivery scheduling approach. Computers in Industry, 48, 109— 125.[CrossRef][Web of Science]
  • Werger, B.B. (1999). Cooperation without deliberation: a minimal behavior-based approach to multi-robot teams. Artificial Intelligence, 110, 293—320.[CrossRef][Web of Science]

Adaptive Behavior, Vol. 15, No. 4, 423-445 (2007)
DOI: 10.1177/1059712307084690
Add to CiteULike CiteULike   Add to Complore Complore   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us   Add to Digg Digg   Add to Reddit Reddit   Add to Technorati Technorati   Add to Twitter Twitter    What's this?



This Article
Right arrow Abstract Freely available
Right arrow Free Full Text (Free PDF) Free
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Right arrow Citation Map
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to Saved Citations
Right arrow Download to citation manager
Right arrowRequest Permissions
Right arrow Request Reprints
Right arrow Add to My Marked Citations
Citing Articles
Right arrow Citing Articles via Google Scholar
Right arrow Citing Articles via Scopus
Google Scholar
Right arrow Articles by Schermerhorn, P.
Right arrow Articles by Scheutz, M.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Complore   Add to Connotea   Add to Del.icio.us   Add to Digg   Add to Reddit   Add to Technorati   Add to Twitter  
What's this?