Ever since RVO2 library came out, I've been itching to dust off my old ORCA test and try to get it to work. I really like the simplicity of the method.
I don't have the required intuition to debug linear programming, so I opted to calculate the union of the constraints as polygon clipping instead. I start with a rectangle, which roughly describes all the admissible velocities, and chip away each of the constraints using poly-plane clipping algorithm in 2D. In above picture the result polygon is drawn in white.
As suggested in the RVO2 forums, in case the resulting polygon would be empty (no admissible velocities), I remove the constraints one at a time, starting from the furthest agent. You can see this effect in the above picture, the green constraints would make the polygon null, so it is discarded. This is simpler initial alternative to 3D linear programming.
While implementing the method I ran into quite a few problems. These can be due to my lack of understanding the method, or because my actual implementation differs somewhat from the RVO2 code.
Firstly, I'm visual person so I always need under-the-hood view before I can understand some method. There was quite a big leap from the agent position and velocity to the actual constraint plane. So I first spent some time trying to see where the planes come from.
Secondly, I have hard time understanding all the intrinsic details of optimal velocity, and I'm even more confused when I compare the paper vs. the library code.
When reading the paper I get the feeling that the planes should be recalculated if you choose another optimal velocity but the library does not do that. The lib calculates the planes once, as if optimal velocity would be current velocity and then uses linear programming to try to find solution to different optimal velocities.
I get super horrible feedback effect if I set optimal velocity to the current velocity, so I used desired velocity instead and things kinda work. Kinda.
Thirdly, I cannot see how the method is able to choose good constraint planes by selecting a single choice for each object. I hope I'm missing something big here.
For example, let's take a look at the picture at the top of this post. That green plane messes things up big time. Had the method chosen the other side of the obstacle, the case would have had good solution.
Even in slightly crowded scenes that kind of problems occur a lot. Many cases I traced through, calculating the constraint using optimal velocity of zero would have solved the problem. I could not figure out good rule when to choose which one of them. I tried some obvious ideas but there always was another case which failed after the change.
I would love to love the ORCA method, but I have had a lot of trouble getting it to work.
I have a hunch that the structure of the combined velocity obstacle plays big role in temporally coherent velocity selection. Fiorini & Shiller described the structure very well in their early papers, but I have not seem much research on that field ever since.
Hope that you will get it to work a 100%! :P
ReplyDeleteGetting it to work at 99.9976% would be fine too, just like 99.9945%.
ReplyDeleteNot entirely sure about 99.44% and below though ...
Olá Mikko!
ReplyDeleteI've also implemented ORCA recently and I'm quite satisfied with the results. I haven't found out a case where it doesn't work well, but I have implemented a few things extra-paper that made it a lot more robust:
1. Agent A only considers agents that he can see as obstacles. An example of this is if two agents, A and B, are moving in a line and agent A considers agent B that is right behind him, then agent A will not be allowed to stop, as agent B which is behind him, putting a constraint on his speed. It was funny to see, though. :)
2. If agent A agent can see agent B but agent B cannot see agent A, then agent A is responsible for fully avoiding the collision, so the half-plane is offset 1*u, as opposed to 0.5u.
3. I couldn't fully grasp the 3D-LP algorithm either so I decided to also go for the ClearPath method, and retry with 1 less agent (furthest away). I stop removing agents if the next agent is closer than MaxSpeed. If this fails I'm happy with the agent stopping until he can move again. This seems to work well in most situations.
Overall, I'm quite happy with the results compared to previous methods. I haven't implemented static obstacles yet - I ran out of time - but will once I pick this up again...
In your picture all your ORCA lines are suspiciously matching the edges of the VO cone, which unless I got something wrong it shouldn't be the case. The half-plane is supposed to be 0.5u offset from the agent's velocity. u is supposed to be the minimum change in relative velocity to avoid collision.
Moi Márcio,
ReplyDeleteNice to hear that others are testing orca too!
You're right, the planes should be offset by 0.5*u, but for some obscure reason I did not have time to figure out, my stuff worked better with whole u. I have investigate why it is like that. I build it on top of my previous clearpath code, so it could be that I'm applying some halving somewhere else.
Or it could be because I'm using plane clipping instead of linear programming to find the admissible velocity region. I was planning to test a tweak at some point. The basic idea is that instead of dropping the agent, I would use a plane which is calculated using vopt=zero (as if the agent would like to stop).
You can find a bit more elaborate explanation of that here:
http://wwwx.cs.unc.edu/~geom/RVO2/forum/topic.php?id=3
I've also been experimenting with ORCA a fair bit and have had similar challenges. You are correct in that the algorithm really suffers from picking a side to pass without considering any other choices it has made (and will never reconsider them). This was done for performance reasons, but they get out of it with their 3D linear programming solution (which unfortunately isn't very fast). Basically, I think ORCA doesn't work unless you use that fall back if the straighforward linear programming solution can't find a solution (which is often), basically it finds a "least bad" solution and hopes that things clear up in the future (which they usually do).
ReplyDeleteHere is the linear programming solution they used:
ReplyDeleteThe general strategy we used for linear programming is described in "Computation Geometry: Algorithms and Applications" by M. de Berg et al, Chpt 4, pages 64-94. I don't have the book in front of me, but I don't think the authors name their algorithm, but it is characterized as a "randomized half-plane intersection" algorithm.
Their strategy is simpler (read faster) and more efficient that other methods for low number of dimensions. The basic idea (in 2D) is:
1) Break up the boundary region into several line segments (l1,l2,l3....)
2) For each line segment, Compute the point of minimum distance to each between segment from the desired point (p1,p2,p3...)
3) Choose from p1,p2, p3 etc. the one closet to the desired velocity.
Step 1 could be O(n^2) in worst case, but is linear, on average, in practice