# On motion planning in graphs

 dc.contributor.author Deb, Biswajit dc.date.accessioned 2015-09-17T06:14:11Z dc.date.available 2015-09-17T06:14:11Z dc.date.issued 2012 dc.identifier.other ROLL NO.09612318 dc.identifier.uri http://gyan.iitg.ernet.in/handle/123456789/361 dc.description Supervisor: Kalpesh Kapoor en_US dc.description.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.. en_US dc.language.iso en en_US dc.relation.ispartofseries TH-1155; dc.subject MATHEMATICS en_US dc.title On motion planning in graphs en_US dc.type Thesis en_US
﻿