Finding Near-optimal Solutions in Multi-robot Path Planning
We deal with the problem of planning collision-free trajectories for robots operating in a shared space. Given the start and destination position for each of the robots, the task is to find trajectories for all robots that reach their destinations with minimum total cost such that the robots will no...
Main Authors: | , , |
---|---|
Format: | Text |
Language: | unknown |
Published: |
2014
|
Subjects: | |
Online Access: | http://arxiv.org/abs/1410.5200 |
id |
ftarxivpreprints:oai:arXiv.org:1410.5200 |
---|---|
record_format |
openpolar |
spelling |
ftarxivpreprints:oai:arXiv.org:1410.5200 2023-09-05T13:22:22+02:00 Finding Near-optimal Solutions in Multi-robot Path Planning Čáp, Michal Novák, Peter Kleiner, Alexander 2014-10-20 http://arxiv.org/abs/1410.5200 unknown http://arxiv.org/abs/1410.5200 Computer Science - Robotics text 2014 ftarxivpreprints 2023-08-16T13:28:05Z We deal with the problem of planning collision-free trajectories for robots operating in a shared space. Given the start and destination position for each of the robots, the task is to find trajectories for all robots that reach their destinations with minimum total cost such that the robots will not collide when following the found trajectories. Our approach starts from individually optimal trajectory for each robot, which are then penalized for being in collision with other robots. The penalty is gradually increased and the individual trajectories are iteratively replanned to account for the increased penalty until a collision-free solution is found. Using extensive experimental evaluation, we find that such a penalty method constructs trajectories with near-optimal cost on the instances where the optimum is known and otherwise with 4-10 % lower cost than the trajectories generated by prioritized planning and up to 40 % cheaper than trajectories generated by local collision avoidance techniques, such as ORCA. Text Orca ArXiv.org (Cornell University Library) |
institution |
Open Polar |
collection |
ArXiv.org (Cornell University Library) |
op_collection_id |
ftarxivpreprints |
language |
unknown |
topic |
Computer Science - Robotics |
spellingShingle |
Computer Science - Robotics Čáp, Michal Novák, Peter Kleiner, Alexander Finding Near-optimal Solutions in Multi-robot Path Planning |
topic_facet |
Computer Science - Robotics |
description |
We deal with the problem of planning collision-free trajectories for robots operating in a shared space. Given the start and destination position for each of the robots, the task is to find trajectories for all robots that reach their destinations with minimum total cost such that the robots will not collide when following the found trajectories. Our approach starts from individually optimal trajectory for each robot, which are then penalized for being in collision with other robots. The penalty is gradually increased and the individual trajectories are iteratively replanned to account for the increased penalty until a collision-free solution is found. Using extensive experimental evaluation, we find that such a penalty method constructs trajectories with near-optimal cost on the instances where the optimum is known and otherwise with 4-10 % lower cost than the trajectories generated by prioritized planning and up to 40 % cheaper than trajectories generated by local collision avoidance techniques, such as ORCA. |
format |
Text |
author |
Čáp, Michal Novák, Peter Kleiner, Alexander |
author_facet |
Čáp, Michal Novák, Peter Kleiner, Alexander |
author_sort |
Čáp, Michal |
title |
Finding Near-optimal Solutions in Multi-robot Path Planning |
title_short |
Finding Near-optimal Solutions in Multi-robot Path Planning |
title_full |
Finding Near-optimal Solutions in Multi-robot Path Planning |
title_fullStr |
Finding Near-optimal Solutions in Multi-robot Path Planning |
title_full_unstemmed |
Finding Near-optimal Solutions in Multi-robot Path Planning |
title_sort |
finding near-optimal solutions in multi-robot path planning |
publishDate |
2014 |
url |
http://arxiv.org/abs/1410.5200 |
genre |
Orca |
genre_facet |
Orca |
op_relation |
http://arxiv.org/abs/1410.5200 |
_version_ |
1776202883686989824 |