raja-s / orca Goto Github PK

So the Line class is implemented based on the equation: y = a x + b, where a is the slope of the line and b is its y-intercept. This is not ideal in my opinion. For example, in case of a vertical line, the slope is set to std::numeric_limits<double>::infinity() from the limits package.

A better implementation could be based on the equation: a x + b y + c = 0, which I think represents all orientations of a line in a cleaner way.

Another possibility to consider is to represent a line by a point and a vector, which is equivalent to a line parametrization:
x = x0 + vx t
y = y0 + vy t

As the whole implementation is still buggy, reimplementing the Line class and readapting all the other classes using it might help uncover bugs and hopefully fix them.

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.

As is well explained in both the paper and the book, the linear program that maximizes a vector in the intersection of a set of half-planes could at any point in time not have any solution. In the implementation, this translates into an exception called LinearProgramInfeasibleException thrown at any point where the linear program is found to be infeasible.

When running the demos, I get this exception way too many times, especially in cases where the agents are clearly far from one another and can't possibly be on a collision course.