A Lyapunov Analysis of a Most Probable Path Finding Algorithm

被引：0

作者：

Mo, Yuanqiu ^{[1
]}

Dasgupta, Soura ^{[2
,3
]}

Beal, Jacob ^{[4
]}

机构：

[1] Westlake Univ, Westlake Inst Adv Study, Inst Adv Technol, Hangzhou 310024, Peoples R China

[2] Univ Iowa, Dept Elect & Comp Engn, Iowa City, IA 52242 USA

[3] Shandong Acad Sci, Shandong Comp Sci Ctr, Jinan 250014, Peoples R China

[4] Raytheon BBN Technol, Dept Informat & Knowledge Technol, Cambridge, MA 02138 USA

来源：

IEEE CONTROL SYSTEMS LETTERS | 2022年 / 6卷

关键词：

Lyapunov methods; Convergence; Perturbation methods; Asymptotic stability; Urban areas; Task analysis; Stability criteria; Lyapunov function; regional stability; aggregate computing; ultimate bounds;

D O I：

10.1109/LCSYS.2021.3088260

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Distributed information spreading algorithms are important building blocks in Aggregate Computing. We consider a special case, namely for finding a most probable path for message delivery from a set of sources to each device in a network. We formulate a Lyapunov function to prove its regional stability subject to initialization of estimated probabilities to the natural interval [0,1). We also prove that the algorithm converges in a finite time, and is ultimately bounded under persistent measurement errors. We provide tight bounds for convergence time, the ultimate bound, and the time for its attainment.

引用

页码：1052 / 1057

页数：6

共 12 条

[1] Albared M, 2010, LECT NOTES ARTIF INT, V6401, P361, DOI 10.1007/978-3-642-16248-0_52
[2] Bellman R., 1958, Quart. Appl. Math., V16, P87
[3] The Hidden Geometry of Complex, Network-Driven Contagion Phenomena
Brockmann, Dirk
Helbing, Dirk
[J]. SCIENCE, 2013, 342 (6164) : 1337 - 1342
[4] Semiautomated Transition State Localization for Organometallic Complexes with Semiempirical Quantum Chemical Methods
Dohm, Sebastian
Bursch, Markus
Hansen, Andreas
Grimme, Stefan
[J]. JOURNAL OF CHEMICAL THEORY AND COMPUTATION, 2020, 16 (03) : 2002 - 2012
[5] Ekisheva Svetlana, 2006, Int J Bioinform Res Appl, V2, P305
[6] A Lyapunov formulation of the nonlinear small-gain theorem for interconnected ISS systems
Jiang, ZP
Mareels, IMY
Wang, Y
[J]. AUTOMATICA, 1996, 32 (08) : 1211 - 1215
[7] Khalife H., 2008, P IEEE GLOB TEL C, P4861
[8] Robustness of the Adaptive Bellman -Ford Algorithm: Global Stability and Ultimate Bounds
Mo, Yuanqiu
Dasgupta, Soura
Beal, Jacob
[J]. IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2019, 64 (10) : 4121 - 4136
[9] Mo YQ, 2018, IEEE DECIS CONTR P, P607, DOI 10.1109/CDC.2018.8618735
[10] Most probable paths in temporal weighted networks: An application to ocean transport
Ser-Giacomi, Enrico
Vasile, Ruggero
Hernandez-Garcia, Emilio
Lopez, Cristobal
[J]. PHYSICAL REVIEW E, 2015, 92 (01)

← 1 2 →