Graphbots: Cooperative motion planning in discrete spaces

Samir Khuller; Ehud Rivlin; Azriel Rosenfeld

doi:10.1109/5326.661088

Graphbots: Cooperative motion planning in discrete spaces

Samir Khuller^*, Ehud Rivlin, Azriel Rosenfeld

^*Corresponding author for this work

Computer Science

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

Most previous theoretical work on motion planning for a group of robots has addressed the problem of path planning for the individual robots sequentially, in geometrically simple regions of Euclidean space (e.g., a planar region containing polygonal obstacles). In this paper, we define a version of the motionplanning problem in which the robots move simultaneously. We establish conditions under which a team of robots having a particular configuration can move from any start location to any goal destination in a graph-structured space. We show that for a group of robots that maintain a fixed formation we can find the shortest path in polynomial time, and we give faster algorithms for special kinds of environments.

Original language	English (US)
Pages (from-to)	29-38
Number of pages	10
Journal	IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews
Volume	28
Issue number	1
DOIs	https://doi.org/10.1109/5326.661088
State	Published - 1998

Funding

Manuscript received August 12, 1995; revised August 27, 1996 and February 2, 1997. This work was supported by NSF Research Initiation Award CCR-9307462, NSF Career Award CCR-9501355S, and by ARPA and AFOSR under Grant F49260-95-1-0462.

Keywords

Graphs
Motion planning

ASJC Scopus subject areas

Control and Systems Engineering
Software
Information Systems
Human-Computer Interaction
Computer Science Applications
Electrical and Electronic Engineering

Access to Document

10.1109/5326.661088

Cite this

@article{60432c7ba11f402eb9d69efc8f94cfc2,

title = "Graphbots: Cooperative motion planning in discrete spaces",

abstract = "Most previous theoretical work on motion planning for a group of robots has addressed the problem of path planning for the individual robots sequentially, in geometrically simple regions of Euclidean space (e.g., a planar region containing polygonal obstacles). In this paper, we define a version of the motionplanning problem in which the robots move simultaneously. We establish conditions under which a team of robots having a particular configuration can move from any start location to any goal destination in a graph-structured space. We show that for a group of robots that maintain a fixed formation we can find the shortest path in polynomial time, and we give faster algorithms for special kinds of environments.",

keywords = "Graphs, Motion planning",

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

note = "Funding Information: Manuscript received August 12, 1995; revised August 27, 1996 and February 2, 1997. This work was supported by NSF Research Initiation Award CCR-9307462, NSF Career Award CCR-9501355S, and by ARPA and AFOSR under Grant F49260-95-1-0462.",

year = "1998",

doi = "10.1109/5326.661088",

language = "English (US)",

volume = "28",

pages = "29--38",

journal = "IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews",

issn = "1094-6977",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "1",

}

TY - JOUR

T1 - Graphbots

T2 - Cooperative motion planning in discrete spaces

AU - Khuller, Samir

AU - Rivlin, Ehud

AU - Rosenfeld, Azriel

N1 - Funding Information: Manuscript received August 12, 1995; revised August 27, 1996 and February 2, 1997. This work was supported by NSF Research Initiation Award CCR-9307462, NSF Career Award CCR-9501355S, and by ARPA and AFOSR under Grant F49260-95-1-0462.

PY - 1998

Y1 - 1998

N2 - Most previous theoretical work on motion planning for a group of robots has addressed the problem of path planning for the individual robots sequentially, in geometrically simple regions of Euclidean space (e.g., a planar region containing polygonal obstacles). In this paper, we define a version of the motionplanning problem in which the robots move simultaneously. We establish conditions under which a team of robots having a particular configuration can move from any start location to any goal destination in a graph-structured space. We show that for a group of robots that maintain a fixed formation we can find the shortest path in polynomial time, and we give faster algorithms for special kinds of environments.

AB - Most previous theoretical work on motion planning for a group of robots has addressed the problem of path planning for the individual robots sequentially, in geometrically simple regions of Euclidean space (e.g., a planar region containing polygonal obstacles). In this paper, we define a version of the motionplanning problem in which the robots move simultaneously. We establish conditions under which a team of robots having a particular configuration can move from any start location to any goal destination in a graph-structured space. We show that for a group of robots that maintain a fixed formation we can find the shortest path in polynomial time, and we give faster algorithms for special kinds of environments.

KW - Graphs

KW - Motion planning

UR - https://www.scopus.com/pages/publications/0032003472

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

U2 - 10.1109/5326.661088

DO - 10.1109/5326.661088

M3 - Article

AN - SCOPUS:0032003472

SN - 1094-6977

VL - 28

SP - 29

EP - 38

JO - IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews

JF - IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews

IS - 1

ER -

Graphbots: Cooperative motion planning in discrete spaces

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this