Technical Reports

The ICICS/CS Reading Room


UBC CS TR-2008-11 Summary

Efficient Dynamic Programming for Optimal Multi-Location Robot Rendezvous with Proofs, August 06, 2008 Ken Alton and Ian M. Mitchell, 8 pages

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.


If you have any questions or comments regarding this page please send mail to help@cs.ubc.ca.