Fringe search
This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages)
|
In
In essence, fringe search is a middle ground between A* and the iterative deepening A* variant (IDA*).
If g(x) is the cost of the search path from the first node to the current, and h(x) is the
There are three major inefficiencies with IDA*. First, IDA* will repeat states when there are multiple (sometimes non-optimal) paths to a goal node - this is often solved by keeping a cache of visited states. IDA* thus altered is denoted as memory-enhanced IDA* (ME-IDA*), since it uses some storage. Furthermore, IDA* repeats all previous operations in a search when it iterates in a new threshold, which is necessary to operate with no storage. By storing the leaf nodes of a previous iteration and using them as the starting position of the next, IDA*'s efficiency is significantly improved (otherwise, in the last iteration it would always have to visit every node in the tree).
Fringe search implements these improvements on IDA* by making use of a data structure that is more or less two
An important difference here between fringe and A* is that the contents of the lists in fringe do not necessarily have to be sorted - a significant gain over A*, which requires the often expensive maintenance of order in its open list. Unlike A*, however, fringe will have to visit the same nodes repeatedly, but the cost for each such visit is constant compared to the worst-case logarithmic time of sorting the list in A*.
Pseudocode
Implementing both lists in one doubly linked list, where nodes that precede the current node are the later portion and all else are the now list. Using an array of pre-allocated nodes in the list for each node in the grid, access time to nodes in the list is reduced to a constant. Similarly, a marker array allows lookup of a node in the list to be done in constant time. g is stored as a hash-table, and a last marker array is stored for constant-time lookup of whether or not a node has been visited before and if a cache entry is valid.
init(start, goal)
fringe F = s
cache C[start] = (0, null)
flimit = h(start)
found = false
while (found == false) AND (F not empty)
fmin = ∞
for node in F, from left to right
(g, parent) = C[node]
f = g + h(node)
if f > flimit
fmin = min(f, fmin)
continue
if node == goal
found = true
break
for child in children(node), from right to left
g_child = g + cost(node, child)
if C[child] != null
(g_cached, parent) = C[child]
if g_child >= g_cached
continue
if child in F
remove child from F
insert child in F past node
C[child] = (g_child, node)
remove node from F
flimit = fmin
if reachedgoal == true
reverse_path(goal)
Reverse pseudo-code.
reverse_path(node)
(g, parent) = C[node]
if parent != null
reverse_path(parent)
print node
Experiments
When tested on grid-based environments typical of computer games including impassable obstacles, fringe outperformed A* by some 10 percent to 40 percent, depending on use of tiles or octiles. Possible further improvements include use of a data structure that lends itself more easily to caches.
References
- Björnsson, Yngvi; Enzenberger, Markus; Holte, Robert C.; Schaeffer, Johnathan. Fringe Search: Beating A* at Pathfinding on Game Maps. Proceedings of the 2005 IEEE Symposium on Computational Intelligence and Games (CIG05). Essex University, Colchester, Essex, UK, 4–6 April, 2005. IEEE 2005. https://web.archive.org/web/20090219220415/http://www.cs.ualberta.ca/~games/pathfind/publications/cig2005.pdf
External links
- Jesús Manuel Mager Hois's implementation of Fringe Search in C https://github.com/pywirrarika/fringesearch