More Web Proxy on the site http://driver.im/

research-article

Modeling Robot Swarms Using Integrals of Birth-Death Processes

Authors:

Marco DorigoAuthors Info & Claims

ACM Transactions on Autonomous and Adaptive Systems (TAAS), Volume 11, Issue 2

Article No.: 8, Pages 1 - 16

https://doi.org/10.1145/2870637

Published: 06 June 2016 Publication History

Abstract

This article investigates the use of the integral of linear birth-death processes in the context of analyzing swarm robotics systems. We show that when a robot swarm can be modeled as a linear birth-death process, well-established results can be used to compute the expected value and/or the distribution of important swarm performance measures, such as the swarm activity time or the swarm energy consumption. We also show how the linear birth-death model can be used to estimate the long-term value of such performance measures and design robot controllers that satisfy constraints on these measures.

References

[1]

N. Bailey. 1990. The Elements of Stochastic Processes With Applications to the Natural Sciences. Wiley, New York, NY.

[2]

F. Ball and V. Stefanov. 2001. Further approaches to computing fundamental characteristics of birth-death processes. Journal of Applied Probability 38, 4, 995--1005.

[3]

S. Berman. 2010. Abstractions, Analysis Techniques, and Synthesis of Scalable Control Strategies for Robot Swarms. Ph.D. Dissertation. Department of Mechanical Engineering and Applied Mechanics, University of Pennsylvania.

[4]

M. Brambilla, E. Ferrante, M. Birattari, and M. Dorigo. 2013. Swarm robotics: A review from the swarm engineering perspective. Swarm Intelligence 7, 1, 1--41.

[5]

A. Campo and M. Dorigo. 2007. Efficient multi-foraging in swarm robotics. In Advances in Artificial Life. Springer, Berlin, Germany, 696--705.

Digital Library

[6]

F. Crawford and M. Suchard. 2012. Transition probabilities for general birth-death processes with applications in ecology, genetics, and evolution. Journal of Mathematical Biology, 553--580.

[7]

P. Flajolet and F. Guillemin. 2000. The formal theory of birth-and-death processes, lattice path combinatorics and continued fractions. Advances in Applied Probability 32, 3, 750--778.

[8]

J. Gani and D. Jerwood. 1972. The cost of a general stochastic epidemic. Journal of Applied Probability 9, 2, 257--269.

[9]

E. Gjondrekaj, M. Loreti, R. Pugliese, F. Tiezzi, C. Pinciroli, M. Brambilla, M. Birattari, and M. Dorigo. 2012. Towards a formal verification methodology for collective robotic systems. In Formal Methods and Software Engineering. Springer, Berlin, Germany, 54--70.

Digital Library

[10]

H. Hamann. 2010. Space-Time Continuous Models of Swarm Robotic Systems: Supporting Global-to-Local Programming. Vol. 9. Springer, Berlin, Germany.

Digital Library

[11]

H. Hamann, G. Valentini, Y. Khaluf, and M. Dorigo. 2014. Derivation of a micro-macro link for collective decision-making systems: Uncover network features based on drift measurements. In Parallel Problem Solving from Nature—PPSN XIII. Lecture Notes in Computer Science, Vol. 8672. Springer, 181--190.

[12]

J. Hereford. 2010. Analysis of a new swarm search algorithm based on trophallaxis. In Proceedings of the 2010 IEEE Congress on Evolutionary Computation (CEC’10). IEEE, Los Alamitos, CA, 1--8.

[13]

M. Hernández-Suárez and C. Castillo-Chavez. 1999. A basic result on the integral for birth-death Markov processes. Mathematical Biosciences 161, 1--2, 95--104.

[14]

D. Jerwood. 1970. A note on the cost of the simple epidemic. Journal of Applied Probability 7, 2, 440--443.

[15]

Y. Khaluf, M. Birattari, and H. Hamann. 2014. A swarm robotics approach to task allocation under soft deadlines and negligible switching costs. In From Animals to Animats 13. Lecture Notes in Computer Science, Vol. 8575. Springer, 270--279.

[16]

Y. Khaluf, M. Birattari, and F. Rammig. 2013. Probabilistic analysis of long-term swarm performance under spatial interferences. In Theory and Practice of Natural Computing. Lecture Notes in Computer Science, Vol. 8273. Springer, 121--132.

[17]

K. Lerman, A. Galstyan, A. Martinoli, and A. Ijspeert. 2001. A macroscopic analytical model of collaboration in distributed robotic systems. Artificial Life 7, 4, 375--393.

Digital Library

[18]

W. Liu and A. Winfield. 2010. Modeling and optimization of adaptive foraging in swarm robotic systems. International Journal of Robotics Research 29, 14, 1743--1760.

Digital Library

[19]

M. Mangel and C. Tier. 1994. Four facts every conservation biologist should know about persistence. Ecology 75, 3, 607--614.

[20]

A. Martinoli, K. Easton, and W. Agassounon. 2004. Modeling swarm robotic systems: A case study in collaborative distributed manipulation. International Journal of Robotics Research 23, 4--5, 415--436.

[21]

A. Martinoli, A. Ijspeert, and L. Gambardella. 1999. A probabilistic model for understanding and comparing collective aggregation mechanisms. In Advances in Artificial Life. Springer, Berlin, Germany, 575--584.

Digital Library

[22]

T. Mather and M. Hsieh. 2011. Distributed robot ensemble control for deployment to multiple sites. In Robotics: Science and Systems, H. F. Durrant-Whyte, N. Roy, and P. Abbeel (Eds.). MIT Press, Los Angeles, CA, 201--208.

[23]

P. Moran. 1959. The Theory of Storage. Methuen Ltd, London, UK.

[24]

C. Pinciroli, V. Trianni, R. O’Grady, G. Pini, A. Brutschy, M. Brambilla, N. Mathews, E. Ferrante, G. Di Caro, Frederick F. Ducatelle, M. Birattari, L. Gambardella, and M. Dorig. 2012. ARGoS: A modular, parallel, multi-engine simulator for multi-robot systems. Swarm Intelligence 6, 4, 271--295.

[25]

P. Pollett. 2003. Integrals for continuous-time Markov chains. Mathematical Biosciences 182, 2, 213--225.

[26]

P. Pollett and V. Stefanov. 2002. Path integrals for continuous-time Markov chains. Journal of Applied Probability 39, 901--904.

[27]

S. Puri. 1967. A class of stochastic models of response after infection in the absence of defense mechanism. In Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, Vol. 4. 511--535.

[28]

S. Ross. 2006. Introduction to Probability Models (8th ed). Academic Press.

[29]

F. Shaw and E. Klavins. 2008. Distributed estimation and control for stochastically interacting robots. In Proceedings of the 47th IEEE Conference on Decision and Control. IEEE, Los Alamitos, CA, 1895--1901.

[30]

O. Soysal and E. Şahin. 2006. A macroscopic model for self-organized aggregation in swarm robotic systems. In Swarm Robotics. Lecture Notes in Computer Science, Vol. 4433. Springer, 27--42.

Digital Library

[31]

V. Stefanov. 1995. Mean passage times for tridiagonal transition matrices. Journal of Applied Probability 32, 3, 846--849.

[32]

V. Stefanov and S. Wang. 2000. A note on integrals for birth--death processes. Mathematical Biosciences 168, 2, 161--165.

[33]

G. Valentini and H. Hamann. 2015. Time-variant feedback processes in collective decision-making systems: Influence and effect of dynamic neighborhood sizes. Swarm Intelligence 9, 2--3, 153--176.

[34]

B. Varghese and G. McKee. 2010. A mathematical model, implementation and study of a swarm system. Robotics and Autonomous Systems 58, 3, 287--294.

Digital Library

[35]

A. Winfield, W. Liu, J. Nembrini, and A. Martinoli. 2008. Modelling a wireless connected swarm of mobile robots. Swarm Intelligence 2, 2--4, 241--266.

[36]

A. Winfield and J. Nembrini. 2006. Safety in numbers: Fault-tolerance in robot swarms. International Journal of Modelling, Identification and Control 1, 1, 30--37.

[37]

J. Yeh. 2006. Real Analysis: Theory of Measure and Integration. World Scientific, Singapore.

Cited By

dos Passos YDuquesne XMarcolino L(2022)On the Throughput of the Common Target Area for Robotic Swarm StrategiesMathematics10.3390/math1014248210:14(2482)Online publication date: 16-Jul-2022
https://doi.org/10.3390/math10142482
Rausch ISimoens PKhaluf Y(2020)Adaptive Foraging in Dynamic Environments Using Scale-Free Interaction NetworksFrontiers in Robotics and AI10.3389/frobt.2020.000867Online publication date: 9-Jul-2020
https://doi.org/10.3389/frobt.2020.00086
Li HTan JHe H(2020)MagicHand: Context-Aware Dexterous Grasping Using an Anthropomorphic Robotic Hand2020 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA40945.2020.9196538(9895-9901)Online publication date: May-2020
https://doi.org/10.1109/ICRA40945.2020.9196538
Show More Cited By

Index Terms

Modeling Robot Swarms Using Integrals of Birth-Death Processes
1. Computer systems organization
  1. Embedded and cyber-physical systems
    1. Robotics
2. Computing methodologies
  1. Artificial intelligence

Recommendations

A fluid queue modulated by two independent birth-death processes

We present a fluid queue model driven by two independent finite state birth-death processes with the objective to study the buffer occupancy distribution in any intermediate node in a communication network. In a communication network, at any node, the ...
The combinatorics of birth–death processes and applications to queues

In this paper we present a combinatorial technique which allows the derivation of the transition functions of general birth-death processes. This method provides a flexible tool for the transient analysis of Markovian queueing systems with state ...
Poisson's equation for discrete-time quasi-birth-and-death processes

We consider Poisson's equation for quasi-birth-and-death processes (QBDs) and we exploit the special transition structure of QBDs to obtain its solutions in two different forms. One is based on a decomposition through first passage times to lower levels,...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Autonomous and Adaptive Systems

ACM Transactions on Autonomous and Adaptive Systems Volume 11, Issue 2

Special Section on Best Papers from SASO 2014 and Regular Articles

July 2016

267 pages

ISSN:1556-4665

EISSN:1556-4703

DOI:10.1145/2952298

Editors:
Manish Parashar
Rutgers University, USA
,
Franco Zambonelli
University of Modena e Reggio Emilia, Italy

Issue’s Table of Contents

Copyright © 2016 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2016

Accepted: 01 December 2015

Revised: 01 October 2015

Received: 01 April 2014

Published in TAAS Volume 11, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

F.R.S.-FNRS of Belgium's French Community
European Research Council under the European Union's Seventh Framework Programme (FP7/2007-2013)/ERC Advance

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
231
Total Downloads

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

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

dos Passos YDuquesne XMarcolino L(2022)On the Throughput of the Common Target Area for Robotic Swarm StrategiesMathematics10.3390/math1014248210:14(2482)Online publication date: 16-Jul-2022
https://doi.org/10.3390/math10142482
Rausch ISimoens PKhaluf Y(2020)Adaptive Foraging in Dynamic Environments Using Scale-Free Interaction NetworksFrontiers in Robotics and AI10.3389/frobt.2020.000867Online publication date: 9-Jul-2020
https://doi.org/10.3389/frobt.2020.00086
Li HTan JHe H(2020)MagicHand: Context-Aware Dexterous Grasping Using an Anthropomorphic Robotic Hand2020 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA40945.2020.9196538(9895-9901)Online publication date: May-2020
https://doi.org/10.1109/ICRA40945.2020.9196538
Khaluf YAllwright MRausch ISimoens PDorigo M(2020)Construction Task Allocation Through the Collective Perception of a Dynamic EnvironmentSwarm Intelligence10.1007/978-3-030-60376-2_7(82-95)Online publication date: 23-Oct-2020
https://doi.org/10.1007/978-3-030-60376-2_7
Rausch IKhaluf YSimoens P(2019)Scale-Free Features in Collective Robot ForagingApplied Sciences10.3390/app91326679:13(2667)Online publication date: 30-Jun-2019
https://doi.org/10.3390/app9132667
Khaluf YSimoens PHamann H(2019)The Neglected Pieces of Designing Collective Decision-Making ProcessesFrontiers in Robotics and AI10.3389/frobt.2019.000166Online publication date: 26-Mar-2019
https://doi.org/10.3389/frobt.2019.00016
Khaluf YSimoens P(2019)Collective Sampling of Environmental Features under Limited Sampling BudgetJournal of Computational Science10.1016/j.jocs.2019.01.005Online publication date: Jan-2019
https://doi.org/10.1016/j.jocs.2019.01.005
Khaluf YVanhee SSimoens P(2019)Local ant system for allocating robot swarms to time-constrained tasksJournal of Computational Science10.1016/j.jocs.2018.12.01231(33-44)Online publication date: Feb-2019
https://doi.org/10.1016/j.jocs.2018.12.012
Khaluf Y(2017)Edge Detection in Static and Dynamic Environments using Robot Swarms2017 IEEE 11th International Conference on Self-Adaptive and Self-Organizing Systems (SASO)10.1109/SASO.2017.17(81-90)Online publication date: Sep-2017
https://doi.org/10.1109/SASO.2017.17

View Options

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents