Title :
Surveillance in an abruptly changing world via multiarmed bandits
Author :
Srivastava, Vaibhav ; Reverdy, Paul ; Leonard, Naomi E.
Author_Institution :
Dept. of Mech. & Aerosp. Eng., Princeton Univ., Princeton, NJ, USA
Abstract :
We study a path planning problem in an environment that is abruptly changing due to the arrival of unknown spatial events. The objective of the path planning problem is to collect the data that is most evidential about the events. We formulate this problem as a multiarmed bandit (MAB) problem with Gaussian rewards and change points, and address the fundamental tradeoff between learning the true event (exploration), and collecting the data that is most evidential about the true event (exploitation). We extend the switching-window UCB algorithm for MAB problems with bounded rewards and change points to the context of correlated Gaussian rewards and develop the switching-window UCL (SW-UCL) algorithm. We extend the SW-UCL algorithm to an adaptive SW-UCL algorithm that utilizes statistical change detection to adapt the SW-UCL algorithm. We also develop a block SW-UCL algorithm that reduces the number of transitions among arms in the SW-UCL algorithm, and is more amenable to robotic applications.
Keywords :
Gaussian processes; path planning; robots; Gaussian rewards; MAB problem; adaptive SW-UCL algorithm; block SW-UCL algorithm; correlated Gaussian rewards; data collection; exploitation learning; exploration learning; multiarmed bandits; path planning; statistical change detection; switching-window UCL algorithm; Algorithm design and analysis; Change detection algorithms; Context; Path planning; Resource management; Robots; Surveillance;
Conference_Titel :
Decision and Control (CDC), 2014 IEEE 53rd Annual Conference on
Conference_Location :
Los Angeles, CA
Print_ISBN :
978-1-4799-7746-8
DOI :
10.1109/CDC.2014.7039462