Multi-Robot Collision Avoidance

When many robots share a space, each must avoid the others while they also move. A velocity obstacle is the set of velocities that would lead to a collision with another robot soon, if both keep going. Each robot picks a velocity outside all of them, as close as possible to the one it wants.

Method Robots Look-ahead time

Velocity obstacles

Robot A, with radius $r_A$, would hit robot B within time $\tau$ if its velocity $\mathbf{v}_A$ makes their relative motion enter a disc of radius $r_A + r_B$ around B:

$$VO_{A|B}^{\tau} = \{\, \mathbf{v} : \exists\, t \in [0, \tau],\ \lVert \mathbf{p}_B - \mathbf{p}_A - (\mathbf{v} - \mathbf{v}_B)\,t\rVert < r_A + r_B \,\}$$

Each robot picks the allowed velocity closest to its preferred one, aimed at its goal. In the reciprocal version, RVO, each robot assumes the other will do half the avoiding. ORCA, used widely in practice, turns this into a small linear program.

What to notice

With no avoidance, everyone crashes in the middle. With plain velocity obstacles, robots avoid each other, but pairs can wobble, since each one dodges fully and then both dodge back. Reciprocal avoidance shares the effort, so the paths are smoother and form a swirl in the middle. A longer look-ahead makes robots start avoiding earlier and swerve more gently.