  We present a lightweight, decentralized algorithm for navigating multiple
nonholonomic agents through challenging environments with narrow passages. Our
key idea is to allow agents to yield to each other in large open areas instead
of narrow passages, to increase the success rate of conventional decentralized
algorithms. At pre-processing time, our method computes a medial axis for the
freespace. A reference trajectory is then computed and projected onto the
medial axis for each agent. During run time, when an agent senses other agents
moving in the opposite direction, our algorithm uses the medial axis to
estimate a Point of Impact (POI) as well as the available area around the POI.
If the area around the POI is not large enough for yielding behaviors to be
successful, we shift the POI to nearby large areas by modulating the agent's
reference trajectory and traveling speed. We evaluate our method on a row of 4
environments with up to 15 robots, and we find our method incurs a marginal
computational overhead of 10-30 ms on average, achieving real-time performance.
Afterward, our planned reference trajectories can be tracked using local
navigation algorithms to achieve up to a $100\%$ higher success rate over local
navigation algorithms alone.
