Spatially-distributed coverage optimization and control with limited-range interactions

Jorge Cortés; Sonia Martínez; Francesco Bullo

ESAIM: Control, Optimisation and Calculus of Variations (2010)

  • Volume: 11, Issue: 4, page 691-719
  • ISSN: 1292-8119

Abstract

top
This paper presents coordination algorithms for groups of mobile agents performing deployment and coverage tasks. As an important modeling constraint, we assume that each mobile agent has a limited sensing or communication radius.
Based on the geometry of Voronoi partitions and proximity graphs, we analyze a class of aggregate objective functions and propose coverage algorithms in continuous and discrete time.
These algorithms have convergence guarantees and are spatially distributed with respect to appropriate proximity graphs. Numerical simulations illustrate the results.

How to cite

top

Cortés, Jorge, Martínez, Sonia, and Bullo, Francesco. "Spatially-distributed coverage optimization and control with limited-range interactions." ESAIM: Control, Optimisation and Calculus of Variations 11.4 (2010): 691-719. <http://eudml.org/doc/90783>.

@article{Cortés2010,
abstract = { This paper presents coordination algorithms for groups of mobile agents performing deployment and coverage tasks. As an important modeling constraint, we assume that each mobile agent has a limited sensing or communication radius.
Based on the geometry of Voronoi partitions and proximity graphs, we analyze a class of aggregate objective functions and propose coverage algorithms in continuous and discrete time.
These algorithms have convergence guarantees and are spatially distributed with respect to appropriate proximity graphs. Numerical simulations illustrate the results. },
author = {Cortés, Jorge, Martínez, Sonia, Bullo, Francesco},
journal = {ESAIM: Control, Optimisation and Calculus of Variations},
keywords = {Distributed dynamical systems; coordination and cooperative control; geometric optimization; nonsmooth analysis; Voronoi partitions.; coordination and cooperative control; Voronoi partitions},
language = {eng},
month = {3},
number = {4},
pages = {691-719},
publisher = {EDP Sciences},
title = {Spatially-distributed coverage optimization and control with limited-range interactions},
url = {http://eudml.org/doc/90783},
volume = {11},
year = {2010},
}

TY - JOUR
AU - Cortés, Jorge
AU - Martínez, Sonia
AU - Bullo, Francesco
TI - Spatially-distributed coverage optimization and control with limited-range interactions
JO - ESAIM: Control, Optimisation and Calculus of Variations
DA - 2010/3//
PB - EDP Sciences
VL - 11
IS - 4
SP - 691
EP - 719
AB - This paper presents coordination algorithms for groups of mobile agents performing deployment and coverage tasks. As an important modeling constraint, we assume that each mobile agent has a limited sensing or communication radius.
Based on the geometry of Voronoi partitions and proximity graphs, we analyze a class of aggregate objective functions and propose coverage algorithms in continuous and discrete time.
These algorithms have convergence guarantees and are spatially distributed with respect to appropriate proximity graphs. Numerical simulations illustrate the results.
LA - eng
KW - Distributed dynamical systems; coordination and cooperative control; geometric optimization; nonsmooth analysis; Voronoi partitions.; coordination and cooperative control; Voronoi partitions
UR - http://eudml.org/doc/90783
ER -

References

top
  1. R.C. Arkin, Behavior-Based Robotics. Cambridge, Cambridge University Press (1998).  
  2. Y. Asami, A note on the derivation of the first and second derivative of objective functions in geographical optimization problems. J. Faculty Engineering, The University of Tokio (B)XLI (1991) 1–13.  
  3. R.G. Bartle, The Elements of Integration and Lebesgue Measure, 1st edn. Wiley-Interscience (1995).  
  4. M. de Berg, M. van Kreveld and M. Overmars, Computational Geometry: Algorithms and Applications. New York, Springer-Verlag (1997).  
  5. S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge,Cambridge University Press (2004).  
  6. A.J. Chorin and J.E. Marsden, A Mathematical Introduction to Fluid Mechanics. 3rd edn., Ser. Texts in Applied Mathematics. New York, Springer-Verlag 4 (1994).  
  7. J. Cortés and F. Bullo, Coordination and geometric optimization via distributed dynamical systems. SIAM J. Control Optim. (June 2004), to appear.  
  8. J. Cortés, S. Martínez, T. Karatas and F. Bullo, Coverage control for mobile sensing networks. IEEE Trans. Robotics Automat.20 (2004) 243–255.  
  9. R. Diestel, Graph Theory. 2nd edn., Ser. Graduate Texts in Mathematics. New York, Springer-Verlag 173 (2000).  
  10. Z. Drezner and H.W. Hamacher, Eds., Facility Location: Applications and Theory. New York, Springer-Verlag (2001).  
  11. Q. Du, V. Faber and M. Gunzburger, Centroidal Voronoi tessellations: applications and algorithms. SIAM Rev.41 (1999) 637–676.  
  12. H. Edelsbrunner and N.R. Shah, Triangulating topological spaces. Internat. J. Comput. Geom. Appl.7 (1997) 365–378.  
  13. J. Gao, L.J. Guibas, J. Hershberger, L. Zhang and A. Zhu, Geometric spanner for routing in mobile networks, in ACM International Symposium on Mobile Ad-Hoc Networking & Computing (MobiHoc). Long Beach, CA (Oct. 2001) 45–55.  
  14. R.M. Gray and D.L. Neuhoff, Quantization. IEEE Trans. Inform. Theory44 (1998) 2325–2383. Commemorative Issue 1948–1998.  
  15. U. Helmke and J. Moore, Optimization and Dynamical Systems. New York, Springer-Verlag (1994).  
  16. A. Jadbabaie, J. Lin and A.S. Morse, Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Trans. Automat. Control48 (2003) 988–1001.  
  17. J.W. Jaromczyk and G.T. Toussaint, Relative neighborhood graphs and their relatives. Proc. of the IEEE80 (1992) 1502–1517.  
  18. H.K. Khalil, Nonlinear Systems. Englewood Cliffs, Prentice Hall (1995).  
  19. J.P. LaSalle, The Stability and Control of Discrete Processes. Ser. Applied Mathematical Sciences. New York, Springer-Verlag 62 (1986).  
  20. X.-Y. Li, Algorithmic, geometric and graphs issues in wireless networks. Wireless Communications and Mobile Computing3 (2003) 119–140.  
  21. D.G. Luenberger, Linear and Nonlinear Programming. Reading, Addison-Wesley (1984).  
  22. J. Marshall, M. Broucke and B. Francis, Formations of vehicles in cyclic pursuit. IEEE Trans. Automat. Control49 (2004) 1963–1974.  
  23. A. Okabe, B. Boots, K. Sugihara and S.N. Chiu, Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. 2nd edn., Ser. Wiley Series in Probability and Statistics. New York, John Wiley & Sons (2000).  
  24. A. Okabe and A. Suzuki, Locational optimization problems solved through Voronoi diagrams. European J. Oper. Res.98 (1997) 445–56.  
  25. A. Okubo, Dynamical aspects of animal grouping: swarms, schools, flocks and herds. Adv. Biophysics22 (1986) 1–94.  
  26. R. Olfati-Saber and R.M. Murray, Consensus problems in networks of agents with switching topology and time-delays. IEEE Trans. Automat. Control49 (2004) 1520–1533.  
  27. K.M. Passino, Biomimicry for Optimization, Control, and Automation. New York, Springer-Verlag (2004).  
  28. C.W. Reynolds, Flocks, herds, and schools: A distributed behavioral model. Computer Graphics21 (1987) 25–34.  
  29. K. Rose, Deterministic annealing for clustering, compression, classification, regression, and related optimization problems. Proc. of the IEEE80 (1998) 2210–2239.  
  30. A.R. Teel, Nonlinear systems: discrete-time stability analysis. Lecture Notes, University of California at Santa Barbara (2004).  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.