Bot Navigation: Neural Networks for Obstacle Avoidance
Alex J. Champandard
Alex J. Champandard
Obstacle avoidance is a problem that has been often tackled in the past, mostly in the context of robotics. Many branches of A.I. can be applied to the problem, as the following examples will demonstrate.
Figure 1: Flight trajectories of the individuals in the genetic algorithm population at generation 10. In red is the fittest fly.
Genetic Algorithms have been applied to evolve the behaviour of a fly, passing through a simulated 3D environment crammed with obstacles. Given sensor information from the environment in front of it, the fly is capable of interpreting it and translating it into movement. This is done by two very simple perceptrons, each providing the ability to turn the insect in one direction. After about 28 generations, the fly is able to reach the end of the pre-defined obstacle course.
You can find out more about the project on the McFly page.
More elaborate neural network models have also been evolved in an incremental fashion. They are also fed infra-red sensor data on the input, but this time there are placed both in front and behind. Much incoherence in the results are caused by different lighting conditions, and neural networks are trained to recognise this. Using accurate simulations for the evolution, the solutions can be integrated into real-life robots, displaying complex behaviours which were not possible using standard evolution techniques.
The Neurorobotics lab has a page with such neural network based approaches. There are also many papers available on citeseer.
Figure 2: Trajectory of an agent avoiding a set of obstacles represented as black boxes. Simple fuzzy rules are used to determine the steering action.
Fuzzy logic has also been successfully employed for obstacle avoidance. A set of fuzzy rules was devised in order to provide the navigation for simple robots. Very smooth behaviour was thereby obtained, allowing the reactive behaviour to be blended with the movement corresponding to higher-level destination parameters.
You can see the results, and find out more on their site called fuzzy logic in autonomous navigation. There's also another example of fuzzy logic combined with genetic algorithms, all wrapped up in a nice tutorial.
Figure 3: Screen shot of the java demo demonstrating an agent in a crowded environment. The grey circles are obstacles, which are avoided by applying a steering force away from the potential collision point.
Last but not least, Craig Reynolds has created a very popular model generally applied to flocking. The approach is based on explicit mathematical equations which were devised manually, allowing each autonomous character to modify its state at each step of the simulation. The decisions are based on simple sensor data, collecting the distance of the obstacles.
His paper is online, as well as some very sexy java demos. You can find them here
Remember you can visit the Message Store to discuss this tutorial. Comments are always welcome!. There are already replies in the thread, why not join in?