3D dynamic heterogeneous robotic palletization problem

This paper proposes a practical robotic packing system to automate packing heterogeneous carton boxes into pallets, which is still handled manually in many distribution centers. The main challenge is to solve a 3D dynamic heterogeneous robotic palletization (DHRP) problem. Aside from the NP-completeness, there are two additional complexities in DHRP. First, the packing plan must be executable by a robotic arm without collision. Second, the packing decision must be made in real time with partial information. Tractable models are proposed to avoid collision for a common type of robotic arm and ensure the stability of the packing layout. An efficient algorithm is proposed to compute collision-free trajectories of the robotic arm during packing operations, which is embedded into a tree search algorithm to solve the semi-online counterpart of DHRP. Our semi-online algorithm is extended to solve the online version by adopting a Monte Carlo simulation strategy. A comprehensive set of test cases is generated based on realistic data to measure the performance of our algorithm. Numerical experiments show that our algorithm can produce feasible packing decisions in a few seconds for each incoming box on a modest personal computer, which is adequate for many practical setups. To help practitioners select the best setup for their application, numerical experiments are also conducted to analyze the impact of a few key design parameters in a robotic packing system on packing performance.