10.2.3. Graphs and Trees
10.2.3. Graphs and Trees
This video introduces graph representations of free C-space, including undirected and directed graphs, weighted and unweighted graphs, and trees.
Although the C-space of a robot is a continuous space, in motion planning we typically discretize it in some way. For example, this image shows a mobile robot in a maze. We could represent the free space of this maze by sampling some free configurations and drawing lines between configurations that can reach each other by a straight-line path. This graph is now our discretized representation of the free space.
A graph consists of a set of nodes and a set of edges between them. Consider, for example, this graph consisting of 5 nodes, lettered a through e. Drawn this way, each edge can be followed in either direction, so we call this an unweighted undirected graph. It is undirected because each edge can be followed in either direction. It is unweighted because the cost of traversing any edge is the same. For a weighted graph, however, different edges have different costs. For example, the cost associated with an edge may be the length of the path corresponding to the edge, or the amount of energy or time it takes to traverse it. In this example, it is much cheaper to go from node b to node a than it is to go from node b to node c.
Edges can also be directed, as you see in this weighted directed graph. Here, it is possible to go back and forth between nodes a and b, but it's less costly to go to a than it is to go to b. Also, we can see that it is possible to go from node c to node e, but it is not possible to go from node e to node c. A directed graph is often called a "digraph" for short.
Finally, we define a tree to be a specific type of directed graph, as shown here. A tree has one root node and all other nodes have 1 parent, meaning they can be reached by a single edge from only one other node. A tree has no cycles. Any node with no children is called a leaf of the tree. A tree can be weighted or unweighted.
In the coming videos, we will see examples of graphs and trees in motion planning. In preparation for that, in the next video I will describe the A-star search algorithm for finding optimal paths on a graph.
