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.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Coordinated Motion Planning: The Video (Multimedia Exposition)


    Beteiligte:

    Erscheinungsdatum :

    2018-01-01



    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Klassifikation :

    DDC:    004 / 629




    COORDINATED MOTION SYSTEM

    KOBEL KORRY D / YUTZY FREDRIC L | Europäisches Patentamt | 2023

    Freier Zugriff

    Coordinated Particle Relocation with Global Signals and Local Friction (Media Exposition)

    Baez, Victor M. / Becker, Aaron T. / Schmidt, Arne | BASE | 2020

    Freier Zugriff

    HVS based Motion Estimation on the TMS320C80 Multimedia Video Processor

    Soraghan, J. J. / Fergusson, R. J. / Institution of Electrical Engineers et al. | British Library Conference Proceedings | 1999



    Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch

    Demaine, Erik D. / Keldenich, Phillip / Scheffer, Christian et al. | BASE | 2018

    Freier Zugriff