Robust transport over networks.
Robust transport over networks.
复制标题
DOI：
10.1109/tac.2016.2626796
复制
发表时间：
2017-09
影响因子：
6.8
通讯作者：
Tannenbaum A
中科院分区：
文献类型：
--
作者：
Chen Y;Georgiou T;Pavon M;Tannenbaum A
我们考虑一个强连通有向图上的运输。调度量选择转移概率的离散时间马尔可夫演化的目的是要符合初始和最终的边际约束的大众运输。我们解决的情况下，最初的质量集中在某些节点，需要在一定的时间内被运送到另一组节点，可能从第一个不相交。随机演化被选择为最接近相对熵意义上的路径上的先验测度-这样的构造被称为两个给定边缘之间的薛定谔桥。它可以被看作是一个非典型的随机控制问题，其中的控制包括在适当修改以前的过渡机制。先验可以被选择为结合用于遍历图的特定边的约束和成本，但是也可以被选择为向连接任何两个节点的相等长度的所有路径分配相等的概率（即，路径上的均匀分布）。后一种对先前转换的选择依赖于所谓的Ruelle-Bowen随机步行者，并导致倾向于在拓扑允许的情况下均匀地利用所有路径的调度。因此，将此Ruelle-Bowen定律（RRB）作为先验，导致倾向于减少拥堵并确保一定程度的鲁棒性的交通计划。我们还证明了路径上的分布R_RB，它达到了由拓扑熵给出的随机步行者的最大熵率，它本身可以作为路径上测度的最大熵问题的时间齐次解（也是薛定谔桥问题，尽管先验不是概率测度）。最后，我们表明，薛定谔桥作为一种机制，调度网络上的运输范式可以适应图，是不是强连接，以及加权图。在后一种情况下，我们的方法可以用来设计一个运输计划，有效地鲁棒性和其他标准，如成本之间的妥协。事实上，我们明确地提供了一个强大的运输计划，分配最大的概率最低成本的路径，因此比较有利的最优大众运输策略。
We consider transportation over a strongly connected, directed graph. The scheduling amounts to selecting transition probabilities for a discrete-time Markov evolution which is designed to be consistent with initial and final marginal constraints on mass transport. We address the situation where initially the mass is concentrated on certain nodes and needs to be transported in a certain time period to another set of nodes, possibly disjoint from the first. The random evolution is selected to be closest to a prior measure on paths in the relative entropy sense–such a construction is known as a Schrödinger bridge between the two given marginals. It may be viewed as an atypical stochastic control problem where the control consists in suitably modifying the prior transition mechanism. The prior can be chosen to incorporate constraints and costs for traversing specific edges of the graph, but it can also be selected to allocate equal probability to all paths of equal length connecting any two nodes (i.e., a uniform distribution on paths). This latter choice for prior transitions relies on the so-called Ruelle-Bowen random walker and gives rise to scheduling that tends to utilize all paths as uniformly as the topology allows. Thus, this Ruelle-Bowen law (𝔐RB) taken as prior, leads to a transportation plan that tends to lessen congestion and ensures a level of robustness. We also show that the distribution 𝔐RB on paths, which attains the maximum entropy rate for the random walker given by the topological entropy, can itself be obtained as the time-homogeneous solution of a maximum entropy problem for measures on paths (also a Schrödinger bridge problem, albeit with prior that is not a probability measure). Finally we show that the paradigm of Schrödinger bridges as a mechanism for scheduling transport on networks can be adapted to graphs that are not strongly connected, as well as to weighted graphs. In the latter case, our approach may be used to design a transportation plan which effectively compromises between robustness and other criteria such as cost. Indeed, we explicitly provide a robust transportation plan which assigns maximum probability to minimum cost paths and therefore compares favourably with Optimal Mass Transportation strategies.