PaperlayerView exact revision on arXiv

Source-linked AI summary

Persistent Robotic Tasks: Monitoring and Sweeping in Changing Environments

Stephen L. Smith, Mac Schwager, Daniela Rus

arXiv:1102.0603v1cs.ROmath.OC

TL;DR

Persistent monitoring and sweeping require robots to control continual service of a changing environment while traveling on fixed closed paths. The paper models environmental accumulation and uses finite-basis speed controllers with LP synthesis to guarantee bounded fields, optimize the single-robot maximum, and handle multiple robots without communication. Simulations demonstrate robustness to modeling errors and stochasticity.

  • Problem

    Persistent tasks require continual monitoring or sweeping because environmental material or uncertainty changes at every location over time.

  • Method

    The paper represents speed controllers with finite basis functions and formulates LPs for fixed-path robots, including stabilizing, single-robot optimal, and multi-robot controllers.

  • Results

    The LP formulations produce bounded-field controllers when feasible, with the multi-robot controller requiring no communication; simulations show robustness to model errors and stochasticity.

  • Takeaways & Limitations

    Speed regulation along prescribed paths provides a tractable framework for persistent tasks, including heterogeneous multi-robot operation without inter-robot communication.

Abstract

from arXiv · show

We present controllers that enable mobile robots to persistently monitor or sweep a changing environment. The changing environment is modeled as a field which grows in locations that are not within range of a robot, and decreases in locations that are within range of a robot. We assume that the robots travel on given closed paths. The speed of each robot along its path is controlled to prevent the field from growing unbounded at any location. We consider the space of speed controllers that can be parametrized by a finite set of basis functions. For a single robot, we develop a linear program that is guaranteed to compute a speed controller in this space to keep the field bounded, if such a controller exists. Another linear program is then derived whose solution is the speed controller that minimizes the maximum field value over the environment. We extend our linear program formulation to develop a multi-robot controller that keeps the field bounded. The multi-robot controller has the unique feature that it does not require communication among the robots. Simulation studies demonstrate the robustness of the controllers to modeling errors, and to stochasticity in the environment.

I. INTRODUCTION

The paper formulates persistent monitoring and sweeping as controlling robot speeds on fixed closed paths so a changing field remains bounded. It develops tractable LP-based controllers for single and multiple robots and evaluates their robustness.

  • Motivation: Persistent tasks require robots to revisit every location continually, spending more time where the environment changes faster without neglecting slower-changing locations.Applications include cleaning accumulating material and monitoring states whose uncertainty grows over time.
  • Problem model: The changing environment is modeled by an accumulation function that grows when a robot does not cover a point and decreases when its footprint covers it.Production and consumption rates may vary across environmental locations.
  • Problem setting: Robots follow prescribed closed paths, with speed regulation providing the control mechanism under constraints such as traffic, airspace, or pedestrian interference.The paper focuses on fixed paths rather than path planning.
  • Controller representation: Finite basis functions represent speed controllers as linear combinations, enabling efficient linear-program formulations with off-the-shelf solvers.The LPs can also incorporate location-dependent maximum and minimum speed limits.
  • Single-robot synthesis: For single robots, one LP guarantees a bounded accumulation field when feasible, while another computes a controller minimizing the eventual maximum field value.The stabilizing LP is infeasible when no controller in the represented space can keep the field bounded.
  • Multi-robot synthesis and evaluation: The multi-robot LP yields a bounded-field controller without requiring communication, while simulations show robustness to stochastic, deterministic, and unmodeled vehicle-dynamics errors.The paper does not find an LP-based optimal controller for the multi-robot case.

A. Persistent Tasks

A persistent task combines robots, paths, points of interest, and field production and consumption rates. The formulation models robot coverage through a finite-footprint sensor while constraining motion to a closed curve.

  • Robot and path: The robot moves along a closed curve γ parameterized by position θ and carries a finite footprint B(θ) that determines which environment points it covers.The footprint may represent a sensing field of view or cleaning surface.
  • Field dynamics: The accumulation function Z is defined on points of interest, increases at production rate p(q), and is consumed at rate c(q) when the robot footprint covers q.The model assumes c(q) > p(q) > 0 and known production and consumption parameters.
  • Definition: A persistent task is defined as the tuple (R, γ, Q, p, c), comprising the robot model, closed path, points of interest, and field production and consumption rates.This tuple formalizes the components of the task model.

B. Field Stability and Feasibility

The paper defines field stability for persistent tasks and characterizes it through coverage and consumption over repeated path cycles. It restricts attention to periodic position-feedback controllers, which preserve stabilizability while enabling feasibility and optimization formulations.

  • Stability and Feasibility: Field stability requires the accumulation field to become bounded everywhere, independently of initial conditions.A feasible persistent task is one admitting at least one field-stabilizing speed controller.
  • Stability and Feasibility: A persistent task is feasible exactly when a field-stabilizing speed controller exists.
  • Controller Class: Periodic position-feedback controllers depend only on the robot’s current path position and repeat the same speed at each cycle.They obey position-dependent speed bounds and require model parameters rather than the current field state.
  • Controller Class: Any task stabilizable by a general controller is also stabilizable by a periodic position-feedback controller.
  • Stability Condition: For each point, stability requires field consumption during coverage to exceed production over every cycle.The condition is expressed using the cycle time T and coverage time τ(q).
  • Optimization Problems: The paper formulates stabilization and maximum steady-state-field minimization as linear-programming problems, with the latter introduced for a single robot.

III. SINGLE ROBOT SPEED CONTROLLERS: STABILITY AND OPTIMALITY

The single-robot controller design uses reciprocal speed and a finite basis-function parameterization. This converts the search for speed controllers and minimum-field controllers into tractable optimization within the chosen function class.

  • Problem Representation: The method focuses on a finite set of interest points that may represent regions or a discretized approximation of the environment.
  • Controller Parameterization: The controller is represented through reciprocal speed, v^-1(θ), subject to reciprocal speed bounds.
  • Controller Parameterization: A finite basis such as Fourier, Gaussian, or rectangular functions represents reciprocal speed as a linear combination with coefficients α1, ..., αn.Rectangular functions provide a piecewise-constant approximation that simplifies speed-constraint enforcement.
  • Controller Parameterization: Optimizing the basis coefficients searches for the best controller within the selected finite-dimensional class rather than among all possible speed functions.

A. Synthesis of a Field Stabilizing Controller

For a single robot, the paper derives a linear program whose feasibility is equivalent to finding a stabilizing controller in the chosen basis class. A modified program maximizes robustness to production-rate uncertainty.

  • LP Formulation: The stabilizing-controller formulation uses basis coefficients and coverage integrals to test the cycle-based stability condition.
  • LP Formulation: A persistent task is stabilizable by the selected controller form if and only if the stated linear program is feasible.
  • LP Formulation: The feasibility program has n coefficient variables and 2n + m constraints.There are two speed-bound constraints per basis coefficient and one stability constraint per point of interest.
  • Robustness: Maximizing the stability margin produces the largest decrease in field per cycle and reaches steady state in the minimum number of cycles.
  • Robustness: The maximum-margin controller is robust to errors in estimating the field production rate.
  • Implementation Caveat: For non-rectangular basis functions, enforcing speed constraints over finitely many sampled positions provides a practical approximation rather than an exact LP formulation.Constraint tightening by ξ is used to recover satisfaction of the original speed constraints.

B. Synthesis of an Optimal Controller

The paper minimizes the maximum steady-state field by exploiting the controller’s periodic steady-state structure. It characterizes field values across coverage intervals and derives a linear program whose solution is optimal.

  • Objective: The optimization objective is the maximum steady-state field over the finite region of interest Q.
  • Steady-State Structure: From every initial condition, the field reaches its steady-state bound in finite time, and each point has a robot position where its steady-state value is zero.
  • Steady-State Structure: A stabilizing controller yields a steady-state field independent of the initial field and initial robot position.
  • Field Computation: The coverage set F(q) is decomposed into disjoint intervals where the field decreases during coverage and increases outside coverage.
  • Field Computation: The maximum steady-state field at a point is attained at an endpoint of a coverage interval.The endpoint values can be computed from the preceding interval endpoint and the interval dynamics.
  • Optimal Controller: The linear program in Theorem III.8 yields a controller that minimizes the maximum steady-state field H(v).

IV. MULTI-ROBOT SPEED CONTROLLER

The multi-robot formulation models additive consumption from robots traveling on fixed, possibly intersecting paths. Under rational-period assumptions, stability is characterized by per-point total consumption exceeding production over a common period.

  • Multi-robot model: Multiple robots may follow different or identical fixed paths that intersect arbitrarily, with heterogeneous footprints, consumption rates, and speed limits.Collision handling is not explicitly addressed, though existing avoidance strategies could augment the controller.
  • Multi-robot model: When robot footprints overlap a point, their consumption rates are assumed to add.The field dynamics therefore aggregate the active robots’ effects at each location.
  • Common period: Rational robot periods guarantee a common period containing an integer number of cycles for every robot.This common interval supports the multi-robot stability analysis.
  • Stability condition: The multi-robot stability condition requires total consumption per common period to exceed total production at every point.This condition is both necessary and sufficient for field stabilization.
  • Stability condition: If the condition holds, the field eventually remains below the bound Zmax = maxq∈Q TC(q).The proof shows that values above the threshold decrease over successive common periods, while lower values remain bounded.
  • Assumptions: The rational-period assumption simplifies exposition rather than fundamentally restricting the result, because rational numbers densely approximate real periods.The authors state that the analysis could carry an approximation error through the proof.

A. Synthesis of Field Stabilizing Multi-Robot Controllers

The multi-robot stabilizing controller is synthesized with normalized speed profiles and free inverse-period parameters. Stability becomes a linear-program feasibility problem whose size grows linearly with the number of robots.

  • Controller parametrization: Each robot’s speed controller is normalized by its period, while the inverse period is represented as a separate optimization parameter.The formulation accommodates robot-specific paths, basis functions, and periods.
  • Controller parametrization: Rectangular basis functions and robot-specific frequency parameters produce linear stability constraints with speed-limit bounds.The coefficients are constrained between bounds derived from each robot’s minimum and maximum speeds.
  • Linear-program synthesis: A persistent task is stabilizable by the parametrized controllers if and only if the associated linear program is feasible.The LP uses basis-function coefficients and robot frequencies as optimization variables.
  • Linear-program synthesis: Using n basis functions per robot yields (n + 1)N variables and m+2N(n+1) constraints, so LP size grows linearly with robot count.The variable count includes n coefficients and one frequency per robot.
  • Optimization objective: Maximizing B in the LP can maximize the stability margin and minimize the number of common periods to reach steady state.This replaces the trivial zero objective with a robustness-oriented criterion.
  • Limitation: The optimal multi-robot controller minimizing the steady-state field cannot be formulated as an LP in the same way as for one robot.Relative robot positions create infinitely many configurations that would need consideration; alternative convex methods are under investigation.

V. SIMULATIONS

Simulations demonstrate controller synthesis for discrete and continuous monitoring fields, including single-robot convergence and multi-robot discretized-field experiments. The studies also assess implementation and robustness to modeling and execution uncertainties.

  • Simulation scope: The simulations evaluate implementation details, discrete and continuous fields, and robustness to modeling, parameter, tracking, and stochastic errors.The optimization framework was implemented in MATLAB and solved with SeDuMi after time discretization.
  • Single-robot simulation: A 10-point single-robot task uses a 70 m by 70 m environment, a 300 m closed path, a 12 m footprint, and speeds from 0.2 to 2 m/s.The field production rates are 0.15 for yellow points and 0.35 for the single red point, with consumption rate 1.
  • Single-robot simulation: The red point’s field converges in finite time to a periodic steady-state cycle and reaches zero during every cycle.This behavior matches the steady-state characterization used in the single-robot analysis.
  • Single-robot simulation: 150 rectangular basis functions produce a controller in less than 1/10 of a second, with cycle time T = 420 s.The resulting controller is the optimized speed profile shown for the single-robot example.
  • Multi-robot simulation: A two-robot continuous-field simulation approximates a 690 m by 690 m environment with a 32 × 32 grid and uses a stability-margin-maximizing controller.The robots follow a 2630 m figure-eight path and a four-leaf clover path.

A. A Case Study in Robustness

The case study evaluates whether the speed controller remains effective under production-rate noise, parameter errors, and tracking errors. Simulations show bounded fields despite these disturbances, with performance degradation under stochastic noise and a 13% increase under tracking error.

  • Experimental setup: The robustness study uses a 665 m by 665 m environment discretized into a 32 × 32 grid, with a 4200 m closed path.The controller uses 280 rectangular basis functions and completes one cycle in T = 439 s.
  • Stochastic field evolution: The controller remains stable as zero-mean production-rate noise increases, although the mean maximum field value increases.Each noise level used 20 independent trials over a 2500 s horizon.
  • Parameter errors: 30% production-rate uncertainty is tolerated in the example, with field stability verified for any ϵ ≤0.07.The average production rate is 0.21, while the tested stability threshold is 0.07.
  • Tracking error: A stability margin of B = 97.8 keeps the field stable despite unicycle tracking error.The tracking model uses vmin = 1.5 m/s, vmax = 15 m/s, and angular speed bounded by 0.5 rad/s.
  • Tracking error: Tracking error increases the simulated maximum field height by about 13%, from 268 to 305.The comparison uses 268 for the zero-noise case and 305 with tracking error.

VI. CONCLUSIONS, EXTENSIONS, AND OPEN PROBLEMS

The paper models persistent sweeping and monitoring with robots constrained to prescribed closed paths and controlled through their speeds. Linear programs provide bounded controllers for single and multiple robots, plus an optimal single-robot controller, while the work leaves further problems open.

  • Conclusions: The paper proposes a model and controllers for persistent sweeping and monitoring tasks in changing environments.The formulation targets robots whose actions must continue perpetually.
  • Conclusions: An LP computes single- and multi-robot speed controllers that keep the accumulation function bounded everywhere.The robots are confined to pre-specified closed paths, with speed regulated along those paths.
  • Conclusions: A separate single-robot LP computes the controller that keeps the accumulation function as low as possible everywhere.This optimization targets the maximum accumulation over the environment.
  • Open problems: Many open problems remain beyond this formulation of persistent robotic tasks.The conclusion identifies the presented solution as addressing one kind of persistent task.

A. Extensions and Open Problems

The paper places prescribed-path speed control within a broader design space for persistent tasks. It identifies extensions involving trajectories, multiple robots, unknown or time-varying production, and continuum points, and proposes online LP updates as one future direction.

  • Extensions and open problems: Persistent-task formulations vary by whether robots control speed, path, or complete trajectory.The paper studies speed control over a prescribed path.
  • Extensions and open problems: Persistent-task settings also differ in robot count, production-rate knowledge, temporal variation, and whether points of interest are finite or continuous.This paper considers single and multiple robots, finite environments, and known constant production rates.
  • Extensions and open problems: Future work could plan full robot trajectories, although the high dimensionality of trajectory space makes this difficult.Constrained paths, such as piecewise linear paths for underwater gliders, may admit guaranteed solutions.
  • Extensions and open problems: Online LP recomputation could adapt controllers when production rates are sensed or change over time.The proposed direction is a receding-horizon procedure using newly acquired field-evolution information.

APPENDIX PERIODIC POSITION-FEEDBACK CONTROLLERS

The appendix shows that a general field-stabilizing speed controller can be represented through controllers applied cycle by cycle. Under bounded speed limits, the constructed periodic position-feedback controller also stabilizes the field.

  • Periodic position-feedback controllers: Because position progresses strictly around the closed path and field evolution is deterministic, a general controller can be represented as a sequence of cycle-specific controllers.The controller sequence is indexed by the robot’s successive periods.
  • Periodic position-feedback controllers: Starting from sufficiently large field values, stability implies that every point eventually falls below any fixed bound above the limiting bound.For any δ ∈ (0, ϵ), some finite cycle k satisfies Z(q, tk) ≤ Zmax + δ for every q.
  • Periodic position-feedback controllers: The appendix defines a periodic controller from the cycle-specific controllers once the field has entered the desired bounded region.The construction is introduced after establishing a finite cycle at which all points satisfy the bound.
  • Periodic position-feedback controllers: The resulting controller satisfies the stability condition and is therefore a field-stabilizing position-feedback controller.This conclusion follows directly from the stability condition in Lemma II.5.
Loading 1102.0603v1…