Persistent Monitoring of Events With Stochastic Arrivals at Multiple Stations

Jingjin Yu, Sertac Karaman, Daniela Rus

Research output: Contribution to journalArticlepeer-review

28 Scopus citations

Abstract

This paper introduces a new mobile sensor scheduling problem involving a single robot tasked to monitor several events of interest that are occurring at different locations (stations). Of particular interest is the monitoring of transient events of a 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 interarrival times are available. In monitoring such events, the robot seeks to: 1) maximize the number of events observed and 2) minimize the delay between two consecutive observations of events occurring at the same location. This 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 that 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.

Original languageEnglish (US)
Article number7069200
Pages (from-to)521-535
Number of pages15
JournalIEEE Transactions on Robotics
Volume31
Issue number3
DOIs
StatePublished - Jun 2015

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering

Keywords

  • Optimization
  • Poisson process
  • persistent monitoring
  • stochastic events
  • surveillance

Fingerprint Dive into the research topics of 'Persistent Monitoring of Events With Stochastic Arrivals at Multiple Stations'. Together they form a unique fingerprint.

Cite this