Many problems in planning robot motion can be phrased in terms of finding a path from some starting configuration (or set of configurations) to some goal region in configuration space. Fortunately, the computer science community has studied a similar problem: finding a path from one node in a graph to another point. Unfortunately, the configuration space of a robot is often continuous, and it is not always clear how to represent the connectivity of configuration space by a graph.
This lecture is a brief review of various flavors of graph-search algorithms. Over the next lectures, we'll see some examples of how continuous configuration spaces can be discretized (sometimes cleverly) to allow graph-search planning.
If this lecture is not a review for you, I would recommend chapter three of Russell & Norvig's "Artificial Intelligence: A Modern Approach". You can get this book in the library or borrow a copy from me.
Uninformed graph search strategies
Considering the following map showing a very rough description of the connectedness of various points in Hanover. There are vertices (or nodes) showing locations, and edges connecting adjacent locations. The numbers along edges represent some estimate of the number of minutes needed to drive in a car from one location to another.
A path is described by a sequence of nodes. For example, Sudikoff-Inn-FoodStop-gas-WRJ would represent a path from Sudikoff to White River Junction. The cost of the path is the sum of the cost of the edges along the path. Between two nodes, there may be one path, many paths, or no paths. The graph-search problem takes as input a representation of the graph, a starting location, a goal location, and returns as output a connected path. If there are many paths, the graph search algorithm may have some criterion or property that chooses one of those paths preferentially; for example, it might choose the shortest path (based on cost of edges), the path that visits the least intervening nodes, or it might just choose a path arbitrarily.
We would like to know: how fast does the algorithm run? how much memory does it take? how "good" are the paths returned?
Data-structures review: linked list, graph, stack, queue, priority queue
I asked in class, and it seemed like most people were familiar with these data structures. If this is not the case, please come see me in office hours so we can catch up!
Depth-first search
We'll need a few data structures, in addition to the graph. First, a stack that will contain the next locations to explore, OPEN. Second, a set of locations already explored by the search, called the 'visited list', or CLOSED. (Possibly, CLOSED would be implemented by a hash-set.)
Add a node representing the start to OPEN
WHILE (OPEN is not empty)
Get a node from open
IF node = goal, backchain and terminate
ELSE add node to CLOSED
Add all children of node that are not in CLOSED to OPEN
Add a pointer referencing the parent node to each child node
ENDWHILE
No path exists to goal; terminate.
First, if the algorithm terminates, does this guarantee that a path exists?
