Samenvatting
We consider the following motion-planning problem:
we are given unit discs in a simple polygon with vertices, each
at their own start position, and we want to move the discs to a given
set of 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
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 multi-robot
motion planning problem for discs moving in a simple polygon,
which is known to be strongly NP-hard.
we are given unit discs in a simple polygon with vertices, each
at their own start position, and we want to move the discs to a given
set of 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
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 multi-robot
motion planning problem for discs moving in a simple polygon,
which is known to be strongly NP-hard.
| Originele taal-2 | Engels |
|---|---|
| Pagina's (van-tot) | 1309-1317 |
| Tijdschrift | IEEE Transactions on Automation Science and Engineering |
| Volume | 12 |
| Nummer van het tijdschrift | 4 |
| DOI's | |
| Status | Gepubliceerd - okt. 2015 |