Fast, near-optimal computation for multi-robot path planning on graphs

Jingjin Yu, Steven M. La Valle

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

Abstract

We report a new method for computing near optimal makespan solutions to multi-robot path planning problem on graphs. Our focus here is with hard instances - those with up to 85% of all graph nodes occupied by robots. Our method yields 100-1000x speedup compared with existing methods. At the same time, our solutions have much smaller and often optimal makespans.

Original languageEnglish (US)
Title of host publicationLate-Breaking Developments in the Field of Artificial Intelligence - Papers Presented at the 27th AAAI Conference on Artificial Intelligence, Technical Report
PublisherAI Access Foundation
Pages155-157
Number of pages3
ISBN (Print)9781577356288
StatePublished - 2013
Event27th AAAI Conference on Artificial Intelligence, AAAI 2013 - Bellevue, WA, United States
Duration: Jul 14 2013Jul 18 2013

Publication series

NameAAAI Workshop - Technical Report
VolumeWS-13-17

Other

Other27th AAAI Conference on Artificial Intelligence, AAAI 2013
Country/TerritoryUnited States
CityBellevue, WA
Period7/14/137/18/13

ASJC Scopus subject areas

  • General Engineering

Fingerprint

Dive into the research topics of 'Fast, near-optimal computation for multi-robot path planning on graphs'. Together they form a unique fingerprint.

Cite this