## 4 Soft-Collision M* (SC-M*)
### Completeness and Cost-Suboptimality
#### 4.3.2 Cost-Suboptimality  
Different from M*, which is optimal, SC-M* is suboptimal because Equations (9) and (10) only include the immediate conflicting agents to the soft-collision set; the agents that softly interfere with the conflicting agents in the upstream path are excluded. Those excluded agents also contribute to the announced collision (i.e., making the collision score above the threshold). Because of this, SC-M* cannot guarantee the _inclusion property_, which is the basis to ensure the optimality in M* [6]: _The optimal path for some subset of agents costs no more than the optimal joint path for the entire set of agents._ Without the inclusion property, SC-M* may not guarantee cost optimality.  
Figure 3 provides a counterexample of the inclusion property of SC-M* in the soft-collision MAPP context defined in this paper. Let \(\pi^{\prime}_{\Omega}(v_{k},v_{f})\) be the joint path constructed by combining the optimal path for a subset \(\Omega\in I\) of agents with the individually optimal paths for the agents in \(I\backslash\Omega\). The inclusion property is defined as follows: If the configuration graph contains an optimal path \(\pi_{*}(v_{k},v_{f})\), then \(\forall\Omega\subset I\), \(g(\pi^{\prime}_{\Omega}(v_{k},v_{f}))\leq g(\pi_{*}(v_{k},v_{f}))\). See _Lemma 6_ in [6].  
In the soft-collision context, this inclusion property does not always hold. In Figure 3, we have a three-agent MAPP problem (\(I=\{r1,r2,r3\}\)) in the soft-collision context. Agents \(r1,r2,\) and \(r3\) attempt to move from the vertexes \(a\), \(f\), and \(h\) to the vertexes \(e\), \(g\), and \(i\), respectively. The individually optimal paths (shortest distance) are \(a\to b\to c\to d\to e\) with distance 4 for \(r1\), \(f\to c\to d\to g\) with distance 3 for \(r2\), and \(h\to b\to c\to i\) with distance 3 for \(r3\). The total cost of the joint individually optimal path is 10. However, assuming that the agents can only tolerate a dissatisfying experience with distance 1, \(r1\) will announce a collision at vertex \(d\) because of the interference on the edge \(b\to c\) and \(c\to d\) from agents \(r3\) and \(r2\), respectively.  
If we choose \(\Omega=\{r1,r2\}\in I\), as can be seen in Figure 3, the only solution would be that \(r1\) takes a detour through the vertex \(x\) to avoid the collision on the edge \(c\to d\), resulting in a cost of 5 for \(r1\), and the total \(g(\pi^{\prime}_{\Omega}(v_{k},v_{f}))\) is \(11\) (3 for \(r2,5\) for \(r1\) and 3 for \(r3\)). On the other hand, by searching through all three dimensions, a better solution would be that \(r3\) detours through the vertex \(y\), and \(r1\) is free from collision because the interference on the edge \(b\to c\) disappears. The total cost of this joint path is 10.5, and we have \(g(\pi^{\prime}_{\Omega}(v_{k},v_{f}))=11>g(\pi_{*}(v_{k},v_{f}))=\)10.5, which is contradictory to the inclusion property.  
The reason for this phenomenon is that, in the hard-collision context, only the immediate conflicting agent \(r2\) contributes to the collision of \(r1\) at vertex \(d\). However, in the soft-collision context, both \(r2\) and \(r3\) contribute to the collision of \(r1\) at vertex \(d\), and thus, the inclusion property does not apply. Without this inclusion property, which is the basis of the optimality of M*, the optimality of SC-M* cannot be guaranteed.  
However, we notice that suboptimal methods have long been used successfully to solve many interesting MAPP problems [15; 25; 26]. Given the fact that we show in the next section that SC-M* is superior to other alternative SC-based MAPP solvers (e.g., SC-A* and SC-CBS) in terms of scalability, run time, and path cost, we demonstrate that the proposed method, which is adjusted to MAPP in the soft-collision context, is a powerful tool in practice.