버퍼 활용 무작위 빈 패킹 문제를 위한 강화학습-휴리스틱 결합 모델
Reinforcement Learning with Heuristics for Buffer-Utilized Random Bin Packing Problem
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
본 논문에서는 강화학습과 휴리스틱을 결합하여 매 순간 무작위로 물체가 주어지지만 작은 크기의 적재 버퍼를 활용할 수 있는 bin packing problem (BPP) 문제를 해결하는 방법을 제안한다. 이때 한번 놓인 물체의 위치는 변경될 수 없다. 이러한 환경은 전반적인 물류 프로세스 자동화의 물결에도 아직 원활히 해결되지 않은 상차 환경과 유사하다. 휴리스틱은 인간의 직관에 따라 신속한 최적화가 가능하고, 강화학습은 환경에 대한 반응성이 뛰어나므로 두 방법을 결합한 방법은 실제 물류 환경으로의 적용이 용이하다. 강화학습을 통해 학습한 모델이 신규 물체 및 버퍼 내 일부 물체들에 대한 각각의 가치를 판별하고 그에 따른 최적의 물체를 선택하면, 선택된 물체는 정의된 휴리스틱 알고리즘에 따라 물체의 최적 방위와 위치를 고려하여 배치된다. 이런 방식으로 결합된 자동화 방법은 버퍼를 효과적으로 활용하여 적재 효율을 증대시킬 수 있다. 실험을 통해 실제로 본 연구에서 제시한 방법을 통해 버퍼를 함께 고려했을 때 휴리스틱 모델만을 사용했을 때보다 적재 효율이 증가함을 확인하였다.
Abstract
In this paper, we propose a reinforcement learning algorithm combined with heuristics to solve the bin packing problem (BPP) where the objects are randomly given and once placed objects cannot be moved, but the small load buffer can be utilized. This setting resembles the loading problem which has not been resolved despite of logistics automation. Since heuristics can be rapidly optimized by human intuition, and reinforcement learning is highly responsive to the environment, the combined method is highly available in the real-world industries. When the model learned through reinforcement learning determines the optimal object among the new object and objects in the buffer, then defined heuristics find optimal position and orientation for placement of the selected object. Through experiments, we verified the effectiveness by comparing the loading efficiency between the heuristic-only system and the combined system presented in this study.
참고문헌 (28)
- Arulkumaran, K., "A brief survey of deep reinforcement learning", arXiv preprint arXiv:1708.05866, ~ (2017)
- Benkö, Attila, "Bin Packing", Covering with Delivery, solved with the evolution of algorithms, 2010 (2010), ~
- Browne, C. B., "A survey of monte carlo tree search methods", IEEE Transactions on Computational Intelligence and AI in games, 4(1), pp.1~43 (2012)
- Cai, Q., "Reinforcement learning driven heuristic optimization", arXiv preprint arXiv:1906.06639, ~ (2019)
- Edelkamp, Stefan, "Monte-Carlo tree search for 3D packing with object orientation", Joint German, 2014, ~[DOI]
- Edward G Coffman, Jr, "Performance bounds for level-oriented two-dimensional packing algorithms", SIAM Journal on Computing, 9(4), pp.808~826 (1980)[DOI]
- François-Lavet, V., "An introduction to deep reinforcement learning", Foundations and Trends® in Machine Learning, 11(3-4), pp.219~354 (2018)
- Garey, M. R, "Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences" (1979), W. H. Freeman and Co
- Grondman, I., "A survey of actor-critic reinforcement learning: Standard and natural policy gradients", IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 42(6), pp.1291~1307 (2012)
- Gupta, A., "Fully-dynamic bin packing with limited repacking", arXiv preprint arXiv:1711.02078, ~ (2017)
- Hu, H., "Solving a new 3d bin packing problem with deep reinforcement learning method", arXiv preprint arXiv:1708.05930, ~ (2017)
- Ibarz, J., "How to train your robot with deep reinforcement learning: lessons we have learned.", The International Journal of Robotics Research, 40(4-5), pp.698~721 (2021)
- Iriondo, A., "Pick and place operations in logistics using a mobile manipulator controlled with deep reinforcement learning", Applied Sciences, 9(2), pp.348~ (2019)
- Johannink, T., "Residual reinforcement learning for robot control", 2019 International Conference on Robotics and Automation (ICRA), pp.6023~6029 (2019)
- Johnson, David S., "Near-optimal bin packing algorithms", pp.1973
- Karmarkar, N, "An efficient approx-imation scheme for the one-dimensional bin-packing prob-lem", 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), pp.312~320 (1982), IEEE
- Li, Yuxi, "Deep reinforcement learning: An overview", arXiv preprint arXiv:1701.07274, ~ (2017)
- Lobbezoo, Andrew, "Reinforcement Learning for Pick and Place Operations in Robotics: A Survey", Robotics, 10(3), pp.105~ (2021)
- Lodi, Andrea, "Heuristic algorithms for the three-dimensional bin packing problem", European Journal of Operational Research, 141(2), pp.410~420 (2002)
- Martello, Silvano, "The three-dimensional bin packing problem", Operations research, 48(2), pp.256~267 (2000)
- Puterman, Martin L., "Handbooks in operations research and management science 2", pp.331~434 (1990)
- Schulman, J., "Proximal policy optimization algorithms", arXiv preprint arXiv:1707.06347, ~ (2017)
- Yang, Yang, "Multi-robot path planning based on a deep reinforcement learning DQN algorithm", CAAI Transactions on Intelligence Technology, 5(3), pp.177~183 (2020)
- Zhao, H., "Learning practically feasible policies for online 3D bin packing", Science China Information Sciences, 65(1), pp.1~17 (2022)
- "보스턴 다이내믹스, "물류 로봇 '스트레치' 올해 생산량 이미 매진"" (2022)[URL]
- "피클 로봇, 고속 박스 하적 로봇 '딜(Dill)' 개발" (2021)[URL]
- "‘AI 혁신 기술’이 이끄는 CJ대한통운의 스마트 물류 혁명" (2021)[URL]
- "로봇과 인공지능: 쿠팡 물류의 최신 기술을 소개합니다" (2022)[URL]