Type of Research: Military; Private corporation, Science Applications International Corporation (SAIC), funded by U.S. Army’s Simulation, Training and Instrumentation Command (STRICOM).

Summary:
This research was undertaken to deal with problems encountered by SAIC with their Dismounted Infantry Semi-Automated Forces (DISAF) project (for more information see this web page). Specifically, SAIC’s Modular Semi-Automated Forces (ModSAF) software proved inadequate to the task of moving individual soldiers rather than vehicles.

This paper describes a multi-step process for pathfinding. The first step uses four levels of decision making to set objective points:

1. Long distance or strategic planning (which is ignored here).
2. Intermediate distance of “a few hundred meters”.
3. Short distance of “about a hundred meters”.
4. “Fine motion” which presumably covers everything less than a 100 meters.

However, the details of setting the objective points are not discussed in this paper.

The paper then discusses four different pathfinding algorithms:

1. Cell decomposition.
2. Skeletons.
3. Weighted regions.
4. Potential functions.

Cell decomposition consists of casting a grid across the terrain and then using an A* algorithm to assess potential paths. Each cell in the grid — which can be rectangular, hexagonal or irregular — may be given weighted values representing “anything related to movement, e.g., trafficablity, ground slope, or exposure to threats”.

The skeleton method employs Voronoi diagrams (see How Qualitative Spatial Reasoning Can Improve Strategy Game Ais. Forbus; Mahoney; Dill (2000) and Describing Topological Relations With Voronoi-Based 9-Intersection Model. Chen; Li; Li; Gold (1998) for a description of Voronoi diagrams as applied to terrain pathfinding).

The ‘weighted regions’ method was first described in “A Stochastic Approach to the Weighted-Region Problem: Design and Testing of a Path Annealing Algorithm” and employs a method of first assigning values to each cell and then casting rays in all directions, “… from the start point; each ray bends at region boundaries to obey the optimality criterion... The goal point must be “trapped” between two rays. The path found will be closer to optimal if more rays are used.”

The ‘potential method’ of pathfinding constructs, “a scalar potential (as in energy) function that steadily decreases to a minimum as the distance to the goal decreases. The potential function is high at obstacle boundaries and decreases as the distance to the obstacle increases. The path is determined by following the steepest descent down the potential value surface until the goal is reached.”

The paper then evaluated each algorithm in relation to the following criteria:

1. Path planning through an obstacle field
2. Planning an optimal path through regions of different cost.
3. Planning an optimal path through terrain with continuously varying cost.
4. Using exposure to threats as a terrain cost.

The table below summarizes the strengths and weaknesses of each algorithm as indexed with the evaluation criteria:

The authors conclude, “From the table, it is apparent that there is no approach that is good for all the requirements, but the cell decomposition approach is at least fair for all. We have selected cell decomposition as the path planning mechanism.”

The authors then construct a ‘search space’ of a “grid of 1 meter squares no more than 250 meters long by 200 meters wide,” that is oriented from the starting point to the objective point. The grid is then populated with polygonal terrain obstacles. An A* algorithm is then employed to determine a path. Each cell is weighted based on ground slope and exposure to enemy threats.

When a path is returned by the A* algorithm it is then ‘post-processed with the following procedures:

Exposed segments of the path are grown by one node so that the agent will have a chance to accelerate to a rushing speed before being exposed.

Segments requiring the agent to be prone are grown by one node so that the agent will be prone before it enters the area where it needs to be prone.

Standing segments between prone segments are checked to see how long they are. Short standing segments are replaced by prone segments so that the agent does not waste time standing up for just a short segment. If the standing segment is exposed, the distance threshold is increased so that the agent will more likely stand and run.

The path is examined to see if uniform segments–segments of the path that don’t change direction more than 45 degrees,

Left: Examples of Path planned through building to avoid exposure to threat (star).
Right: Path planned up a steep hill. The path goes laterally and then traverses the hill at an angle so that the effective slope is reduced (right).

---