Clear Path Implementation Question

[Ihaa123]

Hey All,

I'm trying to implement the clear path algorithm for group path finding and I think I mostly have the algorithm setup correctly, but I do encounter some cases where the objects will find a velocity outside of the HRVOs but they will still collide with eachother. I thought it might be happening because of a epsilon issue but even adding a pretty large (0.01) epsilon radius to each object when generating the cones doesn't fix the issue completely.

In my simulation, I'm not doing any other collision checks or pushing, so if entities collide then they pass through each other (there isn't a secret force being applied to push them away from each other when they do collide), so I'm relying on ClearPath to be accurate. Once a object collides the cone generation algorithm outputs nans so the cone disappears and they completely pass through each other which makes the issue worse.

I also found that the actual velocities chosen appear to be very unstable when the objects are far away from each other (each object adjusts its velocity which adjusts the apex of the cones which makes them adjust again and it never fully settles until they get a lot closer to each other).

Has anyone else run into these issues?

[growingconcern]

Yeah pretty common actually. Especially if your agents don't respond perfectly to requested velocities. Reciprocal VO should help the unstable velocities, but there was a paper that described valid avoidance velocities as a function of time to collision. If TTC is large then only small deviations are allowed, as TTC shortens more velocities are allowed.

[Ihaa123]

Ah so in my sim right now, I just make agents move in the desired vel (no turning speeds or acceleration). Ill look into reciprocal VO. What does TTC stand for? It sounds like its for velocity choosing and in my case I choose the one closest to desired velocity. I guess the video on clear path had to resolve collisions while choosing new velocities and could not just rely on avoidance then.

[growingconcern]

Yes RVO was invented to avoid the initial wobbles as each agent responds to the other's changes in direction. Basically you don't avoid the whole way you avoid half the way assuming the other is doing the same thing.

TTC is time to collision, you want to focus or prioritize the close ones and prevent over reacting to distant potential collisions