CaltechAUTHORS
  A Caltech Library Service

Efficiency and Robustness of Threshold-Based Distributed Allocation Algorithms in Multi-Agent Systems

Agassounon, William and Martinoli, Alcherio (2002) Efficiency and Robustness of Threshold-Based Distributed Allocation Algorithms in Multi-Agent Systems. In: Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 3 (AAMAS '02). Vol.3. ACM , New York, NY, pp. 1090-1097. ISBN 1-58113-480-0. https://resolver.caltech.edu/CaltechAUTHORS:20160414-162952720

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20160414-162952720

Abstract

In this paper we present three scalable, fully distributed, threshold-based algorithms for allocating autonomous embodied workers to a given task whose demand evolves dynamically over time. Individuals estimate the availability of work based solely on local perceptions. The differences among the algorithms lie in the threshold distribution among teammates (homogeneous or heterogeneous team), in the mechanism used for establishing threshold values (fixed, parameter-based or variable, rule-based), and in the sharing (public) or not sharing (private) of demand estimations through local peer-to-peer communication. We tested the algorithms’ efficiency and robustness in a collective manipulation case study concerned with the clustering of initially scattered small objects. The aggregation experiment has been studied at two different experimental levels using a microscopic model and embodied simulations. Results show that teams using a number of active workers dynamically controlled by one of the allocation algorithms achieve similar or better performances in aggregation than those characterized by a constant team size while using on average a considerably reduced number of agents over the whole aggregation process. While differences in efficiency among the algorithms are small, differences in robustness are much more apparent. Threshold variability and peer-to-peer communication appear to be two key mechanisms for improving worker allocation robustness against environmental perturbations.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1145/545056.545077DOIPaper
http://dl.acm.org/citation.cfm?doid=545056.545077PublisherPaper
Additional Information:© 2002 ACM. Special thanks to Xiaofeng Li for helping to collect systematic simulation data. This work is supported in part by the TRW Foundation and the TRW Space and Technology Division. Further funding was received from the Caltech Center for Neuromorphic Systems Engineering as part of the NSF Engineering Research Center program under grant EEC-9402726.
Funders:
Funding AgencyGrant Number
TRW FoundationUNSPECIFIED
TRW Space and Technology DivisionUNSPECIFIED
NSFEEC-9402726
Center for Neuromorphic Systems Engineering, CaltechUNSPECIFIED
Subject Keywords:Algorithms, Performance, Reliability, Experimentation, Swarm intelligence, division of labor, response threshold, probabilistic modeling, embodied multi-agent systems
Classification Code:J.2 [Computer Applications]: Physical Science and Engineering – engineering, electronics, mathematics and statistics.
DOI:10.1145/545056.545077
Record Number:CaltechAUTHORS:20160414-162952720
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20160414-162952720
Official Citation:William Agassounon and Alcherio Martinoli. 2002. Efficiency and robustness of threshold-based distributed allocation algorithms in multi-agent systems. In Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 3 (AAMAS '02). ACM, New York, NY, USA, 1090-1097. DOI=http://dx.doi.org/10.1145/545056.545077
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:66198
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:16 Apr 2016 17:53
Last Modified:10 Nov 2021 23:54

Repository Staff Only: item control page