Analysing robot swarm decision-making with Bio-PEPA
Massink M., Brambilla M., Latella D., Dorigo M., Birattari M.
Formal Modeling Informatique générale 68N30 Mathematical aspects of software engineering Informatique mathématique Fluid Flow Analysis Intelligence artificielle Formal modeling Swarm Robotics D.2.4 Software/Program Verification
We present a novel method to analyse swarm robotics sys- tems based on Bio-PEPA. Bio-PEPA is a process algebraic language originally developed to analyse biochemical systems. Its main advantage is that it allows different kinds of analyses of a swarm robotics system starting from a single description. In general, to carry out different kinds of analysis, it is necessary to develop multiple models, raising issues of mutual consistency. With Bio-PEPA, instead, it is possible to perform stochastic simulation, fluid flow analysis and statistical model checking based on the same system specification. This reduces the complexity of the analysis and ensures consistency between analysis results. Bio-PEPA is well suited for swarm robotics systems, because it lends itself well to modelling distributed scalable systems and their space-time characteris- tics. We demonstrate the validity of Bio-PEPA by modelling collective decision-making in a swarm robotics system and we evaluate the result of different analyses.
Source: ANTS 2012 - Swarm Intelligence - 8th International Conference, pp. 25–36, Brussels, Belgium, 12-14 September 2012
Publisher: Springer, London, GBR
2. Lerman, K., Martinoli, A., Galstyan, A.: A review of probabilistic macroscopic models for swarm robotic systems. In: Swarm robotics. Volume 3342 of LNCS. Springer, Heidelberg (2005) 143-152
3. Dixon, C., Winfield, A., Fisher, M.: Towards temporal verification of emergent behaviours in swarm robotic systems. In: Towards Autonomous Robotic Systems. Volume 6856 of LNCS. Springer, Heidelberg (2011) 336-347
4. Konur, S., Dixon, C., Fisher, M.: Analysing robot swarm behaviour via probabilistic model checking. Robotics and Autonomous Systems 60(2) (2012) 199 - 213
5. Ciocchetta, F., Hillston, J.: Bio-PEPA: A framework for the modelling and analysis of biological systems. TCS 410(33-34) (2009) 3065-3084
6. Massink, M., Latella, D., Bracciali, A., Harrison, M., Hillston, J.: Scalable contextdependent analysis of emergency egress models. Formal Aspects of Computing (2011) 1-36 In press.
7. Massink, M., Latella, D., Bracciali, A., Hillston, J.: Modelling non-linear crowd dynamics in Bio-PEPA. In: Fundamental Approaches to Software Engineering. Volume 6603 of LNCS. Springer, Heidelberg (2011) 96-110
8. Montes de Oca, M.A., Ferrante, E., Scheidler, A., Pinciroli, C., Birattari, M., Dorigo, M.: Majority-rule opinion dynamics with differential latency: A mechanism for self-organized collective decision-making. Swarm Intelligence 5(3-4) (2011) 305-327
9. Scheidler, A.: Dynamics of majority rule with differential latencies. Phys. Rev. E 83 (Mar 2011) 031116
10. Ijspeert, A., Martinoli, A., Billard, A., Gambardella, L.M.: Collaboration through the exploitation of local interactions in autonomous collective robotics: The stick pulling experiment. Autonomous Robots 11 (2001) 149-171
11. Martinoli, A., Easton, K., Agassounon, W.: Modeling swarm robotic systems: a case study in collaborative distributed manipulation. The International Journal of Robotics Research 23(4-5) (2004) 415-436
12. Baier, C., Katoen, J.P., Hermanns, H.: Approximate Symbolic Model Checking of Continuous-Time Markov Chains. In: Concur '99. Volume 1664 of LNCS., Springer, Berlin, Heidelberg (1999) 146-162
13. Brambilla, M., Pinciroli, C., Birattari, M., Dorigo, M.: Property-driven design for swarm robotics. In: Proceedings of 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2012), IFAAMAS (2012) In press.
14. Ciocchetta, F., Duguid, A., Gilmore, S., Guerriero, M.L., J., H.: The Bio-PEPA Tool Suite. In: Proceedings of the 6th International Conference on Quantitative Evaluation of SysTems (QEST 2009), Washington, DC, USA, IEEE Computer Society (2009) 309-310
15. Hillston, J.: Fluid flow approximation of PEPA models. In: Proceedings of the 2th International Conference on Quantitative Evaluation of SysTems (QEST 2005), Washington, DC, USA, IEEE Computer Society (2005) 33-43
16. Gillespie, D.T.: Exact stochastic simulation of coupled chemical reactions. The Journal of Physical Chemistry 81(25) (1977) 2340-2361
17. Ciocchetta, F., Hillston, J.: Bio-PEPA: An extension of the process algebra PEPA for biochemical networks. ENTCS 194(3) (2008) 103-117
18. Kwiatkowska, M., Norman, G., Parker, D.: PRISM 4.0: Verification of probabilistic real-time systems. In: Proc. 23rd International Conference on Computer Aided Verification (CAV'11). Volume 6806 of LNCS., Springer, Heidelberg (2011) 585- 591
19. Kleinrock, L.: Queueing Systems. Volume 1: Theory. Wiley, New York, NY, USA (1975)
20. Aziz, A., Sanwal, K., Singhal, V., Brayton, R.: Model checking Continuous Time Markov Chains. ACM Transactions on Computational Logic 1(1) (2000) 162-170
21. Kurtz, T.: Solutions of ordinary differential equations as limits of pure jump Markov processes. Journal of Applied Probability 7 (1970) 49-58
Metrics
Back to previous page
@inproceedings{oai:it.cnr:prodotti:190155,
title = {Analysing robot swarm decision-making with Bio-PEPA},
author = {Massink M. and Brambilla M. and Latella D. and Dorigo M. and Birattari M.},
publisher = {Springer, London, GBR},
doi = {10.1007/978-3-642-32650-9_3},
booktitle = {ANTS 2012 - Swarm Intelligence - 8th International Conference, pp. 25–36, Brussels, Belgium, 12-14 September 2012},
year = {2012}
}
0000-0002-3257-9059DOIAlso available from
