PROJECT TITLE :

Performance Guarantee of an Approximate Dynamic Programming Policy for Robotic Surveillance

ABSTRACT:

This paper is concentrated on the development and analysis of suboptimal decision algorithms for a collection of robots that assist a remotely located operator in perimeter surveillance. The operator is tasked with the classification of incursions across the perimeter. whenever there's an incursion into the perimeter, an unattended ground sensor (UGS) within the vicinity, signals an alert. A robot services the alert by visiting the alert location, collecting data, e.g., photo and video imagery, and transmitting it to the operator. The accuracy of operator's classification depends on the degree and freshness of knowledge gathered and provided by the robots at locations where incursions occur. There are two competing objectives for a robot: it wants to pay adequate time at an alert location to collect evidence for aiding the operator in correct classification however it also desires to service alternative alerts whilst potential, so that the proof collected is relevant. The decision downside is to see the optimal amount of time a robot should spend servicing an alert. The incursions are stochastic and their statistics are assumed to be known. This drawback can be posed as a Markov Decision Drawback. But, even for two robots and 5 UGS locations, the quantity of states is of the order of billions rendering actual dynamic programming methods intractable. Approximate dynamic programming (ADP) via linear programming (LP) provides a way to approximate the worth function and derive suboptimal methods. The novel feature of this paper is that the derivation of a tractable lower bound via LP and the development of a suboptimal policy whose performance improves upon the lower certain. An illustrative perimeter surveillance example corroborates the results derived during this paper.