Sub-Optimal Stationary Policies for a Class of Stochastic Optimization Problems Arising in Robotic Surveillance Applications
Conference Paper
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
This paper deals with the development of sub-optimal decision making algorithms for a collection of robots in order to aid a remotely located human operator in the task of classification of incursions across a perimeter in a surveillance application. The operator is tasked with the classification of incursion as either a nuisance or a threat. Whenever there is an incursion into the perimeter, Unattended Ground Sensors (UGS) raise an alert and the robots service the alerts by visiting the alert location and collecting evidence in the form of video and other images and transmit them to the operator. There are two competing needs for a robot: it needs to spend more time at an alert location for aiding the operator in accurate classification and it needs to service the alerts as quickly as possible so that the evidence collected is relevant. A natural problem is to determine the optimal amount of time a robot must spend servicing an alert. In this paper, we discretize the problem spatially and temporally and recast the optimization problem as follows: Is it better for a robot to spend the next time interval at the alert location in terms of maximizing the expected, discounted payoff? The payoff associated with a state is an increasing function of the time spent by a robot servicing an alert and a decreasing function of the number of unserviced alerts. This problem can be easily be cast as a Markov Decision Process (MDP). However, the number of states runs into billions even for a modest size problem. We consider Approximate Dynamic Programming via linear programming as this approach provides an upper (and lower) bound on the optimal expected discounted payoff and enables the construction of a suboptimal policy. The bounds may then be used to provide an estimate of the quality of sub-optimal policy employed. We also provide a computationally tractable way of computing the lower bound using linear programming. Finally, numerical results supporting our method are provided. Copyright 2012 by ASME.
name of conference
Volume 3: Renewable Energy Systems; Robotics; Robust Control; Single Track Vehicle Dynamics and Control; Stochastic Models, Control and Algorithms in Robotics; Structure Dynamics and Smart Structures;
Volume 3: Renewable Energy Systems; Robotics; Robust Control; Single Track Vehicle Dynamics and Control; Stochastic Models, Control and Algorithms in Robotics; Structure Dynamics and Smart Structures;
author list (cited authors)
Park, M., Darbha, S., Krishnamoorthy, K., Khargonekar, P. P., Pachter, M., & Chandler, P.
citation count
4
complete list of authors
Park, M||Darbha, S||Krishnamoorthy, K||Khargonekar, PP||Pachter, M||Chandler, P
