Introduction and definitions

A graph G = (V, E) consists of a set V of vertices, and a set E of edges, each of them connecting two of these vertices. Here, we want to explore an unknown graph, which means we place a robot at a start vertex s, visit all vertices and edges of G by moving the robot from one vertex over an edge to another vertex (at the opposite side of the edge), and return to s after having visited the entire graph. We also want to perform a constrained exploration; the constraint is that the robot is tethered to a rope with length l = (1 + α)r, where r is the radius of G, i.e. the distance of the farthest vertex from s, and α > 0 is some real number. That rope could be a power cable, fuel line, security line, etc., and one end is fixed at the start vertex.


Press Start-Button to launch applet:


Applet

In this applet the process of the constrained graph exploration is visualized.

Figure 1.

The most important stepts like "calling bDFS" (figure 1), "closest subtree" (figure 2), "merge trees" ( figure 3) etc. are highlighted by colorizing, and also displayed as text in the panel at the bottom.

     
         
 

Figure 2

   

Figure 3

      

                                                                        

After starting the exploration, the manipulation of the applet is limited. No further modification of the graph or of the input parameters are allowed (until the end of the exploration). This is necessary to assure that the algorithm runs correctly.

The algorithm terminates in two cases. The first case is, the graph has been completely explored (see figure 4). The second case is, all vertices that can be reached with the rope length have been explored (see figure 5).

     
         

                                                                 

Figure4

 

 

Figure 5

       

 

Algorithm

The first step is to run a depth first search (DFS) on the graph and stop, when the maximum rope length l has been reached. This algorithm is called bounded DFS (bDFS). Its weakness is that some vertices which are potentially reachable could remain unexplored, as shown in figure 6.


Figure 6

If the robot walks the path (s, 1, 2, ..., r-1, r), the remaining three pink vertices cannot be reached, since the maximum rope length of r has been reached. But if the robot had walked the shorter path (s, r+1, r-1, r) first, he could have visited the pink vertices as well.

Thus, the next step is to improve the algorithm and solve this problem. To do so, we invoke bDFS several times, each time starting from an appropriate vertex. During the exploration, the algorithm holds a list of vertex-disjoint subtrees T = {T1, ..., Tk} with roots s1, ..., sk, from which the subtree Ti is chosen that is the closest to start vertex s. This subtree is being pruned: Subtrees Twj (with root wj) are cut off, if two conditions are satisfied:

This pruning keeps trees at an appropriate size.

After the pruning step the robot performs a DFS on the tree, and each time it encounters an incomplete explored vertex (i.e. a vertex that has incident edges which are unexplored), it runs a bDFS on that vertex. Vertices and edges that are newly discovered during the bDFS are used to create a new tree and appended to the list T. After exploration of Ti, all completely explored trees are removed from T, and trees with common vertices are merged. The algorithm stops when all trees in T have been explored and removed.

With this algorithm and parameters, the exploration is competetive.

References

Literatur:

[1]: Duncan, Kobourov, Kumar. Optimal Constrained Graph Exploration. 2001.