## 4 Soft-Collision M* (SC-M*)
### Soft-Collision Constraint on Common Resources
#### 4.1.3 Definition 3 (Soft-Collision Function)  
Now, according to the collision scores from Definition 2, we want to pick out the above-threshold agents and place them into the soft-collision set via the _soft-collision function_ for the purpose of applying the sub-dimensional expansion. Given a path \(\pi=\pi\left(v_{s},v_{b}\right)\) and corresponding resource experience \(D^{j}\) for the agent \(j\), the _soft-collision  
where critical commands relative to the soft-collision constraint are underscored. In this algorithm, Lines 1-7 initialize each vertex \(v\) in the vertex set \(V\) with infinite cost from the source \(v_{s}\) (the cost of \(v_{s}\) itself is zero), set dissatisfying experience to zero and make collision set \(C_{k}\) empty. The initial open list contains \(v_{s}\) only (Line 8). In each iteration, SC-M* expands the first-ranked vertex \(v_{k}\) in the open list ordered by the total cost \(v_{k}.cost+heuristic[v_{k}]\) (Lines 10 and 11). The algorithm terminates and returns the result if the expanded \(v_{k}\) is the destination \(v_{d}\) (Lines 12-14) or jumps to the next iteration if immediate collision occurs at \(v_{k}\), i.e., \(\widetilde{\psi}\left(v_{k}\right)\
eq\emptyset\) (Lines 15-17). Line 18 constructs the _limit neighbors_\(V_{k}^{nbh}\) of \(v_{k}\) using Equation (4). For each vertex \(v_{l}\) in \(V_{k}^{nbh}\) (Line 19), it adds \(v_{l}\) to the descendant set \(V_{k}\) of \(v_{k}\) (Line 20), updates the dissatisfying experience of \(v_{l}\) using Algorithm 1 (Line 21), and merges the immediate collision at \(v_{l}\) to its soft-collision set \(C_{l}\) (Line 22). On top of the new collision set of \(v_{l}\), SC-M* backpropagates to update all the affected ancestor vertexes from \(v_{l}\) (see Equation (3)) and adds them back to the open list for re-expanding (Line 23). After this collision set updating operation, if \(v_{l}\) is free from collision and has improved cost, the algorithm accepts the new cost by save the trace-back information and adding \(v_{l}\) to the open list for expansion (Lines 24-28). This process repeats until the open list is empty (Line 9) when no solution exists or the optimal solution is found (Lines 12-14). ```
1:\(v_{s}\): source joint vertex; \(v_{d}\): destination joint vertex; \(\{V,E\}\): joint configuration graph;
2:\(A\): list of resources
3:Path finding results
4:for all \(v_{k}\) in \(V\)do
5:\(v_{k}\).cost \(\leftarrow\)\(+\infty\)
6:\(v_{k}\).exp \(\leftarrow\) all zero experience
7:\(C_{k}\leftarrow\emptyset\)
8:\(v_{k}\).traceBack \(\leftarrow\emptyset\)
9:endfor
10:\(v_{s}\).cost \(\leftarrow\) 0
11:open \(\leftarrow\)\(\{v_{s}\}\)
12:while open\(\
eq\emptyset\)do
13: open.sort() by \(v\).cost+heuristic[\(v\)] //i.e., sort the open list from small to large
14:\(v_{k}\leftarrow\) open.pop()
15:if\(v_{k}=v_{d}\)then
16:return back_track_path[\(v_{k}\)] //optimal path found
17:endif
18:if\(\widetilde{\psi}(v_{k})\
eq\emptyset\)then
19:continue //skip the vertex in collisions
20:endif
21: conduct the construction of \(V_{k}^{nbh}\) using Equation (4)
22:for\(v_{l}\) in \(V_{k}^{nbh}\)do
23: add \(v_{l}\) to \(V_{k}\) //note \(V_{k}=\{v_{q}|\exists\pi(v_{k},v_{q})\subseteq G^{exp}\}\)
24:\(v_{l}\leftarrow\) experience(\(v_{k},v_{l},A\)) //update experience using Algorithm 1
25:\(C_{l}\leftarrow\)\(C_{l}\cup\widetilde{\psi}(v_{l})\)
26:backpro_update(\(v_{k},C_{l}\), open) // 1) update all the affected soft-collision sets using Eq. (3) //2) add all affected vertexes back to open list (see reference [6] for details)
27:if\(\widetilde{\psi}(v_{l})=\emptyset\)and\(v_{k}\).cost+\(e_{kl}\).cost \(<v_{l}\).cost then
28:\(v_{l}\).cost \(\gets\)\(v_{k}\).cost+\(e_{kl}\).cost
29:\(v_{l}\).traceBack\(\gets v_{k}\)
30: open.add(\(v_{l}\))
31:endif
32:endfor
33:endwhile
34:return no path exists
```  
**Algorithm 2** Soft-collision M*. SC-M* can make a transition from a decoupled individual A* (\(T=1\)) to a standard hard-collision constrained M* (\(T=0\)), providing more flexibility to the performance of the algorithm with bounded soft-collision scores.