Back to search

Boston University

Persistent monitoring of targets with uncertain states

Abstract

dc:description.abstract

In a wide range of domains, such as pipeline inspection, surveillance in smart cities and tracking of multiple microparticles by an optical microscope, a common goal is to use mobile agents to persistently monitor a set of targets. We refer to this as the persistent monitoring problem. In this dissertation, we assume that each of these targets has an internal state that evolves with linear stochastic dynamics. The agents can observe these states when they are close to the targets, and the goal is to plan agent trajectories such that the sensed data can be used to minimize the uncertainty of the estimation process. We study scalable approaches for planning agent trajectories that minimize the long term uncertainty of the target states. We design algorithms that are computationally efficient and simple to implement, but grounded in mathematically proven performance guarantees. First we approach the problem from a continuous time perspective with the goal of finding locally optimal agent trajectories using a gradient descent scheme. We assume that trajectories are fully defined by a finite set of parameters and compute the cost gradients. Considering periodic agent trajectories and an infinite time horizon, we prove that, under some natural assumptions, the uncertainty of each target converges to a limit cycle. We also show that, in 1D environments with bounded controls, an optimal control is parametric. In multidimensional settings, we propose an efficient parameterization using Fourier curves. Simulation results show the efficiency of our approach. Next, we consider a graph-constrained, single-agent version of the problem, where agents can only move in the edges of the graph and observe the target when they are visiting the node corresponding to it. We prove that, in this scenario, an optimal policy is such that all the agent have a common peak uncertainty. Using this property of the optimal solution, we develop lightweight algorithms that, instead of directly solving the optimization problem, balance the dwelling times to fulfill such property of an optimal policy. In some particular situations, global optimality of the proposed algorithm is proven. Using a custom-designed greedy exploration scheme, we develop an efficient method for obtaining efficient target visiting sequences. We extended this approach to multi-agent scenarios by using a divide-and conquer strategy, where targets are divided in clusters and each of these clusters is only visited by one agent. Then, we extend those ideas to a discrete time version of the problem. We show that, for a periodic trajectory with fixed cycle length, the problem can be formulated as set of semidefinite programs. This allowed us to leverage efficient SDP solvers to provide fast solutions to the persistent monitoring problem. We design a scheme that leverages the spatial configuration of the targets to guide the search over this set of optimization problems to provide efficient trajectories. Finally we describe an application of the proposed techniques to the problem of tracking multiple diffusing particles using a feedback-driven confocal microscope. The proposed persistent monitoring algorithm was used as the higher level controller in a hierarchical scheme, defining which particle should be tracked at each instant. Then an extremum seeking controller was used as a lower level controller in order to track the moving particle and provide efficient observations.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Mechanical Engineering
Grantor
Boston University
Year dc:date.issued
2021

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Cerqueira Pinto, Samuel
Advisor dc:contributor.advisor
  • Andersson, Sean B.
ORCID dc:identifier.orcid

Subjects

dc:subject × 1

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-ShareAlike 4.0 International
Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/2144/43104

Chain of custody

source
Harvested from
Boston University
Base URL
open.bu.edu/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
related terms
citation

Cerqueira Pinto, Samuel. Persistent monitoring of targets with uncertain states. doctoral thesis, Boston University, 2021. https://hdl.handle.net/2144/43104