The Robust Canadian Traveler Problem Applied to Robot Routing

Abstract

The stochastic Canadian Traveler Problem (CTP), which finds application in robot route selection under uncertainty, aims to find the traversal policy with the minimum expected cost. This paper extends the CTP to what we call the Robust Canadian Traveler Problem (RCTP), in which the variability of the policy cost is also part of the evaluation criteria. An optimal (offline) algorithm and an approximate (online) algorithm are then proposed to compute the policy that has a good balance of both mean and variation of the traversal cost. The benefit of the proposed framework versus traditional approaches is shown by doing simulations in randomly generated worlds as well as on a map of 5 km of paths built from robot field trials. Specifically, the RCTP framework is able to search for sub-optimal policy alternatives with significantly lower worst-case cost and less computational time compared to the optimal policy, but with little sacrifice on the expected cost.