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, without collisions. 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 \(\textsf{NP}\) -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. These results extend to a wide range of scheduling, reconfiguration, and motion planning applications.