Toward Optimal Multi-Agent Robot and Lift Schedules via Boolean Satisfiability

As a multirobot system grows in its number of agents, contention over shared resources poses a more significant risk of deadlock and operational deficiencies. When integrating with buildings, one of the most common pieces of equipment that robots have to use is the lift (elevator). This work focuses on exploring different Anytime Constraint Programming techniques for finding time-optimal schedules across multiple robots and lifts. The choice of which lift each robot uses to complete its task has a noticeable impact on the makespan of the system. This work explores a Time-Ordered-based approach and a Time-Expansion Graph-based approach. The Time-Expansion Graph-based approach is found to outperform the Time-Ordered-based approach. This is because the Time-Expansion Graph method has immediate access to more comprehensive information. Additionally, this paper shows that, in some cases, applying such an optimization can considerably reduce the makespan.