Anytime Heuristic Search. Hansen, Zhou

  1. Uses weighted heuristic search to quickly find some solution and then continues to search in the same manner to find improved solutions.  Considers generally how to turn recursive search into anytime search
  2. Previous work studied how to bound the error weighted search can introduce in terms of found policy vs optimal.  Generally it is assumed search is terminated after weighted search finds a result, but this paper proposes to keep searching after that point.
  3. The paper claims that as long as the heuristic is admissible, the first goal node selected for expansion is guaranteed to be optimal, but someone told me A* can lead to suboptimal results in the mult-goal setting…
    1. Whenever a node is expanded, it optimal value has already been computed
  4. Weighting the heuristic function makes the value estimate non-admissible, so the result found may not be optimal.  On the other hand, the result is generally found more quickly than in the case where an admissible function is computed.
  5. For f'(n)=g(n)+w*h(n), the cost of the solution can’t be more than a factor of w worse than optimal.  This solution is said to be epsilon-admissible for epsilon
  6. “Weighted heuristic search is most effective for search problems with close-to-optimal solutions, and can often find a close-to-optimal solution in a small fraction of the time it takes to find an optimal solution”  Basic idea of kappa in Bubeck’s stuff
  7. Other approaches of biasing search are adjusting weights according to depth in search, using weighted heuristics to identify a subset of open nodes that can be opened w/o loss of epsilon-optimality
  8. Can check convergence to optimal by computing costs with unweighted admissible heuristic (or just actual costs)
  9. Basic idea can be used with non-admissible heuristics as well, but I guess in that case the epsilon-optimality is gone
  10. They also discuss using heuristic to avoid pushing nodes that must be suboptimal onto the queue
  11. They also mention it may be good to apply pruning to items in queue that can’t be optimal can be helpful
  12. A node can be reinserted into the queue if its cost is later revised to be lower than originally computed, seems like the dynamic programming in LAO* is a better method than reprocessing the graph like this
  13. Proofs for convergence to optimality and bound of suboptimality of anytime weighted A*
  14. The upper bounds on the cost of the best path found are strictly monotonically decreasing
  15. The empirical performance of the algorithm is evaluated on 8 benchmark problems from biennial planning competitions.
    1. In some cases blew through 2 gigs of ram and couldn’t complete search
  16. Also look into sequence alignment, discusses method that doesn’t expand all vertices from each node
    1. A domain like this might serve FS^3 better than A* variants
  17. A big issue seems to be maintaining a small open list in terms of memory requirements
  18. Vanilla weighted A* is often faster than A* because in cases where there are many near-optimal paths, it doesn’t spend much time trying to differentiate between them.
  19. Anytime weighted A* sometimes reaches the optimal solution using less memory and time than A*.  A* is optimally efficient in terms of the #of nodes expanded, but not optimal in terms of these other metrics
  20. Instead of weights, could use any other non-admissible heuristics
  21. Show how to convert Recursive Best-First Search (has linear memory in the depth of the search) into an anytime method.
  22. RBFS is a heuristic algorithm that expands frontier nodes in a best-first manner, but does so with a DFS-based search
    1. Build a stack containing all nodes visited along the current path and all the siblings of those nodes, has memory requirements of O(depth*branching factor)
    2. Instead of going fully depth-first, RBFS keeps track of f-cost of best alternative path available from any ancestor of current node.  If f-cost of current path exceeds the next best cost over the nodes currently recorded by a certain threshold, backtrack and start search from cheaper nodes
    3. <Skipping rest of that as it doesn’t seem particularly relevant>
  23. Previous algorithm called Anytime Repairing A*(Likachev, Gordon, Thrun) is pretty similar to AWA* except it decreases the weight after each search and has a technique of limiting the node reexpansions.  It was used on real time robot planning.
  24. Reducing the weight after each step brings results closer to optimal each time, at the cost of potential longer search times
  25. Show an example where ARA* seems to have nodes stored exponential in that of AWA* (as weight increases)
    1. This is due to the changing weights.  Since using weights makes the algorithm inconsistent(a node can be expanded before its cheapest cost is found), a node may have to be put on the queue again so the new value can propagate through.  Changing the weights incrementally can make this happen over and over again.
    2. Also argue that the method used to prevent nodes from being readded to the queue causes more distinct nodes to be expanded and can prevent good solutions from being found.
  26. Discuss Real-Time A* which assumes search is interleaved with execution, also something called DTA*
  27. Depth-first branch and bound (DFBnB) are good for problems that have many solutions a the same depth (traveling salesperson).  Finds a suboptimal solution and then prunes anything that has to be worst than the best found so far.
    1. Ideas similar to DFBnB was brought into A* with Iterative-Deepening A* (IDA*), but this is bad in cases were all nodes have distinct edge costs (like if they are reals), empirically good a tree-searching
  28. Bidirectional A* starts one search from the beginning and one from the goal
  29. Some methods that do local-search by finding a suboptimal path and then exploring segments around the path.
  30. Also k-group A* that focuses on groups of sequences as opposed to one large sequence

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: