Obtaining High-Dimensional Configuration Space for Robotic Systems Operating in a Common Environment

Authors: U. Yerlikaya, R. T. Balkan

Abstract:

In this research, a method is developed to obtain high-dimensional configuration space for path planning problems. In typical cases, the path planning problems are solved directly in the 3-dimensional (D) workspace. However, this method is inefficient in handling the robots with various geometrical and mechanical restrictions. To overcome these difficulties, path planning may be formalized and solved in a new space which is called configuration space. The number of dimensions of the configuration space comes from the degree of freedoms of the system of interest. The method can be applied in two ways. In the first way, the point clouds of all the bodies of the system and interaction of them are used. The second way is performed via using the clearance function of simulation software where the minimum distances between surfaces of bodies are simultaneously measured. A double-turret system is held in the scope of this study. The 4-D configuration space of a double-turret system is obtained in these two ways. As a result, the difference between these two methods is around 1%, depending on the density of the point cloud. The disparity between the two forms steadily decreases as the point cloud density increases. At the end of the study, in order to verify 4-D configuration space obtained, 4-D path planning problem was realized as 2-D + 2-D and a sample path planning is carried out with using A* algorithm. Then, the accuracy of the configuration space is proved using the obtained paths on the simulation model of the double-turret system.

Keywords: A* Algorithm, autonomous turrets, high-dimensional C-Space, manifold C-Space, point clouds.

References:

[1] M. Bahrin, M. Othman, N. H. N. Azli and M. F. Talib, “Industry 4.0: A review on industrial automation and robotic,” Jurnal Teknologi (Sciences and Engineering), pp. 137– 143, 2016.
[2] Günther Schuh et al., “Collaboration Mechanisms to Increase Productivity in the Context of Industrie 4.0” in Procedia CIRP, 2014.
[3] M. Reuter, H. Oberc, M. Wannöffel, D. Kreimeier, J. Klippert, P. Pawlicki and B. Kuhlenkötter, “Learning factories’ trainings as an enabler of proactive workers participation regarding industrie 4.0,” Procedia Manufacturing, pp. 354– 360, 2017.
[4] F. Padula and V. Perdereau, “An on-line path planner for industrial manipulators,” International Journal of Advanced Robotic Systems, January 2013.
[5] J. Zhao, Y. Chao and Y. Yuan, “A cooperative obstacle-avoidance approach for two-manipulator based on A* algorithm,” International Conference on Intelligent Robotics and Applications (ICIRA), pp. 16-25, 2019.
[6] H. Choset and J. Latombe, “Principles of robot motion: theory, algorithms, and implementations
[Book Review],” IEEE Robotics & Automation Magazine, vol. 12, 2005.
[7] K. H. Kim, S. Sin and W. Lee, “Exploring 3D shortest distance using A* algorithm in unity3d,” TechArt: Journal of Arts and Imaging Science, vol.2, no. 3, pp. 81-85, August 2015.
[8] J. Pan and D. Manocha, “Efficient configuration space construction and optimization for motion planning,” Engineering, vol. 1, no 1, pp 46–57, 2015.
[9] “Multiple cradle launcher,” Roketsan Missiles Inc., www.roketsan.com.tr/wpcontent/uploads/2013/05/ IDEX-1.pdf (last accessed: April-2021).
[10] Implementing multi-turret and twin-barrel support with a 3rd soviet heavy line, 2015, Retrieved from http://ritastatusreport.blogspot.com/ 2015/12/implementing-multi-turret-and-twin_16.html
[11] O. Khatib, “Real-Time Obstacle Avoidance for Manipulators and Mobile Robots” in Proceedings - IEEE International Conference on Robotics and Automation, 1985.
[12] T. Lozano-Pérez, M. A. Wesley, “An algorithm for planning collision-free paths among polyhedral obstacles,” Commun of the ACM, vol. 22, no. 10, pp. 560-570, 1979.
[13] T. Lozano-Pérez, “Automatic planning of manipulator transfer movements,” IEEE Transactions on Systems, Man and Cybernetics, vol. 11, no. 10, pp. 681–98, October 1981.
[14] G. K. Lin and T. Lozano-Perez, “Spatial Planning: A Configuration Space Approach,” Ieee Transactions On Computers, vol. 32, 1983.
[15] P. Jiménez, F. Thomas, and C. Torras, “3d collision detection: a survey,” Computers & Graphics, vol. 25, no. 2, pp. 269-285, 2001.
[16] T. Liski, 3-D collision checking for improving machine operator's spatial awareness (Master Thesis), Aalto University-School of Electrical Engineering, Finland, 2014.
[17] W. Wu, H. Zhu, X. Zhuang, G. Ma and Y. Cai, “A multi-shell cover algorithm for contact detection in the three-dimensional discontinuous deformation analysis,” Theoretical and Applied Fracture Mechanics, vol. 72, no. 1, pp. 136–49, 2014.
[18] J. Klein and G. Zachmann, “Point cloud collision detection,” Computer Graphics Forum, vol. 23, no. 3, pp. 567-576, 2004.
[19] G. Zachmann, “Minimal Hierarchical Collision Detection,” ACM Symposium on Virtual Reality Software and Technology, Proceedings, VRST, 121–28, 2002.
[20] M. Figueiredo, J. Oliveira, B. Araújo, J. Pereira, “An efficient collision detection algorithm for point cloud models,” 20th International Conference on Computer Graphics and Vision, GraphiCon'2010 - Conference Proceedings, 2010.
[21] J. Han, “An efficient approach to 3D path planning,” Information Sciences, vol. 478, pp. 318–30, April 2019.
[22] M. Likhachev, D. Ferguson, G. Gordon, A. Stentz, S. Thrun, “Anytime Dynamic A*: An Anytime, Replanning Algorithm,” in ICAPS 2005 - Proceedings of the 15th International Conference on Automated Planning and Scheduling, 2005.
[23] J. J. Kuffner, S. LaValle, “RRT-connect: An efficient approach to single-query path planning”, In: Proceedings of IEEE International Conference on Robotics and Automation, 995–1001, 2000.
[24] L. Kavraki, P. Svestka, J. C. Latombe and M. Overmars, “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” IEEE Trans. Robot. Autom., vol. 12, no. 4, pp. 566–580, August 1996.
[25] D. Henrich, C. Wurll, H. Worn, “Online path planning with optimal c-space discretization,” Proceedings of the 1998 IEEE/RSJ International Conference on Robots and System, Victoria, BC, Canada, pp. 1479–84, 1998.