摘要: |
This paper investigates consensus of flocks consisting of $n$ autonomous agents in the plane, where each agent has the same constant moving speed $v_n$ and updates its heading by the average value of the $k_n$ nearest agents from it, with $v_n$ and $k_n$ being two prescribed parameters depending on $n$. Such a topological interaction rule is referred to as $k_n$-nearest-neighbors rule, which has been validated for a class of birds by biologists and verified to be robust with respect to disturbances. A theoretical analysis will be presented for this flocking model under a random framework with large population, but without imposing any {\it a priori} connectivity assumptions. We will show that the minimum number of $k_n$ needed for consensus is of the order ${\rm O}(\log n)$ in a certain sense. To be precise, there exist two constants $C_1>C_2>0$ such that, if $k_n > C_1\log n$, then the flocking model will achieve consensus for any initial headings with high probability, provided that the speed $v_n$ is suitably small. On the other hand, if $k_n
|
关键词: $k$-nearest-neighbor, consensus, topological interaction, random geometric graph |
DOI: |
|
基金项目:This work was supported by the National Natural Science Foundation of China (No. 91427304, 61673373, 11688101), the National Key Basic Research Program of China (973 program) (No. 2014CB845301/2/3), and the Leading Research Projects of Chinese Academy of Sciences (No. QYZDJ-SSW-JSC003). |
|
On the minimum number of neighbors needed for consensus of flocks |
C. Chen,G. Chen,L. Guo |
(Noah's Ark Laboratory, 2012 Lab, Huawei Technologies Co. Ltd, Beijing 100085, China;LSC & NCMIS, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China) |
Abstract: |
This paper investigates consensus of flocks consisting of $n$ autonomous agents in the plane, where each agent has the same constant moving speed $v_n$ and updates its heading by the average value of the $k_n$ nearest agents from it, with $v_n$ and $k_n$ being two prescribed parameters depending on $n$. Such a topological interaction rule is referred to as $k_n$-nearest-neighbors rule, which has been validated for a class of birds by biologists and verified to be robust with respect to disturbances. A theoretical analysis will be presented for this flocking model under a random framework with large population, but without imposing any {\it a priori} connectivity assumptions. We will show that the minimum number of $k_n$ needed for consensus is of the order ${\rm O}(\log n)$ in a certain sense. To be precise, there exist two constants $C_1>C_2>0$ such that, if $k_n > C_1\log n$, then the flocking model will achieve consensus for any initial headings with high probability, provided that the speed $v_n$ is suitably small. On the other hand, if $k_n
|
Key words: $k$-nearest-neighbor, consensus, topological interaction, random geometric graph |