Geometry Design Supported by Minimizing and Visualizing Collision in Dynamic Packing

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.

Authors:

• Johan Segeborn
• Johan S. Carlson
• Robert Bohlin
• Rikard Söderberg

Keywords:

• Dynamic packing
• path planning
• shrinking.

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.