Consensus Algorithms¶
Consensus¶
- class disropt.algorithms.consensus.Consensus(agent, initial_condition, enable_log=False)[source]¶
Bases:
disropt.algorithms.algorithm.AlgorithmConsensus Algorithm [OlSa07]
From the perspective of agent \(i\) the algorithm works as follows. For \(k=0,1,\dots\)
\[x_i^{k+1} = \sum_{j=1}^N w_{ij} x_j^k\]where \(x_i\in\mathbb{R}^n\). The weight matrix \(W=[w_{ij}]\) should be doubly-stochastic in order to have convergence to the average of the local initial conditions. If \(W\) is row-stochastic convergence is still attained but at a different point. Other type of matrices can be used, but convergence is not guaranteed. Also time-varying graphs can be adopted.
- Parameters
agent (Agent) – agent to execute the algorithm
initial_condition (numpy.ndarray) – initial condition
enable_log (bool) – True for enabling log
- x0¶
initial condition
- Type
- x¶
current value of the local solution
- Type
AsynchronousConsensus¶
- class disropt.algorithms.consensus.AsynchronousConsensus(agent, initial_condition, enable_log=False, force_sleep=False, maximum_sleep=0.01, sleep_type='random', force_computation_time=False, maximum_computation_time=0.01, computation_time_type='random', force_unreliable_links=False, link_failure_probability=0)[source]¶
Bases:
disropt.algorithms.algorithm.AlgorithmAsynchronous Consensus Algorithm
From the perspective of agent \(i\) the algorithm works as follows. When agent \(i\) gets awake it updates its local solution as
\[x_i \gets \sum_{j\in\mathcal{N}_i} w_{ij} x_{j\mid i}\]where \(\mathcal{N}_i\) is the current set of in-neighbors and \(x_{j\mid i},j\in\mathcal{N}_i\) is the local copy of \(x_j\) available at node \(i\) (which can be outdated, due to asynchrony, computation time and link failures).
- Parameters
agent (
Agent) – agent to execute the algorithminitial_condition (
ndarray) – initial conditionenable_log (
bool) – True for enabling log. Defaults to False.force_sleep (
bool) – True if one wanst to force sleep after the computation phase. Defaults to False.maximum_sleep (
float) – Maximum allowed sleep. Defaults to 0.01.sleep_type (
str) – Type of sleep time(“constant”, “random”). Defaults to “random”.force_computation_time (
bool) – True if one want sto force length computation phase. Defaults to False.maximum_computation_time (
float) – Maximum allowed computation time. Defaults to 0.01.computation_time_type (
str) – Type of computation time (“constant”, “random”). Defaults to “random”.force_unreliable_links (
bool) – True if one wants to force unreliable links. Defaults to False.link_failure_probability (
float) – Probability of incoming links failure. Defaults to 0.
- x0¶
initial condition
- Type
- x¶
current value of the local solution
- Type
- force_sleep¶
True if one wanst to force sleep after the computation phase. Defaults to False.
- maximum_sleep¶
Maximum allowed sleep. Defaults to 0.01.
- sleep_type¶
Type of sleep time(“constant”, “random”). Defaults to “random”.
- force_computation_time¶
True if one want sto force length computation phase. Defaults to False.
- maximum_computation_time¶
Maximum allowed computation time. Defaults to 0.01.
- computation_time_type¶
Type of computation time (“constant”, “random”). Defaults to “random”.
- force_unreliable_links¶
True if one wants to force unreliable links. Defaults to False.
- link_failure_probability¶
Probability of incoming links failure. Defaults to 0.
BlockConsensus¶
- class disropt.algorithms.consensus.BlockConsensus(agent, initial_condition, enable_log=False, blocks_list=None, probabilities=None, awakening_probability=1.0)[source]¶
Bases:
disropt.algorithms.algorithm.AlgorithmBlock-wise consensus [FaNo19]
At each iteration, the agent can update its local estimate or not at each iteration according to a certain probability (awakening_probability). From the perspective of agent \(i\) the algorithm works as follows. At iteration \(k\) if the agent is awake, it selects a random block \(\ell_i^k\) of its local solution and updates
\[\begin{split}x_{i,\ell}^{k+1} = \begin{cases} \sum_{j\in\mathcal{N}_i} w_{ij} x_{j\mid i,\ell}^k & \text{if} \ell = \ell_i^k \\ x_{i,\ell}^{k} & \text{otherwise} \end{cases}\end{split}\]where \(\mathcal{N}_i\) is the current set of in-neighbors and \(x_{j\mid i},j\in\mathcal{N}_i\) is the local copy of \(x_j\) available at node \(i\) and \(x_{i,\ell}\) denotes the \(\ell\)-th block of \(x_i\). Otherwise \(x_{i}^{k+1}=x_i^k\).
- Parameters
agent (
Agent) – agent to execute the algorithminitial_condition (
ndarray) – initial conditionenable_log (
bool) – True for enabling logblocks_list (
Optional[List[Tuple]]) – the list of blocks (list of tuples)probabilities (
Optional[List[float]]) – list of probabilities of drawing each blockawakening_probability (
float) – probability of getting awake at each iteration
PushSumConsensus¶
- class disropt.algorithms.consensus.PushSumConsensus(agent, initial_condition, enable_log=False)[source]¶
Bases:
disropt.algorithms.algorithm.AlgorithmPush-Sum Consensus Algorithm
From the perspective of agent \(i\) the algorithm works as follows. For \(k=0,1,\dots\)
\[ \begin{align}\begin{aligned}x_i^{k+1} &= \sum_{j=1}^N w_{ij} x_j^k\\y_i^{k+1} &= \sum_{j=1}^N w_{ij} y_j^k\\z_i^{k+1} &= \frac{x_i^{k+1}}{y_i^{k+1}}\end{aligned}\end{align} \]where \(x_i\in\mathbb{R}^n\). The weight matrix \(W=[w_{ij}]\) should be column-stochastic in order to let \(z_i^k\) converge to the average of the local initial conditions. Also time-varying graphs can be adopted.
- Parameters
agent (Agent) – agent to execute the algorithm
initial_condition (numpy.ndarray) – initial condition
enable_log (bool) – True for enabling log
- z0¶
initial condition
- Type
- z¶
current value of the local solution
- Type
References
- OlSa07
Olfati-Saber, Reza; J. Alex Fax; and Richard M. Murray: Consensus and cooperation in networked multi-agent systems: Proceedings of the IEEE 95.1 (2007): 215-233.