Rediscovering Obstacle Avoidance

EDIT: Added picture describing the new method, video coming soon.

After fiddling around with the different methods to implement velocity obstacles (especially the directive circle style approaches), I noticed that there are two parameters which can be used to tune to get out of the cases where the agent is completely surrounded by the velocity obstacle. The parameters are: desired movement speed and time horizon. Time horizon means the latest potential collision we are interested in avoiding (or reversely, how early something should be avoided).


The directive circle or BOA style velocity obstacle implementations assume that the agent wants to travel at constant speed. This allows to simplify some of the calculations, since the admissible velocities can be found at a circle, which radius is desired speed. In practice it means that instead of choosing amongst all admissible velocities, we choose an admissible direction. Simplifies things a lot.


What should the system do, when all the directions are blocked? There two options and it is quite hard to choose which one is better.

The first option is to slowdown. That is, reduce the size of the circle. This usually leads the obstructed areas on the directive circle to become smaller and it may reveal new openings to follow.

The second option is to reduce the time horizon. The higher the time horizon value is set, the earlier the obstacles are avoided. By reducing the time horizon value, the velocity obstacle cones will be truncated more, which gives some extra space around the agent to manouver again.

The directive circle (and ND, and VFH) approach looses it charm one you start to try to solve those two problems. You end breaking their simple and intuitive premise and either doing a directive circle for each velocity you might find useful and even more complex spaghetti to choose amongst them. One of the biggest problems is that you need to make decisions based in binary data, which leads to jittering when you try to chanse the correct value.

This led me to another idea, which combining several things I discovered while prototyping the different methods.


Recursively Reciprocal Directive Velocity Obstacle Circle

By exercising the age old AI truth: "In case of doubt, discretize and brute force!" I managed to make yet another sampling based obstacle avoidance, which is super simple to implement, easy to understand, intuitive to tune and seems to work well in practice too.

The basic idea is:

1. Sample the first time of collision at different directions around the moving agent
2. Score each sample based on time to collision and how much it deviates from the desired movement direction
   
3. The direction with best score is chosen
4. That's it!

Calculating the time of impact for two moving circles is simple, it is featured in books and there probably some code laying in the webs too. The devil is of course in the details, as follows.

To get it working better, I introduced minimum and maximum time horizons. The max time horizon is used to clamp the time-to-collision values, so that every direction where collision is not likely to happen really soon now gets the same time-to-impact score. This will make sure that the nearest direction will be chosen instead. Larger max time horizon will make the agent to avoid things earlier. This can be thought as sort of shininess factor.

The minimum time horizon is used to scale down the velocity. If the time-of-impact towards the best direction is less than min time horizon, the velocity is scaled down proportionally. That is, if the agent is standing next to an obstacle, the velocity will be scale to zero. Or if the agent tries to run towards a wall, the system will scale the actual velocity down.

Another thing that can be adjusted are the weights used for score calculation. If the time-of-impact is weighted more, you tend to get more straight segments of movement, while if the angle difference is weighted more, the agent tends to approach the goal more. Usually that means more wiggly trajectory in micro scale, but more goal directed movement in general.

That sort of solved most annoying problems that the directive circle type of methods, namely speed selection and approaching a goal in front of an obstacle.

On top of all that I use multiple iterations. This adds the needed reciprocal, recursive or reflective or any other R starting property into the mix. What it means in practice is that the velocity selection does not flicker that much nor does the system have problems choosing sides on head-to-head cases. It should be possible to extend the system to use the reciprocal rule too.

All in all, it is quite a bit similar to the reciprocal velocity obstacles implementation except that I formulated the change in speed in different terms. In practice this means crap loads of less samples (although you can have them back by using more iterations).

I'm so happy about this discovery that I think I'm going to go and have a beer instead of digesting yet another heap of more papers for supper :)