Skip to content Skip to navigation

Persistent Monitoring of Events with Stochastic Arrivals at Multiple Stations

Persistent Monitoring of Events with Stochastic Arrivals at Multiple Stations

Author Name: 

Jingjin Yu, Sertac Karaman, and Daniela Rus

Publication Type: 
Journal Publications
Publication Date: 
May, 2015
Abstract: 
This paper introduces a new mobile sensor scheduling problem involving a single robot tasked to monitor several events of interest occurring at different locations (stations). Of particular interest is the monitoring of transient events of stochastic nature, with applications ranging from natural phenomena (e.g., monitoring abnormal seismic activity around a volcano using a ground robot) to urban activities (e.g., monitoring early formations of traffic congestion using an aerial robot). Motivated by examples like these, this paper focuses on problems in which the precise occurrence times of the events are unknown a priori, but statistics for their inter-arrival times are available. In monitoring such events, the robot seeks to: (i) maximize the number of events observed and (ii) minimize the delay between two consecutive observations of events occurring at the same location. The paper considers the case when a robot is tasked with optimizing the event observations in a balanced manner, following a cyclic patrolling route. To tackle this problem, first, assuming the cyclic ordering of stations is known, we prove the existence and uniqueness of the optimal solution, and show that the solution has desirable convergence rate and robustness. Our constructive proof also yields an efficient algorithm for computing the unique optimal solution with O(n) time complexity, in which n is the number of stations, with O(log n) time complexity for incrementally adding or removing stations. Except for the algorithm, our analysis remains valid when the cyclic order is unknown. We then provide a polynomial-time approximation scheme that computes for any ϵ > 0 a (1 + ϵ)-optimal solution for this more general, NP-hard problem.