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