Swamp Intelligence Algorithm

Many real-time applications search for shortest paths in known graphs. Examples include strategy games where multiple units traverse a large board, as well as robotics applications where robots are required to navigate, planning their path through some environment. The frequency that the system has to search for paths can strain its resources and damage performance. Heuristics are commonly used to improve the running time of search over graphs. While heuristic algorithms, such as A*, usually succeed in improving search cost when compared to uninformed search algorithms, there is still much room for improvement.

This paper focuses on a method that prunes the search graph by removing areas where search is usually wasted; this pruning thus lowers the overall search cost.

The method guarantees that the paths that are found are optimal, even after the graph has been pruned

First, let’s consider “difficult search areas”. Consider the map given in Figure 1; in this example, algorithms such as A* (Hart, Nilsson, & Raphael July1968) (with a good heuristic) can search very efficiently in some areas of the map, while being very inefficient in other areas. Figure 1 shows the nodes that are expanded during a search from node S to node T, as carried out by the A* algorithm, using a Manhattan distance heuristic on a four-neighbor, two-dimensional grid. Note that while the optimal path that is eventually found is quite short, the number of expanded nodes is significantly larger. Many nodes are expanded inside the cup-shaped region, while the final path does not pass through any node in that region. In fact, any shortest path that does not start inside the cup or end in it will never pass through any node within it.

				T
				15	15	15	15
							15
			11	9	11		15
			11	9	11		15
			11	9	11		15
			11	9	11		15
		13	11	9	11	13	15
		13	11	9	11	13
		13	11	S	11	13
			11	11	13
				13

Figure 1: Nodes expanded during an A* search from node S to node T. Obstacles are marked in black, the expanded nodes are marked in light gray, and the f value used during the search is noted for each one. The path that is eventually found is marked in darker gray.

This approach will be to automatically identify areas such as the cup, which we will call swamp-regions, and store information about them in the graph, without wasting too much memory. Then, while searching for shortest paths between two nodes of the graph, we can block the search as it tries to unnecessarily enter those regions.

I begin by briefly reviewing related work before formally defining swamps on general graphs, and proving some of their properties before explaining how to exploit information about swamp-regions during the search to obtain shortest paths while expanding fewer nodes. Next, I present an algorithm to detect swamps on a 2D four-neighbor grid,

REVIEW OF RELATED WORK

Much research has been carried out in the field of artificial intelligence to improve the speed of search operations on graphs under various circumstances, while not consuming a large amount of memory.  A* (Hart, Nilsson, & Raphael July1968) and IDA* (Korf  1985) are widely used, where A* is usually faster but can consume more memory than IDA*. Several methods, such as (Sturtevant 2007), (Botea Muller, & Schaeffer 2004) and (Sturtevant & Buro 2005), use graph abstractions to increase the speed of search. Those methods pre-process a grid and build an abstract representation of the search graph, sometimes at multiple levels. The search is then done in the abstract graph, which is smaller, and is refined into the original graph. These methods have been shown to work well on large graphs, though they do not guarantee shortest paths, and sometimes require a path smoothing phase after the path refinement in order to get good results.

Another approach is to use previous searches to improve new search performance. LPRA* (Korf 1990), (Koenig 2004) and RTAA (Koenig & Likhachev 2006) search with limited look-ahead, and update the heuristic of the nodes visited.

These approaches solve the first move delay problem, but pay a price since the paths they find are not guaranteed to be shortest paths, and convergence time may be long.

LPA*  (Koenig, Likhachev, & Furcy 2004) and D*lite (Koenig & Likhachev 2002) reuse previous search information when the environment is dynamic; thus the path found in previous searches might no longer be passable, or might no longer be the optimal path, due to a change in the map. Those algorithms use the previous search information to recalculate the path, either from the original start point (LPA*) or from the current position of the agent (D* lite), and usually perform better than beginning a new A* search.

Exploiting swamps implies searching in a smaller set of available nodes, and can therefore be of benefit to all the algorithms mentioned above and many others. This algorithm just adds a pre-processing stage that should be executed once per graph.

DEFINITION OF SWAMPS

A swamp is an area in the graph such that any shortest path that passes through it either starts or ends inside that area, or has an alternative shortest path that does not pass through.

A swamp-set S in an undirected graph G = (V,E) is a group of nodes S ⊆ V such that any two nodes v1,v2 which are not part of S have a shortest path that does not pass through S:

For each v1, v2 NOT IN S, there exists a shortest path P_1,2  that connects v1 and v2 such that P_1,2 ∩ S = ∅

A swamp-region R Is a set of connected nodes that is a swamp-set. The Example below illustrates the definition of a Swamp

Figure 2 demonstrates a swamp-region. Let R = {s1,s2,s3,s4}. For any search from node S ∈ V\R to a node T ∈ V\R there exists a shortest path that does not pass through any of the nodes in {s1,...,s4}

		S4	S1
		S2	S3

Figure 2: An example of a swamp-region. Nodes filled in black are obstacles. Nodes {s1,s2,s3,s4} form a swamp region.

The external boundary of a swamp-set S, B(S), is the collection of nodes that are connected directly to nodes of the swamp-set but are not part of it.

OTHER PROPERTIES OF A SWAMP

PROPERTY 1

Let S be a set of nodes in  V. If for any two nodes on the external boundary of S, v1, v2 ∈ B(S), there exists a shortest path between v1,v2 that does not pass through S, then S is a swamp-set.

PROPERTY 2

Any connected component R that is contained in a swamp-set S, and is isolated from the rest of the swamp (i.e. B(R) ∩ S = ∅) is also a swamp-region.

PROPERTY 3

The intersection of two swamp-sets, S1 and S2, is not necessarily a swamp-set.

		2		1
		2	1, 2	1

Figure 2. Shows that the intersection of two swamp sets, is not necessarily a swamp set.

PROPERTY 4

The unification of two swamp-sets, S1 and S2, may not be a swamp-set.

		T	1
		2	S

Figure 3.  Shows the unification of swamp sets is not necessarily a swamp set’

Here, the node marked by one is a swamp set if all other nodes are not swamps. The same holds for the node marked by 2.  Their unification however is not a swamp set as the shortest path from S to T must pass either through node 1 or through node 2.

USING SWAMPS TO REDUCE SEARCH COST

A naïve approach to using a swamp-set to lower search costs is to consider them as blocked whenever a search between two nodes from outside the swamp-set is performed. The

Search is then performed on an effectively smaller graph, and could be expected to open fewer nodes. By the definition of swamp-sets, the path that is found is still optimal.

Using this approach, more nodes are pruned from the graph when the swamp is larger. However, in these cases fewer paths will enjoy the benefits of pruning, since any arbitrary source and target nodes are less likely to be outside a large swamp-set.

We will try to increase the benefits we get from swamps by using a swamp-set that is completely partitioned into different swamp-regions. As we later show, we can construct

a swamp-set such that any subset of the swamp-regions that make up this swamp-set will also constitute a swamp-set. This way, when we search between two nodes in the graph, we will consider any swamp-region that they do not belong to as blocked, and thus achieve significant savings on searches between swamp nodes as well. More formally, when searching for a path between nodes v1 and v2:

•         Let V be the set of vertices in the graph.
•         Let S be the full swamp-set that was found in the graph, and is completely partitioned   into swamp-regions such that every subset of swamp-regions forms a swamp-set as well.
•         Let R1 be the swamp-region that v1 belongs to, or ∅ If v1 does not belong to any swamp-region.
•  Let R2 be the swamp-region that v2 belongs to, or ∅ If v2 does not belong to any swamp-region.
•  Search only in the nodes of (V \ S) ∪ R1 ∪ R2.

PROPERTY 5

Thus searching under the above conditions maintains optimality in the sense of shortest path.

DETECTING SWAMPS IN GRIDS

Swamp detection algorithm is based on the fact that each swamp-region contains at-least one special node that we call a seed. We detect those seeds and then try to expand them into swamps.

Our definition of seeds is restricted to graphs that are represented by a 2D four-neighbor grid that may contain obstacles in some of the grid coordinates. This methods work for any other graph as well, except that, in those cases, more suspected nodes must be examined as possibilities for swamps. For simplicity of presentation, I will be using only graphs that are represented by 2D four-neighbor grids.

I will start by defining a seed before explaining how we utilize this to detect swamps that have the properties needed for property 5.

SEED

In a four-neighbor 2-dimensional grid, a seed is a node S ∈ V for which:

1. S is unblocked

2. At least one of the nodes above or below S is blocked (or does not exist)

3. At least one of the nodes to the right or left of S is blocked (or does not exist).

Thus every swamp region contains at least one seed.

The figure below shows a few seeds in a 2D grid

S2		S3
S1

Figure 4: An example of seeds. s1, s2, and s3 are all seeds in this example

THE SWAMP DETECTION ALGORITHM

The pseudo-code of the swamp detection algorithm is described in Algorithm 1. First, the swamp region is initialized to be the empty set and find all the seeds in the graph. Then, we try to extend each seed: first we check if it is a swamp-region by itself. If it is, we take the group of the seed plus all the nodes that it can reach in k moves (not including other swamp-regions), and try to trim it into a swamp. We keep increasing k until we reach our size limit or until a few consecutive rounds of increasing k do not change our swamp size (notice that if we increase our radius by k and do not find a large swamp it does not mean that increasing by k+1 will not find a larger swamp-region). We then return the largest swamp-region we have found so far

A swamp-set can be efficiently represented in memory. Each node in the graph needs just a few bits that tell to which swamp-region it belongs. This is very low cost (linear in the size of the graph), especially when considering currently available alternatives such as caching paths in the graph (where the number of paths is quadratic in its size, and therefore a large cache is needed to get significant improvements in performance).

Algorithm 2 describes how to trim a group of nodes into a swamp that contains a seed. First, we find the boundary of the group including points that are also inside other existing swamp-regions. Then, we go over all pairs of points on the boundary, and search for the shortest path between them, twice. First, we search while ignoring the current group (but taking into account the other swamp regions). Then, we search while counting our current group as a swamp-region as well. If the lengths of the paths differ, it means that the unification of this group with the rest of the swamp-set will not yield a valid swamp-set. We try to fix this by removing from the current group all nodes in the shortest path that passed through it, and then repeat the process. We are left with a group of nodes that is a valid addition to the swamp-set. However, the trimmed-down group may no longer include the seed, or may no longer be a single connected component.

To make sure we return a swamp that contains the seed, we only return remaining nodes in the group that are in the component of the seed.

Thus, after each stage t of the algorithm, swamps^t  is a swamp-set, and every subset of the regions in swamps^t  is also a swamp-set.

ALGORITHM

1.        THE SWAMP DETECTION ALGORITHM

procedure GROWSWAMPS (sizeLimit)

swamps⁰ = ∅

seeds = detectSeeds()

t = 1

for all s ∈ seeds do

region = extendSeed (s, sizeLimit)

if region not empty then

swamps^t =  swamps^t−1 ∪ {region}

t =  t + 1

procedure EXTENDSEED (s, sizeLimit)

radius =  0;

size =  0;

while radius < MAX  AND size <  sizeLimit do

cluster =  getReachable (seed, radius)

current swamp =  trimToSwamp (cluster, radius)

if size(currentswamp) > size then

size = size(currentswamp)

radius = radius +  1

return largest swamp found that had size less than size Limit

ALGORITHM

2.   TRIMMING TO SWAMP ALGORITHM

procedure TRIMTOSWAMP(s, group)

      B =  getBoundary(group)

           For all v1, v2 ∈ B do

P1 = findPath(v1, v2, swamps^t−1)

P2 = findPath(v1, v2, swamps^t)

              If length(P2)> length(P1) then

                 For all V_p2 ∈ P2 do

                   If V_p2 ∈ group then

                      Remove V_p2 from group

                         Add V_p2 to B (group)

CONCLUSION

The swamp algorithm addresses the problem of quickly finding shortest paths in known graphs. This is done by identifying areas that tend to be searched needlessly (areas we call swamps) and exploit the knowledge to improve search. This method requires relatively little memory and reduces search cost significantly, while still finding optimal paths.