Efficient Optimal Multi-Location Robot Rendezvous

Ken Alton and Ian M. Mitchell
Publishing date
October 05, 2007
21 pages
We present an efficient algorithm to solve the problem of optimal multi-location robot rendezvous. The rendezvous problem considered can be structured as a tree, with each node representing a meeting of robots, and the algorithm computes optimal meeting locations and connecting robot trajectories. The tree structure is exploited by using dynamic programming to compute solutions in two passes through the tree: an upwards pass computing the cost of all potential solutions, and a downwards pass computing optimal trajectories and meeting locations. The correctness and efficiency of the algorithm are analyzed theoretically, while a discrete robotic clinic problem and a continuous robot arm problem demonstrate the algorithm's practicality.