Low-cost mini-drones with advanced sensing and maneuverability enable a new class of intelligent sensing systems. This trend motivated several research efforts to employ drones as standalone systems or to assist legacy deployments. However, several fundamental challenges remain unsolved including: 1) Adequate coverage of sizable targets; 2) Target orientation that render coverage effective only from certain view points; 3) Occlusion by elements in the environment, including other targets. In this paper, we present Argus, a system that provides coverage of wide and oriented targets, using camera-mounted drones, taking into account the challenges stated above. Argus relies on a geometric model that captures both target shapes and coverage constraints. With drones being the scarcest resource in Argus, we study the problem of minimizing the number of drones required to cover a set of such targets and derive a best-possible approximation algorithm. Furthermore, we present a sampling heuristic that yields a comparable performance, yet is up to 100x faster than the approximation algorithm. We build a prototype of Argus to demonstrate and evaluate the proposed coverage algorithms as part of a complete autonomous surveillance system. We evaluate the proposed algorithms using simulations to compare their performance at scale under various conditions. Finally, we present extensions and discuss open problems related to the studied problem.
The goal of area coverage algorithms is to detect any activity of interest within a certain area in a sensor network deployment, or to ensure all clients can communicate within an area for wireless communication. Several approaches to area coverage have been studied including static randomly deployed sensors @cite_32 and strategically placed mobile sensors @cite_62 using either isotropic @cite_60 or anisotropic sensors @cite_40 . Full-view coverage algorithms are another example of area coverage algorithms. Target coverage algorithms are used to cover a number of targets within an area, and were studied in randomly deployed sensors @cite_51 @cite_29 @cite_57 , or strategically placed directional sensors or antennas @cite_4 @cite_1 @cite_38 . Target coverage under quality constraints using randomly placed Pan-Tilt-Zoom (PTZ) cameras was shown to be NP-hard and a 2-approximation algorithm was presented @cite_29 . A 3-approximation algorithm was developed for antenna placement to cover targets such that the bandwidth demand on each antenna stays within a certain limit @cite_4 .
@cite_38 @cite_62 @cite_4 @cite_60 @cite_29 @cite_1 @cite_32 @cite_57 @cite_40 @cite_51
2058040501 2539096940 2091629531 2108662033 1980394886 1992859463 2163807729
Recent advancements in manufacturing low-cost wireless battery operated cameras has made their application in Wireless Video Sensor Networks (WVSN) increasingly more feasible and affordable. The application of robotic sensing agents equipped with cameras in WVSNs, seems particularly promising in performing coverage tasks for ad hoc surveillance. Their application in this context can be specifically useful for surveying areas with little to no available or affordable infrastructure, or where quick deployment is necessary. In this paper, we address the target coverage problem for finding the minimum number of cameras, their placement, and orientation to cover arbitrarily located targets in an area of interest. We propose a computationally light-weight heuristic, where the number of used mobile cameras is close to those found by near-optimal algorithms. Specifically, we address this problem for non-uniform target distributions that naturally form clusters. Having light-weight heuristics will be particularly useful when the application is required to adapt to target mobility and or is implemented in embedded systems. Our simulation study shows that when clusters are sufficiently separated, the required number of cameras found by our proposed method is very close to those acquired by the near-optimal algorithm, whereas the computational complexity of our algorithm is about ten times less. We also deploy our algorithm on a drone testbed using off-the-shelf components to verify its feasibility. In this paper, we address the problem of persistently covering an environment with a group of mobile robots. In contrast to traditional coverage, in our scenario the coverage level of the environment is always changing. For this reason, the robots have to continually move to maintain a desired coverage level. In this context, our contribution is a complete approach to the problem, including distributed estimation of the coverage and control of the motion of the robots. First, we present an algorithm that allows every robot to estimate the global coverage function only with local information. We pay special attention to the characterization of the algorithm, establishing bounds on the estimation error, and we demonstrate that the algorithm guarantees a perfect estimation in particular areas. Second, we introduce a new function to determine the possible improvement of the coverage at each point of the environment. Upon this metric, we build a motion control strategy that drives the robots to the points of the highest improvement while following the direction of the gradient of the function. Finally, we simulate the proposal to test its correctness and performance. Motivated by the widespread proliferation of wireless networks employing directional antennas, we study some capacitated covering problems arising in these networks. Geometrically, the area covered by a directional antenna with parameters α,ρ,r is a set of points with polar coordinates (r,θ) such that r ≤ r and α ≤ θ ≤ α + ρ. Given a set of customers, their positions on the plane and their bandwidth demands, the capacitated covering problem considered here is to cover all the customers with the minimum number of directional antennas such that the demands of customers assigned to an antenna stays within a bound. We consider two settings of this capacitated cover problem arising in wireless networks. In the first setting where the antennas have variable angular range, we present an approximation algorithm with ratio 3. In the setting where the angular range of antennas is fixed, we improve this approximation ratio to 1.5. These results also apply for a related problem of bin packing with deadlines. In this problem we are are given a set of items, each with a weight, arrival time and deadline, and we want to pack each item into a bin after it arrives but before its deadline. The objective is to minimize the number of bins used. We present a 3-approximation algorithm for this problem, and 1.5-approximation algorithm for the special case when each difference between a deadline and the corresponding arrival time is the same. Distributed algorithms for (re)configuring mobile sensors to cover a given area are important for autonomous multi-robot operations in application areas such as surveillance and environmental monitoring. Depending on the assumptions about the choice of the environment, the sensor models, the coverage metric, and the motion models of sensor nodes, there are different versions of the problem that have been formulated and studied. In this paper, we consider a system of holonomic mobile robots equipped with anisotropic sensors (e.g., limited field of view cameras) that are required to cover a polygonal region with polygonal obstacles to detect interesting events. We assume a given probability distribution of the events over a region. Motivated by scenarios where the sensing performance not only depends on the resolution of sensing but also on the relative orientation between the sensing axis and the event, we assume that the probability of detection of an event depends on both sensing parameters and the orientation of observation. We present a distributed gradient-ascent algorithm for reconfiguring the system of mobile robots so that the joint probability of detection of events over the whole region is maximized (i.e., positioning the mobile robots and determining their sensor parameters). As an example case study, we use a system of mobile robots equipped with limited field of view cameras with pan and zoom capabilities. We present simulation results demonstrating the performance of our algorithm. Wireless sensor and actuator networks have been extensively deployed for enhancing industrial control processes and supply-chains, and many forms of surveillance and environmental monitoring. The availability of low-cost mobile robots equipped with a variety of sensors in addition to communication and computational capabilities makes them particularly promising in target coverage tasks for ad hoc surveillance, where quick, low-cost or non-lasting visual sensing solutions are required, e.g. in border protection and disaster recovery. In this paper, we consider the problem of low complexity placement and orientation of mobile cameras to cover arbitrary targets. We tackle this problem by clustering proximal targets, while calculating estimating the camera location direction for each cluster separately through our cover-set coverage method. Our proposed solutions provide extremely computationally efficient heuristics with only a small increase in number of cameras used, and a small decrease in number of covered targets. Multiple cameras are used to track targets moving amongst obstacles. Surveillance video streamed from a top-view camera is processed to control the orientation of multiple pan-tilt-zoom cameras to cover as many targets as possible at high resolutions. The problem of maximizing the number of covered targets with a set of cameras has been shown to be computationally expensive and hence, several approximations have been suggested in the literature. We develop our own ones, compare them to some existing approaches by extensive simulation and show their superiority. Our new heuristics make an attempt at continuous panning that is needed when moving to real world experimentation to achieve seamless target tracking. We study a novel “coverage by directional sensors” problem with tunable orientations on a set of discrete targets. We propose a Maximum Coverage with Minimum Sensors (MCMS) problem in which coverage in terms of the number of targets to be covered is maximized whereas the number of sensors to be activated is minimized. We present its exact Integer Linear Programming (ILP) formulation and an approximate (but computationally efficient) centralized greedy algorithm (CGA) solution. These centralized solutions are used as baselines for comparison. Then we provide a distributed greedy algorithm (DGA) solution. By incorporating a measure of the sensors residual energy into DGA, we further develop a Sensing Neighborhood Cooperative Sleeping (SNCS) protocol which performs adaptive scheduling on a larger time scale. Finally, we evaluate the properties of the proposed solutions and protocols in terms of providing coverage and maximizing network lifetime through extensive simulations. Moreover, for the case of circular coverage, we compare against the best known existing coverage algorithm.