On motion planning in graphs

Abstract

Consider an undirected graph G in which a robot is placed at a vertex, say u, and obstacles are placed at all other vertices except at vertex v. The vertex without a robot or an obstacle is said to have a hole. We refer to this placement of robot and obstacles as a configuration Cu v of G. We say that Cu v is reachable from Cv u by an mRJ move of the robot provided there is a u-v path [u = u0, u1, u2, D D D um, um+1 = v] of length m + 1 in G. For m = 0, an mRJ move is also known as a simple move of the robot. In this thesis, we obtain necessary conditions for trees in which any two configurations are reachable from each other by using a sequence of mRJ moves of the robot for some fixed positive integer m and simple moves of the robot as well as obstacles. We call such a tree as complete mRJ-reachable. We characterize complete mRJ-reachable trees for m = 0, 1, 2, 3. We introduce the concept of complete S-reachable graphs, where S is a finite set of non-negative integers. By a complete S-reachable graph we mean a graph in which any two configurations are reachable from each other by using a sequence of mRJ moves of the robot for m D S and simple moves of the obstacles. We give necessary conditions for a graph to be complete S-reachable. We also characterize the cycles that are complete {m}-reachable. In addition we identify the graphs that are complete {1, 2}-reachable. Lastly, we give expression for minimum number of simple moves to take the robot from an initial position to any other vertex in various classes of product graphs..