Online 3D Bin Packing with Constrained Deep Reinforcement Learning

Authors

  • Hang Zhao National University of Defense Technology
  • Qijin She National University of Defense Technology
  • Chenyang Zhu National University of Defense Technology
  • Yin Yang Clemson University
  • Kai Xu National University of Defense Technology

Keywords:

Transportation

Abstract

We solve a challenging yet practically useful variant of 3D Bin Packing Problem (3D-BPP). In our problem, the agent has limited information about the items to be packed into a single bin, and an item must be packed immediately after its arrival without buffering or readjusting. The item's placement also subjects to the constraints of order dependence and physical stability. We formulate this online 3D-BPP as a constrained Markov decision process (CMDP). To solve the problem, we propose an effective and easy-to-implement constrained deep reinforcement learning (DRL) method under the actor-critic framework. In particular, we introduce a prediction-and-projection scheme: The agent first predicts a feasibility mask for the placement actions as an auxiliary task and then uses the mask to modulate the action probabilities output by the actor during training. Such supervision and projection facilitate the agent to learn feasible policies very efficiently. Our method can be easily extended to handle lookahead items, multi-bin packing, and item re-orienting. We have conducted extensive evaluation showing that the learned policy significantly outperforms the state-of-the-art methods. A preliminary user study even suggests that our method might attain a human-level performance.

Downloads

Published

2021-05-18

How to Cite

Zhao, H., She, Q., Zhu, C., Yang, Y., & Xu, K. (2021). Online 3D Bin Packing with Constrained Deep Reinforcement Learning. Proceedings of the AAAI Conference on Artificial Intelligence, 35(1), 741-749. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/16155

Issue

Section

AAAI Technical Track on Application Domains