## Abstract

We consider transporting a mass on a given directed graph. The mass is initially concentrated on certain nodes and needs to be transported in a certain time period to another set of nodes, typically disjoint from the first. We seek a transport plan which is robust with respect to links and nodes failure. In order to achieve that, we need our mass to spread over time on all available routes between source and sink nodes as much as the topology of the graph allows. The scheduling consists in selecting transition probabilities for a Markovian evolution which is designed to be consistent with given initial and final marginal distributions. In order to construct such a transportation plan, we set up a maximum entropy problem (Schrödinger bridge problem) for probability laws on paths which can be viewed as an atypical stochastic control problem. To achieve robustness, we employ a prior distribution on paths which allocates equal probability to paths of equal length connecting any two nodes namely the Ruelle-Bowen random walker (M_{RB}). The latter is also shown to be itself the time-homogeneous solution of a maximum entropy problem for (unnormalized) measures on paths. Since the optimal transport plan is computed via a Schrödinger bridge like problem, for which an efficient iterative algorithm is available [1], our approach appears also computationally attractive. We provide a few examples which illustrate the effectiveness of this method. While in this paper, we only consider strongly connected graphs, in a forthcoming journal paper [2], we show that our approach can be readily extended to not strongly connected graphs and weighted graphs. In the latter case, this strategy may be used to design a transportation plan which effectively compromises between robustness and other criteria such as cost.

Original language | English (US) |
---|---|

Title of host publication | 2016 IEEE 55th Conference on Decision and Control, CDC 2016 |

Publisher | Institute of Electrical and Electronics Engineers Inc. |

Pages | 7623-7628 |

Number of pages | 6 |

ISBN (Electronic) | 9781509018376 |

DOIs | |

State | Published - Dec 27 2016 |

Event | 55th IEEE Conference on Decision and Control, CDC 2016 - Las Vegas, United States Duration: Dec 12 2016 → Dec 14 2016 |

### Publication series

Name | 2016 IEEE 55th Conference on Decision and Control, CDC 2016 |
---|

### Other

Other | 55th IEEE Conference on Decision and Control, CDC 2016 |
---|---|

Country/Territory | United States |

City | Las Vegas |

Period | 12/12/16 → 12/14/16 |

## ASJC Scopus subject areas

- Artificial Intelligence
- Decision Sciences (miscellaneous)
- Control and Optimization