Online-Polycube-Packing

Introduction

Bin Packing Problems (BPP) are some of the most popular and well-studied combinatorial optimization problems. Given a container with fixed dimensions, the goal is to pack as many (geometric) items as possible. Traditionally, BPP assumes that all items to be packed are known a priori, which is referred to as offline BPP. However, in many real-world applications items arrive sequentially, and it is not always possible to move items once they have been placed in the container. This variation is known as online BPP, and is considered harder because of the limited information available.

In this repository we provide a highly customizable Python-based framework for the online polycube packing problem: a variant of online 3D-BPP that uses polycubes as items. This framework, among other things, includes:

• A Gymnasium-based packing environment, where the state space is the current state of the container together with the current polycube, and the action space is a position and orientation in the container to place the current polycube.
• A customizable greedy agent, that can pack polycubes based on a set of heuristics. Implemented heuristics include BLBF, HAPE, and Heightmap Minimization.
• A reinforcement learning agent that uses Proximal Policy Optimization (PPO) together with invalid action masking to learn how to optimally pack a container.
• An Open3D-based UI that can visualize the packing process, either through step-by-step polycube placement or a final packing preview.

Dependencies

See requirements.txt.

Usage

See examples/ for a series of examples on how to use various aspects of the code:

• constraints.py, heuristic_packing.py, packing_with_ui.py, and ppo_packing.py all show examples of how to pack a container piece-by-piece using the included UI. To place the next shape, use the next shape button under the actions tab at the top of the UI.
• full_packing.py shows how to pack a container without using the UI.
• Files starting with training_ show examples of how to train models on the packing environment, with models and logs automatically saved to the resources folder.

Note that to use this code, you first need to place the relevant cache files in resources/polycubes/. These cache files contain all possible polycubes of a given size, saving the computational cost of computing them on the fly. These cache files can be created using this repository.

All code is purposefully structured and documented to encourage customization. The documentation, examples and experiments should be sufficient to understand the general workflow and purpose of all modules, functions, etc.

Acknowledgements

This repository was prepared in partial fulfillment of the requirements for the Degree of Bachelor of Science in Data Science and Artificial Intelligence, Maastricht University.

License

MIT