Jiani Li, Waseem Abbas, Muddasir Shabbir, Xenofon Koutsoukos
 |
 |
In this paper, we study the resilient diffusion problem in a network of robots aiming to perform a task by optimizing a global cost function in a cooperative manner. In distributed diffusion, robots combine the information collected from their local neighbors and incorporate this aggregated information to update their states. If some robots are adversarial, this cooperation can disrupt the convergence of robots to the desired state. We propose a resilient aggregation rule based on the notion of centerpoint, which is a generalization of the median in the higher dimensional Euclidean space. Robots exchange their $d$-dimensional state vectors with neighbors. We show that if a normal robot implements the centerpoint-based aggregation rule and has $n$ neighbors, of which at most $\lceil\frac{n}{d+1}\rceil - 1$ are adversarial, then the aggregated state always lies in the convex hull of the states of the normal neighbors of the robot. Consequently, all normal robots implementing the distributed diffusion algorithm converge resiliently to the true target state. We also show that commonly used aggregation rules based on the coordinate-wise median and geometric median are, in fact, not resilient to certain attacks. We numerically evaluate our results on mobile multi-robot networks and demonstrate the cases where diffusion with the weighted average, coordinate-wise median, and geometric median-based aggregation rules fail to converge to the true target state, whereas diffusion with the centerpoint-based rule is resilient in the same scenario.
 | Start Time | End Time |
|---|---|---|
| 07/14 15:00 UTC | 07/14 17:00 UTC |
* Main comments Unfortunately, the theoretical analysis of the method is not as rigorous as the rest of the paper: - In the inline equation before eq. (8): It is not clear why $\frac{2\mu_l}{L}-\mu_l^2$ becomes $\mu_l^2$. This step is crucial for the proof of the main theoretical result of the paper, and it does not seem to be correct. - Section V.D: the authors seem to suggest that the proposed method is a particular case of DLMS, and so it inherits the same benefits in terms of MSD. However, the authors need to prove or cite a result showing that the relation between DLMS and non-cooperative LMS results holds also for time-varying weights (which is how the proposed algorithm falls into the DLMS category). - Lemma 1: in order to make the proof valid, the authors need to provide (either prove or refer to) a theorem stating that the center point is always in the convex hull of the points (this is rather simple, but it needs to be done for completeness). Also, Lemma 1 should be stated in its more generic (and powerful) form: for any subset of $\ceil{\frac{n}{d+1}}-1$ points, the centerpoint cannot be in their convex hull. This is because the centerpoint does not know which points are the Byzantine agents, so the result should be invariant to their choice. Finally, it would be nice if the authors could test the performance of the algorithm where the squared 2-norm in the cost in Section VI.A is substituted with an 1-norm; in this case the cost separates across coordinates, so the median-based algorithm should return to work robustly. Overall, the paper is based on an innovative idea, but it is not publishable in its current form due to the theoretical analysis. * Additional comments - Abstract: "optimizing global cost" should be "optimizing a global cost" - Page 3, column 2: "In one dimension, median" should be "In one dimension, the median" - Lemma 1: It seems that there should be some assumption on the minimum n. - Section V.C: - Property 1: the customary assumption of Lischitz continuity uses the distance between two arbitrary points (not just a single point and the origin), and links B and D. As it is, this definition is not clear (can B depend on w?), and it does not imply that the function is actually continuous (e.g., take a J which is a "staircase") - Property 2: the authors invoke co-coercivity of the function, which requires simple convexity (mu=0) - Page 5, column 1, first equation: \mu_l should be \mu_k - Eq (4), second line: the term containing \eta and \rho should have a plus sign instead of a minus sign. - Page 8, column 1: "sates" should be "states"
The paper has proposed an aggregation rule based on center points for distributed fusion for multi-robot systems in the presence of adversarial robots. Such center points can be achieved based only on local information available to each robot. The proposed method can guarantee the aggregated state always lie in the convex hull of the states of normal neighbors. Convergence analysis and numerical simulations are provided to validate the proposed method. While the whole paper looks very nice in general, especially in quality and clarity, the key idea to achieve a state in the convex hull of normal states is not new. There has recently been several other existing methods to achieve such a convex combination without knowing which state is malicious. To name a few, please refer to the followings: [1]. H. Mendes, M. Herlihy, N. Vaidya and V. Garg, Multidimensional agreement in byzantine systems, Distributed Computing, 28 (2015), 423–441 [2] H. Park and S. A. Hutchinson, Fault-tolerant rendezvous of multirobot systems, IEEE Transactions on Robotics, 33 (2017), 565–582. [3] L. Tseng and N. H. Vaidya, Asynchronous convex hull consensus in the presence of crash faults, in Proceedings of the 2014 ACM symposium on Principles of distributed computing, ACM, 2014, 396–405 [4]. X. Wang, S. Mou, S. Sundaram. A resilient convex combination for consensus-based distributed algorithms. Numerical Algebra, Control and Optimization. 269-281, 9(3), 2019. The authors could compare their methods with the above papers and further justify their contribution.
 |
 |
 |