Bot Navigation: Design Philosophy
By ai-depot | June 30, 2002
A Modular Framework
If you’ve paid attention so far, you should realise the need for three components.
Reactive Obstacle Avoidance
Goal
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.
Data
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.
Options
Without going into too much detail, there seems to be two possibilities for implementing this component:
- An explicit mathematical approach, based on equations of movement taking into account the sensor parameters and values. The problem with this approach lies in the confection of generic equations to take into account many situations. This can be a very time consuming process. On the other hand, once implemented it can be simulated efficiently, and tested thoroughly.
- A machine learning approach, which would involve training neural networks to perform this task for us. The advantages lie in our ability to control the behaviour with higher level parameters: a fitness function that we will use with the optimisation algorithm.
Deliberative Path-Planning
Goal
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.
Data
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.
Options
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.
Amalgamation Component
Goal
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).
Options
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.
Tags: none
Category: essay |
October 7th, 2007 at 8:44 am
thanks .. .good