PaperlayerView exact revision on arXiv

Source-linked AI summary

Real-Time Area Coverage and Target Localization using Receding-Horizon Ergodic Exploration

Anastasia Mavrommati, Emmanouil Tzorakoleftherakis, Ian Abraham, Todd D. Murphey

arXiv:1708.08416v1cs.RO

TL;DR

Coverage, search, and target localization are often treated separately, leaving open the question of a unified, application-independent strategy. The paper uses receding-horizon ergodic control to plan motions against an information distribution, and reports target localization in under 60 seconds in most trials.

  • Problem

    Coverage, search, and target localization are commonly addressed separately, and a unified strategy for these objectives remains an open research question.

    Source: §I · p. 2, A. Area Search and Coverage · p. 2

  • Method

    The paper uses hybrid-systems-based receding-horizon ergodic control to plan trajectories that match a spatial information distribution, with agents computing controls locally while sharing information.

    Source: §I · pp. 1–2

  • Results

    In most experimental trials, targets were localized in less than 60 seconds, and the paper establishes ergodic stability under stated assumptions.

    Source: B. Stability analysis · p. 8, A. Experiment 1 · p. 14

  • Takeaways & Limitations

    The approach tracks a non-parameterized information distribution, so its motion-planning strategy is independent of the number of targets being tracked.

    Source: §I · p. 2

Abstract

from arXiv · show

Although a number of solutions exist for the problems of coverage, search and target localization---commonly addressed separately---whether there exists a unified strategy that addresses these objectives in a coherent manner without being application-specific remains a largely open research question. In this paper, we develop a receding-horizon ergodic control approach, based on hybrid systems theory, that has the potential to fill this gap. The nonlinear model predictive control algorithm plans real-time motions that optimally improve ergodicity with respect to a distribution defined by the expected information density across the sensing domain. We establish a theoretical framework for global stability guarantees with respect to a distribution. Moreover, the approach is distributable across multiple agents, so that each agent can independently compute its own control while sharing statistics of its coverage across a communication network. We demonstrate the method in both simulation and in experiment in the context of target localization, illustrating that the algorithm is independent of the number of targets being tracked and can be run in real-time on computationally limited hardware platforms.

I. INTRODUCTION

The paper unifies area search, coverage, and target localization by planning trajectories whose spatial statistics match a terrain information distribution. It presents receding-horizon ergodic control as an online, adaptive approach with stability guarantees, multi-agent distributability, and applicability to nonlinear systems.

I. INTRODUCTION

  • Hybrid-systems-based receding-horizon control computes actions to improve ergodicity, with low execution times and stability guarantees for dynamic states and information evolution.The paper also establishes conditions for ergodic stability of the closed-loop system.Source: §I · p. 1
  • The method is demonstrated in real-time simulation with a quadrotor model and in an experiment using a sphero SPRK robot for bearing-only target localization.The proposed algorithm also adapts reactively to changing information distributions and new target estimates.Source: §I · p. 1
  • Agents compute controls locally while sharing information after each iteration, enabling distributed ergodic control without added computational complexity.The approach tracks a non-parameterized information distribution rather than planning a separate motion for each target, making it independent of target count.Source: §I · p. 2
  • The approach jointly addresses search and tracking by encoding both objectives in a spatial information distribution that trajectory statistics must match.This avoids planning independently for each target and supports localization while searching for additional targets.Source: §I · pp. 1–2

A. Area Search and Coverage

  • For area search and coverage, the paper replaces workspace decomposition with a continuous information distribution and online motion planning that responds to changes while accounting for agent dynamics.Prior decomposition methods can require computationally intensive grid updates in changing environments and may plan paths that are infeasible for the agent dynamics,,.Source: A. Area Search and Coverage · p. 2
  • Ergodic coverage matches the spatial statistics of agents’ full trajectories to the terrain distribution over time, rather than optimizing only their final positions.An instantaneous agent configuration need not maximize detection probability; the approach is intended for online coverage with time-dependent or real-time-sensed density functions.Source: A. Area Search and Coverage · pp. 2–3

B. Motion Planning for Target Localization

The section contrasts target-localization strategies with ergodic exploration, which plans against a spatial information distribution rather than individual targets. It then defines ergodicity as matching a trajectory’s time-averaged spatial statistics to that distribution.

B. Motion Planning for Target Localization

  • Information-maximization methods can be computationally intensive or application-specific, while the proposed approach explores an expected-information map and supports multiple moving targets without added complexity.The approach tracks a non-parameterized distribution rather than planning separately for each target.Source: B. Motion Planning for Target… · p. 3

C. Ergodic Control Algorithms

  • Hybrid-systems-based ergodic control is presented as a fast, real-time alternative that adapts to changing information distributions for moving-target tracking.Prior finite-horizon trajectory optimization is described as too costly for real-time receding-horizon use.Source: C. Ergodic Control Algorithms · p. 4

III. Ergodicity metric

  • The ergodic metric compares Fourier coefficients of the terrain distribution with those of the trajectory’s time-averaged spatial statistics.The spatial distribution can represent probability of detection or expected information density.Source: §III · p. 4

IV. Receding-horizon ergodic exploration

The receding-horizon method addresses ergodic motion planning for nonlinear control-affine systems through a hybrid control formulation. At each step it computes a control action intended to improve ergodicity while contracting the cost enough to support stability and real-time execution.

IV. Receding-horizon ergodic exploration

  • The formulation considers systems that may be nonlinear in state but are linear or linearized in control, and distinguishes dynamic states from trajectory-statistic information states.The ergodic cost is non-quadratic and not in Bolza form with respect to dynamic states, creating computational and stability challenges for standard approaches.Source: A. Algorithm Derivation · p. 5
  • The method seeks real-time control by computing a single action in closed form that improves ergodicity enough to guarantee stability with respect to dynamic and information states.The approach aims for cost contraction rather than full cost optimization at each step.Source: A. Algorithm Derivation · pp. 5–6
  • RHEE repeatedly solves an open-loop ergodic-control problem online from the current state, then applies the resulting control over the sampling interval.The stated algorithm inputs include the spatial distribution, initial state and time, and ergodic initial time.Source: A. Algorithm Derivation · p. 5
  • The open-loop problem uses a default control and seeks a specified ergodic-cost decrease, enabling a rapid solution while retaining the stated stability condition.The system is described as nonlinear control-affine with input constraints.Source: A. Algorithm Derivation · pp. 5–6

1) Predict:

The prediction step simulates the system under its default control and uses the predicted trajectory to compute the mode-insertion-gradient action schedule. The schedule contains candidate infinitesimal actions, with control constraints handled by direct saturation.

1) Predict:

  • The prediction step simulates the system from the current state under default control and backward-simulates the associated sensitivity trajectory.The predicted state trajectory is used to compute ρE.Source: 1) Predict · p. 6
  • The optimal schedule lists candidate action values and application times, assuming infinitesimal durations before a later step selects a finite action.It is obtained by minimizing the mode insertion gradient, which measures the cost’s rate of change under an infinitesimal control switch.Source: 1) Predict · p. 6
  • The schedule’s aggressiveness is tuned by the user-specified parameter αd, and its actions can be saturated directly to meet min/max control bounds.The closed-form schedule follows evaluation of the system and sensitivity dynamics.Source: 1) Predict · pp. 6–7

3) Determine application time τA (and thus uA value):

The algorithm selects an application time and action value from the candidate schedule, then chooses a finite duration that ensures cost descent. It also bounds the history used to compare trajectory statistics with a changing spatial distribution.

3) Determine application time τA (and thus uA value):

  • The selected application time τA identifies the candidate action uA that yields the greatest cost reduction relative to default control.The algorithm chooses from the action schedule computed in the preceding step.Source: 3) Determine application time τA (and… · p. 7

4) Determine control duration λA:

  • A finite control duration λA is chosen to satisfy the descent condition, and a nonzero neighborhood near zero guarantees that such a duration exists.A line search can calculate the finite duration.Source: 4) Determine control duration λA · p. 7
  • After the action’s value, application time, and duration are specified, iteration produces piecewise-continuous, input-constrained ergodic control laws for nonlinear systems.When a new distribution becomes available, RHEE is reinitialized; known distribution evolution can allow offline coefficient calculation to reduce computational cost.Source: 4) Determine control duration λA · p. 7
  • Ergodic memory Merg limits how far back trajectory statistics are retained, balancing adaptation to changing distributions with avoiding recently visited states.For cost computation, stored trajectory coefficients remain constant in number as time progresses.Source: 4) Determine control duration λA · pp. 7–8

B. Stability analysis

The stability analysis imposes a contractive constraint on the ergodic cost and establishes convergence of the closed-loop trajectory statistics to the target distribution under stated assumptions.

B. Stability analysis

  • A contractive constraint on the open-loop cost requires sufficient improvement between time steps, supporting the closed-loop stability proof.The constraint is applied to the cost defined from the open-loop problem.Source: B. Stability analysis · p. 8
  • Ergodic stability means the trajectory’s spatial statistics converge to the desired distribution, rather than convergence to a single equilibrium state.The paper expresses this through convergence of the Fourier coefficients and distinguishes stability of a motion from equilibrium-point stability.Source: B. Stability analysis · p. 8
  • Under Assumptions 1–2, the receding-horizon strategy is ergodically stable: its trajectory coefficients converge to the target coefficients as time tends to infinity.The proof uses a bounded integral and Barbalat’s lemma to establish asymptotic convergence.Source: B. Stability analysis · p. 8

C. Multi-agent ergodic exploration

Agents independently compute local controls while exchanging trajectory statistics after each iteration, allowing the team’s combined coverage to track a shared spatial distribution.

C. Multi-agent ergodic exploration

  • Each agent runs the algorithm locally, but exchanges Fourier-parameterized trajectory statistics with other agents after every algorithm cycle.The shared statistics include other agents’ past trajectories and their intended trajectories over the previous planning horizon.Source: C. Multi-agent ergodic exploration · pp. 8–9
  • Sharing trajectory statistics lets agents account for collective coverage and coordinate their exploration so combined statistics match the assigned distribution.Each agent adds received statistics from other agents’ previous trajectories when computing its ergodic cost.Source: C. Multi-agent ergodic exploration · p. 9
  • If two or more agents occupy identical states, their motion degenerates to a single-agent motion and does not use all agents’ control authority.Source: C. Multi-agent ergodic exploration · p. 9
  • Per-agent computation remains O(1) as team size grows, while receiving communication capacity scales as O(N).Each agent transmits at constant capacity when the coefficient order and number of ergodic variables are fixed.Source: C. Multi-agent ergodic exploration · p. 9

A. Expected Information Density

Expected information density is built from Fisher information averaged over target belief, providing the spatial distribution for ergodic localization. With limited sensor range, convergence to that distribution can ensure a measurement is eventually acquired under an explicit assumption.

A. Expected Information Density

  • Expected information density is obtained by averaging the Fisher information matrix over the target-parameter belief, with numerical discretization used to reduce integration cost.The belief representation and update method may vary; the derivation is independent of the number of targets.Source: A. Expected Information Density · pp. 9–10
  • The expected-information-density derivation remains independent of both the number of targets and the method used to update target belief.Source: A. Expected Information Density · p. 10

B. Remarks on Localization with Limited Sensor Range

  • When the true target location is uncertain and sensing range is limited, motion toward maximum information may miss the target and prevent new measurements.The paper’s localization result addresses this risk under an assumption that positive expected information density exists at some in-range location.Source: B. Remarks on Localization with… · p. 10
  • Under Assumption 3, ergodic localization eventually visits an in-range location with positive expected information density, enabling new measurements and an update to that density.Source: B. Remarks on Localization with… · p. 10
  • The required nonzero information near the true target can be supported by slowing filter convergence or artificially introducing nonzero information values across the terrain.Source: B. Remarks on Localization with… · p. 10

VI. Simulation Results

Simulations show ergodic exploration covering an occluded terrain and coordinating five aerial vehicles over a shared detection distribution. The examples include a nonlinear 12-state quadrotor model.

A. Ergodic Exploration and Coverage

  • As the simulation proceeds, trajectory lines fill the square terrain and their spatial statistics approach the desired uniform probability-of-detection distribution.The example uses second-order agent dynamics and occlusions with zero detection probability; these regions are not obstacles to avoid completely.Source: A. Ergodic Exploration and Coverage · pp. 10–11

2) Multi-agent aerial exploration:

  • Five aerial vehicles explore one shared detection distribution rather than receiving separate peaks, with motion planned simultaneously toward high-probability areas.The demonstration uses a 12-state quadrotor model; the occluded-environment figure also reports matching spatial statistics and decreasing ergodic cost, with small numerical fluctuations.Source: 2) Multi-agent aerial exploration · p. 11, Figure 3 · p. 11

B. Ergodic Coverage and Target Localization

The section applies ergodic control to coverage and bearing-only target localization, including simultaneous exploration and tracking. Simulations and robot experiments illustrate real-time operation across single- and multi-agent settings.

B. Ergodic Coverage and Target Localization

  • Five quadrotors collectively explore one shared spatial distribution, with combined trajectory statistics approaching that distribution by the end of simulation.Agents avoid exploring the same region simultaneously and return to visited areas after time has passed.Source: Figure 4 · p. 12

1) Bearing-only localization of a moving target with limited sensor range:

  • The quadrotor tracks a moving target without a prior motion model, producing a cyclic, swirling path around it while adapting to expected information density.The simulation runs for 45 seconds in approximately 25 seconds; localization is slower than exploration because expected information density must be recalculated.Source: 1) Bearing-only localization of a… · p. 13

2) Multi-agent simultaneous terrain exploration and target localization:

  • The multi-agent simulation uses a centralized EKF for simplicity, while allowing other filters that estimate target state; cooperative sensing filters are not addressed.The example tracks a random number of targets using two UAVs.Source: 2) Multi-agent simultaneous terrain… · p. 13
  • Two UAVs combine exploration for undetected targets with localization of detected targets by encoding detection probability and expected measurement information in the spatial distribution.Areas with no information from detected-target measurements retain a middle information-density value to promote exploration.Source: 2) Multi-agent simultaneous terrain… · p. 13

VII. Experimental Results

  • Across twenty trials with two random static targets, 100% of first targets were localized within 40 seconds, and 80% of trials localized both within 40 seconds.Localization required the position-belief error to fall below 0.05; all targets were eventually localized by 100 seconds, including delayed-detection or EKF non-convergence cases.Source: Figure 8 · p. 14
  • The robot experiment also localizes increasing numbers of moving targets, alternating attention as each estimate’s variance falls sufficiently.With moving targets and limited sensor range, belief standard deviations fluctuate over time; the alternating behavior arises autonomously from the ergodicity objective.Source: Figure 9 · p. 14
  • The robot experiments run the ergodic controller at approximately 10 Hz, using bearing-only estimates and a simulated 0.2 m sensor range.An overhead camera supplies position data that are transformed into bearing-only measurements.Source: §VII · pp. 13–14

A. Experiment 1

The experiments assess localization robustness, while the coefficient and convergence-rate discussions qualify how ergodic trajectories are represented and constrained. The conclusion reports real-time target tracking and stability demonstrations in simulation and experiment.

A. Experiment 1

  • In twenty trials, the robot eventually localized both static targets even when detection was delayed or the EKF failed to converge, supporting convergence guarantees under poor estimates and limited range.Most trials localized targets in less than 60 seconds.Source: A. Experiment 1 · p. 14

B. Experiment 2

  • For moving targets, the robot alternates between target estimates as their variances fall, with fluctuations arising from target motion and limited sensor range.This behavior emerges autonomously from the ergodicity objective.Source: B. Experiment 2 · p. 14, Figure 10 · p. 15

A. Number of Fourier coefficients

  • All choices of Fourier-coefficient order K satisfy the stated stability definition, but different K values can produce different trajectories because convergence concerns trajectory statistics, not the trajectory itself.Lower K makes the trajectory-statistics representation more diffuse and can omit fine-scale search-density detail; returns diminish as K increases.Source: A. Number of Fourier coefficients · p. 15, Figure 11 · p. 15
  • The required K depends on search-density refinement; the paper reports that K = 5 sufficed for its simulation and experimental tasks.Source: A. Number of Fourier coefficients · p. 15

B. Convergence Rate

  • The convergence-rate bound is determined by M, with an additional time-dependent constraint D(t) satisfying L ≥ M ≥ D; the bound is the highest rate for which a finite-duration control action exists at each step.The discussion notes that sampling time can be manipulated to satisfy this requirement.Source: B. Convergence Rate · p. 15

IX. Conclusions

  • The paper concludes that ergodic control tracked moving targets in real time using bearing-only measurements in simulation and robot experiments, with target count unknown and motion modeled as diffusion.The examples also demonstrate stability with respect to expected information density, as established by the theoretical results.Source: §IX · p. 16

Appendix A Proof

The appendix proof introduces action-dependent control inputs and a cost parameterized by action application, then derives an expression for the ergodic-cost mode insertion gradient.

Appendix A Proof

  • The proof makes the control input’s dependence on action A explicit by writing it as a function of the action parameters.Source: Appendix A · p. 16
  • When λA = 0, the control u(t; 0, ·, ·) is identically equal to udef.Source: Appendix A · p. 16
  • The proof defines an ergodic performance cost parameterized by the action’s application parameters, including its start time.Source: Appendix A · p. 16
  • It uses the linearized-system state transition matrix and the defined quantity ℓ to obtain the mode insertion gradient of the ergodic cost.Source: Appendix A · p. 16
Loading 1708.08416v1…