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.
Mots-clés : distributed dynamical systems, coordination and cooperative control, geometric optimization, nonsmooth analysis, Voronoi partitions
@article{COCV_2005__11_4_691_0,
author = {Cort\'es, Jorge and Mart{\'\i}nez, Sonia and Bullo, Francesco},
title = {Spatially-distributed coverage optimization and control with limited-range interactions},
journal = {ESAIM: Control, Optimisation and Calculus of Variations},
pages = {691--719},
publisher = {EDP-Sciences},
volume = {11},
number = {4},
year = {2005},
doi = {10.1051/cocv:2005024},
mrnumber = {2167880},
zbl = {1080.90070},
language = {en},
url = {http://www.numdam.org/articles/10.1051/cocv:2005024/}
}
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 PY - 2005 SP - 691 EP - 719 VL - 11 IS - 4 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/cocv:2005024/ DO - 10.1051/cocv:2005024 LA - en ID - COCV_2005__11_4_691_0 ER -
%0 Journal Article %A Cortés, Jorge %A Martínez, Sonia %A Bullo, Francesco %T Spatially-distributed coverage optimization and control with limited-range interactions %J ESAIM: Control, Optimisation and Calculus of Variations %D 2005 %P 691-719 %V 11 %N 4 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/cocv:2005024/ %R 10.1051/cocv:2005024 %G en %F COCV_2005__11_4_691_0
Cortés, Jorge; Martínez, Sonia; Bullo, Francesco. Spatially-distributed coverage optimization and control with limited-range interactions. ESAIM: Control, Optimisation and Calculus of Variations, Tome 11 (2005) no. 4, pp. 691-719. doi : 10.1051/cocv:2005024. http://www.numdam.org/articles/10.1051/cocv:2005024/
[1] , Behavior-Based Robotics. Cambridge, Cambridge University Press (1998).
[2] , 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. | MR
[3] , The Elements of Integration and Lebesgue Measure, 1st edn. Wiley-Interscience (1995). | MR | Zbl
[4] , and, Computational Geometry: Algorithms and Applications. New York, Springer-Verlag (1997). | MR | Zbl
[5] and, Convex Optimization. Cambridge,Cambridge University Press (2004). | MR | Zbl
[6] and, A Mathematical Introduction to Fluid Mechanics. 3rd edn., Ser. Texts in Applied Mathematics. New York, Springer-Verlag 4 (1994). | Zbl
[7] and, Coordination and geometric optimization via distributed dynamical systems. SIAM J. Control Optim. (June 2004), to appear. | MR | Zbl
[8] ,, and, Coverage control for mobile sensing networks. IEEE Trans. Robotics Automat. 20 (2004) 243-255.
[9] , Graph Theory. 2nd edn., Ser. Graduate Texts in Mathematics. New York, Springer-Verlag 173 (2000). | MR | Zbl
[10] and, Eds., Facility Location: Applications and Theory. New York, Springer-Verlag (2001). | MR | Zbl
[11] , and, Centroidal Voronoi tessellations: applications and algorithms. SIAM Rev. 41 (1999) 637-676. | MR | Zbl
[12] and, Triangulating topological spaces. Internat. J. Comput. Geom. Appl. 7 (1997) 365-378. | MR | Zbl
[13] ,,, and, 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] and, Quantization. IEEE Trans. Inform. Theory 44 (1998) 2325-2383. Commemorative Issue 1948-1998. | MR | Zbl
[15] and, Optimization and Dynamical Systems. New York, Springer-Verlag (1994). | MR | Zbl
[16] , and, Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Trans. Automat. Control 48 (2003) 988-1001. | MR
[17] and, Relative neighborhood graphs and their relatives. Proc. of the IEEE 80 (1992) 1502-1517.
[18] , Nonlinear Systems. Englewood Cliffs, Prentice Hall (1995). | Zbl
[19] , The Stability and Control of Discrete Processes. Ser. Applied Mathematical Sciences. New York, Springer-Verlag 62 (1986). | MR | Zbl
[20] , Algorithmic, geometric and graphs issues in wireless networks. Wireless Communications and Mobile Computing 3 (2003) 119-140.
[21] , Linear and Nonlinear Programming. Reading, Addison-Wesley (1984). | Zbl
[22] , and, Formations of vehicles in cyclic pursuit. IEEE Trans. Automat. Control 49 (2004) 1963-1974. | MR
[23] ,, and, Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. 2nd edn., Ser. Wiley Series in Probability and Statistics. New York, John Wiley & Sons (2000). | MR | Zbl
[24] and, Locational optimization problems solved through Voronoi diagrams. European J. Oper. Res. 98 (1997) 445-56. | Zbl
[25] , Dynamical aspects of animal grouping: swarms, schools, flocks and herds. Adv. Biophysics 22 (1986) 1-94.
[26] and, Consensus problems in networks of agents with switching topology and time-delays. IEEE Trans. Automat. Control 49 (2004) 1520-1533. | MR
[27] , Biomimicry for Optimization, Control, and Automation. New York, Springer-Verlag (2004). | Zbl
[28] , Flocks, herds, and schools: A distributed behavioral model. Computer Graphics 21 (1987) 25-34.
[29] , Deterministic annealing for clustering, compression, classification, regression, and related optimization problems. Proc. of the IEEE 80 (1998) 2210-2239.
[30] , Nonlinear systems: discrete-time stability analysis. Lecture Notes, University of California at Santa Barbara (2004).
Cité par Sources :
