Modelling, analysis and execution of multi-robot tasks using petri nets

ABSTRACT

This paper introduces Petri net (PN) based models of cooperative robotic tasks, namely those involving the coordination of two or more robots, thus requiring the exchange of synchronisation messages, either using explicit (e.g., wireless) or implicit (e.g., vision-based observation of teammates) communication. In the models, PN places represent primitive actions, subtasks and predicates set by sensor readings and communicated messages. Events are associated to PN transitions. The PN models can be used for task planning, plan execution and plan analysis. Different PN views enable the analysis of different properties. In this work we focus on plan analysis, namely on properties such as boundedness and liveness, corresponding to checking if resources usage is stable and plans have no deadlocks, as well as on stochastic performance, concerning the plan success probability. One novel feature of our work is that the analysis consists of composing several small action PN models with environment PN models, leading to a closed loop robot team/environment analysis methodology. Examples of application to simulated robotic soccer scenarios are presented.

References

1. C. Cassandras, S. Lafortune. Introduction to Discrete Event Systems, Kluwer Academic Publishers, 1999.
2. Philip R. Cohen; Hector J. Levesque, Teamwork, Nous, vol. 25, no. 4, pp. 487--512, 1991.
3. F. Wang et al, A Petri-Net Coordination Model for an Intelligent Mobile Robot, IEEE Transactions on Robotics and Automation, Vol. 9, No. 3, pp. 257--271, 1993.
4. L. Montano, F. García, J. Villaroel, Using the Time Petri Net Formalism for Specification, Validation, and Code Generation in Robot-Control Applications, The International Journal of Robotics Research, vol. 19, no. 1, pp. 59--76, 2000.
5. H. Costelha, P. Lima, Modelling, Analysis and Execution of Robotic Tasks using Petri Nets, Proc. of IROS 2007 - IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 1449--1454, San Diego, CA, USA, 2007.
6. V. Ziparo, L. Iocchi, Petri Net Plans, Proc. of the Fourth International Workshop on Modelling of Objects, Components, and Agents, pp. 267--290, Turku, Finland, 2006.
7. N. Viswanadham, Y. Narahari, Performance Modelling of Automated Manufacturing Systems, Prentice Hall, 1992.
8. A. Zimmermann, A Software Tool for the Performability Evaluation with Stochastic Petri Nets, http://pdv.cs.tu-berlin.de/~timenet/, 2001.

Index Terms

• Computer systems organization

  • Embedded and cyber-physical systems

    • Robotics

• Computing methodologies

  • Artificial intelligence

    • Control methods

      • Robotic planning

    • Planning and scheduling

      • Robotic planning

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Software system models

        • Petri nets