Otte's Assignment 13

I read the PhD thesis of Maxim Likhachev for this assignment.

The thesis is titled "Search-based Planning for Large Dynamic Environments.

The thesis presents three search algorithms that can be used for the task of navigation (i.e. Finding a path) from a start state (node) to a goal state (node) in directed graphs. The thesis was written with the specific application of autonomous robot navigation in mind, however, the algorithms are applicable to a number of tasks. The three algorithms presented are: Anytime Repairing Astar Search (ARAstar), Lifelong Planning Astar(LPAstar), and Anytime Dstar(ADstar).

ARAstar is an anytime search algorithm, which means that it will return a solution quickly (though, probably a suboptimal one), and then spend more time iteratively refining that solution. Anytime algorithms are used for real-time applications that have large search spaces, where some solution must be found, but the optimal solution may take too long to compute. ARAstar has bounds on its suboptimality; therefore, the cost of any path returned is guaranteed to be within a tunable constant of the true cost of the optimal path (the smaller the bound, the longer the search will probably take).

LPAstar is an incremental search algorithm. Incremental search algorithms are commonly used when an agent is traversing a dynamic graph over time. Incremental search algorithms save information about previous searches so that they can perform subsequent searches more rapidly (by modify the old search results), instead of always re-planning the path from the agent to the goal whenever information in the graph changes. If implemented correctly, many incremental search algorithms are guaranteed to produce optimal paths.

ADstar combines aspects from the previous two algorithms to produce a graph search algorithm that is both incremental and anytime with bounded suboptimality. This is the first algorithm in the literature that can do both of these things at once.

Likhachev tests his first two algorithms against the current best (as of 2005), and finds that his perform better or comparable to the others. He also tests ADstar against a few other algorithms, but I think that the comparison may be less fair because he forces the other algorithms to use the same suboptimality constraint as the first search of ADstar–ADstar can then refine its search if there is more time left, but the other algorithms have no means of improving their suboptimality. Obviously this is consequence of not having anything else to perform a fair comparison against.

Experiments are performed on a variety of robotic platforms (including two rovers and a robotic arm), as well as on a few different types of simulated environments (sparse object worlds and fractal generated worlds). The latter provide a simple way to determine the average performance of the algorithms against their peers over the course of many trials.

I would say that the thesis was fairly well written and contained only a few obvious typos. I would recommend it to anybody that wanted an in-depth look a couple of different graph bases search algorithms.

Last modified 27 November 2007 at 9:36 am by MOtte