An official website of the United States government
This paper addresses the complete area coverage problem of a known environment by multiple-robots. Complete area coverage is the problem of moving an end-effector over all available space while avoiding existing obstacles. In such tasks, using multiple robots can increase the efficiency of the area coverage in terms of minimizing the operational time and increase the robustness in the face of robot attrition. Unfortunately, the problem of finding an optimal solution for such an area coverage problem with multiple robots is known to be NP-complete. In this paper we present two approximation heuristics for solving the multi-robot coverage problem. The first solution presented is a direct extension of an efficient single robot area coverage algorithm, based on an exact cellular decomposition. The second algorithm is a greedy approach that divides the area into equal regions and applies an efficient single-robot coverage algorithm to each region. We present experimental results for two algorithms. Results indicate that our approaches provide good coverage distribution between robots and minimize the workload per robot, meanwhile ensuring complete coverage of the area.
more »
« less
This content will become publicly available on January 1, 2026
Fast Ergodic Search With Kernel Functions
Ergodic search enables optimal exploration of an information distribution with guaranteed asymptotic coverage of the search space. However, current methods typically have exponential computational complexity and are limited to Euclidean space. We introduce a computationally efficient ergodic search method. Our contributions are two-fold: First, we develop a kernel-based ergodic metric, generalizing it from Euclidean space to Lie groups. We prove this metric is consistent with the exact ergodic metric and ensures linear complexity. Second, we derive an iterative optimal control algorithm for trajectory optimization with the kernel metric. Numerical benchmarks show our method is two orders of magnitude faster than the state-of-the-art method. Finally, we demonstrate the proposed algorithm with a peg-in-hole insertion task. We formulate the problem as a coverage task in the space of SE(3) and use a 30-second-long human demonstration as the prior distribution for ergodic coverage. Ergodicity guarantees the asymptotic solution of the peg-in-hole problem so long as the solution resides within the prior information distribution, which is seen in the 100% success rate.
more »
« less
- Award ID(s):
- 2237576
- PAR ID:
- 10577250
- Publisher / Repository:
- IEEE
- Date Published:
- Journal Name:
- IEEE Transactions on Robotics
- Volume:
- 41
- ISSN:
- 1552-3098
- Page Range / eLocation ID:
- 1841 to 1860
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Goaoc, Xavier; Kerber, Michael (Ed.)We consider the following surveillance problem: Given a set P of n sites in a metric space and a set R of k robots with the same maximum speed, compute a patrol schedule of minimum latency for the robots. Here a patrol schedule specifies for each robot an infinite sequence of sites to visit (in the given order) and the latency L of a schedule is the maximum latency of any site, where the latency of a site s is the supremum of the lengths of the time intervals between consecutive visits to s. When k = 1 the problem is equivalent to the travelling salesman problem (TSP) and thus it is NP-hard. For k ≥ 2 (which is the version we are interested in) the problem becomes even more challenging; for example, it is not even clear if the decision version of the problem is decidable, in particular in the Euclidean case. We have two main results. We consider cyclic solutions in which the set of sites must be partitioned into 𝓁 groups, for some 𝓁 ≤ k, and each group is assigned a subset of the robots that move along the travelling salesman tour of the group at equal distance from each other. Our first main result is that approximating the optimal latency of the class of cyclic solutions can be reduced to approximating the optimal travelling salesman tour on some input, with only a 1+ε factor loss in the approximation factor and an O((k/ε) ^k) factor loss in the runtime, for any ε > 0. Our second main result shows that an optimal cyclic solution is a 2(1-1/k)-approximation of the overall optimal solution. Note that for k = 2 this implies that an optimal cyclic solution is optimal overall. We conjecture that this is true for k ≥ 3 as well. The results have a number of consequences. For the Euclidean version of the problem, for instance, combining our results with known results on Euclidean TSP, yields a PTAS for approximating an optimal cyclic solution, and it yields a (2(1-1/k)+ε)-approximation of the optimal unrestricted (not necessarily cyclic) solution. If the conjecture mentioned above is true, then our algorithm is actually a PTAS for the general problem in the Euclidean setting. Similar results can be obtained by combining our results with other known TSP algorithms in non-Euclidean metrics.more » « less
-
Abstract We study the problem of stability of the catenoid, which is an asymptotically flat rotationally symmetric minimal surface in Euclidean space, viewed as a stationary solution to the hyperbolic vanishing mean curvature equation in Minkowski space. The latter is a quasilinear wave equation that constitutes the hyperbolic counterpart of the minimal surface equation in Euclidean space. Our main result is the nonlinear asymptotic stability, modulo suitable translation and boost (i.e., modulation), of the$$n$$ -dimensional catenoid with respect to a codimension one set of initial data perturbations without any symmetry assumptions, for$$n \geq 5$$ . The modulation and the codimension one restriction on the data are necessary and optimal in view of the kernel and the unique simple eigenvalue, respectively, of the stability operator of the catenoid. In a broader context, this paper fits in the long tradition of studies of soliton stability problems. From this viewpoint, our aim here is to tackle some new issues that arise due to the quasilinear nature of the underlying hyperbolic equation. Ideas introduced in this paper include a new profile construction and modulation analysis to track the evolution of the translation and boost parameters of the stationary solution, a new scheme for proving integrated local energy decay for the perturbation in the quasilinear and modulation-theoretic context, and an adaptation of the vectorfield method in the presence of dynamic translations and boosts of the stationary solution.more » « less
-
Wallach, H.; Larochelle, H.; Beygelzimer, A.; d'Alché-Buc, F.; null; Garnett, R. (Ed.)In this paper, we consider the nonparametric least square regression in a Reproducing Kernel Hilbert Space (RKHS). We propose a new randomized algorithm that has optimal generalization error bounds with respect to the square loss, closing a long-standing gap between upper and lower bounds. Moreover, we show that our algorithm has faster finite-time and asymptotic rates on problems where the Bayes risk with respect to the square loss is small. We state our results using standard tools from the theory of least square regression in RKHSs, namely, the decay of the eigenvalues of the associated integral operator and the complexity of the optimal predictor measured through the integral operator.more » « less
-
null (Ed.)The authors develop a theory characterizing optimal stopping times for discrete-time ergodic Markov processes with discounted rewards. The theory differs from prior work by its view of per-stage and terminal reward functions as elements of a certain Hilbert space. In addition to a streamlined analysis establishing existence and uniqueness of a solution to Bellman's equation, this approach provides an elegant framework for the study of approximate solutions. In particular, the authors propose a stochastic approximation algorithm that tunes weights of a linear combination of basis functions in order to approximate a value function. They prove that this algorithm converges (almost surely) and that the limit of convergence has some desirable properties. The utility of the approximation method is illustrated via a computational case study involving the pricing of a path dependent financial derivative security that gives rise to an optimal stopping problem with a 100-dimensional state spacemore » « less
