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.
[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.
[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.
@article{"International Journal of Mechanical, Industrial and Aerospace Sciences:56527", author = "Johan Segeborn and Johan S. Carlson and Robert Bohlin and Rikard Söderberg", title = "Geometry Design Supported by Minimizing and Visualizing Collision in Dynamic Packing", 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.", volume = "1", number = "7", pages = "359-8", }