## 4 Soft-Collision M* (SC-M*)
### Soft-Collision Constraint on Common Resources
#### 4.1.1 Definition 1 (Resource Experience)  
We define _resource experience_ to quantify the dissatisfying experience per resource about which an agent cares.  
Let  
* \(\pi=\pi\left(v_{s},v_{b}\right)\) be a path from the source \(v_{s}\) to some \(v_{b}\);
* \(v_{q}=\pi\left(v_{p}\right)\) be the immediate successor of \(v_{p}\) along the path \(\pi\);
* \(A_{k}(e^{j}_{pq})\) be the capacity (amount) of the subset of the resource \(A_{k}\) on the edge \(e^{j}_{pq}\), given by the graph model; and
* \(A^{i}_{k}(e^{j}_{pq})\) be the amount of the subset of the resource \(A_{k}\)_actually allocated_ to the agent \(j\) on the edge \(e^{j}_{pq}\), called the _allocated resource value_.  
The _resource experience_ is then defined as the _disatisfying_ experience of agent \(j\) on resource \(A_{k}\) along the path \(\pi\)\({}^{j}\):  
\[D\left(\pi\!\!\!^{j},A_{k}\right)=\sum_{v_{p}|v_{p}\in\pi/v_{b}}\mathbf{1} \left(A_{k}(e^{j}_{pq})\geq\varepsilon_{k}\wedge A^{j}_{k}(e^{j}_{pq})< \varepsilon_{k}\right)\cdot g(e^{j}_{pq}), \tag{6}\]  
where \(\mathbf{1}(\cdot)\) is the indicator function, whose value is one if the logical condition is true, else zero; \(\varepsilon_{k}\in\varepsilon=\{\varepsilon_{1},\ldots,\varepsilon_{L}\}\) is the _satisfying value_ regarding the resource \(A_{k}\), which is a positive real value; \(g(e^{j}_{pq})\) is the edge cost regarding travel time/distance given by the graph model; and \(A^{j}_{k}(e^{j}_{pq})\) is formulated as:  
\[A^{j}_{k}(e^{j}_{pq})\ =\frac{A_{k}(e^{j}_{pq})}{\sum_{k\in I}\mathbf{1}\left(e^{k}_{ pq}=\dot{e}^{j}_{pq}\right)}. \tag{7}\]  
Obviously, \(A^{j}_{k}(e^{j}_{pq})=A_{k}(e^{j}_{pq})\) if and only if no other agents are physically moving along with agent \(j\) on the edge \(e^{j}_{pq}\). The allocated resource value \(A^{j}_{k}(e^{j}_{pq})\) quantifies the level of interference incurred by other agents when they physically move together. In contrast, the traditional hard-collision setting will always label a collision to the agent \(j\) and all other involved agents whenever \(A_{k}^{j}(e_{pq}^{j})\) is (even slightly) smaller than \(A_{k}(e_{pq}^{j})\). The resource experience is implemented as an attribute of the vertex class and can be calculated incrementally using Algorithm 1.  
```
0:\(v_{k}\): base vertex; \(v_{l}\): immediate successor of the base vertex; A: list of resources
0:\(v_{l}\) with updated experience
1:for\(A_{p}\) in \(A\)do
2:for\(j\) in \(l\)do
3:\(v_{l}.\text{exp}[A_{p}][j]\gets v_{k}.\text{exp}[A_{p}][j]+D(\pi(v_{k},v_ {l})^{j},A_{p})\)
4:endfor
5:endfor
6:return\(v_{l}\) //the successor with updated experience
```  
**Algorithm 1** Function: experience(\(v_{k},v_{l},A\)).  
Combined with the allocated resource value, which serves as a proxy of the interference level, the definition of resource experience in Equation (6) actually defines a property of an agent: Only the situation in which the resource allocated to an agent is dissatisfying because of the co-existence of other agents (i.e., \(A_{k}(e_{pq}^{j})\geq\epsilon_{k}\) should hold), will contribute to the dissatisfying experience of that agent. Furthermore, each dissatisfying condition is weighted by the edge cost \(g(e_{pq}^{j})\). In this way, we can quantify the resource experience in terms of how long such a dissatisfying condition lasts in travel time or distance, which is quantified by \(g(e_{pq}^{j})\). As discussed below, the resource experience of an agent will determine its collision score, which is defined from a probabilistic point of view.