We consider the problem of multi-robot sensor coverage, which deals with deploying a multi-robot team in an environment and optimizing the sensing quality of the overall environment. As real-world environments involve a variety of sensory information, and individual robots are limited in their available number of sensors, successful multi-robot sensor coverage requires the deployment of robots in such a way that each individual team member’s sensing quality is maximized. Additionally, because individual robots have varying complements of sensors and both robots and sensors can fail, robots must be able to adapt and adjust how they value each sensing capability in order to obtain the most complete view of the environment, even through changes in team composition. We introduce a novel formulation for sensor coverage by multi-robot teams with heterogeneous sensing capabilities that maximizes each robot's sensing quality, balancing the varying sensing capabilities of individual robots based on the overall team composition. We propose a solution based on regularized optimization that uses sparsity-inducing terms to ensure a robot team focuses on all possible event types, and which we show is proven to converge to the optimal solution. Through extensive simulation, we show that our approach is able to effectively deploy a multi-robot team to maximize the sensing quality of an environment, responding to failures in the multi-robot team more robustly than non-adaptive approaches.
more »
« less
Sensor Placement for Globally Optimal Coverage of 3D-Embedded Surfaces
We carry out a structural and algorithmic study
of a mobile sensor coverage optimization problem targeting 2D
surfaces embedded in a 3D workspace. The investigated settings
model multiple important applications including camera net-
work deployment for surveillance, geological monitoring/survey
of 3D terrains, and UVC-based surface disinfection for the
prevention of the spread of disease agents (e.g., SARS-CoV-
2). Under a unified general “sensor coverage” problem, three
concrete formulations are examined, focusing on optimizing
visibility, single-best coverage quality, and cumulative quality,
respectively. After demonstrating the computational intractabil-
ity of all these formulations, we describe approximation schemes
and mathematical programming models for near-optimally
solving them. The effectiveness of our methods is thoroughly
evaluated under realistic and practical scenarios.
more »
« less
- PAR ID:
- 10219063
- Date Published:
- Journal Name:
- IEEE International Conference on Robotics and Automation
- ISSN:
- 1049-3492
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)Collaborative sensing of spatio-temporal events/processes is at the basis of many applications including e.g., spectrum and environmental monitoring, and self-driving cars. A system leveraging spatially distributed possibly airborn sensing nodes can in principle deliver better coverage as well as possibly redundant views of the observed processes. This paper focuses on modeling, characterising and quantifying the benefits of optimal sensor activation/scanning policies in resource constrained settings, e.g., constraints tied to energy expenditures or the scanning capabilities of nodes. Under a natural model for the process being observed we show that a periodic sensor activation policy is optimal, and characterize the relative phases of such policies via an optimization problem capturing knowledge of the sensor geometry, sensor coverage sets, and spatio-temporal intensity and event durations. Numerical and simulation results for simple different sensor geometries exhibit how performance depends on the underlying processes. We also study the gap between optimal and randomized policies and how it scales with the density of sensors and resource constraints.more » « less
-
Sensor coverage is the critical multi-robot problem of maximizing the detection of events in an environment through the deployment of multiple robots. Large multi-robot systems are often composed of simple robots that are typically not equipped with a complete set of sensors, so teams with comprehensive sensing abilities are required to properly cover an area. Robots also exhibit multiple forms of relationships (e.g., communication connections or spatial distribution) that need to be considered when assigning robot teams for sensor coverage. To address this problem, in this paper we introduce a novel formulation of sensor coverage by multi-robot systems with heterogeneous relationships as a graph representation learning problem. We propose a principled approach based on the mathematical framework of regularized optimization to learn a unified representation of the multi-robot system from the graphs describing the heterogeneous relationships and to identify the learned representation’s underlying structure in order to assign the robots to teams. To evaluate the proposed approach, we conduct extensive experiments on simulated multi-robot systems and a physical multi-robot system as a case study, demonstrating that our approach is able to effectively assign teams for heterogeneous multi-robot sensor coverage.more » « less
-
This paper addresses the problem of generating coverage paths-that is, paths that pass within some sensor footprint of every point in an environment-for vehicles with Dubins motion constraints. We extend previous work that solves this coverage problem as a traveling salesman problem (TSP) by introducing a practical heuristic algorithm to reduce runtime while maintaining near-optimal path length. Furthermore, we show that generating an optimal coverage path is NP-hard by reducing from the Exact Cover problem, which provides justification for our algorithm's conversion of Dubins coverage instances to TSP instances. Extensive experiments demonstrate that the algorithm does indeed produce length paths comparable to optimal in significantly less time.more » « less
-
The Glimpse.3D is a body-worn camera that captures, processes, stores, and transmits 3D visual information of a real-world environment using a low cost camera-based sensor system that is constrained by its limited processing capability, storage, and battery life. The 3D content is viewed on a mobile device such as a smartphone or a virtual reality headset. This system can be used in applications such as capturing and sharing 3D content in the social media, training people in different professions, and post-facto analysis of an event. Glimpse.3D uses off-the-shelf hardware and standard computer vision algorithms. Its novelty lies in the ability to optimally control camera data acquisition and processing stages to guarantee the desired quality of captured information and battery life. The design of the controller is based on extensive measurements and modeling of the relationships between the linear and angular motion of a body-worn camera and the quality of generated 3D point clouds as well as the battery life of the system. To achieve this, we 1) devise a new metric to quantify the quality of generated 3D point clouds, 2) formulate an optimization problem to find an optimal trigger point for the camera system that prolongs its battery life while maximizing the quality of captured 3D environment, and 3) make the model adaptive so that the system evolves and its performance improves over time.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
