| Titre : | On synchronous robotic networks—Part II : time complexity of rendezvous and deployment algorithms (2008) |
| Titre original : | Sur les réseaux robotiques synchrones Partie II: complexité de temps des algorithmes de rendez-vous et de déploiement |
| Auteurs : | Sonia Martinez, Auteur ; Cortés, Jorge, Auteur ; Bullo, Francesco, Auteur ; Frazzoli, Emilio, Auteur |
| Type de document : | Article : texte imprimé |
| Dans : | IEEE transactions on automatic control (Vol. 52 N°12, Decembre 2007) |
| Article en page(s) : | 2214-2226 p. |
| Note générale : | Automatique |
| Langues : | Anglais |
| Index. décimale : | 629.8 |
| Tags : | Circumcenter and centroid laws Coordination algorithms Deployment Rendezvous Robotic networks Time complexity et lois centroïdes Algorithmes de coordination Déploiement Réseaux robotiques Complexité temps |
| Résumé : |
This paper analyzes a number of basic coordination algorithms running on synchronous robotic networks. We provide upper and lower bounds on the time complexity of the move-toward-average and circumcenter laws, both achieving rendezvous, and of the centroid law, achieving deployment over a region of interest. The results are derived via novel analysis methods, including a set of results on the convergence rates of linear dynamical systems defined by tridiagonal Toeplitz and circulant matrices.
Ce document analyse un certain nombre d'algorithmes de base de coordination fonctionnant sur les réseaux robotiques synchrones. Nous fournissons les limites supérieures et inférieures sur la complexité de temps des lois déplacer-vers-moyennes et de circumcenter, toutes les deux qui réalisent des rendez-vous, et de la loi centroïde, réalisant le déploiement au-dessus d'une région d'intérêt. Les résultats sont dérivés par l'intermédiaire des méthodes d'analyse originales, y compris un ensemble de résultats sur les taux de convergence des systèmes dynamiques linéaires définis par tridiagonal Toeplitz et matrices circulant. |
| DEWEY : | 629.8 |
| ISSN : | 0018-9286 |
| RAMEAU : | Algorithms |
| En ligne : | soniamd@ucsd.edu, cortes@ucsd.edu, bullo@engineering.ucsb.edu, frazzoli@mit.edu |
