On motion planning in graphs
| dc.contributor.author | Deb, Biswajit | |
| dc.date.accessioned | 2015-09-17T06:14:11Z | |
| dc.date.accessioned | 2023-10-20T12:30:31Z | |
| dc.date.available | 2015-09-17T06:14:11Z | |
| dc.date.available | 2023-10-20T12:30:31Z | |
| dc.date.issued | 2012 | |
| 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.identifier.other | ROLL NO.09612318 | |
| dc.identifier.uri | https://gyan.iitg.ac.in/handle/123456789/361 | |
| 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 |