Graphbots: Mobility in discrete spaces

Samir Khuller, Ehud Rivlin, Azriel Rosenfeld

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 “robot” or team of robots having a particular graph structure can move from any start location to any goal destination in a graph-structured space.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 22nd International Colloquium, ICALP 1995, Proceedings
EditorsZoltan Fulop, Ferenc Gecseg
PublisherSpringer Verlag
Number of pages12
ISBN (Print)3540600841, 9783540600848
StatePublished - 1995
Event22nd International Colloquium on Automata, Languages and Programming, ICALP 1995 - Szeged, Hungary
Duration: Jul 10 1995Jul 14 1995

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference22nd International Colloquium on Automata, Languages and Programming, ICALP 1995

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Graphbots: Mobility in discrete spaces'. Together they form a unique fingerprint.

Cite this