Monday, October 26, 2009
Not Bumping Into Things
Usually when I do research to solve some problem, I get fond of some particular method, try it out, get disappointed because it did not quite solve all my cases, then I try to track back towards the root of the idea to try to figure out what might have been the original motivation behind the solution and try to find a better suiting method from there.
My relationship with velocity obstacles has reached the point that I have gotten a bit disappointed with the solution. I have a feeling it has gotten certain things right, but it does not quite deliver.
It looks like the basic idea has been invented in the literature over and over again. For example one of my Google searches led me back to the old Craig Raynolds (Mr. Boids) paper from SIGGRAPH 88 called: Not Bumping Into Things.
I must have read that paper numerous times, but it did not strike me until today that it is actually describing velocity obstacles. The left side of the picture at to top of the post is from Raynold's paper, and the scribble right to it is my drawing from another angle.
I also found Fiorini's disseration, Robot Motion Planning in Dynamic Environments, which goes a bit more into certain details as well as list of references, which is missing from the paper that is usually available on the net. I wonder if his website along with complete list of publications is available somewhere? The one at NASA does not respond anymore.
One reason which made me revisit Fiorini's work is that unlike many more recent papers he tries to build meaning to the different safe velocity areas. One thing I noticed while testing VOs is that it is really easy to get a lot of noise in the input data, that is the cones jump around quite a bit, and that seems to be the greatest reason for any sort of oscillation problems. Shit in shit out, surprise, suprise!
Just take a look at this youtube video. The flashing red rectangle at top right corner is the velocity obstacles of the agent. I have witnessed similar behavior in my tests. Also, because of the feedback nature of the system once you get noise, it will amplify. One way to get rid of that (and as a side effect, inject a horde of other problems) is to either lowpass filter the velocity that is passed to the VO calculation or, lowpass the change in velocity. RVOs is kinda-sorta doing that, by adjusting the velocity towards the safe velocity just by a fraction.
So my gut feeling is that it is possible to build better method to choose good safe velocity by analyzing the arrange of the VO structure. I also think it is possible have better temporal behavior using similar tricks as in Coherent Stylized Silhouettes. The better temporal behavior should fix the usual pitfalls of VOs such as oscillations and choosing side to pass and still keep the system responsive.