Bot Navigation: Advanced Obstacle Avoidance
Alex J. Champandard
Alex J. Champandard
This seems to be a very important issue for the average gamer, but bares little challenges for a bot. Strafing is simply a matter of looking in a different direction than the movement, so strafing around a corner is simply a matter of looking ahead around that corner. So you simply run the navigation code independently, and decide the focus point afterwards.
In practice, you may need to express the movement vector as relative to the view vector, which can be done with matrix math to rotate the vectors, or using the standard helper functions that come with your standard quake like engine (see the page on Alternate Circle Strafing for more low-level details).
The issues raised by this involve having to simulate movement outside of the field of view of the bot. This is acceptable, as most production bots use navigation meshes that allow them to control their movement regardless of whether they can see the location or not. If this is problematic, some sort of caching representation of the local surroundings may be required. Queue my current research description... ;)
So far, the speed has been inflicted on the neural network as a requirement: it must be able to avoid walls at running pace. Although existing work in robotics and steering behaviour has indentified the need for a braking action together with steering, this was considered to be an independant aspect of the obstacle avoidance. So the motion steering and speed control systems were separated. This allows the speed to be controlled by high-level path-finding algorithms, potentially over-ridden by a braking force. A simple neural network could be trained to do this, using a sense of urgency in the proximity of the obstacles as heuristics. This is part of on-going work, and is showing great promise.
Jumping and ducking can also be considered as independant from the steering direction. The first thing that need to be changed is the movement simulation code. This is trivial for the ducking case, as it's simply a matter of simulating a walk with a smaller bounding box. For the jumping, this requires a more complex gravity based simulation, so that maximum jumping distances can be anticipated. As you can expect when scanning the terrain for places where the agent can potentially land, this is fairly expensive!
Then it's only a matter of triggering the jump if the navigation decides this is the path desired. There is little need to train a neural network for this, as a simple hard coded function would perform best. The same applies to ducking. If the next step is taken within a confined area, the state should be set to 'ducking'.
Water is challenging in that the agent can move along three axis, including up and down, giving it six degrees of freedom. Solutions to this problem involve sampling the distances by rotating around the Z axis as well as the X axis (+Y is up in Quake based shooters). This solution increases the search space size of the neural network solution drastically, but with the enhancements presented, this should cause no problems.
A simple alternative to this is to apply the existing neural network to the pitch as well as the yaw. This allows the samplings to be reduced to 2 * N instead of N ^ 2, and produces acceptable results.
The final thing to consider is to force the bot to move updwards when he's running out of air.
As I was watching intermediate generations of not especially good bots, I noticed one was hugging the wall on the left side perfectly. When he found a corner, he turned to follow the rest of the wall. This was a complete accident, a miracle of evolution, most of which are considered completely useless.
In this case, the wall following has below average obstacle avoidance skills, due to it driving the bot in close proximity to walls. However, by rewarding the bot for moving forward instead of punishing him for being close to a wall, this fitness can be artificially increased. Also, by rewarding minimal distances on the left hand side, and punishing close distances on the right side, the bot will learn to follow the walls explicitly.
So why do we need wall following? I honestly don't know yet. I just have a hunch that this will come in very handy during the level recognition...
With regards to multi-agent systems, there's a lot of work being done on setting low-level rules and observing the emergent behaviour. This is admittedly very interesting, but often it's more a case of wanting to set high-level behaviours no matter what the underlying rules are. This neural network and genetic algorithm approach allows this very simply. By setting a fitness function that judges the entire population, emergent behaviours can be specified.
Croud simulation is the first thing that comes to mind for this kind of work.
I've just started research on this, notably for level exploration. The results are very interesting to say the least. Multiple agents can cooperate together to learn complex levels by knowing nothing but local obstacles. More on that soon!
All along the development, I've mentioned human attributes that were observed in the obstacle avoidance. All these could be put together in a list of parameters, and specified to the learning mechanism. Things like clumsiness, laziness, drunkeness or efficiency are all parameters that can be tuned, or randomly created along with the bot's personality
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?