Time-Ordered Ad-hoc Resource Sharing for Independent Robotic Agents

Resource sharing is a crucial part of a multi-robot system. We propose a Boolean satisfiability problem (SAT) based approach to resource sharing. Our key contributions are an algorithm for converting any constrained assignment to a weighted-SAT based optimization. We propose a theorem that allows optimal resource assignment problems to be solved via repeated application of a SAT solver. Additionally we show a way to encode continuous time ordering constraints using Conjunctive Normal Form (CNF). We benchmark our new algorithms and show that they can be used in an ad-hoc setting. We test our algorithms on a fleet of simulated and real world robots and show that the algorithms are able to handle real world situations. Our algorithms and test harnesses are open source and build on Open-RMF’s fleet management system.