An Approximation Algorithm for an Assisted Shortest Path Problem

摘要

In this article, we introduce a cooperative path planning algorithm for a cardinal and a support robot where the cardinal robot is unable to traverse a subset of edges in a network until the support robot has first traversed them. This subset of edges represent paths in an environment that are initially unavailable to the cardinal robot and require the assistance of the support robot. A (2 + α)-approximation algorithm (where α is the supremum of the ratio of the travel time of the support robot versus the travel time of the cardinal robot) is presented for this problem and is applied to various types of networks in order to examine the quality of the solutions it produces. We then conclude by discussing some potential future work concerning variations of this problem.