Please note: This PhD seminar will take place in DC 1304 and online.
Remy El Sabeh, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Naomi Nishimura
Coordinating the motion of multiple agents in constrained environments is a fundamental challenge in robotics, motion planning, and scheduling. A motivating example involves n robotic arms, each represented as a line segment. The objective is to rotate each arm to its vertical orientation, one at a time (clockwise or counterclockwise), without collisions nor rotating any arm more than once. This scenario is an example of the more general k-Compatible Ordering problem, where n agents, each capable of k state-changing actions, must transition to specific target states under constraints encoded as a set \mathcal{G} of k pairs of directed graphs.
We show that k-Compatible Ordering is 𝖭𝖯-complete, even when \mathcal{G} is planar, degenerate, or acyclic. On the positive side, we provide polynomial-time algorithms for cases such as when k=1 or \mathcal{G} has bounded treewidth. We also introduce generalized variants supporting multiple state-changing actions per agent, broadening the applicability of our framework. These results extend to a wide range of scheduling, reconfiguration, and motion planning applications in constrained environments.
To attend this PhD seminar in person, please go to DC 1304. You can also attend virtually on Zoom.