Abstract
This paper formulates two variants of packing problems in which the set of items is known but the arrival order is unknown. The goal is to certify that the items can be packed in a given container, and/or to optimize the size or cost of a container so that that the items are guaranteed to be packable, regardless of arrival order. The Nondeterministically ordered packing (NDOP) variant asks to generate a certificate that a packing plan exists for every ordering of items. Quasionline packing (QOP) asks to generate a partially-observable packing policy that chooses the item location as each subsequent item is revealed. Theoretical analysis demonstrates that even the simple subproblem of verifying feasibility of a packing policy is NP-complete. Despite this worst-case complexity, practical solvers for both NDOP and QOP are developed, and experiments demonstrate their application to packing irregular 3D shapes with manipulator loading constraints.
Introduction
In modern automated fulfillment centers, robotic systems are tasked with packing diverse sets of items into shipping containers. While traditional packing research often assumes either full knowledge of the sequence (offline) or no knowledge of future items (online), real-world logistics frequently operate in a "quasi-online" middle ground. In these environments, the specific items for a customer's order are known, but the internal delivery system may present them to the packing robot in a nondeterministic sequence.
Robotic packing is constrained not only by geometry but by physical realities:
- Stability: The arrangement must remain stable as each item is added.
- Reachability: The robotic manipulator must be able to place an item without colliding with those already in the container.
This paper addresses the challenge of certifying that a set of items can be successfully packed regardless of the order in which they arrive.
Problem Formulation and Methods
The researchers propose two distinct frameworks to handle arrival nondeterminism:
- Nondeterministically Ordered Packing (NDOP): The arrival order is revealed just before packing begins. The goal is to maintain a library of plans such that at least one plan is valid for any possible permutation of the items.
- Quasi-Online Packing (QOP): Items are revealed one by one. The system must commit to a placement for the current item without knowing the future sequence, necessitating a robust packing policy.
Technical Innovations
The core of the proposed solution is the Constraint Dependency Graph (CDG). A CDG explicitly models the necessary placement order to ensure stability and robot access. If an arrival sequence respects the directed edges of a CDG, the corresponding plan is considered compatible.
To handle the $n!$ possible permutations, the authors developed a recursive Coverage Verification algorithm with singleton pruning. This allows the solver to efficiently check if a set of plans covers all possible arrival orders. For the QOP variant, the solver generates a decision tree to determine placements dynamically.
Complexity Analysis
The authors prove that verifying whether a packing policy works for all possible orders is NP-complete (via a reduction from 3-SAT). This theoretical result highlights the inherent difficulty of the problem and justifies the development of specialized heuristic solvers.
Experimental Evaluation
The algorithms were evaluated using 3D scanned irregular objects from the APC 2015 and YCB datasets, tested against standard Amazon Robotics Challenge container sizes.
Key Results
- Success Rates: For small sets (2–5 items), the NDOP solver achieved a 99.3% success rate. For larger sets of 10 items, the rate dropped to 64%, as the tighter packing required for more items leaves less room for sequence flexibility.
- Efficiency: Despite the theoretical complexity, the solvers typically found solutions within seconds or minutes for sets of up to 5 items.
- Container Optimization: The study demonstrated that guaranteeing packability for all orders occasionally requires a slightly larger container (approximately 5% of cases for 5-item sets) compared to scenarios where the order is controlled.
Conclusion and Future Work
This research provides a formal framework and practical tools for robotic packing under nondeterministic arrival orders. While effective for typical consumer orders, scalability remains a challenge for very large item sets. Future work may explore probabilistic arrival models, where certain sequences are more likely than others, and the use of "k-buffered" packing, where a small staging area allows the robot to reorder a limited number of items before final placement.
Summary updated