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: Christos G. Cassandras , Stephane Lafortune, Introduction to Discrete Event Systems, Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 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 modeling of automated manufacturing systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 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

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.9 Robotics

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Petri nets

General Terms:
Design, Performance, Verification

Keywords:
Petri nets, analysis, modelling, multi-robot systems