## Suboptimal Map Pathfinding Algorithms

This demo illustrates several different suboptimal path planning algorithms. These include:
• A*: f = g+h
This is the classical best-first heuristic search algorithm that combines g+h evenly to find the shortest path
• Weighted A*: f = g+w*h
This is a simple modification to weighted A* that finds w-optimal solutions. Weighted A* does not need to re-open states to find w-optimal solutions.
• Weighted A* (XDP): f = (1/2w)[g+(2w-1)h+sqrt((g-h)2+4wgh)]
XDP stands for convex downward parabola. This is a small modification to weighted A*. In Weighted A*, the set of states with the same priority are on a straight line. XDP changes this straight line to a parabola. XDP causes the best-first search to find near-optimal paths near the start and paths that are up to (2w-1) supoptimal near the goal. Overall the paths found are still w-optimal, and re-openings are not required.
• Weighted A* (XUP): f = (1/2w)(g + h + sqrt((g+h)2+4w(w-1)h2))
XUP stands for convex upward parabola. XUP is similar to XDP, except it looks for (2w-1)-optimal paths near the start and optimal paths near the start.
• A* epsilon: focal list f = h; open list f = g + h
A* epsilon introduced the idea of a focal list - the subset of states within the open that have a given property. A* epsilon interleaves greedy search to the goal with A* expansions to prove that the solution is w-optimal. (This implementation doesn't quite handle the focal list properly, but is a very similar approach.)
• Optimistic Search: optimistic: f = g + (2w-1)h; proof: f = g+h
Optimistic search relies on the fact that WA* often finds paths that are better than w-suboptimal. It searches with a larger weight to find the solution and then tries to prove that the solution is still w-optimal. Optimistic search re-opens states with a shorter path is found. (Note that in the demo below you can choose the w-bound and exactly which bound to use for the optimistic search.)
• Dynamic Potential Search: f = (w*fmin-g(n))/h(n) where fmin is the minimum f-cost on open
Dynamic Potential Search searches dynamically based on the minimum f-cost in the open list. It often performs quite well, but not on grid domains, because it must re-open states when a shorter path is found, and the open list must be re-sorted when fmin changes.
• Improved Optimistic Search
Improved Optimistic Search (IOS) is very similar to Optimistic search except (1) it doesn't re-open closed states in the optimistic portion of the search, (2) it has a better method of keeping track of improved solution quality, (3) it has better termination conditions, and (4) can use the alternate XDP/XUP priority functions.
• Improved Optimistic Search (XDP)
This is IOS with the optimistic search using the XDP search.
• Improved Optimistic Search (XUP)
This is IOS with the optimistic search using the XDP search.

### Instructions

1. Choose an algorithm
2. Choose suboptimality bounds (if appropriate)
3. Drag to select a path on the map on the left
4. The plot on the right visualizes the h (x-axis) and g (y-axis) of each state on the open list as well as the boundary of the priority function used to determine which state to expand next.

Algorithm: Optimality Bound: Search Weight (when applicable):