We motivate, visualize and demonstrate recent work for minimizing the total execution time of a coordinated, parallel motion plan for a swarm of N robots in the absence of obstacles. Under relatively mild assumptions on the separability of robots, the algorithm achieves constant stretch: If all robots want to move at most d units from their respective starting positions, then the total duration of the overall schedule (and hence the distance traveled by each robot) is O(d) steps; this implies constant-factor approximation for the optimization problem. Also mentioned is an NP-hardness result for finding an optimal schedule, even in the case in which robot positions are restricted to a regular grid. On the other hand, we show that for densely packed disks that cannot be well separated, a stretch factor Omega(N^{1/4}) is required in the worst case; we establish an achievable stretch factor of O(N^{1/2}) even in this case. We also sketch geometric difficulties of computing optimal trajectories, even for just two unit disks.
Coordinated Motion Planning: The Video (Multimedia Exposition)
2018-01-01
Aufsatz (Konferenz)
Elektronische Ressource
Englisch
Coordinated Particle Relocation with Global Signals and Local Friction (Media Exposition)
BASE | 2020
|HVS based Motion Estimation on the TMS320C80 Multimedia Video Processor
British Library Conference Proceedings | 1999
|Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch
BASE | 2018
|