Graphbots: Mobility in discrete spaces

Samir Khuller; Ehud Rivlin; Azriel Rosenfeld

doi:10.1007/3-540-60084-1_108

Graphbots: Mobility in discrete spaces

Samir Khuller, Ehud Rivlin, Azriel Rosenfeld

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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 language	English (US)
Title of host publication	Automata, Languages and Programming - 22nd International Colloquium, ICALP 1995, Proceedings
Editors	Zoltan Fulop, Ferenc Gecseg
Publisher	Springer Verlag
Pages	593-604
Number of pages	12
ISBN (Print)	3540600841, 9783540600848
DOIs	https://doi.org/10.1007/3-540-60084-1_108
State	Published - Jan 1 1995
Event	22nd International Colloquium on Automata, Languages and Programming, ICALP 1995 - Szeged, Hungary Duration: Jul 10 1995 → Jul 14 1995

Publication series

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

Conference

Conference	22nd International Colloquium on Automata, Languages and Programming, ICALP 1995
Country	Hungary
City	Szeged
Period	7/10/95 → 7/14/95

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/3-540-60084-1_108

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

Cite this

Khuller, S., Rivlin, E., & Rosenfeld, A. (1995). Graphbots: Mobility in discrete spaces. In Z. Fulop, & F. Gecseg (Eds.), Automata, Languages and Programming - 22nd International Colloquium, ICALP 1995, Proceedings (pp. 593-604). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 944). Springer Verlag. https://doi.org/10.1007/3-540-60084-1_108

Khuller, Samir ; Rivlin, Ehud ; Rosenfeld, Azriel. / Graphbots : Mobility in discrete spaces. Automata, Languages and Programming - 22nd International Colloquium, ICALP 1995, Proceedings. editor / Zoltan Fulop ; Ferenc Gecseg. Springer Verlag, 1995. pp. 593-604 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{2e3cc9c82e674552bc42689a38d6f429,

title = "Graphbots: Mobility in discrete spaces",

abstract = "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.",

author = "Samir Khuller and Ehud Rivlin and Azriel Rosenfeld",

year = "1995",

month = jan,

day = "1",

doi = "10.1007/3-540-60084-1_108",

language = "English (US)",

isbn = "3540600841",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "593--604",

editor = "Zoltan Fulop and Ferenc Gecseg",

booktitle = "Automata, Languages and Programming - 22nd International Colloquium, ICALP 1995, Proceedings",

address = "Germany",

note = "22nd International Colloquium on Automata, Languages and Programming, ICALP 1995 ; Conference date: 10-07-1995 Through 14-07-1995",

}

Khuller, S, Rivlin, E & Rosenfeld, A 1995, Graphbots: Mobility in discrete spaces. in Z Fulop & F Gecseg (eds), Automata, Languages and Programming - 22nd International Colloquium, ICALP 1995, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 944, Springer Verlag, pp. 593-604, 22nd International Colloquium on Automata, Languages and Programming, ICALP 1995, Szeged, Hungary, 7/10/95. https://doi.org/10.1007/3-540-60084-1_108

Graphbots : Mobility in discrete spaces. / Khuller, Samir; Rivlin, Ehud; Rosenfeld, Azriel.

Automata, Languages and Programming - 22nd International Colloquium, ICALP 1995, Proceedings. ed. / Zoltan Fulop; Ferenc Gecseg. Springer Verlag, 1995. p. 593-604 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 944).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Graphbots

T2 - 22nd International Colloquium on Automata, Languages and Programming, ICALP 1995

AU - Khuller, Samir

AU - Rivlin, Ehud

AU - Rosenfeld, Azriel

PY - 1995/1/1

Y1 - 1995/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84958050465&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84958050465&partnerID=8YFLogxK

U2 - 10.1007/3-540-60084-1_108

DO - 10.1007/3-540-60084-1_108

M3 - Conference contribution

AN - SCOPUS:84958050465

SN - 3540600841

SN - 9783540600848

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 593

EP - 604

BT - Automata, Languages and Programming - 22nd International Colloquium, ICALP 1995, Proceedings

A2 - Fulop, Zoltan

A2 - Gecseg, Ferenc

PB - Springer Verlag

Y2 - 10 July 1995 through 14 July 1995

ER -

Khuller S, Rivlin E, Rosenfeld A. Graphbots: Mobility in discrete spaces. In Fulop Z, Gecseg F, editors, Automata, Languages and Programming - 22nd International Colloquium, ICALP 1995, Proceedings. Springer Verlag. 1995. p. 593-604. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/3-540-60084-1_108