Combining Monte Carlo Tree Search and Depth First Search Methods for a Car Manufacturing Workshop Scheduling Problem

Authors Valentin Antuori, Emmanuel Hebrard , Marie-José Huguet, Siham Essodaigui, Alain Nguyen



PDF
Thumbnail PDF

File

LIPIcs.CP.2021.14.pdf
  • Filesize: 0.73 MB
  • 16 pages

Document Identifiers

Author Details

Valentin Antuori
  • Renault, Plessis-Robinson, France
  • LAAS-CNRS, Université de Toulouse, CNRS, France
Emmanuel Hebrard
  • LAAS-CNRS, Université de Toulouse, CNRS, ANITI, France
Marie-José Huguet
  • LAAS-CNRS, Université de Toulouse, CNRS, INSA, France
Siham Essodaigui
  • Renault, Plessis-Robinson, France
Alain Nguyen
  • Renault, Plessis-Robinson, France

Cite AsGet BibTex

Valentin Antuori, Emmanuel Hebrard, Marie-José Huguet, Siham Essodaigui, and Alain Nguyen. Combining Monte Carlo Tree Search and Depth First Search Methods for a Car Manufacturing Workshop Scheduling Problem. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.CP.2021.14

Abstract

Many state-of-the-art methods for combinatorial games rely on Monte Carlo Tree Search (MCTS) method, coupled with machine learning techniques, and these techniques have also recently been applied to combinatorial optimization. In this paper, we propose an efficient approach to a Travelling Salesman Problem with time windows and capacity constraints from the automotive industry. This approach combines the principles of MCTS to balance exploration and exploitation of the search space and a backtracking method to explore promising branches, and to collect relevant information on visited subtrees. This is done simply by replacing the Monte-Carlo rollouts by budget-limited runs of a DFS method. Moreover, the evaluation of the promise of a node in the Monte-Carlo search tree is key, and is a major difference with the case of games. For that purpose, we propose to evaluate a node using the marginal increase of a lower bound of the objective function, weighted with an exponential decay on the depth, in previous simulations. Finally, since the number of Monte-Carlo rollouts and hence the confidence on the evaluation is higher towards the root of the search tree, we propose to adjust the balance exploration/exploitation to the length of the branch. Our experiments show that this method clearly outperforms the best known approaches for this problem.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatoric problems
  • Mathematics of computing → Combinatorial optimization
  • Computing methodologies → Planning and scheduling
  • Computing methodologies → Discrete space search
Keywords
  • Monte-Carlo Tree Search
  • Travelling Salesman Problem
  • Scheduling

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. David Allouche, Simon de Givry, George Katsirelos, Thomas Schiex, and Matthias Zytnicki. Anytime hybrid best-first search with tree decomposition for weighted CSP. In Proceedings of the 21st International Conference on Principles and Practice of Constraint Programming (CP), pages 12-29, 2015. URL: https://doi.org/10.1007/978-3-319-23219-5_2.
  2. Valentin Antuori, Emmanuel Hebrard, Marie-José Huguet, Siham Essodaigui, and Alain Nguyen. Leveraging Reinforcement Learning, Constraint Programming and Local Search: A Case Study in Car Manufacturing. In Proceedings of the 26th International Conference on Principles and Practice of Constraint Programming (CP), pages 657-672, 2020. URL: https://doi.org/10.1007/978-3-030-58475-7_38.
  3. Dimitris Bertsimas, J. Daniel Griffith, Vishal Gupta, Mykel J. Kochenderfer, and Velibor V. Misic. A comparison of Monte Carlo tree search and rolling horizon optimization for large-scale dynamic resource allocation problems. European Journal of Operational Research, 263(2):664-678, 2017. URL: https://doi.org/10.1016/j.ejor.2017.05.032.
  4. Cameron Browne, Edward Jack Powley, Daniel Whitehouse, Simon M. Lucas, Peter I. Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez Liebana, Spyridon Samothrakis, and Simon Colton. A Survey of Monte Carlo Tree Search Methods. IEEE Transactions on Computational Intelligence and AI in Games, 4(1):1-43, 2012. URL: https://doi.org/10.1109/TCIAIG.2012.2186810.
  5. Guillaume Chaslot, Steven Jong, Jahn-Takeshi Saito, and Jos Uiterwijk. Monte-Carlo Tree Search in Production Management Problems. In Proceedings of the 18th Belgium-Netherlands Conference on Artificial Intelligence (BNAIC), pages 91-98, January 2006. Google Scholar
  6. Rémi Coulom. Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search. In Proceedings of the 5th International Conference on Computers and Games (CG), pages 72-83, 2006. URL: https://doi.org/10.1007/978-3-540-75538-8_7.
  7. Gecode Team. Gecode: Generic constraint development environment, 2006. Available from http://www.gecode.org. Google Scholar
  8. Sylvain Gelly and David Silver. Combining online and offline knowledge in UCT. In Proceedings of the 24th International Conference on Machine Learning (ICML), pages 273-280, 2007. URL: https://doi.org/10.1145/1273496.1273531.
  9. Jack Goffinet and Raghuram Ramanujan. Monte-Carlo Tree Search for the Maximum Satisfiability Problem. In Proceedings of the 22nd International Conference on Principles and Practice of Constraint Programming (CP), pages 251-267, 2016. URL: https://doi.org/10.1007/978-3-319-44953-1_17.
  10. Ernst A. Heinz. New Self-Play Results in Computer Chess. In Proceedings of the Second International Conference on Computers and Games (CG), pages 262-276, 2000. URL: https://doi.org/10.1007/3-540-45579-5_18.
  11. Levente Kocsis and Csaba Szepesvári. Bandit Based Monte-Carlo Planning. In Proceedings of the 17th European Conference on Machine Learning (ECML), pages 282-293, 2006. URL: https://doi.org/10.1007/11871842_29.
  12. Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning. In Proceedings of the 17th European Conference on Machine Learning (ECML), ECML'06, page 282–293, Berlin, Heidelberg, 2006. Springer-Verlag. URL: https://doi.org/10.1007/11871842_29.
  13. Manuel Loth, Michèle Sebag, Youssef Hamadi, and Marc Schoenauer. Bandit-Based Search for Constraint Programming. In Proceedings of the 19th International Conference on Principles and Practice of Constraint Programming (CP), pages 464-480, 2013. URL: https://doi.org/10.1007/978-3-642-40627-0_36.
  14. Jacek Mandziuk and Cezary Nejman. UCT-Based Approach to Capacitated Vehicle Routing Problem. In Proceedings of the 14th International Conference on Artificial Intelligence and Soft Computing (ICAISC), pages 679-690, 2015. URL: https://doi.org/10.1007/978-3-319-19369-4_60.
  15. Shimpei Matsumoto, Noriaki Hirosue, Kyohei Itonaga, Nobuyuki Ueno, and Hiroaki Ishii. Monte-carlo tree search for a reentrant scheduling problem. In Proceedings of the 40th International Conference on Computers Indutrial Engineering (CIE), pages 1-6, 2010. URL: https://doi.org/10.1109/ICCIE.2010.5668320.
  16. Minh Anh Nguyen, Kazushi Sano, and Vu Tu Tran. A monte carlo tree search for traveling salesman problem with drone. Asian Transport Studies, 6:100028, 2020. URL: https://doi.org/10.1016/j.eastsj.2020.100028.
  17. Alessandro Previti, Raghuram Ramanujan, Marco Schaerf, and Bart Selman. Monte-Carlo Style UCT Search for Boolean Satisfiability. In Proceedings of the 12th International Conference of the Italian Association for Artificial Intelligence (AI*IA), pages 177-188, 2011. URL: https://doi.org/10.1007/978-3-642-23954-0_18.
  18. Charles Prud'homme, Jean-Guillaume Fages, and Xavier Lorca. Choco Solver Documentation. TASC, INRIA Rennes, LINA CNRS UMR 6241, COSLING S.A.S., 2016. URL: http://www.choco-solver.org.
  19. Stefan Ropke and David Pisinger. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, 40(4):455-472, 2006. URL: https://doi.org/10.1287/trsc.1050.0135.
  20. Thomas Philip Runarsson, Marc Schoenauer, and Michèle Sebag. Pilot, Rollout and Monte Carlo Tree Search Methods for Job Shop Scheduling. In Proceedings of the 6th International Conference on Learning and Intelligent Optimization (LION), pages 160-174, 2012. URL: https://doi.org/10.1007/978-3-642-34413-8_12.
  21. Ashish Sabharwal, Horst Samulowitz, and Chandra Reddy. Guiding combinatorial optimization with UCT. In Proceedings of the 9th International Conference on Integration of AI and OR Techniques in Contraint Programming for Combinatorial Optimzation Problems (CPAIOR), pages 356-361, 2012. URL: https://doi.org/10.1007/978-3-642-29828-8_23.
  22. David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Vedavyas Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy P. Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):484-489, 2016. URL: https://doi.org/10.1038/nature16961.
  23. David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy P. Lillicrap, Fan Hui, Laurent Sifre, George van den Driessche, Thore Graepel, and Demis Hassabis. Mastering the game of go without human knowledge. Nature, 550(7676):354-359, 2017. URL: https://doi.org/10.1038/nature24270.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail