  Planning for multi-robot teams in complex environments is a challenging
problem, especially when these teams must coordinate to accomplish a common
objective. In general, optimal solutions to these planning problems are
computationally intractable, since the decision space grows exponentially with
the number of robots. In this paper, we present a novel approach for
multi-robot planning on topological graphs using mixed-integer programming.
Central to our approach is the notion of a dynamic topological graph, where
edge weights vary dynamically based on the locations of the robots in the
graph. We construct this graph using the critical features of the planning
problem and the relationships between robots; we then leverage mixed-integer
programming to minimize a shared cost that depends on the paths of all robots
through the graph. To improve computational tractability, we formulated our
optimization problem with a fully convex relaxation and designed our decision
space around eliminating the exponential dependence on the number of robots. We
test our approach on a multi-robot reconnaissance scenario, where robots must
coordinate to minimize detectability and maximize safety while gathering
information. We demonstrate that our approach is able to scale to a series of
representative scenarios and is capable of computing optimal coordinated
strategic behaviors for autonomous multi-robot teams in seconds.
