  This work deals with the problem of planning conflict-free paths for mobile
robots in cluttered environments. Since centralized, coupled planning
algorithms are computationally intractable for large numbers of robots, we
consider decoupled planning, in which robots plan their paths sequentially in
order of priority. Choosing how to prioritize the robots is a key
consideration. State-of-the-art prioritization heuristics, however, do not
model the coupling between a robot's mobility and its environment. In this
paper, we propose a prioritization rule that can be computed online by each
robot independently, and that provides consistent, conflict-free path plans.
Our innovation is to formalize a robot's path prospects to reach its goal from
its current location. To this end, we consider the number of homology classes
of trajectories, and use this as a prioritization rule in our decentralized
path planning algorithm, whenever any robots enter negotiation to deconflict
path plans. This prioritization rule guarantees a partial ordering over the
robot set. We perform simulations that compare our method to five benchmarks,
and show that it reaches the highest success rate (w.r.t. completeness), and
that it strikes the best balance between makespan and flowtime objectives.
