Compute Optimal Waiting Times for Collaborative Route Planning

Collaborative routing tries to discover paths of multiple robots that avoid mutual collisions while optimising a common cost function. A collision can be avoided in two ways: a robot modifies its route to pass another robot, or one robot waits for the other to move first. Recent work assigns priorities to robots or models waiting times as an ‘action’ similar to driving. However, these methods have certain disadvantages. This paper introduces a new approach that computes theoretically optimal waiting times for given multi-routes. If all collisions can be avoided through waiting, the algorithm computes optimal places and durations to wait. We used this approach as component to introduce a collaborative routing system capable of solving complex routing problems involving mutual blocking.