Relaxed Schrodinger Bridges and Robust Network Routing

作     者：Chen, Yongxin Georgiou, Tryphon T. Pavon, Michele Tannenbaum, Allen 

作者机构：Georgia Inst Technol Sch Aerosp Engn Atlanta GA 30332 USA Univ Calif Irvine Dept Mech & Aerosp Engn Irvine CA 92697 USA Univ Padua Dipartimento Matemat Tullio Levi Civita I-35121 Padua Italy SUNY Stony Brook Dept Comp Sci Stony Brook NY 11794 USA SUNY Stony Brook Dept Appl Math & Stat Stony Brook NY 11794 USA 

出 版 物：《IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS》 (IEEE Trans. Control Netw. Syst.)

年 卷 期：2020年第7卷第2期

页      面：923-931页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Air Force Office of Scientific Research [FA9550-17-1-0435] Army Research Office [W911NF-17-1-049] National Science Foundation [1509387, 1665031, 1807664, 1839441, 1901599] National Center for Research Resources [P41-RR-013218] National Institute of Biomedical Imaging and Bioengineering [P41-EB-015902] National Cancer Institute [1U24CA18092401A1] National Institute of Aging [R01 AG053991] Breast Cancer Research Foundation University of Padova Research Project [CPDA 140897] Div Of Electrical, Commun & Cyber Sys Directorate For Engineering Funding Source: National Science Foundation 

主　　题：Iterative algorithm optimal mass transport relaxed maximum entropy problem robust network routing 

摘      要：We seek network routing towards a desired final distribution that can mediate possible random link failures. In other words, we seek a routing plan that utilizes alternative routes so as to be relatively robust to link failures. To this end, we provide a mathematical formulation of a relaxed transport problem where the final distribution only needs to be close to the desired one. The problem is cast as a maximum entropy problem for probability distributions on paths with added terminal cost. The entropic regularizing penalty aims at distributing the choice of paths amongst possible alternatives. We prove that the unique solution may be obtained by solving a generalized Schrodinger system of equations. An iterative algorithm to compute the solution is provided. Each iteration of the algorithm contracts the distance (in the Hilbert metric) to the optimal solution by more than 1/2, leading to extremely fast convergence.