[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

Modeling Robot Swarms Using Integrals of Birth-Death Processes

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.
[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.
[10]
H. Hamann. 2010. Space-Time Continuous Models of Swarm Robotic Systems: Supporting Global-to-Local Programming. Vol. 9. Springer, Berlin, Germany.
[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.
[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.
[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.
[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.
[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.
[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

View all
  • (2022)On the Throughput of the Common Target Area for Robotic Swarm StrategiesMathematics10.3390/math1014248210:14(2482)Online publication date: 16-Jul-2022
  • (2020)Adaptive Foraging in Dynamic Environments Using Scale-Free Interaction NetworksFrontiers in Robotics and AI10.3389/frobt.2020.000867Online publication date: 9-Jul-2020
  • (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
  • Show More Cited By

Recommendations

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
Issue’s Table of Contents
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.

Check for updates

Author Tags

  1. Birth-death processes
  2. mathematical modeling

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

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)8
  • Downloads (Last 6 weeks)1
Reflects downloads up to 06 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2022)On the Throughput of the Common Target Area for Robotic Swarm StrategiesMathematics10.3390/math1014248210:14(2482)Online publication date: 16-Jul-2022
  • (2020)Adaptive Foraging in Dynamic Environments Using Scale-Free Interaction NetworksFrontiers in Robotics and AI10.3389/frobt.2020.000867Online publication date: 9-Jul-2020
  • (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
  • (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
  • (2019)Scale-Free Features in Collective Robot ForagingApplied Sciences10.3390/app91326679:13(2667)Online publication date: 30-Jun-2019
  • (2019)The Neglected Pieces of Designing Collective Decision-Making ProcessesFrontiers in Robotics and AI10.3389/frobt.2019.000166Online publication date: 26-Mar-2019
  • (2019)Collective Sampling of Environmental Features under Limited Sampling BudgetJournal of Computational Science10.1016/j.jocs.2019.01.005Online publication date: Jan-2019
  • (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
  • (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

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media