Towards a distribution of large scale MDP. Case study of inland waterway networks

Towards a distribution of large scale MDP. Case study of inland waterway networks

Guillaume Desquesnes Guillaume Lozenguez Arnaud Doniec Éric Duviella 

Mines Douai IA, F-59508 Douai, FRANCE

Corresponding Author Email:
| |
| | Citation



Inland waterways networks management methods should undergo significant changes due to a commitment to increase the waterway traffic in a context of climate change. These new constraints will impose an adaptive and resilient management of the water resource leading to an optimal planning of its distribution over the integrity of the inland waterway network, while taking into account the uncertainties arising from their operation. A MDP based approach is proposed to address this problem. It allows the coordination of multiple entities over multiple time steps. Its use on a subnetwork of the waterway made from 2 reaches leads to a minimization of the impacts of flood and drought periods. Despite promising results, the scaling mechanisms for considering a real application are not fully defined. Different approaches proposed in the literature for scaling are discussed by identifying their advantages and imitations. Among them, a distributed modeling is privileged and a new resolution algorithm is proposed. It is tested on a subnetwork composed of 7 reaches.


Markov decision process, inland waterway network, large model

1. Introduction
2. Gestion d’un réseau de voies navigables
3. Processus décisionnels markoviens
4. Gestion d’un réseau composé de deux biefs
5. Approches existantes dédiées au passage à l’échelle
6. Modélisation par MDP distribué
7. Conclusion

Arkell B., Darch G. (2006). Impact of climate change on London’s transport network. Proceedings of the ICE - Municipal Engineer, vol. 159, p. 231-237.

Bates B., Kundzewicz Z., Wu S., Palutikof J. (2008). Climate change and water. Technical repport, Intergovernmental Panel on Climate Change, Geneva.

Bellifemine F., Poggi A., Rimassa G. (1999). Jade–a fipa-compliant agent framework. In Proceedings of paam, vol. 99, p. 33.

Bellman R. (1957). A Markovian Decision Process. Journal of Mathematics and Mechanics, vol. 6, no 4, p. 679–684.

Beuthe M., Jourquin B., Urbain N., Bruinsma F., Lingemann I., Ubbels B. et al. (2012). Estimating the impacts of water depth and new infrastructures on transport by inland navigation: A multimodal approach for the rhine corridor. Procedia - Social and Behavioral Sciences - Proceedings of EWGT2012 - 15th Meeting of the EURO Working Group on Transportation, vol. 54, p. 387 - 401.

Beuthe M., Jourquin B., Urbain N., Lingemann I., Ubbels B. (2014). Climate change impacts on transport on the rhine and danube: A multimodal approach. Transportation Research Part D: Transport and Environment, vol. 27, p. 6 - 11.

Bichot C.-E., Siarry P. (2011). Graph Partitioning. Wiley-ISTE.

Boutilier C., Dean T., Hanks S. (1999). Decision-theoretic planning: Structural assumptions and computational leverage. Journal of Artificial Intelligence Research, vol. 11, p. 1–94.

Boutilier C., Dearden R., Goldszmidt M., others. (1995). Exploiting structure in policy construction. In IJCAI, vol. 14, p. 1104–1113.

Brand C., Tran M., Anable J. (2012a). The UK transport carbon model: An integrated life cycle approach to explore low carbon futures. Energy Policy, vol. 41, p. 107-124.

Brand C., Tran M., Anable J. (2012b). The UK transport carbon model: An integrated life cycle approach to explore low carbon futures. Energy Policy, vol. 41, p. 107–124. Consulté sur

Chades I., Scherrer B., Charpillet F. (2002). A Heuristic Approach for Solving Decentralized-POMDP: Assessment on the Pursuit Problem. In SAC ’02: Proceedings of the 2002 ACM symposium on Applied computing, p. 57–62. Madrid, Spain, ACM.

Dean T., Lin S. hong. (1995). Decomposition techniques for planning in stochastic domains. In In proceedings of the fourteenth international joint conference on artificial intelligence (ijcai-95), p. 1121–1127. Morgan Kaufmann.

Duviella E., Nouasse H., Doniec A., Chuquet K. (2016). Dynamic optimization approaches for resource allocation planning in inland navigation networks. ETFA’2016, Berlin, Allemagne, September 6-9.

EnviCom. (2008). Climate change and navigation - waterborne transport, ports and waterways: A review of climate change drivers, impacts, responses and mitigation. EnviCom - Task Group 3.

IPCC. (2014). Climate change 2014. The Core Writing Team, R. K. Pachauri and L. Meyer, Synthesis Report. Consulté sur

IWAC. (2009). Climate change mitigation and adaptation. implications for inland waterways in england and wales. Report.

Kocsis L., Szepesvári C. (2006). Bandit Based Monte-Carlo Planning. In J. Fürnkranz, T. Scheffer, M. Spiliopoulou (Eds.), Machine Learning: ECML 2006, vol. 4212, p. 282–293. Springer Berlin Heidelberg.

Lozenguez G., Adouane L., Beynier A., Mouaddib A.-I., Martinet P. (2015). Punctual versus continuous auction coordination for multi-robot and multi-task topological navigation. Autonomous Robots, p. 1–15.

Mallidis I., Dekker R., Vlachos D. (2012). The impact of greening on supply chain design and cost: a case for a developing region. Journal of Transport Geography, vol. 22, p. 118–128. Consulté sur

Mihic S., Golusin M., Mihajlovic M. (2011). Policy and promotion of sustainable inland waterway transport in Europe – Danube River. Renewable and Sustainable Energy Reviews, vol. 15, no 4, p. 1801–1809. Consulté sur

Nair R., Varakantham P., Tambe M., Yokoo M. (2005). Networked Distributed POMDPs: A Synthesis of Distributed Constraint Optimization and POMDPs. In National Conference on Artificial Intelligence, p. 7.

Nouasse H., Doniec A., Duviella E., Chuquet K. (2016). Efficient management of inland navigation reaches equipped with lift pumps in a climate change context. 4th IAHR Europe Congress, Liege, Belgium 27-29 July.

Nouasse H., Rajaoarisoa L., Doniec A., Duviella E., Chuquet K., Chiron P. et al. (2015). Study of drought impact on inland navigation systems based on a flow network model. In Information, Communication and Automation Technologies (ICAT), 2015 XXV International Conference on, p. 1–6. IEEE.

Pachauri R. K., Allen M., Barros V., Broome J., Cramer W., Christ R. et al. (2014). Climate Change 2014: Synthesis Report. Contribution of Working Groups I, II and III to the Fifth Assessment Report of the Intergovernmental Panel on Climate Change.

Parr R. (1998). Flexible Decomposition Algorithms for Weakly Coupled Markov Decision Problems. In 14th Conference on Uncertainty in Artificial Intelligence, p. 422–430.

Puterman M. L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc.

Sabbadin R. (2002). Graph partitioning techniques for Markov Decision Processes decomposition. In 15th Eureopean Conference on Artificial Intelligence, p. 670–674.

Wanders N., Wada Y. (2015). Human and climate impacts on the 21st century hydrological drought. Journal of Hydrology, vol. 526, p. 208-220.