Bin packing problem

Algorithm

Scheme (mathematics)

Process (computing)

Engineering

Statistics

Markov process

Systems engineering

Stability (learning theory)

Markov chain

Operating system

Computer science

Mathematical optimization

Markov decision process

Projection (relational algebra)

Reinforcement learning

Task (project management)

Mathematics

Mathematical analysis

Artificial intelligence

Machine learning

State (computer science)

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.

Online 3D Bin Packing with Constrained Deep Reinforcement Learning