TY - GEN

T1 - Brief Announcement

T2 - 3rd Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2024

AU - Adamson, Duncan

AU - Flaherty, Nathan

AU - Potapov, Igor

AU - Spirakis, Paul G.

N1 - Publisher Copyright:
© Duncan Adamson, Nathan Flaherty, Igor Potapov, and Paul G. Spirakis.

PY - 2024/6

Y1 - 2024/6

N2 - Robots are becoming an increasingly common part of scientific work within laboratory environments. In this paper, we investigate the problem of designing schedules for completing a set of tasks at fixed locations with multiple robots in a laboratory. We represent the laboratory as a graph with tasks placed on fixed vertices and robots represented as agents, with the constraint that no two robots may occupy the same vertex, or traverse the same edge, at the same time. Each schedule is partitioned into a set of timesteps, corresponding to a walk through the graph (allowing for a robot to wait at a vertex to complete a task), with each timestep taking time equal to the time for a robot to move from one vertex to another and each task taking some given number of timesteps during the completion of which a robot must stay at the vertex containing the task. The goal is to determine a set of schedules, with one schedule for each robot, minimising the number of timesteps taken by the schedule taking the greatest number of timesteps within the set of schedules. We show that the problem of finding a task-fulfilling schedule in at most L timesteps is NP-complete for many simple classes of graphs. Explicitly, we provide this result for complete graphs, bipartite graphs, star graphs, and planar graphs. Finally, we provide positive results for line graphs, showing that we can find an optimal set of schedules for k robots completing m tasks of equal length of a path of length n in O(kmn) time, and a k-approximation when the length of the tasks is unbounded.

AB - Robots are becoming an increasingly common part of scientific work within laboratory environments. In this paper, we investigate the problem of designing schedules for completing a set of tasks at fixed locations with multiple robots in a laboratory. We represent the laboratory as a graph with tasks placed on fixed vertices and robots represented as agents, with the constraint that no two robots may occupy the same vertex, or traverse the same edge, at the same time. Each schedule is partitioned into a set of timesteps, corresponding to a walk through the graph (allowing for a robot to wait at a vertex to complete a task), with each timestep taking time equal to the time for a robot to move from one vertex to another and each task taking some given number of timesteps during the completion of which a robot must stay at the vertex containing the task. The goal is to determine a set of schedules, with one schedule for each robot, minimising the number of timesteps taken by the schedule taking the greatest number of timesteps within the set of schedules. We show that the problem of finding a task-fulfilling schedule in at most L timesteps is NP-complete for many simple classes of graphs. Explicitly, we provide this result for complete graphs, bipartite graphs, star graphs, and planar graphs. Finally, we provide positive results for line graphs, showing that we can find an optimal set of schedules for k robots completing m tasks of equal length of a path of length n in O(kmn) time, and a k-approximation when the length of the tasks is unbounded.

KW - Approximation Algorithms

KW - Graph Exploration

KW - NP-Completeness

KW - Scheduling

UR - http://www.scopus.com/inward/record.url?scp=85195380203&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.SAND.2024.22

DO - 10.4230/LIPIcs.SAND.2024.22

M3 - Conference contribution

AN - SCOPUS:85195380203

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 3rd Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2024

A2 - Casteigts, Arnaud

A2 - Kuhn, Fabian

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

Y2 - 5 June 2024 through 7 June 2024

ER -