Online Trajectory Optimization for Persistent Monitoring Problems in Partitioned Environments

Jonas Håll, Christos G. Cassandras, Sean B. AnderssonarXiv 2024 · DOI · arXiv

TL;DR

This paper introduces a framework for autonomous agents to monitor targets in "partitioned environments"—worlds where the agent's movement rules change depending on the terrain (e.g., a drone flying over water vs. land). The authors propose a two-stage approach: an offline planner called RRBT* that finds time-optimal paths across these different regions, and an online optimizer that fine-tunes how long the agent stays at each target to minimize overall estimation error.

What Problem Does This Paper Address?

Persistent Monitoring (PM) involves a robot moving between targets to keep its "uncertainty" about them low. Imagine a drone monitoring forest fires or water levels; if it stays at one spot too long, its data on other spots becomes stale.

Most existing research assumes the robot moves the same way everywhere. In reality, environments are heterogeneous. A robot might move quickly through an open field but slowly through a dense urban area or a windy coastal zone. This creates a "hybrid dynamical system" where the math governing movement changes abruptly at the boundary of two regions. The challenge is twofold:

  1. Path Planning: How do you find the fastest route when the "speed limit" and physics change every few meters?
  2. Scheduling: How do you balance the time spent collecting data at a target versus the time lost traveling through complex terrains?

Methods

The authors tackle this using a hierarchical decomposition:

  • Hybrid Dynamics Modeling: The environment is partitioned into polyhedra, each with its own smooth vector field describing the agent's dynamics.
  • RRBT* (Rapidly-exploring Random Boundary Tree): This is the paper's core algorithmic contribution. Standard sampling-based planners (like RRT) struggle with hybrid systems because transitions only happen at boundaries. RRBT specifically samples points on the boundaries between regions to build a tree of time-optimal paths. They prove this algorithm is "probabilistically optimal," meaning it will eventually find the best possible path.
  • Graph Abstraction & TSP: They turn the environment into a graph where nodes are targets and edges are the time-optimal paths found by RRBT*. They then solve a Traveling Salesperson Problem (TSP) to find the best visiting sequence.
  • Online Trajectory Optimization: Once the robot is moving, it uses a "local" optimizer to decide the exact path within a region and a "global" optimizer to adjust the duration of each visit. They use "shadow prices" (dual variables from optimization theory) to calculate exactly how changing the time spent at Target A will affect the uncertainty at Target B.

Datasets

The paper does not use external real-world datasets. Instead, it evaluates the framework using synthetic simulations designed to test the hybrid dynamics:

  • Small Scale: 4 targets distributed across 10 distinct regions.
  • Large Scale: 10 targets distributed across 20 regions.
  • Dynamics: Each region was assigned randomly generated constant dynamics to simulate varied terrains.

Key Insights and Ideas

  • The Boundary is Key: In partitioned environments, the "action" happens at the edges. By forcing the sampling-based planner to focus on boundaries, the authors overcome the "zero-measure" problem where a random search might never find the exact point needed to cross from one region to another.
  • Shadow Prices for Sensitivity: The authors utilize the "shadow price" from the local monitoring problem to determine the gradient of the global cost. This allows the agent to update its schedule online without needing to re-solve the entire massive optimization problem from scratch.
  • Steady-State vs. Instant Updates: They compared two ways to update the schedule: waiting for the system to reach a "steady state" before changing visit durations, or updating after every single loop. Surprisingly, updating after every loop (Variant ii) converged much faster, suggesting that "perfect" gradients aren't necessary for effective online learning.

Key Results

  • Optimality Proof: The authors provide a mathematical proof that RRBT* converges in probability to a time-optimal solution, provided the environment meets certain Lipschitz continuity requirements.
  • Simulation Success: In both small and large-scale tests, the agent successfully minimized the average estimation error. The plots show the agent "learning" to balance its time; as it optimizes, the peaks in uncertainty across all targets are leveled out.
  • Control Constraints: The online optimizer successfully respected physical limits (e.g., maximum thrust/velocity) while maintaining a periodic trajectory that kept target uncertainty stable over infinite horizons.

Limitations and Future Work

  • Fixed Switching Points: Currently, the points where the agent enters and leaves a region (the "switching points") are fixed based on the initial offline TSP solution. The authors acknowledge that optimizing these points online could further improve performance but would significantly increase complexity.
  • Computational Cost: While RRBT* is performed offline, it is still computationally expensive. Scaling this to hundreds of regions might require more aggressive pruning or heuristic-guided sampling.
  • Dynamic Environments: The current model assumes the regions and their dynamics are known and static. A major next step would be handling environments where the "partitions" change (e.g., a spreading fire or moving weather front).

Summary updated

Abstract

We consider the problem of using an autonomous agent to persistently monitor a collection of dynamic targets distributed in an environment. We generalize existing work by allowing the agent's dynamics to vary throughout the environment, leading to a hybrid dynamical system. This introduces an additional layer of complexity towards the planning portion of the problem: we must not only identify in which order to visit the points of interest, but also in which order to traverse the regions. We design an offline high-level sequence planner together with an online trajectory optimizer realizing the computed visiting sequence. We provide numerical experiments to illustrate the performance of our approach.
BibTeX
@misc{hall2024online,
  author = {Jonas Håll and Christos G. Cassandras and Sean B. Andersson},
  title = {{Online Trajectory Optimization for Persistent Monitoring Problems in Partitioned Environments}},
  year = {2024},
  eprint = {2403.19769},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2403.19769},
}
Figure