0
\$\begingroup\$

I've decided to implement my own algorithm for optimal reciprocal collision avoidance. It doesn't use linear programming, but iteratively projecting velocity on intersections of ORCA lines and checks if it is collision-free. It works great for relatively slow units, but fast units tend to stop under certain circumstances.

The problem arises when there are two or more obstacles with the same velocity, and their velocity obstacles are intersecting with each other, and the goal velocity is inside the both velocity obstacles, and the goal velocity is close to the edges of both of the velocity obstacles rather than the truncated parts.

So, according to the ORCA lines, the closest collision-free velocity sometimes becomes not optimal, or locally optimal, which can cause a unit to slow down or go backward or even stop (when obstacles have zero velocity) while there actually exists a better collision-free velocity but is left out due to ORCA lines.

  • I've read some papers, but none of them mentioned such problem.
  • I've also tried to inspect the library which the original algorithm resides, but I was unable to understand it.
  • I've tried merging obstacles into single bounding obstacle, which worked when the problematic obstacles were only two, but when there were more of them, it caused a very big obstacle, which blocked the whole way the agent was supposed to use.

If anyone is familiar with the concept and can let me know how to deal with the issue, or if anyone has another idea, I'll be glad.

enter image description here

\$\endgroup\$
1
\$\begingroup\$

Okay, I've found the problem, and it was written in the original paper, which I missed among all other papers apperantly… I mean, there were tons of papers about it, that, for some reason I never thought of “What about the original research?”

Anyway, if anyone else wonders, it seems that, we are not suppose to use the goal velocity during creation of ORCA lines, but the current velocity of the agent. The reason to that is, the goal velocity is most of the time very big in size, like almost constant, so it has that problem I stated, but the current velocity is more dynamic. For example if an agent can't find a valid collision-free spot and stops or slows down, then in the next turn it will be doing all calculation with that zero or some small velocity, which has much greater chance of finding a solution.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.