“Learning Gradient Fields for Scalable and Generalizable Irregular Packing” by Xue, Wu, Lu, Wang, Dong, et al. …
Conference:
Type(s):
Title:
- Learning Gradient Fields for Scalable and Generalizable Irregular Packing
Session/Category Title: Put Things Together
Presenter(s)/Author(s):
Abstract:
The packing problem, also known as cutting or nesting, has diverse applications in logistics, manufacturing, layout design, and atlas generation. It involves arranging irregularly shaped pieces to minimize waste while avoiding overlap. Recent advances in machine learning, particularly reinforcement learning, have shown promise in addressing the packing problem. In this work, we delve deeper into a novel machine learning-based approach that formulates the packing problem as conditional generative modeling. To tackle the challenges of irregular packing, including object validity constraints and collision avoidance, our method employs the score-based diffusion model to learn a series of gradient fields. These gradient fields encode the correlations between constraint satisfaction and the spatial relationships of polygons, learned from teacher examples. During the testing phase, packing solutions are generated using a coarse-to-fine refinement mechanism guided by the learned gradient fields. To enhance packing feasibility and optimality, we introduce two key architectural designs: multi-scale feature extraction and coarse-to-fine relation extraction. We conduct experiments on two typical industrial packing domains, considering translations only. Empirically, our approach demonstrates spatial utilization rates comparable to, or even surpassing, those achieved by the teacher algorithm responsible for training data generation. Additionally, it exhibits some level of generalization to shape variations. We are hopeful that this method could pave the way for new possibilities in solving the packing problem.
References:
[1]
Marco Attene. 2015. Shapes In a Box: Disassembling 3D Objects for Efficient Packing and Fabrication. Computer Graphics Forum 34, 8 (may 2015), 64–76. https://doi.org/10.1111/cgf.12608
[2]
J A Bennell and J F Oliveira. 2009. A tutorial in irregular shape packing problems. Journal of the Operational Research Society 60, sup1 (may 2009), S93–S105. https://doi.org/10.1057/jors.2008.169
[3]
Lingxin Cao, Lihao Tian, Hao Peng, Yu Zhou, and Lin Lu. 2021. Constrained stacking in DLP 3D printing. Computers & Graphics 95 (2021), 60–68. https://doi.org/10.1016/j.cag.2021.01.003
[4]
Weikai Chen, Yuexin Ma, Sylvain Lefebvre, Shiqing Xin, Jonàs Martínez, and Wenping Wang. 2017. Fabricable tile decors. ACM Transactions on Graphics 36, 6 (nov 2017), 1–15. https://doi.org/10.1145/3130800.3130817
[5]
Xuelin Chen, Hao Zhang, Jinjie Lin, Ruizhen Hu, Lin Lu, Qixing Huang, Bedrich Benes, Daniel Cohen-Or, and Baoquan Chen. 2015. Dapper: decompose-and-pack for 3D printing. ACM Transactions on Graphics 34, 6 (nov 2015), 1–12. https://doi.org/10.1145/2816795.2818087
[6]
Hai Ci, Mingdong Wu, Wentao Zhu, Xiaoxuan Ma, Hao Dong, Fangwei Zhong, and Yizhou Wang. 2022. GFPose: Learning 3D Human Pose Prior with Gradient Fields. arxiv:2212.08641 [cs.CV]
[7]
Qiaodong Cui, Victor Rong, Desai Chen, and Wojciech Matusik. 2023. Dense, Interlocking-Free and Scalable Spectral Packing of Generic 3D Objects. ACM Trans. Graph. 42, 4, Article 141 (jul 2023), 14 pages. https://doi.org/10.1145/3592126
[8]
Lu Duan, Haoyuan Hu, Yu Qian, Yu Gong, Xiaodong Zhang, Jiangwen Wei, and Yinghui Xu. 2019. A Multi-Task Selected Learning Approach for Solving 3D Flexible Bin Packing Problem. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (Montreal QC, Canada) (AAMAS ’19). International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 1386–1394.
[9]
Jie Fang, Yunqing Rao, Xusheng Zhao, and Bing Du. 2023. A Hybrid Reinforcement Learning Algorithm for 2D Irregular Packing Problems. Mathematics 11, 2 (jan 2023), 327. https://doi.org/10.3390/math11020327
[10]
A.Miguel Gomes and José F. Oliveira. 2002. A 2-exchange heuristic for nesting problems. European Journal of Operational Research 141, 2 (sep 2002), 359–370. https://doi.org/10.1016/s0377-2217(02)00130-3
[11]
Baosu Guo, Yu Zhang, Jingwen Hu, Jinrui Li, Fenghe Wu, Qingjin Peng, and Quan Zhang. 2022. Two-dimensional irregular packing problems: A review. Frontiers in Mechanical Engineering 8 (aug 2022). https://doi.org/10.3389/fmech.2022.966691
[12]
E Hopper and B.C.H Turton. 2001. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem. European Journal of Operational Research 128, 1 (jan 2001), 34–57. https://doi.org/10.1016/s0377-2217(99)00357-4
[13]
Ruizhen Hu, Juzhan Xu, Bin Chen, Minglun Gong, Hao Zhang, and Hui Huang. 2020. TAP-Net: transport-and-pack using reinforcement learning. ACM Transactions on Graphics 39, 6 (nov 2020), 1–15. https://doi.org/10.1145/3414685.3417796
[14]
Wenchao Hu, Zhonggui Chen, Hao Pan, Yizhou Yu, Eitan Grinspun, and Wenping Wang. 2016. Surface Mosaic Synthesis with Irregular Tiles. IEEE Transactions on Visualization and Computer Graphics 22, 3 (mar 2016), 1302–1313. https://doi.org/10.1109/tvcg.2015.2498620
[15]
Aapo Hyvärinen. 2005. Estimation of Non-Normalized Statistical Models by Score Matching. J. Mach. Learn. Res. 6 (dec 2005), 695–709.
[16]
Bongjin Koo, Jean Hergel, Sylvain Lefebvre, and Niloy J. Mitra. 2017. Towards Zero-Waste Furniture Design. IEEE Transactions on Visualization and Computer Graphics 23, 12 (dec 2017), 2627–2640. https://doi.org/10.1109/tvcg.2016.2633519
[17]
Kin Chung Kwan, Lok Tsun Sinn, Chu Han, Tien-Tsin Wong, and Chi-Wing Fu. 2016. Pyramid of arclength descriptor for generating collage of shapes. ACM Transactions on Graphics 35, 6 (nov 2016), 1–12. https://doi.org/10.1145/2980179.2980234
[18]
Aline A.S. Leao, Franklina M.B. Toledo, José Fernando Oliveira, Maria Antónia Carravilla, and Ramón Alvarez-Valdés. 2020. Irregular packing problems: A review of mathematical models. European Journal of Operational Research 282, 3 (may 2020), 803–822. https://doi.org/10.1016/j.ejor.2019.04.045
[19]
Bruno Lévy, Sylvain Petitjean, Nicolas Ray, and Jérome Maillot. 2002. Least squares conformal maps for automatic texture atlas generation. ACM Transactions on Graphics 21, 3 (jul 2002), 362–371. https://doi.org/10.1145/566654.566590
[20]
Max Limper, Nicholas Vining, and ALLA SHEFFER. 2018. Box cutter: atlas refinement for efficient packing via void elimination. ACM Transactions on Graphics 37, 4 (jul 2018), 1–13. https://doi.org/10.1145/3197517.3201328
[21]
Tsung-Yi Lin, Piotr Dollár, Ross Girshick, Kaiming He, Bharath Hariharan, and Serge Belongie. 2017. Feature Pyramid Networks for Object Detection. arxiv:1612.03144 [cs.CV]
[22]
Hao-Yu Liu, Xiao-Ming Fu, Chunyang Ye, Shuangming Chai, and Ligang Liu. 2019. Atlas refinement with bounded packing efficiency. ACM Transactions on Graphics 38, 4 (jul 2019), 1–13. https://doi.org/10.1145/3306346.3323001
[23]
Yang Liu, Wenping Wang, Bruno Lévy, Feng Sun, Dong-Ming Yan, Lin Lu, and Chenglei Yang. 2009. On Centroidal Voronoi Tessellation—energy Smoothness and Fast Computation. ACM Trans. Graph. 28, 4, Article 101 (sep 2009), 17 pages. https://doi.org/10.1145/1559755.1559758
[24]
Shitong Luo and Wei Hu. 2021. Score-based point cloud denoising. In Proceedings of the IEEE/CVF International Conference on Computer Vision. IEEE Computer Society, Los Alamitos, CA, USA, 4583–4592.
[25]
Thelma D. Mavridou and Panos M. Pardalos. 1997. Simulated Annealing and Genetic Algorithms for the Facility Layout Problem: A Survey. Computational Optimization and Applications 7, 1 (1997), 111–126. https://doi.org/10.1023/a:1008623913524
[26]
Victor J. Milenkovic. 1999. Rotational polygon containment and minimum enclosure using only robust 2D constructions. Computational Geometry 13, 1 (may 1999), 3–19. https://doi.org/10.1016/s0925-7721(99)00006-1
[27]
Mattia Montanari and Nik Petrinic. 2018. OpenGJK for C, C# and Matlab: Reliable solutions to distance queries between convex bodies in three-dimensional space. SoftwareX 7 (jan 2018), 352–355. https://doi.org/10.1016/j.softx.2018.10.002
[28]
Mattia Montanari, Nik Petrinic, and Ettore Barbieri. 2017. Improving the GJK Algorithm for Faster and More Reliable Distance Queries Between Convex Objects. ACM Transactions on Graphics 36, 4 (jun 2017), 1. https://doi.org/10.1145/3072959.3083724
[29]
T. Nöll and D. Strieker. 2011. Efficient Packing of Arbitrary Shaped Charts for Automatic Texture Atlas Generation. Computer Graphics Forum 30, 4 (jun 2011), 1309–1317. https://doi.org/10.1111/j.1467-8659.2011.01990.x
[30]
José F. Oliveira, A. Miguel Gomes, and J. Soeiro Ferreira. 2000. TOPOS – A new constructive algorithm for nesting problems. OR Spektrum 22, 2 (2000), 263. https://doi.org/10.1007/s002910050105
[31]
Charles R. Qi, Hao Su, Kaichun Mo, and Leonidas J. Guibas. 2017a. PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation. arxiv:1612.00593 [cs.CV]
[32]
Charles R. Qi, Li Yi, Hao Su, and Leonidas J. Guibas. 2017b. PointNet++: Deep Hierarchical Feature Learning on Point Sets in a Metric Space. arxiv:1706.02413 [cs.CV]
[33]
Guocheng Qian, Yuchen Li, Houwen Peng, Jinjie Mai, Hasan Hammoud, Mohamed Elhoseiny, and Bernard Ghanem. 2022. PointNeXt: Revisiting PointNet++ with Improved Training and Scaling Strategies. In Advances in Neural Information Processing Systems (NeurIPS).
[34]
Bernhard Reinert, Tobias Ritschel, and Hans-Peter Seidel. 2013. Interactive by-example design of artistic packing layouts. ACM Transactions on Graphics 32, 6 (nov 2013), 1–7. https://doi.org/10.1145/2508363.2508409
[35]
Yang Song and Stefano Ermon. 2019. Generative modeling by estimating gradients of the data distribution. Advances in Neural Information Processing Systems 32 (2019).
[36]
Yang Song, Liyue Shen, Lei Xing, and Stefano Ermon. 2021a. Solving inverse problems in medical imaging with score-based generative models. arXiv preprint arXiv:2111.08005 (2021).
[37]
Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. 2020. Score-based generative modeling through stochastic differential equations. arXiv preprint arXiv:2011.13456 (2020).
[38]
Yang Song, Jascha Sohl-Dickstein, Diederik P. Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. 2021b. Score-Based Generative Modeling through Stochastic Differential Equations. arxiv:2011.13456 [cs.LG]
[39]
Yang Song, Jascha Sohl-Dickstein, Diederik P. Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. 2021c. Score-Based Generative Modeling through Stochastic Differential Equations. arxiv:2011.13456 [cs.LG]
[40]
Peihan Tu, Li-Yi Wei, and Matthias Zwicker. 2022. Clustered vector textures. ACM Transactions on Graphics 41, 4 (jul 2022), 1–23. https://doi.org/10.1145/3528223.3530062
[41]
J. Vanek, J. A. Garcia Galicia, B. Benes, R. Měch, N. Carr, O. Stava, and G. S. Miller. 2014. PackMerger: A 3D Print Volume Optimizer. Computer Graphics Forum 33, 6 (may 2014), 322–332. https://doi.org/10.1111/cgf.12353
[42]
Richa Verma, Aniruddha Singhal, Harshad Khadilkar, Ansuma Basumatary, Siddharth Nayak, Harsh Vardhan Singh, Swagat Kumar, and Rajesh Sinha. 2020. A Generalized Reinforcement Learning Algorithm for Online 3D Bin-Packing. arxiv:2007.00463 [cs.AI]
[43]
Pascal Vincent. 2011. A connection between score matching and denoising autoencoders. Neural computation 23, 7 (2011), 1661–1674.
[44]
Fan Wang and Kris Hauser. 2019. Stable Bin Packing of Non-Convex 3D Objects with a Robot Manipulator. In 2019 International Conference on Robotics and Automation (ICRA) (Montreal, QC, Canada). IEEE Press, 8698–8704. https://doi.org/10.1109/ICRA.2019.8794049
[45]
Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E. Sarma, Michael M. Bronstein, and Justin M. Solomon. 2019. Dynamic Graph CNN for Learning on Point Clouds. arxiv:1801.07829 [cs.CV]
[46]
Ziqi Wang, Peng Song, and Mark Pauly. 2021. State of the Art on Computational Design of Assemblies with Rigid Parts. Computer Graphics Forum 40, 2 (may 2021), 633–657. https://doi.org/10.1111/cgf.142660
[47]
Maciej Wołczyk. 2018. Deep learning-based initialization for object packing. Schedae Informaticae 27 (2018), 9–17. https://doi.org/10.4467/20838476si.18.001.10406
[48]
Chenming Wu, Haisen Zhao, Chandrakana Nandi, Jeffrey I. Lipton, Zachary Tatlock, and Adriana Schulz. 2019. Carpentry compiler. ACM Transactions on Graphics 38, 6 (nov 2019), 1–14. https://doi.org/10.1145/3355089.3356518
[49]
Mingdong Wu, Fangwei Zhong, Yulong Xia, and Hao Dong. 2022. TarGF: Learning Target Gradient Field to Rearrange Objects without Explicit Goal Specification. In Advances in Neural Information Processing Systems, S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (Eds.). Vol. 35. Curran Associates, Inc., 31986–31999. https://proceedings.neurips.cc/paper_files/paper/2022/file/cf5a019ae9c11b4be88213ce3f85d85c-Paper-Conference.pdf
[50]
Miaojun Yao, Zhili Chen, Linjie Luo, Rui Wang, and Huamin Wang. 2015. Level-set-based partitioning and packing optimization of a printable model. ACM Transactions on Graphics 34, 6 (nov 2015), 1–11. https://doi.org/10.1145/2816795.2818064
[51]
Hang Zhao, Qijin She, Chenyang Zhu, Yin Yang, and Kai Xu. 2022. Online 3D Bin Packing with Constrained Deep Reinforcement Learning. arxiv:2006.14978 [cs.LG]
[52]
Hang Zhao and Kai Xu. 2022. Learning Efficient Online 3D Bin Packing on Packing Configuration Trees. In International Conference on Learning Representations. https://openreview.net/forum?id=bfuGjlCwAq
[53]
Hang Zhao, Chenyang Zhu, Xin Xu, Hui Huang, and Kai Xu. 2021. Learning practically feasible policies for online 3D bin packing. Science China Information Sciences 65, 1 (dec 2021). https://doi.org/10.1007/s11432-021-3348-6
[54]
Changqing Zou, Junjie Cao, Warunika Ranaweera, Ibraheem Alhashim, Ping Tan, Alla Sheffer, and Hao Zhang. 2016. Legible compact calligrams. ACM Transactions on Graphics 35, 4 (jul 2016), 1–12. https://doi.org/10.1145/2897824.2925887
