  Team Coordination on Graphs with Risky Edges (TCGRE) is a recently emerged
problem, in which a robot team collectively reduces graph traversal cost
through support from one robot to another when the latter traverses a risky
edge. Resembling the traditional Multi-Agent Path Finding (MAPF) problem, both
classical and learning-based methods have been proposed to solve TCGRE,
however, they lacked either computation efficiency or optimality assurance. In
this paper, we reformulate TCGRE as a constrained optimization and perform
rigorous mathematical analysis. Our theoretical analysis shows the NP-hardness
of TCGRE by reduction from the Maximum 3D Matching problem and that efficient
decomposition is a key to tackle this combinatorial optimization problem.
Further more, we design three classes of algorithms to solve TCGRE, i.e., Joint
State Graph (JSG) based, coordination based, and receding-horizon sub-team
based solutions. Each of these proposed algorithms enjoy different provable
optimality and efficiency characteristics that are demonstrated in our
extensive experiments.
