Planning large systems with MDPs: case study of inland waterways supervision

Abstract

Inland waterway management is likely to go through heavy changes due to an expected traffic increase in a context of climate change. Those changes will require an adaptive and resilient management of the water resource. The aim is to have an optimal plan for the distribution of the water resource on the whole inland waterway network, while taking into account the uncertainties arising from the operations of such a network. A representative model using Markov decision processes is proposed to model the dynamic and the uncertainties of the waterways. The proposed model is able to coordinate multiple entities over multiple time steps in order to prevent an overflow of a test network. However, this model suffers from a lack of scalability and is unable to represent real case applications. Advantages and limitations of several approaches of the literature to circumvent this limitation are discussed according to our case study.
  • Referencias
  • Cómo citar
  • Del mismo autor
  • Métricas
Arkell, B. and Darch, G., 2006. Impact of climate change on London's transport network. Proceedings of the ICE - Municipal Engineer, 159:231–237. https://doi.org/10.1680/muen.2006.159.4.231

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

Bellman, R., 1957. A Markovian Decision Process. Journal of Mathematics and Mechanics, 6(4):679–684. ISSN 0022-2518.

Beuthe, M., Jourquin, B., Urbain, N., Bruinsma, F., Lingemann, I., Ubbels, B., and Heumen, E. V., 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, 54:387 – 401. https://doi.org/10.1016/j.sbspro.2012.09.758

Beuthe, M., Jourquin, B., Urbain, N., Lingemann, I., and Ubbels, B., 2014. Climate change impacts on transport on the Rhine and Danube: A multimodal approach. Transportation Research Part D: Transport and Environment, 27:6–11. https://doi.org/10.1016/j.trd.2013.11.002

Bichot, C.-E. and Siarry, P., 2011. Graph Partitioning. Wiley-ISTE. Boutilier, C., Dean, T., and Hanks, S., 1999. Decision-theoretic planning: Structural assumptions and computational leverage. Journal of Artificial Intelligence Research, 11:1–94.

Boutilier, C., Dearden, R., Goldszmidt, M., and others, 1995. Exploiting structure in policy construction. In IJCAI, volume 14, pages 1104–1113.

Brand, C., Tran, M., and Anable, J., 2012. The UK transport carbon model: An integrated life cycle approach to explore low carbon futures. Energy Policy, 41:107–124. ISSN 0301-4215. https://doi.org/10.1016/j.enpol.2010.08.019

Chades, I., Scherrer, B., and 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, pages 57–62. ACM, Madrid, Spain. ISBN 1-58113-445-2. https://doi.org/10.1145/508791.508804

Dean, T. and hong Lin, S., 1995. Decomposition Techniques for Planning in Stochastic Domains. In Proceedings Of The Fourteenth International Joint Conference On Artificial Intelligence (IJCAI-95), pages 1121–1127. Morgan Kaufmann.

Duviella, E., Nouasse, H., Doniec, A., and 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.

Guestrin, C., Koller, D., and Parr, R., 2001. Multiagent Planning with Factored MDPs. In NIPS, volume 1, pages 1523–1530.

Guestrin, C., Venkataraman, S., and Koller, D., 2002. Context-specific multiagent coordination and planning with factored MDPs. In AAAI/IAAI, pages 253–259.

Hoey, J., St-Aubin, R., Hu, A., and Boutilier, C., 1999. SPUDD: Stochastic planning using decision diagrams. In Proceedings of the Fifteenth conference on Uncertainty in artificial intelligence, pages 279–288. MorganKaufmann Publishers Inc.

IWAC, 2009. Climate change mitigation and adaptation. Implications for inland waterways in England and Wales. Report.

Kocsis, L. and Szepesvári, C., 2006. Bandit Based Monte-Carlo Planning. In Fürnkranz, J., Scheffer, T., and Spiliopoulou, M., editors, Machine Learning: ECML 2006, volume 4212 of Lecture Notes in Computer Science, pages 282–293. Springer Berlin Heidelberg. ISBN 978-3-540-45375-8. https://doi.org/10.1007/11871842_29

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

Mallidis, I., Dekker, R., and Vlachos, D., 2012. The impact of greening on supply chain design and cost: a case for a developing region. Journal of Transport Geography, 22:118–128. ISSN 0966-6923. https://doi.org/10.1016/j.jtrangeo.2011.12.007

Mihic, S., Golusin, M., and Mihajlovic, M., 2011. Policy and promotion of sustainable inland waterway transport in Europe - Danube River. Renewable and Sustainable Energy Reviews, 15(4):1801–1809. ISSN 1364-0321. https://doi.org/10.1016/j.rser.2010.11.033

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

Nouasse, H., Doniec, A., Duviella, E., and 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. https://doi.org/10.1201/b21902-152

Nouasse, H., Rajaoarisoa, L., Doniec, A., Duviella, E., Chuquet, K., Chiron, P., and Archimede, B., 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, pages 1–6. IEEE. https://doi.org/10.1109/icat.2015.7340512

Pachauri, R. K., Allen, M., Barros, V., Broome, J., Cramer, W., Christ, R., Church, J., Clarke, L., Dahe, Q., Dasgupta, P., and others, 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, pages 422–430.

Puterman, M. L., 1994. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc. ISBN 0-471-61977-9. https://doi.org/10.1002/9780470316887

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

Wanders, N. and Wada, Y., 2015. Human and climate impacts on the 21st century hydrological drought. Journal of Hydrology, 526:208–220. https://doi.org/10.1016/j.jhydrol.2014.10.047
Desquesnes, G., Lozenguez, G., Doniec, A., & Duviella, Éric. (2016). Planning large systems with MDPs: case study of inland waterways supervision. ADCAIJ: Advances in Distributed Computing and Artificial Intelligence Journal, 5(4), 71–84. https://doi.org/10.14201/ADCAIJ2016547184

Downloads

Download data is not yet available.

Author Biography

Guillaume Desquesnes

,
Douai School of Mines
Phd student
+