Type of Research: Academic.
Summary:
Cohn’s paper is a good introduction to qualitative spatial reasoning (QSR). QSR is a “subfield of AI” that deals with not only “our everyday commonsense knowledge about the physical world, but the underlying abstractions used by engineers and scientists when they create quantitative models.”
One of the interesting standard assumptions in QSR is that change is continuous. This becomes obvious when you think of QSR in terms of 3D terrain data (such as DTED or DEM files). While two adjacent points might have values of +2 and +4 it is obvious that there is a place between these two points with a value of +3.
Forbus, et. al., suggests that QSR is a logical tool to be used in strategy game AI routines. They specifically look at two types of problems (terrain analysis and pathfinding):
The three figures above illustrate the “Massed Fire” problem (Figure 3 is the solution for Figure 1) and the Ambush problem. The pathfinding problems (a constant source of angst in computer wargame AI) could, theoretically be facilitated by Voronoi diagrams:
In the above for snapshots:
- The original tactical battlefield map.
- The areas of the map that are impassable to armored vehicles.
- The Voronoi diagram (which calculates a path equidistant between obstructions).
- The free space areas. “This description of free space and corridors still needs work — for example, there are edge effects where the distinctions between regions and paths seem visually unnatural. However, we do find it encouraging, given that we have only just started exploring this space of algorithms. From a practical standpoint, it is important to note that these computations only need to be done once per map. The entire sequence of computations described here took six seconds on a mid-range machine, using a Javabased general-purpose implementation.”
