Collision-Free Robot Scheduling

Adamson, Duncan ORCID: 0000-0003-3343-2435, Flaherty, Nathan, Potapov, Igor and Spirakis, Paul G ORCID: 0000-0001-5396-3749 (2025) Collision-Free Robot Scheduling In: 20th International Symposium on Algorithmics of Wireless Networks (ALGOWIN 2024), 2024-9-5 - 2024-9-6, Royal Holloway, University of London UK.

Text collision-free-robot-scheduling.pdf - Author Accepted Manuscript Available under License Creative Commons Attribution. Download (356kB) | Preview

Abstract

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 at any given timestep. 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 this problem is NP-complete for both star graphs (for k≥2 robots), and planar graphs (for any number of robots). Finally, we provide positive results for path, cycle, and tadpole graphs, showing that we can find an optimal set of schedules for k robots completing m tasks of equal duration of a path of length n in O(kmn), O(kmn²) time, and O(k³m⁴n) time respectively.

Item Type:	Conference Item (Unspecified)
Additional Information:	Source info: YINCO-D-24-00305
Uncontrolled Keywords:	46 Information and Computing Sciences, 4608 Human-Centred Computing, 4602 Artificial Intelligence
Divisions:	Faculty of Science & Engineering Faculty of Science & Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	04 Oct 2024 07:25
Last Modified:	23 May 2026 09:22
DOI:	10.1007/978-3-031-74580-5_1
Related Websites:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3184865
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.