## 3 Technical Briefing of M*
### Algorithm Description of M*  
The high-level description of M* is as follows [6]: Initially, M* computes the individually optimal policy \(\phi\) for each agent from source \(v_{s}\) to destination \(v_{d}\). The initial search graph \(G^{sch}\) only consists of an individually optimal path: Initial \(G^{exp}\) contains \(v_{s}\) only; initial \(G^{nht}\) contains \(\phi(v_{s})\) only, which is the successor of \(v_{s}\) along the individually optimal policy; and initial \(G^{\phi}\) contains the optimal policy path from the vertex in \(G^{nth}\) and \(G^{exp}\) all the way to \(v_{d}\). \(C_{p}=\emptyset\) for all \(v_{p}\) in initial \(G^{sch}\). Given the initial \(G^{sch}\), the A* algorithm is applied using the following _admissible heuristic_  
\[h\left(v_{p}\right)=g(\pi_{\phi}(v_{p},v_{d})\ )\leq g(\pi_{*}(v_{p},v_{d})), \tag{5}\]  
where \(\pi_{\phi}\) is the individually optimal path induced by policy \(\phi\), and \(\pi_{*}\) is the ground-truth optimal multi-agent path we want to find. The initial _open list_ (i.e., _priority queue_) contains \(v_{s}\) only, with zero cost. The open list is sorted according to \(v_{p}.cost+h\left(v_{p}\right),\) where \(v_{p}.cost\) is the current cost of \(v_{p}\) from the source. In each iteration, M* expands the first-ranked vertex \(v_{p}\) from the open list to \(G^{exp}\) and investigates each joint vertex \(v_{q}\) in the limited neighbors of \(v_{p}\) (i.e., \(v_{q}\in V_{p}^{nht}\)) if no collision occurs at \(v_{p}\); otherwise, it jumps to the next iteration. If there exists a collision (i.e., \(\psi\left(v_{q}\right)\
eq\emptyset\)), M* will update the collision set \(C_{q}\) with \(C_{q}\cup\psi\left(v_{q}\right)\), and this update will back-propagate from \(v_{q}\) to: (1) its immediate predecessor \(v_{p}\); and (2) all the way back to any ancestors that have at least one path inside of \(G^{exp}\) leading to \(v_{q}\) (see Equation (3) for details). After this pre-processing, the algorithm:  
* investigates and updates the cost of the vertex \(v_{q}\) and records its corresponding predecessor; and
* adds \(v_{q}\) and all its predecessors/ancestors, of which the collision sets are changed, to the open list. This process is repeated until \(v_{d}\) is expanded or open list is empty. The critical point is that: Only when a collision set \(C_{p}\) is changed will the search graph \(G^{sch}\) change. It is the operation of updating the collision set in a back-propagation way that makes the story different: By including \(\psi\left(v_{p}\right)\) to \(C_{p}\), M* can tell which agents are _immediately_ collided at the current \(v_{p}\); by including all \(\psi\left(v_{q}\right)\) for \(v_{q}\in V_{p}\) to \(C_{p}\) (i.e., the collision information of all the expanded downstream successors from \(v_{p}\)), M* can preview which agents will collide in the future, making it possible to pre-plan to avoid that. Therefore, using the limited neighbor set in Equation (4) makes sense: It advises M* to only expand the dimensions where there exists an immediate collision at \(v_{p}\) or there will be collisions in the future, starting from \(v_{p}\), in the current expanded graph \(G^{exp}\). Figure 1 shows an example of how M* solves the optimal collision-free path planning for the two agents. In Figure 1, we can visualize the evolution of the search graph \(G^{sch}\) of Agent 2. \(G^{sch}\) consists of an expanded graph \(G^{exp}\) (circle), a neighbor graph \(G^{nth}\) (diamond), and a policy graph \(G^{\phi}\) (square). Edge cost and direction-changing cost are considered during planning. Yellow zones are preferred areas with lower edge cost. In M*, individually optimal paths are induced by \(\phi\) for each individual agent (Figure 1a). We can observe that there will be a collision at vertex \(s_{10}\), which is ignored by \(\phi\). For Agent 2, M* searches in the subspace, and the most promising vertex is expanded at each iteration (Figure 1b,c).