## 5 Experiments and Results
### Comparison of SC-M* to Baselines
#### 5.3.1 Path Cost  
Firstly, we compared the path cost of the three algorithms. We designed 60 planning tasks for environments with 4-6 agents (20 tasks for each), in which agents will encounter at least one collision along the individually optimal paths under the \(T=0.05,~{}\delta=1\) setting. We start with small agent numbers because SC-A* cannot handle a large number of agents. Figure 7 shows the average difference of the three SC-based solvers relative to the individually optimal cost (i.e., the sum of the optimal cost of each agent when the agent is the only one in the system). In other words, the Y-axis represents the cost of collisions. We observe that SC-A* and SC-CBS have the lowest and highest additional cost, respectively. SC-M* solutions cost more than SC-A* but noticeably less than SC-CBS. \begin{table}
\begin{tabular}{c c c c|c c c c} \hline \hline \(m\) & _T = 0.2_ & _T = 0.35_ & _T = 0.45_ & \(m\) & \(\delta\) = 6.0_ & \(\delta\) = 12.0_ & \(\delta\) = 15.0 \\ \hline
5 & 0.3438 & 0.3493 & 0.363948 & 5 & 0.333498 & 0.3677 & 0.527464 \\
20 & 1.2485 & 1.8549 & 1.807993 & 20 & 1.479236 & 1.4032 & 2.369483 \\
40 & 10.102 & 3.2387 & 4.415021 & 40 & 61.49792 & 4.5024 & 4.04331 \\
60 & 503.94 & 106.02 & 104.6499 & 60 & 521.2721 & 306.46 & 60.30944 \\
90 & 901.91 & 801.47 & 702.4526 & 70 & 627.0925 & 347.14 & 209.5725 \\
100 & \(>\)1000 & 909.0 & 901.1799 & 100 & 901.91 & 751.78 & 606.6522 \\ \hline \multicolumn{8}{c|}{Left. \(\delta\) = 9.0} & \multicolumn{8}{c}{Right: \(T\) = 0.35} \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Run time of two-resource-two-type SC-M* under different parameters. Figure 7: Average cost difference of soft-collision-based multi-agent path planning (SC-based MAPP) solvers from the individually optimal cost in the one-resource-one-type context. To be more detailed, in the experiments, we designed MAPP tasks for environments containing 4-6 agents with 20 tasks for each. All tasks were designed to encounter at least one collision along the individually optimal paths under the above-mentioned configuration. Thus, additional costs relative to the individually optimal path are expected for each of the three SC-based MAPP solvers. Table 3 compares the results of SC-M* and SC-CBS to the optimal solutions obtained by SC-A*. The top half of the table shows the increase in cost relative to the cost for SC-A*; the costs for SC-A* for all scenarios vary within a small range so the results are in absolute numbers. The bottom half shows the ratio in run time with respect to SC-A*; the run time for SC-A* varies greatly across the experiments so we show the cost reduction as a percentage. In the table, we observe that the additional cost of SC-M* from the SC-A*  
The reason for the results is that SC-A* is an optimal solver for this type of MAPP problem because it always explores cheaper paths in the entire multi-agent joint space before considering the paths that cost more [7]. SC-M* is suboptimal because of the process discussed in Section 4.3.2. Compared to SC-M*, SC-CBS suffers from more path cost due to the way it collects a collision: CBS collects collisions into a _conflict tree_ and arranges the collision into the form [agent \(j\), vertex \(v\), step \(s\)], indicating that agent \(j\) collides at vertex \(v\) at step \(s\). In each iteration, CBS conducts decoupled planning to avoid agent \(j\) reaching vertex \(v\) at step \(s\). This might lose some information in the soft-collision context because there might exist another path that leads \(j\) to vertex \(v\) at step \(s\) without announcing a collision, by avoiding one of the upstream vertexes involved in soft interference. In contrast, SC-M* can explore those paths excluded by SC-CBS because it searches the entire space of the immediate colliding agents. Figure 8 provides an example to visualize the difference in planning among the three SC-based MAPP solvers. Figure 8 shows a two-agent MAPP problem in the soft-collision context.