During last years the eld of Multi-Robot Systems (MRS) has developed signi cantly 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 speci cation of parallel actions, interruptions of task in execution, synchronization between robots, and so forth.
Petri Nets (PN) [
In this work, we analyse the use of Coloured Petri Net (CPN) [
PNP is a plan speci cation language based on Petri Nets that has been widely used for several robotics applications ranging from robotic soccer to search and rescue and service robotics1. 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 di er from PNs in one signi cant respect; tokens can be of di erent
types which are usually called colours. Hence, places in CPN can contain a
multi-set of coloured tokens and the ring rules associated to transitions depend
on such colours. As a consequence, Coloured Petri Nets are equivalent to Petri
Nets with respect to descriptive power [
The general idea behind our methodology is described in Figure 1. We start
by designing the multi-robot plan by using Coloured Petri Nets, we then translate
the Coloured Petri Net Plan in a Petri Net Plan and we execute the plan within
the Petri Net Framework [
Our work is based on two main ingredients: rst, we elaborate a speci c CPN formalism that can be translated to executable plans for the PNP framework. Second, we provide an algorithm for the automatic conversion of a such CPN plans in PNP plans. Speci cally, in our CPN plan we have three basic elements that compose a multi-robot plan: i) Action: An action represents an operation that the robots should execute in the world (e.g., explore a given region of the environment). Following the PNP framework an action can be preceded by a start transition, that de nes the preconditions for executing the action. We then have an execution place that represents the fact that the action is being executed and nally an end transition that follows the execution place and res whenever the end conditions for the actions are true (see Figure 2). However, in contrast to PNP the execution place associated to an action can contain a multi-set of coloured tokens, indicating that a set of robots are executing the action in parallel. ii) Operator: An operator is a place used for the control of the behavior of the net, that is not related to any action in the real word. For example, Figure 3 shows the use of an operator to connect the end and start transitions of Action 1 and Action 2 respectively. Notice that, the translation of the operator in the PNP framework de nes di erent behaviors and depends on modi ers that we can de ne on the transitions. For example, the SYNC modi er (speci ed in the end transition associated to Action 1) results in a PNP plan that synchronizes the parallel actions of all robots (i.e., no robot will start Action 2 until all robots have completed Action 1). Our formalism allows to handle in a similar way other important constructs such as team level or individual level interrupts, i.e., interrupts that change the behaviors of the whole team or of a single robot respectively. iii) Resources: A resource is a coloured token that can represent a robot or a set of robots. This element determines which robots should execute the actions.
The combination of the above elements allows to design complex multi-robot plan. In particular, thanks to the use of coloured token, we can achieve a signifAction:exec
Action:end FORK
R1#Action:start R1#Action:exec R1#Action:end R2#Action:start R2#Action:exec R2#Action:end R3#Action:start R3#Action:exec R3#Action:end
R4#Action:start R4#Action:exec R4#Action:end icant reduction in terms of space, essentially because we can represent parallel actions executed by n robots with a single place that contains n tokens. This is crucial as it signi cantly eases the design and monitoring tasks for the human operators. Moreover, notice that we can maintain the identity of the robots executing the action: for example, an explore action (represented with a single place in the CPN) could be executed in di erent ways depending on whether the di erent coloured tokens represent UGVs or AGVs.
Action1:exec 1'R1, 1'R2 1'R3
Action1:endSY NC
Action2:exec 1'R1, 1'R2 1'R3 1'R1, 1'R2 1'R3 1'R1, 1'R2 1'R3
Action2:start R1#Action1:end
JOIN
FORK
R1#Action2:start R1#Action1:exec R2#Action1:exec R3#Action1:exec
R2#Action1:end R3#Action1:end
R2#Action2:start R3#Action2:start
R1#Action2:exec R2#Action2:exec R3#Action2:exec
There are several free available softwares that allows the design and the
analysis of Coloured Petri Net, here we used the "CPN tools" [
A key point of this work is that the compilation of a CPN plan to an executable PNP plan is automatic, and we provide an algorithm (not reported here in the interest of space) to realize such conversion. 3
The proposed system has been evaluated using the Stageros simulator. In particular, we consider three di erent use cases related to the collaborative exploration of an indoor area. The evaluation con rms the e cacy of the system in terms of space reduction and ease in the design of the plan.
A video of the execution of one of these use cases is available at:https://youtu. be/9e9x87FCjiY. This video is a proof of concept for a cooperative exploration scenario, where a team of two heterogeneous robots should explore a pre-speci ed area. We have two teams, composed by two green and two blue robots respectively, and we want only one team (i.e., the closest one) to perform the exploration. The rst part of the video shows the translation of the CPN to PNP, notice that each robot has been represented as a single token so to control each one of them (e.g., for possible single robot interrupts). We have a decision making point at the beginning of the mission, where the plan evaluates the distance of the two team members from the target area (the room in the top left) so to choose which team will perform the explore action (i.e., the team that minimizes the sum of travel distance). In our case this is the blue team. During the exploration, one of the two robots detects a low battery state, hence the current mission is interrupted and this robot goes to a recharge base (red area). Then both robots move to the home position, and since the original speci cation of the CPN was to synchronize the end of the mission, only when both robots are back to the home position the mission is over (i.e., tokens enter the goal state). 4
In this work we propose a compact and e ective representation of multi-robot plans by using Coloured Petri Nets; such a representation is comprehensive, easily readable by humans, has minimum space requirements, and is suitable for real time execution. Experimental evaluation of the considered use cases suggests that our approach is indeed capable of automatically generating executable PNP plans from a CPN description, handling interesting cases such as for example parallel action execution, as well as team level and individual interrupts. Our work opens several scenarios for future improvements. Speci cally, an interesting direction would be to work towards an on-line translator for multi-robot CPN plans hence converting parts of the CPN as the execution progress so to avoid a static conversion of the whole plan. Moreover, while in our work the evaluation is based on a standard and widely used robotic simulation environment, an empirical evaluation with robotic platforms is important to precisely assess the impact of our methodology.