Collision-Free Robot Scheduling

27^th November 2024, 14:00 Ashton 208
Nathan Flaherty
University of Liverpool

Abstract

Mobile robots are becoming an increasingly common part of scientific work within laboratory environments and therefore effectively coordinating them to complete necessary tasks around the laboratory whilst preventing collisions is of great practical interest. We model this with a graph G=(V,E) with m tasks and k robots, each task is on a vertex and has a certain duration (the time taken to complete the task). The problem being to find schedules for the robots which complete all the tasks in G without any two robots sharing the same vertex or traversing the same edge at any given time. This problem is NP-complete for several graph classes, notably planar graphs, trees and cliques. We have designed a O(kmn) k-approximation algorithm for paths which is optimal for tasks of equal duration.

This is work done jointly with Duncan Adamson, Igor Potapov and Paul Spirakis

Additional Materials

• https://arxiv.org/abs/2402.12019