Bot Navigation: Design Philosophy
Alex J. Champandard
Alex J. Champandard
If you've paid attention so far, you should realise the need for three components.
This module must be capable of avoiding small obstacles that litter the path of the agent. Do do this, it will have to provide a desired direction change. Most objects will be of small magnitude, so minimal deviations will be common. The agent must, however, retrace his steps if a full obstacle impedes his way.
After the obstacle is avoided, the agent must return to the intended path, in order to reach his destination. In the event of a large object obstructing the desired path, it will need to be re-planned to take that into account. A indicative signal from the reactive component may therefore be required.
This must be done in an automated fashion, since obstacles are of little importance. This allows the agent's A.I. to concentrate on higher-level problems.
In order to provide decisions based on the current position, the module will have access to sensor data. The sensors will be simple distance detectors, reporting the gap with the closest wall in a given direction.
For computer games, this data will usually be accurate. The agent should benefit from this, but the possibility of noisy data should also be considered. For mobile robots, this is often the case: precise sensors are usually very expensive.
Efficient use of these sensors will be necessary, as the information may be expensive to compute dynamically within a game. For robots, the sensors may be costly, imposing the design with a minimal number of them. The solution should, therefore, be able to deal with small amounts of information.
Without going into too much detail, there seems to be two possibilities for implementing this component:
Firstly, and most importantly, the agent should be able to learn the structure of the terrain automatically. This implies laying out the waypoints as the bot moves within the level. Over time, performance will increase. Human like deficiencies should also be possible, for example forgetting areas of the map and not using the shortest path.
Planning should be dynamic, allowing a change of routes depending on context specific conditions (enemy in the way, armor pack not respawned yet). This will also allow to learn paths, in a similar fashion to human routine. Preferences should also be dynamically assigned to paths, based on good or bad experiences.
In order to layout the set of waypoints, the current position of the agent will be known at all times. Together with that, the existing set of waypoints will be accessible in memory. Finally, to assist the optimal creation of the graph, the immediate surroundings of the agent may be used.
Most bots currently use waypoints. These waypoints are mostly static, created by the designer or the user with various tools. Some waypoints are placed algorithmically, but they are usually grid based, which limits the flexibility of the solution.
A few notable efforts have been made to learn the map, but these are based on human interaction. The Eraser bot uses human routes to navigate, but individual routes are fairly long complex and the connectivity does not realistically represent the level's structure. The solution proposed should allow automatic learning of waypoint and their connectivity.
The only goal of this component is to combine the result of the two previous modules. This should be done in such a way that does not compromise the life of the agent. Indeed, by ignoring either of the orders, problems may arise (e.g. never reaching the destination, and falling in simple lava traps).
There are two solutions that seem particularly interesting:
A third party component that deals with the immediate result of the two others. This may be problematic to do explicitly using vector math, as some in-game situations may not be taken into account by the equation. The neural network learning approach would be better suited to this task.
The final decision can be integrated to the obstacle avoidance module, by feeding it the desired heading which resulted from the path-planning. Once again, the same problems apply, so a learnt solution is prefered
Remember you can visit the Message Store to discuss this essay. Comments are always welcome!. There are already replies in the thread, why not join in?