Article

Tunably decentralized algorithms for cooperative target observation

Authors:

Keith Sullivan,

Gabriel BalanAuthors Info & Claims

AAMAS '05: Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems

Pages 911 - 917

https://doi.org/10.1145/1082473.1082611

Published: 25 July 2005 Publication History

Abstract

Multi-agent problem domains may require distributed algorithms for a variety of reasons: local sensors, limitations of communication, and availability of distributed computational resources. In the absence of these constraints, centralized algorithms are often more efficient, simply because they are able to take advantage of more information. We introduce a variant of the cooperative target observation domain which is free of such constraints. We propose two algorithms, inspired by K-means clustering and hill-climbing respectively, which are scalable in degree of decentralization. Neither algorithm consistently outperforms the other across over all problem domain settings. Surprisingly, we find that hill-climbing is sensitive to degree of decentralization, while K-means is not. We also experiment with a combination of the two algorithms which draws strength from each.

References

[1]

T. Balch. Behavioral Diversity in Learning Robot Teams. PhD thesis, College of Computing, Georgia Institute of Technology, 1998.

Digital Library

[2]

Y. Bar-Shalom, editor. Multitarget-multisensor Tracking. Artech House, 1990.

[3]

R. Beckers, O. E. Holland, and J.-L. Deneubourg. From local actions to global tasks: Stigmergy and collective robotics. In Artificial Life IV: Proceedings of the International Workshop on the Synthesis and Simulation of Living Systems, third edition. MIT Press, 1994.

[4]

A. Billard, A. Ijspeert, and A. Martinoli. A multi-robot system for adaptive exploration of a fast changing environment: Probabilistic modeling and experimental study. Connection Science, 11:359--379, 1999.

[5]

S. S. Blackman. Multiple-Target Tracking with Radar Applications. Artech House, 1986.

[6]

T. S. Dahl, M. J. Mataric, and G. S. Sukhatme. Adaptive spatio-temporal organization in groups of robots. In Proceedings of the 2002 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS-02), 2002.

[7]

J. L. Deneubourg, S. Goss, N. Franks, A. Sendova-Franks, C. Detrain, and L. Chretien. The dynamics of collective sorting: Robot-like ants and ant-like robots. In From Animals to Animats: Proceedings of the First International Conference on Simulation of Adaptive Behavior, pages 356--363. MIT Press, 1991.

Digital Library

[8]

D. Fox, W. Burgard, H. Kruppa, and S. Thrun. A probabilistic approach to collaborative multi-robot localization. Autonomous Robots, 8(3):325--344, 2000.

Digital Library

[9]

A. J. Ijspeert, A. Martinoli, A. Billard, and L. M. Gambardella. Collaboration through the exploitation of local interactions in autonomous collective robotics: The stick pulling experiment. Autonomous Robots, 11(2), 2001.

Digital Library

[10]

S. LaValle, H. Gonzalez-Banos, C. Becker, and J. Latombe. Motion strategies for maintaining visibility of a moving target. In Proceedings of IEEE International Conference on Robotics and Automation, 1997.

[11]

L. Li, A. Martinoli, and Y. S. Abu-Mostafa. Diversity and specialization in collaborative swarm systems. In T. Balch and C. Anderson, editors, Proceedings of the 2nd International Workshop on the Mathematics and Algorithms of Social Insects, pages 91--98, Atlanta, Georgia, USA, Dec. 15--17 2003.

[12]

S. Luke, G. C. Balan, L. A. Panait, C. Cioffi-Revilla, and S. Paus. MASON: a Java multi-agent simulation library. In Proceedings of Agent 2003 Conference on Challenges in Social Simulation, 2003.

[13]

A. Martinoli and F. Mondada. Collective and cooperative group behaviours: Biologically inspired experiments in robotics. In Proceedings of the Fourth Symposium on Experimental Robotics, ISER-95, 1995.

Digital Library

[14]

M. J. Mataric. Interaction and Intelligent Behavior. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, 1994. Also Technical Report AITR-1495.

Digital Library

[15]

L. Parker. Alliance: An architecture for fault tolerance multi-robot cooperation. AIEEE Transactions on Robotics and Automation, 14(2), 1998.

[16]

L. Parker. Distributed algorithms for multi-robot observation of multiple moving targets. Autonomous Robots, 12(3):231--255, 2002.

Digital Library

[17]

L. Parker and B. Emmons. Cooperative multi-robot observation of multiple moving targets. In Proceedings of 1997 International Conference on Robotics and Automation, pages 2082--2089, 1997.

[18]

L. Parker and C. Touzet. Multi-robot learning in a cooperative observation task. In J. B. Lynne Pakers, George Bekey, editor, Robotic Systems 4, pages 391--401. Springer, 2000.

[19]

C. Touzet. Robot awareness in cooperative mobile robot learning. Autonomous Robots, 2:1--13, 2000.

Digital Library

[20]

B. B. Werger and M. Mataric. Broadcast of local eligibility for multi-target observation. In Proceedings, 5th International Symposium on Distributed Autonomous Robotic Systems (DARS), pages 347--356, 2000.

Cited By

Zhang ZLi YXu JWang Z(2024)Simultaneous Search and Tracking of Non-cooperative Mobile Targets Using Multiple UAVs in Uneven EnvironmentsInternational Journal of Aeronautical and Space Sciences10.1007/s42405-024-00750-4Online publication date: 24-May-2024
https://doi.org/10.1007/s42405-024-00750-4
Engel A(2024)Multi‐objective Multi‐agent Decision‐MakingSystems Science for Engineers and Scholars10.1002/9781394211678.ch17(391-409)Online publication date: Mar-2024
https://doi.org/10.1002/9781394211678.ch17
Araújo MDa Costa Lde Campos GNogueira Y(2023)Smart Organizations of Unmanned Aerial Vehicles Using SOMs for Monitoring Cars on Urban Roads2023 Latin American Robotics Symposium (LARS), 2023 Brazilian Symposium on Robotics (SBR), and 2023 Workshop on Robotics in Education (WRE)10.1109/LARS/SBR/WRE59448.2023.10332968(83-88)Online publication date: 9-Oct-2023
https://doi.org/10.1109/LARS/SBR/WRE59448.2023.10332968
Show More Cited By

Index Terms

Tunably decentralized algorithms for cooperative target observation
1. Computing methodologies
  1. Artificial intelligence
    1. Distributed artificial intelligence
  2. Modeling and simulation
2. Mathematics of computing
  1. Probability and statistics

Recommendations

DIC-DOC-K-means: Dissimilarity-based Initial Centroid selection for DOCument clustering using K-means for improving the effectiveness of text document clustering

In this article, a new initial centroid selection for a K-means document clustering algorithm, namely, Dissimilarity-based Initial Centroid selection for DOCument clustering using K-means (DIC-DOC-K-means), to improve the performance of text document ...
Inter cluster distance management model with optimal centroid estimation for K-means clustering algorithm

Clustering techniques are used to group up the transactions based on the relevancy. Cluster analysis is one of the primary data analysis method. The clustering process can be done in two ways such that Hierarchical clusters and partition clustering. ...
K-means clustering versus validation measures: a data-distribution perspective

K-means is a well-known and widely used partitional clustering method. While there are considerable research efforts to characterize the key features of the K-means clustering algorithm, further investigation is needed to understand how data ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

AAMAS '05: Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems

July 2005

1407 pages

ISBN:1595930930

DOI:10.1145/1082473

Program Chairs:
Michal Pechoucek
Czech Republic
,
Donald Steiner
USA
,
Simon Thompson
UK

Copyright © 2005 ACM.

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

SIGAI: ACM Special Interest Group on Artificial Intelligence

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 July 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

AAMAS05

Sponsor:

SIGAI

AAMAS05: AAMAS '05 - Fourth International Joint Conference on Autonomous Agents and Multiagent Systems 2005

July 25 - 29, 2005

The Netherlands

Acceptance Rates

Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
501
Total Downloads

Downloads (Last 12 months)31
Downloads (Last 6 weeks)1

Reflects downloads up to 29 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang ZLi YXu JWang Z(2024)Simultaneous Search and Tracking of Non-cooperative Mobile Targets Using Multiple UAVs in Uneven EnvironmentsInternational Journal of Aeronautical and Space Sciences10.1007/s42405-024-00750-4Online publication date: 24-May-2024
https://doi.org/10.1007/s42405-024-00750-4
Engel A(2024)Multi‐objective Multi‐agent Decision‐MakingSystems Science for Engineers and Scholars10.1002/9781394211678.ch17(391-409)Online publication date: Mar-2024
https://doi.org/10.1002/9781394211678.ch17
Araújo MDa Costa Lde Campos GNogueira Y(2023)Smart Organizations of Unmanned Aerial Vehicles Using SOMs for Monitoring Cars on Urban Roads2023 Latin American Robotics Symposium (LARS), 2023 Brazilian Symposium on Robotics (SBR), and 2023 Workshop on Robotics in Education (WRE)10.1109/LARS/SBR/WRE59448.2023.10332968(83-88)Online publication date: 9-Oct-2023
https://doi.org/10.1109/LARS/SBR/WRE59448.2023.10332968
Zammit Cvan Kampen E(2021)Comparison Between A* and RRT Algorithms for 3D UAV Path PlanningUnmanned Systems10.1142/S230138502250007810:02(129-146)Online publication date: 8-Oct-2021
https://doi.org/10.1142/S2301385022500078
Araujo MAndrade JDa Silva Junior TDa Costa LJunior RMelo GDa Silva DDe Campos G(2021)Cooperative Observation of Malicious Targets in a 3D Urban Traffic Environment Using UAVs2021 Latin American Robotics Symposium (LARS), 2021 Brazilian Symposium on Robotics (SBR), and 2021 Workshop on Robotics in Education (WRE)10.1109/LARS/SBR/WRE54079.2021.9605390(60-65)Online publication date: 11-Oct-2021
https://doi.org/10.1109/LARS/SBR/WRE54079.2021.9605390
da Silva TAraújo MFerro Junior Rda Costa LAndrade Jde Campos G(2021)Intelligent Agents for Observation and Containment of Malicious Targets OrganizationsIntelligent Systems10.1007/978-3-030-91702-9_4(48-63)Online publication date: 28-Nov-2021
https://doi.org/10.1007/978-3-030-91702-9_4
Kalra BMunnangi SMajmundar KManwani NParuchuri P(2021)Cooperative Monitoring of Malicious Activity in Stock ExchangesTrends and Applications in Knowledge Discovery and Data Mining10.1007/978-3-030-75015-2_13(121-132)Online publication date: 3-May-2021
https://doi.org/10.1007/978-3-030-75015-2_13
Franca da Silva TSantos Araujo MCampos Ferro Junior RFerreira da Costa LBernardino Andrade JLima de Campos GCelestino Junior J(2020)Improving the Behavior of Evasive Targets in Cooperative Target Observation2020 IEEE 44th Annual Computers, Software, and Applications Conference (COMPSAC)10.1109/COMPSAC48688.2020.00015(36-41)Online publication date: Jul-2020
https://doi.org/10.1109/COMPSAC48688.2020.00015
Andrade Jda Silva TJunior RMaia Jde Campos G(2020)Cooperative Target Observation using Density-based Clustering with Self-tuning and a New Grid Environment2020 XLVI Latin American Computing Conference (CLEI)10.1109/CLEI52000.2020.00011(33-38)Online publication date: Oct-2020
https://doi.org/10.1109/CLEI52000.2020.00011
Araújo Mda Silva TSampaio VMelo GJunior Rda Costa LAndrade Jde Campos G(2020)Cooperative Observation of Smart Target AgentsIntelligent Systems10.1007/978-3-030-61380-8_6(77-92)Online publication date: 13-Oct-2020
https://doi.org/10.1007/978-3-030-61380-8_6
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents