Team Coordination on Graphs with Risky Edges (TCGRE) is a multi-agent problem, proposed
by Xiao et al. 1
in recent years. In this problem, the agents’ task is to minimize the total cost of
traversing through a graph, which
includes risky edges. The cost of traversing over such edges may be reduced by an
agent from a support node,
meaning that the optimal solution has to account for possible cooperation between
agents by detouring from their
individual shortest paths. Multiple algorithms have already been proposed 2 with different
trade-offs between
optimality and computation time to solve this problem. Through our work, we improved
the time complexity of the
Coordination Exhaustive Search 2 method by rearranging the operations, thus creating
a cahced functionality. In
this paper, we present our suggested changes and compare our improved algorithm with
the originally suggested
over a number of random graphs to show the practical effect of the proposed changes.
