Justifying and Improving Meta-Agent Conflict-Based Search
  The Meta-Agent Conflict-Based Search~(MA-CBS) is a recently proposed
algorithm for the multi-agent path finding problem. The algorithm is an
extension of Conflict-Based Search~(CBS), which automatically merges
conflicting agents into meta-agents if the number of conflicts exceeds a
certain threshold. However, the decision to merge agents is made according to
an empirically chosen fixed threshold on the number of conflicts. The best
threshold depends both on the domain and on the number of agents, and the
nature of the dependence is not clearly understood.
  We suggest a justification for the use of a fixed threshold on the number of
conflicts based on the analysis of a model problem. Following the suggested
justification, we introduce new decision policies for the MA-CBS algorithm,
which considerably improve the algorithm's performance. The improved variants
of the algorithm are evaluated on several sets of problems, chosen to underline
different aspects of the algorithms.
