This paper investigates control laws allowing mobile, autonomous agents to optimally position themselves on the line for distributed sensing in a nonuniform field. We show that a simple static control law, based only on local measurements of the field by each agent, drives the agents close to the optimal positions after the agents execute in parallel a number of sensing movement computation rounds that is essentially quadratic in the number of agents. Further, we exhibit a dynamic control law which, under slightly stronger assumptions on the capabilities and knowledge of each agent, drives the agents close to the optimal positions after the agents execute in parallel a number of sensing communication computation movement rounds that is essentially linear in the number of agents. Crucially, both algorithms are fully distributed and robust to unpredictable loss and addition of agents.
In @cite_0 , uniform coverage algorithms are derived using Voronoi cells and gradient laws for distributed dynamical systems. Uniform constrained coverage control is addressed in @cite_39 where the constraint is a minimum limit on node degree. Virtual potentials enable repulsion between agents to maximize coverage and attraction between agents to enforce the constraint. In @cite_10 , gradient control laws are proposed to move sensors to a configuration that maximizes expected event detection frequency. Local rules are enforced by defining a sensing radius for each agent, which also makes computations simpler. The approach is demonstrated for a nonuniform but symmetric density field with and without communication constraints. Further results for distributed coverage control are presented in @cite_37 for a coverage metric defined in terms of the Euclidean metric with a weighting factor that allows for nonuniformity. As in @cite_37 , the methodology makes use of Voronoi cells and Lloyd descent algorithms. The papers @cite_15 @cite_25 identified a class of non-convex regions for which the coverage problem may be solved by reduction to the convex case through a well-chosen transformation of the region. The papers @cite_36 @cite_16 explored an optimization-based approach to some complex variations of the covering problem.
@cite_37 @cite_36 @cite_39 @cite_0 @cite_15 @cite_16 @cite_10 @cite_25
2167485994 1984648987 2153239294 2007403280 2042398697 2156561078 2135792961 2084690910
This paper describes decentralized control laws for the coordination of multiple vehicles performing spatially distributed tasks. The control laws are based on a gradient descent scheme applied to a class of decentralized utility functions that encode optimal coverage and sensing policies. These utility functions are studied in geographical optimization problems and they arise naturally in vector quantization and in sensor allocation tasks. The approach exploits the computational geometry of spatial structures such as Voronoi diagrams. In this paper, we consider a class of dynamic vehicle routing problems, in which a number of mobile agents in the plane must visit target points generated over time by a stochastic process. It is desired to design motion coordination strategies in order to minimize the expected time between the appearance of a target point and the time it is visited by one of the agents. We propose control strategies that, while making minimal or no assumptions on communications between agents, provide the same level of steady-state performance achieved by the best-known decentralized strategies. In other words, we demonstrate that inter-agent communication does not improve the efficiency of such systems, but merely affects the rate of convergence to the steady state. Furthermore, the proposed strategies do not rely on the knowledge of the details of the underlying stochastic process. Copyright © 2007 John Wiley & Sons, Ltd. We consider the problem of self-deployment of a mobile sensor network. We are interested in a deployment strategy that maximizes the area coverage of the network with the constraint that each of the nodes has at least K neighbors, where K is a user-specified parameter. We propose an algorithm based on artificial potential fields which is distributed, scalable and does not require a prior map of the environment. Simulations establish that the resulting networks have the required degree with a high probability, are well connected and achieve good coverage. We present analytical results for the coverage achievable by uniform random and symmetrically tiled network configurations and use these to evaluate the performance of our algorithm. This paper discusses dynamical systems for disk-covering and sphere-packing problems. We present facility location functions from geometric optimization and characterize their differentiable properties. We design and analyze a collection of distributed control laws that are related to nonsmooth gradient systems. The resulting dynamical systems promise to be of use in coordination problems for networked robots; in this setting the distributed control laws correspond to local interactions between the robots. The technical approach relies on concepts from computational geometry, nonsmooth analysis, and the dynamical system approach to algorithms. We present a framework for extending coverage algorithms from convex to nonconvex domains. We are particularly interested in coverage in the presence of obstacles, that is domains that contain holes. We identify a class of connected regions in Ropf2 than can be mapped through a diffeomorphism to an almost convex region in Ropf2 - a convex region from which a finite (possibly empty) set of points has been subtracted. The transformation allows us to solve the coverage problem using the approach of , and obtain the solution of the original problem through inverse transformation. We provide a formal analysis of the approach and demonstrate its effectiveness through simulations. We conclude the paper with a discussion on possible extensions of the work that we are currently undertaking. In this paper we address the problem of dynamic coverage control of a convex polygonal region in the plane using N agents with bounded velocities and finite instantaneous area of coverage. The proposed coverage algorithm guarantees finite- time search of the region, does not depend on gradient-based methods, and can be carried out by the agents in a distributed fashion. We provide an upper bound on the completion time as well as the number of messages that need to be exchanged by the agents. A simulation is provided to illustrate the algorithm. We present a distributed coverage control scheme for cooperating mobile sensor networks. The mission space is modeled using a density function representing the frequency of random events taking place, with mobile sensors operating over a limited range defined by a probabilistic model. A gradient-based algorithm is designed requiring local information at each sensor and maximizing the joint detection probabilities of random events. We also incorporate communication costs into the coverage control problem, viewing the sensor network as a multi-source, single-basestation data collection network. Communication cost is modeled as the power consumption needed to deliver collected data from sensor nodes, thus trading off sensing coverage and communication cost. The control Scheme is tested in a simulation environment to illustrate its adaptive, distributed, and asynchronous properties. The paper describes a framework for solving the coverage problem for a class of non-convex domains. In we have shown how a diffeomorphism can be used to transform a non-convex coverage problem to a convex one to which the Lloyd?s algorithm can be applied. In this paper we show how a diffeomorphism can be constructed for convex regions with obstacles in its interior, so that the solution of the transformed problem yields the solution of the original non-convex problem. As part of this investigation we also identify stationary points of the Lloyd?s algorithm in non-convex domains. We provide the formal analysis of the approach and demonstrate its effectiveness through simulations.