## Abstract

We consider the following motion-planning problem: we are given m unit discs in a simple polygon with n vertices, each at their own start position, and we want to move the discs to a given set of m target positions. Contrary to the standard (labeled) version of the problem, each disc is allowed to be moved to any target position, as long as in the end every target position is occupied. We show that this unlabeled version of the problem can be solved in O (n log n + mn + m^{2}) time, assuming that the start and target positions are at least some minimal distance from each other. This is in sharp contrast to the standard (labeled) and more general multirobot motion planning problem for discs moving in a simple polygon, which is known to be strongly np-hard.

Original language | English |
---|---|

Title of host publication | Algorithmic Foundations of Robotics XI |

Subtitle of host publication | ed Contributions of the Eleventh International Workshop on the Algorithmic Foundations of Robotics |

Editors | H. Levent Atkin, N.M. Amato, V. Isler, A.F. van der Stappen |

Place of Publication | Dordrecht |

Publisher | Springer |

Pages | 1-17 |

Number of pages | 17 |

ISBN (Electronic) | 978-3-319-16595-0 |

ISBN (Print) | 978-3-319-16594-3 |

DOIs | |

Publication status | Published - 2015 |

Event | 11th International Workshop on the Algorithmic Foundations of Robotics (WAFR 2014), August 3-5, 2014, Istanbul, Turkey - Boğaziçi University, Istanbul, Turkey Duration: 3 Aug 2014 → 5 Aug 2014 http://robot.cmpe.boun.edu.tr/wafr2014/ |

### Publication series

Name | Springer Tracts in Advanced Robotics |
---|---|

Volume | 107 |

ISSN (Print) | 1610-7438 |

ISSN (Electronic) | 1610-742X |

### Conference

Conference | 11th International Workshop on the Algorithmic Foundations of Robotics (WAFR 2014), August 3-5, 2014, Istanbul, Turkey |
---|---|

Abbreviated title | WAFR 2014 |

Country | Turkey |

City | Istanbul |

Period | 3/08/14 → 5/08/14 |

Internet address |