Coloured petri net plans for cooperative multi-robot systems

During last years the field of Multi-Robot Systems (MRS) has developed significantly growing in size and importance. There exist numerous areas where multi-robot systems have been used successfully and, in the majority of them, MRS must execute complex tasks in environments that are dynamic and unpredictable. This has led to the problem of synthesis and monitoring of complex plans that can provide high level commands to the system allowing the specification of parallel actions, interruptions of task in execution, synchronization between robots, and so forth. Petri Nets (PN) [1,2] have recently emerged as a promising approach for modeling either single-robot or multi-robot plans. This approach provides a clear graphical representation for modeling and developing systems which are concurrent, distributed, asynchronous, non-deterministic and/or stochastic. One of the issues of the approaches that uses Petri Nets is the space complexity associated to the specification of the plans, which can become very large (i.e., with many graphical elements), especially in the case of multi-robot systems. In this work, we analyse the use of Coloured Petri Net (CPN) [3] for the creation and validation of multi-robot systems. More specifically, we describe a formalism for representing multi-robot plan by using CPN and an algorithm to translate the CPN plan in a Petri Net Plan (PNP) [4]. PNP is a plan specification language based on Petri Nets that has been widely used for several robotics applications ranging from robotic soccer to search and rescue and service robotics. PNP are based on PNs and the support for multirobot plans is obtained by specifying the name of the robot or of the role within the description of each action. This features allows for easy implementation of centralized and distributed plans, but it is suitable for situations where the number of robots/roles is limited. CPNs differ from PNs in one significant respect; tokens can be of different types which are usually called colours. Hence, places in CPN can contain a multi-set of coloured tokens and the firing rules associated to transitions depend on such colours. As a consequence, Coloured Petri Nets are equivalent to Petri Nets with respect to descriptive power [7] but provide a more compact plan specification and are particularly well suited for multi-robot plans [6]. The use of CPN for modelling multi-robot plans has the advantage of using coloured tokens to represent different robots/roles and thus of improving its scalability.