BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260409T124327Z
UID:Seminar-ACTO-1257@lxserverA.csc.liv.ac.uk.csc.liv.ac.uk
ORGANIZER:CN=Nikhil Mande:MAILTO:Nikhil.Mande@liverpool
DTSTART:20241127T140000
DTEND:20241127T150000
SUMMARY:Algorithms, Complexity Theory and Optimisation Series
DESCRIPTION:Nathan Flaherty: Collision-Free Robot Scheduling\n\nMobile 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.\n\n \n\nThis is work done jointly with Duncan Adamson, Igor Potapov and Paul Spirakis\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1257
LOCATION:Ashton 208
END:VEVENT
END:VCALENDAR