%0 Journal Article %J Automata, Languages and Programming %D 1995 %T Graphbots: Mobility in discrete spaces %A Khuller, Samir %A Rivlin,E. %A Rosenfeld, A. %X Most previous theoretical work on motion planning has addressed the problem of path planning for geometrically simple robots in geometrically simple regions of Euclidean space (e.g., a planar region containing polygonal obstacles). In this paper we define a natural version of the motion planning problem in a graph theoretic setting. We establish conditions under which a ldquorobotrdquo or team of robots having a particular graph structure can move from any start location to any goal destination in a graph-structured space. %B Automata, Languages and Programming %P 593 - 604 %8 1995/// %G eng %R 10.1007/3-540-60084-1_108