X*: Anytime Multiagent Path Planning With Bounded Search

Multi-agent planning in dynamic domains is a challenging problem: the size of the configuration space increases exponentially in the number of agents, and plans need to be re-evaluated periodically to account for moving obstacles. However, we have two key insights that hold in several domains: 1) conflicts between multi-agent plans often have geometrically local resolutions within a small repair window, even if such local resolutions are not globally optimal; and 2) the partial search tree for such local resolutions can then be iteratively improved over successively larger windows to eventually compute the global optimal plan. Building upon these two insights, we introduce 1) a class of anytime multiagent planning solvers, 2) a naive solver in this class, and 3) an efficient solver in this class which reuses prior search information when improving a solution.