Basic RVO code seems broken (dtObstacleAvoidanceQuery::processSample)

[Jesse Cluff]

I'm posting this because I don't understand the purpose of the code in question and I have nothing to compare it to to determine it's correctness.

The lines in question are these inside if dtObstacleAvoidanceQuery::processSample:

// RVO

float vab[3];

dtVscale(vab, vcand, 2);

dtVsub(vab, vab, vel);

dtVsub(vab, vab, cir->vel);

I get the last line which is getting the relative velocity of the obstacles.

What I don't understand is why vcand (the candidate velocity) is being scaled by 2 and then having the velocity of the agent subtracted from it.

This *appears* like an ad hoc way to combine vcand with the current velocity.

But just subtracting these velocities doesn't seem like a valid way to blend them. 

Is there some mathematical explanation for this code? I'm reasonably familiar with RVO math and I can't find anything analogous with the conventional formulations.

In the case of a velocity lateral to the vcand why would it switch the velocity to the opposite side of the agent? 

It seems quite easy to show it wrong in the case of a vcand of 0,0,0 which results in a combined velocity opposite to the current velocity - which is why I discovered this - I was having sweepCircleCircle detect a potential collision between objects that were moving away from each other and the agent in question was wanting to remain still (vcand was 0,0,0).

I tested another scenario where I got an agent to run through the origin and created a procedural obstacle to avoid at the origin (a dtObstacleCircle at the origin with zero velocity and setup the side vectors just like dtObstacleAvoidanceQuery::prepare), the original code above had great difficulty navigating around this simple stationary circle.

If I simplified the code to 

// RVO

float vab[3];

dtVsub(vab, vcand, cir->vel);

It passed the simple stationary circle avoidance perfectly. However this results in pretty terrible avoidance in the general case.

The original code seems to work in most cases though and has been around for a long time. So I'm terribly confused.

Thanks for any assistance.

[Mikko Mononen]

Hi,

I'm not sure how I came up with the equation. There must have been a reason for it :) The times 2 looks like some odd version of the reciprocity rule.

The example you have is not taking reciprocity into account.

I would expect the code to look like this:

vab = vcand - (vel + cir->vel) * 0.5;

float vab[3], tmp[3];

dtVlerp(tmp, vel, cir->vel, 0.5f);

dtVsub(vab, vcand, tmp);

How does that work in your tests?

--mikko

--

---
You received this message because you are subscribed to the Google Groups "recastnavigation" group.
To unsubscribe from this group and stop receiving emails from it, send an email to recastnavigati...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Jesse Cluff]

Thanks so much for your quick response Mikko!

But no that didn't really work. I wasn't sure if you also implied the subtraction to get the relative velocity too so I also tried this:

//vab = vcand - (vel + cir->vel) * 0.5;

float vab[3], tmp[3];

dtVlerp(tmp, vel, cir->vel, 0.5f);

dtVsub(vab, vcand, tmp);

dtVsub(vab, vab, cir->vel); //tested with or without this line

I'm really wondering how to validate (even conceptually) my changes to this system.

What is the point of subtracting my velocity from the vcand? 

Is this trying to compensate for the fact that I can't update my velocity to vcand instantaneously?

If it had infinite acceleration could this term be removed? Though if I couldn't update to vcand quickly I'd be considering a velocity toward me current velocity not away from it.

The "dtVsub(vab, vab, cir->vel);" is required because the sweepCircleCircle assumes that the circle is stationary and the velocity of the agent is the relative velocity of the two.

Basically sweepCircleCircle doesn't know anything about RVO, it's just testing if one moving circle is going to hit another stationary circle (thus the relative velocity - if the function was changed to accept two velocities we wouldn't need to do any consideration of the cir->vel). 

We're just gathering information about a potential velocity from ourselves and intersecting it with the agents around us. This calculation doesn't require our velocity at all and the classic VO formulation doesn't involve our velocity (a velocity obstacle is formed by our positions and the velocity of the other object - we have many potential velocities we can test it against). We only add our current velocity into the mix when are trying to offset the VO by (our velocity + their velocity) * 0.5 (which is RVO - which I don't see any of in the detour crowd code. It looks like it's VO + the side bias in the sample ratings. Note I'm not trying to add this in or anything, I'm happy with VO method of detour crowd - I just want to understand this more deeply).

Thanks again.

[Mikko Mononen]

Hi,

It's been so long ago that I have forgotten most of the details. At quick look, the original RVO paper [1] has formula which multiplies something by 2, and their sampling based reference implementation has:

Vab = 2*vCand - _v - other->_v;

So I suspect that I have picked it up from there. I'm pretty sure vab has both the reciprocity as well as the relative velocity thing required for the circle-cast.

[1] http://gamma.cs.unc.edu/RVO/icra2008.pdf

[2] http://gamma.cs.unc.edu/RVO2/downloads/ (version 1.1)

--mikko

[Jesse Cluff]

Oh awesome, thanks for the references!!

I was doing some testing and tried just using:

dtVcopy(vab, vcand);

dtVsub(vab, vab, cir->vel);

And that along with some tweaks to the toi penalty:

tpen = tmin >= m_horizTime? 0.f : m_params.weightToi * (1.0f / (0.1f + tmin*m_invHorizTime));

was giving some good consistent results. The avoidance looks a little less predictable but less slowing down and less stuttering as agents approach each other.

I'm almost starting to suspect that the stuttering on agents approaching of the original code is just them getting bad velocities which put them repeatedly on a collision course, eventually resulting in them slowing down and perhaps at that point there are fewer options to escape the upcoming collision so they tend to take more predictable paths out of the upcoming collision. But that last bit is pretty speculative at this point.

Anyways thanks again for the references I'll dig into that stuff there.

[Jesse Cluff]

So I made some progress (still waiting to hear back from Guy on what his thoughts about the code in question is doing in RVOLib). 

Basically I'm pretty sure that vcand can just be used directly like this:

dtVcopy(vab, vcand);

dtVsub(vab, vab, cir->vel);

After a little more investigation I also figured out how to do RVO in your system too. The basic premise behind RVO is that if you find a candidate velocity not in the VO of the object you're trying to avoid you simply average it with your current velocity. That's it.

So basically you take the best vcand (tested as above) which is stored as "res" - inside of dtObstacleAvoidanceQuery::sampleVelocityAdaptive and just call

dtVlerp(nvel, res, vel, 0.5f)

instead of 

dtVcopy(nvel, res);

I don't get any phantom collisions when my vcand is zero, it avoids stationary objects, and I don't get any slowdowns or stuttering on the 4 person passing in the middle test.

All in all I'm quite happy with it (I'm also using a pretty small number of samples (relatively speaking).

Anyways, thanks again for your help,

Jesse

[Jesse Cluff]

Just wanted to follow up one more time. 

Though what I described above does work I wanted to support variable levels of avoidance (not just 50/50 reciprocal avoidance) so this necessitated adjust the VOs inside processSample. I worked out the math and came out with exactly what you originally suggested. The odd thing is that the results are so different, my hypothesis is that it is interacting with the sampling pattern differently. I realized then too that the version of DetourCrowd I'm using is from Unreal Engine so I tried the original change back in the GitHub version or RecastNavigation.

The change:

float vab[3], tmp[3];

dtVlerp(tmp, vel, cir->vel, 0.5f);

dtVsub(vab, vcand, tmp);

greatly improves the collision avoidance in the RecastDemo program (I built an extension to the TestCases system that runs through some crowd avoidance scenarios). Looks pretty slick actually, I'm impressed with the quality of your solution - the adaptive sampling with the RVO fix performs really well.

Interestingly, the tuning of the penalties is very sensitive, basically any change I made to "improve" it made it worse.

Next step was to changes UE's system to be something much closer to the version on GitHub, however I'm still getting poor results, I've made changes to our system to make it better, but when I try those changes out in the GitHub version the results are worse. There are quite large differences in scale, speed, how the agent's position is updated each frame, frame rate, etc. So there's more work to do figuring out what's going on.

But regardless of all that I just wanted to let you know about the fact that the RVO code as it exists on GitHub currently is broken and vastly improved by your original suggestion.

[Mikko Mononen]

Thanks for following up. When tuning the variables I suggest to run the brute force (grid) method with a lot of samples. It allows you to see "ground truth". The adaptive sampling has its' own quirks and sometimes hides problems. Tuning the variables is black magic indeed, just like tuning a PID. Feedback systems are like that, unfortunately.

Would you mind adding an issues to the github page referencing to this discussion? Also if you can suggest test cases which show good/bad behavior of the avoidance, I think that would be a good starting point for whoever is taking a stab at fixing the problem.

--mikko