skip to main content
10.1145/1068009.1068223acmconferencesArticle/Chapter ViewAbstractPublication PagesgeccoConference Proceedingsconference-collections
Article

From supervised ranking to evolving behaviours of a robotic team

Published: 25 June 2005 Publication History

Abstract

Using artificial evolution successfully to design behaviours of multiple robot systems has been reported in recent years. Most of such reports are focused on the design of low level controllers. Design of high level team coordination strategies is rarely covered perhaps because the design of an appropriate chromosome representation for a complex multi-agent system is not an easy task. In this paper we propose that by treating the action decisions of every team member as a supervised ranking problem, the chromosome design problem can be solved systematically.We have tested this approach by dynamically solving the problems in the Solomon's benchmark of Vehicle Routing Problem with Time Windows [1]. Experiments show that our approach can create some simple behaviours which, whilst not optimal, are robust and above average in quality.

References

[1]
M. Solomon, Algorithms for the Vehicle Routing and Scheduling Problem with Time Window Constraints, Operations Research Vol. 35, pp. 254 -- 365, 1987.
[2]
R. Arkin and T. Balch, Cooperative Multiagent Robotic Systems, in David Kortenkamp, R.P. Bonasso, and R. Murphy, editors, Artificial Intelligence and Mobile Robots. MIT/AAAI Press, Cambridge, MA, 1998.
[3]
M.J. Mataric, Coordination and Learning in Multi-Robot Systems, IEEE Intelligent Systems, pp 6--8, 1998.
[4]
M. Dias and A. Stentz, A Market Approach to Multirobot Coordination, Technical Report, CMU-RI-TR-01-26, Carnegie Mellon University, 2001,
[5]
H. Kitano, S. Tadokoro, I. Noda, H. Matsubara, T. Takahashi, A. Shinjou, and S. Shimada, Robocup rescue: Search and rescue in large-scale disasters as a domain for autonomous agents research, Proc. IEEE Conf. on System, Man and Cybernetics, 1999.
[6]
M. Quinn, A comparison of approaches to the evolution of homogeneous multi-robot teams, Proc. the Congress on Evolutionary Computation (GECCO2001) pp. 128--135, Seoul, S. Korea. IEEE Press, 2001
[7]
H. Liu and H. Iba, Multi-agent Learning of Heterogeneous Robots by Evolutionary Subsumption, Proc. the Congress on Evolutionary Computation (GECCO2003), Chicago, USA. IEEE Press, 2003
[8]
K.W. Tang and R.A. Jarvis, An Evolutionary Computing Approach to Generating Useful and Robust Robot Team Behaviours, Proc. 2004 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp 2081 -- 2086, 2004.
[9]
K. Cao-Van and B. Baets, On the definition and representation of a ranking, Proc. Sixth Int'l. Workshop on Relational Methods in Computer Science, pp. 316 -- 324, 2001.
[10]
J. Grefenstette, R. Gopal, B. Rosmaita and D. Van Gucht, Genetic Algorithms for the TSP, Proc. First Int'l. Conf. on Genetic Algorithms and Their Applications, pp. 168 -- 168, 1985.
[11]
E. Zitzler and L. Thiele, Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach, IEEE Transactions on Evolutionary Computation Vol. 3, No. 4, pp. 257 -- 271, 1999.

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computation
June 2005
2272 pages
ISBN:1595930108
DOI:10.1145/1068009
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 June 2005

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. chromosome representation
  2. free market-based architectural approach
  3. supervised ranking
  4. team coordination strategy

Qualifiers

  • Article

Conference

GECCO05
Sponsor:

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 232
    Total Downloads
  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media