Geometry Design Supported by Minimizing and Visualizing Collision in Dynamic Packing

Authors: Johan Segeborn, Johan S. Carlson, Robert Bohlin, Rikard Söderberg

Abstract:

This paper presents a method to support dynamic packing in cases when no collision-free path can be found. The method, which is primarily based on path planning and shrinking of geometries, suggests a minimal geometry design change that results in a collision-free assembly path. A supplementing approach to optimize geometry design change with respect to redesign cost is described. Supporting this dynamic packing method, a new method to shrink geometry based on vertex translation, interweaved with retriangulation, is suggested. The shrinking method requires neither tetrahedralization nor calculation of medial axis and it preserves the topology of the geometry, i.e. holes are neither lost nor introduced. The proposed methods are successfully applied on industrial geometries.

Keywords: Dynamic packing, path planning, shrinking.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1333819

References:

[1] H. Choset, K. et al., "Principles of Robot Motion: Theory, Algorithms, and Implementations," MIT Press, Boston, 2005.
[2] S. M. LaValle, "Planning Algorithms," Cambridge University Press, 2006.
[3] L. E. Kavraki and J.-C. Latombe, "Randomized Preprocessing of Configuration Space for Fast Path Planning," In Proc. the International Conference on Robotics and Automation, IEEE Press, San Diego, CA, 1994.
[4] L. E. Kavraki, P. Svestka, J.-C. Latombe, and M. Overmars, "Probabilistic Roadmaps for Path Planning in High Dimensional Configuration Spaces," IEEE Transactions on Robotics and Automation, 1996.
[5] S. M. LaValle and J. J. Kuffner, "Randomized kinodynamic planning," In Proc. IEEE International Conference on Robotics and Automation, 1999.
[6] R. Geraerts and M. H. Overmars, "Creating High-quality Paths for Motion Planning," The International Journal of Robotics Research, 2007.
[7] R. Bohlin, L. E. Kavraki, "Path Planning using Lazy PRM," In Proc. the 2000 IEEE lntemational Conference on Robotics & Automation San Francisco, 2000.
[8] D. Hsu, L. Kavraki, J-C. Latombe, R. Motwani, and S. Sorkin. "On finding narrow passages with probabilistic roadmap planners," In Proc. Int. Workshop on Algorithmic Foundations of Robotics, 1998.
[9] L. Zhang, Y. J. Kim, G. Varadhan, D. Manocha, "Generalized Penetration Depth Computation," Computer-Aided Design, Volume 39, Issue 8, 2007.
[10] S. Redon and M. C. Lin, "A Fast Method for Local Penetration Depth Computation," In Journal of Graphics Tools, Vol. 11, No. 2: 37-50, 2006.
[11] D. Hsu, G. Sánchez-Ante, Ho-lun Cheng and J.-C. Latombe, "Multi- Level Free-Space Dilation for Sampling Narrow Passages in PRM Planning," In Proc. IEEE International Conference on Robotics and Automation, 2006.
[12] M. Saha and J.-C. Latombe, "Finding narrow passages with probabilistic roadmaps: The small step retraction method," In Proc. IEEE/RSJ Int. Conf. on Intelligent Robots & Systems, 2005.
[13] B. Baginski, "Local motion planning for manipulators based on shrinking and growing geometry models," In Proc. IEEE Int. Conf. on Robotics & Automation, 1996.
[14] P. Ferbach and J. Barraquand, "A method of Progressive Constraints for Manipulation Planning," IEEE, Tr. Rob. Abd Aut., 13(4):473-485, 1997.
[15] M. Foskey, M. Lin, and D. Manocha, "Efficient computation of a simplified medial axis," In ACM Symp. on Solid Modeling & Applications, 2003.
[16] J. Havner and O. Karlsson, "Automatic correction of surface normals on 3D models," M.S. thesis, Dept. Mathematical Sciences, Chalmers University of Technology, Gothenburg, Sweden, 2005.
[17] M. Garland, P. S. Heckbert, "Surface Simplification Using Quadric Error Metrics," IEEE Visualization 98, 1998.
[18] J. S. Carlson, R. Söderberg, R. Bohlin, L. Lindkvist and T. Herrmansson, "Non-nominal path planning of assembly processes," In Proc. the 2005 ASME International Mechanical Engineering Congress and exposition November 5-11, Orlando, FL, 2005.