# Petri Net Toolbox for Multi-Robot Planning under Uncertainty
## 3 Materials and Methods
### Computational Performance and Scalability  
To evaluate the toolbox's computational performance we performed a series of tests for each module. All these tests are built using the same multi-robot scenario. We considered a generic problem with a linear topological map where each node is connected to the next one and the previous one. The first and the last node are only connected to the next or the previous node, respectively. The robots can navigate in this topological map and in each node can execute two different actions: _Action A_ and _Action B_. Every action has a different duration uncertainty, and so it is defined by a different rate. The GSPNR that models this problem is similar to the one depicted in Figure 4, with the difference that was adapted for a topological map with a linear topology. The results were obtained in a machine with an i74690 CPU, 32 GB of RAM and a NVIDIA RTX 2080 Super GPU. The CPU measurements were taken in relation to the usage of a single core. Thus, 100% usage means one CPU core being fully used, 200% corresponds to two CPU cores fully used, and so on. The first test measured the average time required by Algorithm 1 to generate a GSPNR model from a given topological map. Figure 8 (Left) and Figure 8 (Right) show the results obtained as the number of locations and the number of robots grows, respectively. These results show that the time to build the GSPNR model grows quadratically with the number of locations and is constant as the number of robots grows. The Algorithm 1 iterates over all the nodes and then over all the edges. For a topological map with a linear topology the number of edges is \(2(n-1)\), where \(n\) is the number of nodes. Inside each of these loops the algorithm has to merge the newly created action model with the existing GSPNR model. This requires looping through all places and transitions and these elements grow linearly with the number of nodes. So this leads to a computational complexity of \(O(n^{2})\), where \(n\) is the number of nodes in the topological map. A further analysis of the Algorithm 1 shows that the computational complexity depends on the average degree of the topological map. For a fully connected topology the number of edges is \(n(n-1)\) and this means that the computational complexity of the Algorithm 1 is \(O(n^{3})\). Increasing the number of robots does not increase the number of iterations necessary to build the GSPNR. This arises from the fact that the algorithm only needs to iterate over all the nodes and for each node add the total number of robots in that location. Increasing the number of robots does not change the number of nodes on the topological map and therefore the generation time remains constant. Thus, the algorithm has a computational complexity of \(O(1)\) in this case. The computational complexity of the Algorithm 1 is coherent with the results shown in Figure 8.  
The second test assesses how the _policy synthesis module_ scales. Figure 9 (Left) and Figure 9 (Right) shows how the state space of the equivalent MDP grows as the number of locations and the number of robots increases, respectively. For a conservative GSPNR with \(p\) places and \(r\) tokens, the reachable markings upper bound is given by \(p\)_multichose_\(r\). In Figure 9 the growth is slightly slower than \(p\)_multichose_\(r\), since the way the GSPNR model was designed restricts some parts of the state space. Alternative approaches, such as MMDPs [21] or designing a single Petri net for each robot [27], grow faster. These alternatives follow a growth of \(p^{\prime}\) where \(p\) is the number of state factors in the MMDPs and \(r\) the number of robots. Intuitively this can be explained by the fact that alternative  
Figure 8: (Left) Time required to generate the GSPNR model as the number of locations grows, where \(n\) represents the number of locations; (Right) Time required to generate the GSPNR model as the number of robots grows.