Efficient Dynamic Programming for Optimal Multi-Location Robot Rendezvous with Proofs

ID
TR-2008-11
Authors
Ken Alton and Ian M. Mitchell
Publishing date
August 06, 2008
Length
8 pages
Abstract
We present an efficient dynamic programming 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 continuous robot arm problem demonstrates the algorithm's practicality.