The τ-∆t Problem

[raja-s]

I refer to this as the “τ-∆t problem” because it all revolves around the choice of the values of τ and ∆t (which correspond to ORCA::tau_ and ORCA::deltaT_ in the implementation). Here's an explanation of these two values based on the paper:

• τ represents the amount of time for which we want to “plan ahead”. More formally, it is the minimum amount of time in the future during which we want to guarantee that no collisions will occur between agents. So the greater the value of τ, the earlier agents will become aware of the presence of other agents moving closer to them.

• ∆t represents the amount of time during which we want to move our agents with their new velocities obtained by planning ahead for τ time.

This means that the following constraint must hold: 0 < ∆t <= τ, otherwise collision-free navigation is not guaranteed.
To me, it makes sense to have ∆t significantly smaller than τ. If instead we set ∆t = τ, then when agents compute collision-free velocities, they will go all the way until they are literally stuck to one another at which point they recompute new velocities. That is because the ORCA algorithm is optimal by construction, in the sense that agents will deviate as little as possible to avoid collision.
Here's a screenshot of the demo running with this configuration:

If we do set ∆t to be smaller than τ, agents will start slowing down smoothly as expected and deviate from their current trajectories when crowds start forming. The problem is that with this configuration, for some reason agents suddenly start penetrating one another and moving around while they're overlapping.
Here are two screenshots of the demo showing this effect:

Note that in a real-world application with physical robots for example, agents would obviously bump into one another instead, and the behavior from that point on would probably be undefined.

What confuses me even more is the fact that the formulation of the algorithm only mentions ∆t once, in the equation for updating positions at every iteration, and it doesn't say anything about the relationship between τ and ∆t.