Method

Network Architecture 🧠

• Constrained Markov Decision Process: $(S,A,P,R)$, not all actions are allowed
• Model-free method: seeking for a policy $\pi : S \rightarrow A$ to maximize the accumulated discounted reward $J(\pi)=E_{\tau\sim\pi}[\Sigma^{\infty}_{t=0}\gamma^tR(s_t,a_t)]$
• Network architecture: actor-critic framework with Kronecker-Factored Trusted Region (ACKTR), such on-policy methods are better than off-policy ones like SAC according to experimental results

Assumption 🤔

Constrain the sizes of all items to be $$l_i \leq L/2, w_i \leq W/2, h_i \leq H/2$$ because the complexity of BPP decreases drastically for bigger items.

Env State 👀

Discretizing the bottom area as a L x W regular grid along length (X) and width (Y) directions, the current environment state can be written as $s_n=\{\mathbf{H_n},\mathbf{d_n},\mathbf{d_{n+1}},...,\mathbf{d_{n+k-1}}\}$ consisting of:

1. Configuration of the bin: parameterized as a height map $\mathbf{H}_n$ over a L x W grid, $n$ is the next item to be packed.
2. Size of the next item to be packed (green box): the 3 dimensions are stored into a L x W x 3 tensor D, the dimensionality of item $n$ is given as $\mathbf{d}_n=[l_n,w_n,h_n]^T$

A state CNN is used to encoding the raw state vector into features. The state $s_n=(\mathbf{H}_n,\mathbf{D}_n)$ becomes a L x W x 4 array by stretching $\mathbf{d}_n$ into a 3-channel tensor $\mathbf{D}_n$ to fit the state CNN.

Feasibility Mask 🤿

A binary matrix $\mathbf{M}$ of size L x W indicating the placement feasibility at each grid cell.

Feasibility Request:

1. Enough space in the bin to host item $n$
2. Stability at a loading position

A LP is considered feasible if:

1. Providing sufficient room for $n$
2. Satisfying ANY of the following conditions with $n$ placed:

• over 60% of $n$'s bottom area and all of its four bottom corners are supported;
• over 80% of $n$'s bottom area and three out of four bottom corners are supported;
• over 95% of $n$'s bottom area is supported;

The feasibility of all the LPs for item $n$ is stored in the feasibility mask $\mathbf{M}_n$.

Reward and Loss Function 🏅

Volumetric Occupancy Reward

A simplistic step-wise reward $$r_n=10\times{l_n}\cdot{w_n}\cdot{h_n}/({L}\cdot{W}\cdot{H})$$, when $n$ is not placeable, its reward is zero and the episode ends.

This step-wise reward directs the agent to place as many items as possible, better than a termination one.

Feasibility Constraints

• Mask loss $L_{mask}$: An independent MLP, namely the mask predictor, is introduced to predict the feasibility mask. $L_{mask}$ is the MSE loss for mask prediction.

• Inf. loss $E_{inf}$: If the LP is infeasible, the corresponding action probability is set to a small positive quantity like $\epsilon=10^{-3}$. And the summed probability at all infeasible LPs is explicitly minimized: $E_{inf}$, which is plugged into the final loss function for training.

Loss Function

The loss function is defined as: $$L=\alpha \cdot L_{actor}+\beta \cdot L_{critic}+\lambda \cdot L_{mask}+\omega \cdot E_{inf}-\psi \cdot E_{entropy}$$

$E_{entropy}=\Sigma_{\mathbf{M}_n (x,y)=1} -P(a_n|s_n) \cdot log(P(a_n|s_n))$ is an action entropy loss to push the agent to explore more LPs.

Weights of consistently good performance: $\alpha=1,\beta=\lambda=0.5,\omega=\psi=0.01$

BPP-1 ❓

• The case where $k=1$ in $s_n=\{\mathbf{H_n},\mathbf{d_n},...,\mathbf{d_{n+1}},\mathbf{d_{n+k-1}}\}$
• The agent places $n$'s front-left-bottom (FLB) corner at a certain grid point of the loading position (LP) in the bin

BPP-k with k>1 ❓

In a more general case, the agent receives the information of $k\gt1$ lookahead items. The environment state becomes $s_n=\{\mathbf{H_n},\mathbf{d_n},\mathbf{d_{n+1}},...,\mathbf{d_{n+k-1}}\}$.

It cannot well inform the agent about the lookahead items during DRL training and yields limited improvement to employ sequential modeling of the state sequence. Instead, a search-based solution is proposed to leverage the height map $\mathbf{H}$ update and feasibility mask prediction.

Core Idea:

• Virtual placement: condition the placement of the current item $n$ on the next $(k-1)$ ones with virtual placement through updating the height map accordingly.
• Order dependence constraint: the earlier items should never be packed on top of the later ones

Monte Carlo Permutation Tree Search

Explore the permutations of the sequence $\{\mathbf{d_n},\mathbf{d_{n+1}},...,\mathbf{d_{n+k-1}}\}$ to search for a better $a_n$.

Given two items

• $item(v_i) \lt item(v_j)$ means $item(v_i)$ arrives before $item(v_j)$ in the actual order
• $i \gt j$ along a permutation path means $item(v_j)$ is virtually placed before $item(v_i)$

The LPs corresponding to $item(v_j)$'s occupancy are blocked to avoid placing $item(v_i)$ on top of $item(v_j)$.

To make the search scalable, the Monte Carlo tree search (MCTS) is adapted to reduce alleviate the $O(k!)$ computational complexity. The complexity is reduced to $O(km)$ where $m$ is the number of paths sampled.