Pervasive Digital Twin for PI-Containers: A New Packing Problem

Patrick Charpentier, Frédéric Chaxel, Nicolas Krommenacker, Vincent Bombardier, Fabián SeguelSensors 2021 · DOI

TL;DR

This paper introduces a novel "pervasive digital twin" for composite containers within the Physical Internet framework. By leveraging sensor data to infer container proximity, they tackle a new type of packing problem to reconstruct the 3D arrangement of items, crucial for real-time logistics management.

What Problem Does This Paper Address?

The Physical Internet (PI) envisions a global logistics network where goods are encapsulated in standardized containers, similar to data packets on the internet. Efficiently managing these containers requires a precise, real-time understanding of their arrangement within larger composite containers, especially during loading, unloading, and routing operations. Traditional methods struggle to provide this dynamic, pervasive view. This paper addresses the challenge of creating a "pervasive digital twin" – a virtual, always-accessible replica of the physical arrangement of PI-containers within a composite container. This digital twin is not about planning an optimal packing, but rather about "rediscovering" an existing arrangement using sensor-derived proximity information.

Methods

The core of the paper lies in formulating a new packing problem as a Constraint Satisfaction Problem (CSP). The key innovation is the use of proximity information gathered from wireless sensor network (WSN) nodes attached to each PI-container. These nodes communicate their neighbors within a certain radio range, creating a neighborhood graph. This graph, along with the known dimensions of the containers, forms the basis for a mathematical model that infers the 3D positions and orientations of the PI-containers.

The model incorporates novel constraints:

  • Proximity Constraints: Derived from the neighborhood graph, these ensure that containers are placed relative to each other based on sensor readings (e.g., if two nodes are neighbors, their distance is within a certain range; if not, it's outside another range).
  • Instrumentation Constraints: These account for the fact that the sensor node's placement on a container introduces asymmetry, affecting the possible orientations of the container.

An algorithm is developed to enumerate all possible solutions that satisfy these constraints. The approach involves placing larger containers first and then recursively placing smaller ones, checking for overlaps and adherence to proximity information.

Datasets

Not discussed in the paper. The authors use simulated scenarios based on existing literature (Meller's scenario) and custom homogeneous container arrangements for testing.

Key Insights and Ideas

  • Proximity as a Primary Constraint: The paper demonstrates that inferring container positions solely from proximity data, rather than direct 3D scanning, is a viable approach for creating a digital twin. This is particularly relevant in scenarios where direct line-of-sight is limited.
  • Instrumentation's Impact on Orientation: The placement of sensors on containers isn't just for data collection; it fundamentally alters the problem by introducing orientation constraints that must be accounted for in the packing model.
  • Heterogeneity Aids Solution Uniqueness: Surprisingly, heterogeneous container dimensions (as in Meller's scenario) can actually help in finding a unique digital twin, as it provides more distinct spatial relationships to leverage. Homogeneous arrangements, while seemingly simpler, can lead to multiple valid solutions.
  • Uncertainty Amplifies Solutions: Measurement uncertainty in proximity data significantly increases the number of potential solutions, highlighting the need for robust methods or additional information to pinpoint the true arrangement.
  • Multiple Measurements Reduce Ambiguity: Repeating proximity measurements with different coverage radii (and thus different R1/R2 values) acts as a powerful way to reduce the solution space and increase the likelihood of finding a unique digital twin.

Key Results

  • The proposed model and algorithm can successfully enumerate potential arrangements of PI-containers within a composite container based on proximity information.
  • For Meller's scenario (heterogeneous containers), unique solutions were found for specific coverage radii (e.g., R=2.3-3.0).
  • For homogeneous container scenarios, multiple solutions were often found, underscoring the challenge of achieving a unique digital twin without further constraints.
  • Increasing measurement uncertainty (I) generally leads to a higher number of solutions.
  • Using multiple proximity measurements (m > 1) significantly reduces the number of eligible solutions, especially for higher uncertainties. For instance, in Meller's scenario with uncertainty I=0.25, using m=3 measurements reduced the solution count to 74.1% of cases yielding 1-3 solutions, compared to 42.7% with m=1.

Limitations and Future Work

  • Solution Space Size: The primary limitation is the potentially large number of eligible "twins" that can be generated, making it difficult to pinpoint the exact physical arrangement.
  • Reliance on Proximity: While novel, proximity data alone might not always be sufficient to uniquely determine the arrangement, especially with high uncertainty or homogeneous container distributions.

Future work suggested includes:

  • Adding More Constraints: Incorporating additional types of constraints, such as those derived from contact sensors between items, could further reduce the solution space.
  • Exploring Other Measurement Types: Investigating other sensor modalities beyond proximity could enhance the accuracy and uniqueness of the digital twin.
  • Real-World Validation: While tested on simulated scenarios, real-world deployment and validation with actual sensor networks would be crucial.

Summary updated

Abstract

The idea defended in this paper consists in finding, at any time and everywhere, the arrangement of containers within a composite container. The digital image of the real arrangement obtained defines its digital twin. This image evolves at the same time as its real twin. It can be used throughout the logistics chain during loading/unloading phases in hubs, to check the completeness of a load, to find the particular position of a container, etc. This digital twin is obtained through the collection of neighborhood information from the sensor nodes embedded on each container. This embedded solution allows accessibility to this information everywhere. This proximity information and the instrumentation of the containers define new types of constraints and a new version of a packing problem. We propose here a model integrating them. This model is implemented and tested on different test cases, and numerical results are provided. These show that, under certain conditions that will be presented, it is possible to obtain the digital twin of the real arrangement.
BibTeX
@inproceedings{charpentier2021pervasive,
  author = {Patrick Charpentier and Frédéric Chaxel and Nicolas Krommenacker and Vincent Bombardier and Fabián Seguel},
  title = {{Pervasive Digital Twin for PI-Containers: A New Packing Problem}},
  booktitle = {Sensors},
  year = {2021},
  doi = {10.3390/s21237999},
}

Loading related content...

Figure