SEVAC: Sample Efficient Variational Actor Critic for Reliable Navigation Learning in Uncertain Topological Networks

This article investigates the reliable navigation problem, which requires that the ego vehicle navigates itself to the destination with the maximized stochastic on-time arrival (SOTA) probability in a givenuncertaintopological transportation network. One distinctive characteristic of the SOTA problem explored in this paper is the inherent uncertainty stemming from the underlying network's topology, i.e., some of the edges might become untraversable during navigation. To the best of our knowledge, almost all conventional SOTA solutions presume that the network topology remains the same during the ego vehicle's navigation process. However, when facing uncertainties in the network's topology, these algorithms may experience a significant performance degradation. To address the challenge of uncertain network topology, we first formulate the special reliable navigation problem into thevariationalMarkov decision process (MDP) framework, and then initiate a new reinforcement learning (RL)-based algorithm, namely sample efficient variational actor critic (SEVAC) as its solution. SEVAC comprises the variational policy gradient (VPG) module, which optimizes the vehicle's routing policy, and the masked temporal difference (MTD) module, which approximates the underlying routing policy's SOTA probability. Both modules are extended to their off-policy counterparts, namely off-policy VPG and off-policy MTD, to improve the algorithm's sample efficiency. SEVAC is compared with several conventional SOTA solutions as well as Canadian traveller problem (CTP) algorithms in a variety of commonly used transportation test networks, and achieves the best overall SOTA performance. Furthermore, we validate SEVAC's application to real-world scenarios by navigating a physical robot in a self-constructed indoor environment as well as a real-world building environment with uncertain topology.