Decentralized algorithms for optimally rigid network constructions

Attilio Priolo, Ryan K. Williams, Andrea Gasparri, Gaurav S. Sukhatme

Abstract

In this paper, we address the construction of optimally rigid networks that minimize an edge-weighted objective function over a planar graph. We propose two auction-based algorithms to solve this problem in a fully decentralized way. The first approach finds an optimal solution at the cost of high communication complexity; the second approach provides a sub-optimal solution while reducing the computational burden according to a sliding mode parameter ζ, yielding a tradeoff between complexity and optimality. A theoretical characterization of the optimality of the first algorithm is provided, and a closed form for the maximum gap between the optimal solution and the sub-optimal solution is also given. Simulation results are presented to corroborate the theoretical findings.
BibTeX
@inproceedings{priolo2014decentralized,
  author = {Attilio Priolo and Ryan K. Williams and Andrea Gasparri and Gaurav S. Sukhatme},
  title = {{Decentralized algorithms for optimally rigid network constructions}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2014},
  doi = {10.1109/icra.2014.6907593},
}

Loading related content...

Figure