Staff View
Intractability of Optimal Multi-Robot Path Planning on Planar Graphs

Descriptive

TypeOfResource
Text
TitleInfo
Title
Intractability of Optimal Multi-Robot Path Planning on Planar Graphs
Name (authority = orcid); (authorityURI = http://id.loc.gov/vocabulary/identifiers/orcid.html); (type = personal); (valueURI = http://orcid.org/0000-0003-4112-2250)
NamePart (type = family)
Yu
NamePart (type = given)
Jingjin
Affiliation
Computer Science (New Brunswick), Rutgers University
Role
RoleTerm (authority = marcrt); (type = text)
author
Name (authority = RutgersOrg-Department); (type = corporate)
NamePart
Computer Science (New Brunswick)
Name (authority = RutgersOrg-School); (type = corporate)
NamePart
School of Arts and Sciences (SAS) (New Brunswick)
Genre (authority = RULIB-FS)
Article, Refereed
Genre (authority = NISO JAV)
Accepted Manuscript (AM)
Note (type = peerReview)
Peer reviewed
OriginInfo
Publisher
IEEE Robotics and Automation Society
DateIssued (encoding = w3cdtf); (keyDate = yes); (qualifier = exact)
2016
Abstract (type = Abstract)
We study the computational complexity of optimally solving multi-robot path planning problems on planar graphs. For four common time- and distance-based objectives, we show that the associated path optimization problems for multiple robots are all NP-complete, even when the underlying graph is planar. Establishing the computational intractability of optimal multi-robot path planning problems on planar graphs has important practical implications. In particular, our result suggests the preferred approach toward solving such problems, when the number of robots is large, is to augment the planar environment to reduce the sharing of paths among robots traveling in opposite directions on those paths. Indeed, such efficiency boosting structures, such as highways and elevated intersections, are ubiquitous in robotics and transportation applications.
Language
LanguageTerm (authority = ISO 639-3:2007); (type = text)
English
PhysicalDescription
InternetMediaType
application/pdf
Extent
13 p.
Subject (authority = local)
Topic
NP-hardness
Subject (authority = local)
Topic
Multi-robot path planning
Subject (authority = local)
Topic
Planar graphs
Subject (authority = local)
Topic
Transportation networks
Subject (authority = local)
Topic
Boolean satisfiability problems
Subject (authority = LCSH)
Topic
Transportation, Automotive
Subject (authority = LCSH)
Topic
Robots--Kinematics.
Extension
DescriptiveEvent
Type
Citation
DateTime (encoding = w3cdtf)
2016
AssociatedObject
Type
Journal
Relationship
Has part
Name
Robotics and Automation Letters
Identifier (type = volume and issue)
1(1)
Reference (type = url)
https://dx.doi.org/10.1109/LRA.2015.2503143
Detail
33-40
RelatedItem (type = host)
TitleInfo
Title
Yu, Jingjin
Identifier (type = local)
rucore30182100001
Location
PhysicalLocation (authority = marcorg); (displayLabel = Rutgers, The State University of New Jersey)
NjNbRU
Identifier (type = doi)
doi:10.7282/T3BC41HN
Back to the top

Rights

RightsDeclaration (AUTHORITY = FS); (ID = rulibRdec0004)
Copyright for scholarly resources published in RUcore is retained by the copyright holder. By virtue of its appearance in this open access medium, you are free to use this resource, with proper attribution, in educational and other non-commercial settings. Other uses, such as reproduction or republication, may require the permission of the copyright holder.
Copyright
Status
Copyright protected
Availability
Status
Open
Reason
Permission or license
RightsEvent
Type
Permission or license
AssociatedObject
Type
License
Name
Sole author license v. 1
Detail
I hereby grant to Rutgers, The State University of New Jersey (Rutgers) the non-exclusive right to retain, reproduce, and distribute the deposited work (Work) in whole or in part, in and from its electronic format, without fee. This agreement does not represent a transfer of copyright to Rutgers.Rutgers may make and keep more than one copy of the Work for purposes of security, backup, preservation, and access and may migrate the Work to any medium or format for the purpose of preservation and access in the future. Rutgers will not make any alteration, other than as allowed by this agreement, to the Work.I represent and warrant to Rutgers that the Work is my original work. I also represent that the Work does not, to the best of my knowledge, infringe or violate any rights of others.I further represent and warrant that I have obtained all necessary rights to permit Rutgers to reproduce and distribute the Work and that any third-party owned content is clearly identified and acknowledged within the Work.By granting this license, I acknowledge that I have read and agreed to the terms of this agreement and all related RUcore and Rutgers policies.
RightsEvent
Type
Publication notice
Detail
© 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
RightsHolder (type = corporate)
Name
IEEE
Role
Copyright holder
Back to the top

Technical

RULTechMD (ID = TECHNICAL1)
ContentModel
Document
Back to the top
Version 8.3.10
Rutgers University Libraries - Copyright ©2019