Multi Agent Path Finding with Awareness for Spatially Extended Agents
  Path finding problems involve identification of a plan for conflict free
movement of agents over a common road network. Most approaches to this problem
handle the agents as point objects, wherein the size of the agent is
significantly smaller than the road on which it travels. In this paper, we
consider spatially extended agents which have a size comparable to the length
of the road on which they travel. An optimal multi agent path finding approach
for spatially-extended agents was proposed in the eXtended Conflict Based
Search (XCBS) algorithm. As XCBS resolves only a pair of conflicts at a time,
it results in deeper search trees in case of cascading or multiple (more than
two agent) conflicts at a given location. This issue is addressed in eXtended
Conflict Based Search with Awareness (XCBS-A) in which an agent uses awareness
of other agents' plans to make its own plan. In this paper, we explore XCBS-A
in greater detail, we theoretically prove its completeness and empirically
demonstrate its performance with other algorithms in terms of variances in road
characteristics, agent characteristics and plan characteristics. We demonstrate
the distributive nature of the algorithm by evaluating its performance when
distributed over multiple machines. XCBS-A generates a huge search space
impacting its efficiency in terms of memory; to address this we propose an
approach for memory-efficiency and empirically demonstrate the performance of
the algorithm. The nature of XCBS-A is such that it may lead to suboptimal
solutions, hence the final contribution of this paper is an enhanced approach,
XCBS-Local Awareness (XCBS-LA) which we prove will be optimal and complete.
