Optimized Mobile Crane Path Planning in Discretized Polar Space
Publication: Journal of Construction Engineering and Management
Volume 147, Issue 5
Abstract
Improper planning and management of heavy lifts is a major cause of cost overruns, delays, and, more importantly, safety incidents in industrial megaprojects. Automated lift planning is widely acknowledged as an effective solution. This research presents an automated lift path planning system for mobile cranes leveraging space discretization and an obstacle-avoidance technique from robotics. The proposed method treats the lifted object as a three-degree-of-freedom convex traveling through the surrounding environment [a given two-dimensional (2D) elevation] with discretized rotational and translational motions in polar coordinates. It efficiently finds the best feasible pick location and optimized collision-free lift path in the polar coordinate system to the set location. This system is a state-of-the art advancement in crane path planning because it mimics the crane’s intrinsic behavior and generates paths considering cost functions for safety, practicality, and economic objectives to enable its implementation in real practice settings. Illustrative examples are presented to verify the proposed approach and demonstrate its superiority over past similar path planning systems in terms of optimality and operational ease.
Get full access to this article
View all available purchase options and get full access to this article.
Data Availability Statement
Some or all data, models, or codes that support the findings of this study are available from the corresponding author upon reasonable request.
Acknowledgments
The support of PCL Industrial Management Inc. and the Tecnosa R&D Center to accomplish this research is greatly appreciated.
References
Ajmal Deen Ali, M. S., N. Ramesh Babu, and K. Varghese. 2005. “Collision free path planning of cooperative crane manipulators using genetic algorithm.” J. Comput. Civ. Eng. 19 (2): 182. https://doi.org/10.1061/(ASCE)0887-3801(2005)19:2(182).
AlBahnassi, H., and A. Hammad. 2012. “Near real-time motion planning and simulation of cranes in construction: Framework and system architecture.” J. Comput. Civ. Eng. 26 (1): 54–63. https://doi.org/10.1061/(ASCE)CP.1943-5487.0000123.
Al-Hussein, M., S. Alkass, and O. Moselhi. 2005. “Optimization algorithm for selection and on site location of mobile cranes.” J. Constr. Eng. Manage. 131 (5): 579–590. https://doi.org/10.1061/(ASCE)0733-9364(2005)131:5(579).
Al-Hussein, M., M. Athar Niaz, H. Yu, and H. Kim. 2006. “Integrating 3D visualization and simulation for tower crane operations on construction sites.” Autom. Constr. 15 (5): 554–562. https://doi.org/10.1016/j.autcon.2005.07.007.
Cai, P., Y. Cai, I. Chandrasekaran, and J. Zheng. 2016. “Parallel genetic algorithm based automatic path planning for crane lifting in complex environments.” Autom. Constr. 62 (Feb): 133–147. https://doi.org/10.1016/j.autcon.2015.09.007.
Chang, Y.-C., W.-H. Hung, and S.-C. Kang. 2012. “A fast path planning method for single and dual crane erections.” Autom. Constr. 22 (Mar): 468–480. https://doi.org/10.1016/j.autcon.2011.11.006.
Chen, A. Y., F. Peña-Mora, and Y. Ouyang. 2011. “A collaborative GIS framework to support equipment distribution for civil engineering disaster response operations.” Autom. Constr. 20 (5): 637–648. https://doi.org/10.1016/j.autcon.2010.12.007.
Cheng, M.-Y., and G.-L. Chang. 2001. “Automating utility route design and planning through GIS.” Autom. Constr. 10 (4): 507–516. https://doi.org/10.1016/S0926-5805(00)00103-5.
Choi, Y., and A. Nieto. 2011. “Optimal haulage routing of off-road dump trucks in construction and mining sites using Google Earth and a modified least-cost path algorithm.” Autom. Constr. 20 (7): 982–997. https://doi.org/10.1016/j.autcon.2011.03.015.
Cormen, T. H., C. E. Leiserson, R. L. Rivest, and C. Stein. 2009. Introduction to algorithms. Cambridge, MA: MIT Press.
Dijkstra, E. W. 1959. “A note on two problems in connexion with graphs.” Numer. Math. 1 (1): 269–271. https://doi.org/10.1007/bf01386390.
Fredman, M. L., and R. E. Tarjan. 1987. “Fibonacci heaps and their uses in improved network optimization algorithms.” J. ACM 34 (3): 596–615. https://doi.org/10.1145/28869.28874.
Han, S. H., S. Hasan, A. Bouferguène, M. Al-Hussein, and J. Kosa. 2015. “Utilization of 3D visualization of mobile crane operations for modular construction on-site assembly.” J. Manage. Eng. 31 (5): 04014080. https://doi.org/10.1061/(ASCE)ME.1943-5479.0000317.
Hanna, A. S., and W. B. Lotfallah. 1999. “A fuzzy logic approach to the selection of cranes.” Autom. Constr. 8 (5): 597–608. https://doi.org/10.1016/S0926-5805(99)00009-6.
Kang, S., and E. Miranda. 2006. “Planning and visualization for automated robotic crane erection processes in construction.” Autom. Constr. 15 (4): 398–414. https://doi.org/10.1016/j.autcon.2005.06.008.
Kang, S.-C., H.-L. Chi, and E. Miranda. 2009. “Three-dimensional simulation and visualization of crane assisted construction erection processes.” J. Comput. Civ. Eng. 23 (6): 363–371. https://doi.org/10.1061/(ASCE)0887-3801(2009)23:6(363).
Kayhani, N., H. Taghaddos, and S. Behzadipour. 2018. “Construction equipment collision-free path planning using robotic approach.” In Proc., 35th Int. Symp. on Automation and Robotics in Construction (ISARC), 1220–1225. Berlin: International Association for Automation and Robotics in Construction.
Lei, Z., S. Behzadipour, M. Al-Hussein, and U. Hermann. 2011. “Application of robotic obstacle avoidance in crane lift path planning.” In Proc., 28th Int. Symp. on Automation and Robotics in Construction (ISARC), 292–297. Seoul: International Association for Automation and Robotics in Construction.
Lei, Z., S. Han, A. Bouferguène, H. Taghaddos, U. Hermann, and M. Al-Hussein. 2014. “Algorithm for mobile crane walking path planning in congested industrial plants.” J. Constr. Eng. Manage. 141 (2): 05014016. https://doi.org/10.1061/(ASCE)CO.1943-7862.0000929.
Lei, Z., H. Taghaddos, U. Hermann, and M. Al-Hussein. 2013a. “A methodology for mobile crane lift path checking in heavy industrial projects.” Autom. Constr. 31 (May): 41–53. https://doi.org/10.1016/j.autcon.2012.11.042.
Lei, Z., H. Taghaddos, J. Olearczyk, M. Al-Hussein, and U. Hermann. 2013b. “Automated method for checking crane paths for heavy lifts in industrial projects.” J. Constr. Eng. Manage. 139 (10): 04013011. https://doi.org/10.1061/(ASCE)CO.1943-7862.0000740.
Li, H., Z. Chen, L. Yong, and S. C. W. Kong. 2005. “Application of integrated GPS and GIS technology for reducing construction waste and improving construction efficiency.” Autom. Constr. 14 (3): 323–331. https://doi.org/10.1016/j.autcon.2004.08.007.
Lin, Y., D. Wu, X. Wang, X. Wang, and S. Gao. 2012. “Statics-based simulation approach for two-crane lift.” J. Constr. Eng. Manage. 138 (10): 1139–1149. https://doi.org/10.1061/(ASCE)CO.1943-7862.0000526.
Lin, Y., D. Wu, X. Wang, X. Wang, and S. Gao. 2014. “Lift path planning for a nonholonomic crawler crane.” Autom. Constr. 44 (Aug): 12–24. https://doi.org/10.1016/j.autcon.2014.03.007.
Lin, Y., H. Yu, G. Sun, and P. Shi. 2016. “Lift path planning without prior picking/placing configurations: Using crane location regions.” J. Comput. Civ. Eng. 30 (1): 04014109. https://doi.org/10.1061/(ASCE)CP.1943-5487.0000437.
Lozano, P. 1983. “Spatial planning: A configuration space approach.” IEEE Trans. Comput. 32 (2): 108–120. https://doi.org/10.1109/TC.1983.1676196.
Mrena, M., P. Sedlacek, and M. Kvassay. 2019. “Practical applicability of advanced implementations of priority queues in finding shortest paths.” In Proc., 2019 Int. Conf. on Information and Digital Technologies (IDT), 335–344. New York: IEEE.
Nekouvaght Tak, A., H. Taghaddos, A. Mousaei, and U. Hermann. 2020. “Evaluating industrial modularization strategies: Local vs. overseas fabrication.” Autom. Constr. 114 (Jun): 103175. https://doi.org/10.1016/j.autcon.2020.103175.
Olearczyk, J., M. Al-Hussein, and A. Bouferguène. 2014. “Evolution of the crane selection and on-site utilization process for modular construction multilifts.” Autom. Constr. 43 (Jul): 59–72. https://doi.org/10.1016/j.autcon.2014.03.015.
Reddy, H. R., and K. Varghese. 2002. “Automated path planning for mobile crane lifts.” Comput.-Aided Civ. Infrastruct. Eng. 17 (6): 439–448. https://doi.org/10.1111/0885-9507.00005.
Safouhi, H., M. Mouattamid, U. Hermann, and A. Hendi. 2011. “An algorithm for the calculation of feasible mobile crane position areas.” Autom. Constr. 20 (4): 360–367. https://doi.org/10.1016/j.autcon.2010.11.006.
Sawhney, A., and A. Mund. 2002. “Adaptive probabilistic neural network-based crane type selection system.” J. Constr. Eng. Manage. 128 (3): 265–273. https://doi.org/10.1061/(ASCE)0733-9364(2002)128:3(265).
Sivakumar, P., K. Varghese, and N. R. Babu. 2003. “Automated path planning of cooperative crane lifts using heuristic search.” J. Comput. Civ. Eng. 17 (3): 197–207. https://doi.org/10.1061/(ASCE)0887-3801(2003)17:3(197).
Taghaddos, H., S. AbouRizk, Y. Mohamed, and U. Hermann. 2010. “Simulation-based multiple heavy lift planning in industrial construction.” In Proc., Construction Research Congress 2010: Innovation for Reshaping Construction Practice, 349–358. Reston, VA: ASCE.
Taghaddos, H., A. Eslami, U. Hermann, S. AbouRizk, and Y. Mohamed. 2019. “Auction-based simulation for industrial crane operations.” Autom. Constr. 104 (Aug): 107–119. https://doi.org/10.1016/j.autcon.2019.03.015.
Taghaddos, H., U. Hermann, and A. Abbasi. 2018. “Automated crane planning and optimization for modular construction.” Autom. Constr. 95 (Nov): 219–232. https://doi.org/10.1016/j.autcon.2018.07.009.
Wang, X., Y. Y. Zhang, D. Wu, and S. Gao. 2011. “Collision-free path planning for mobile cranes based on ant colony algorithm.” Key Eng. Mater. 467–469 (Feb): 1108–1115. https://doi.org/10.4028/www.scientific.net/KEM.467-469.1108.
Wu, D., Y. Lin, X. Wang, X. Wang, and S. Gao. 2011. “Algorithm of crane selection for heavy lifts.” J. Comput. Civ. Eng. 25 (1): 57–65. https://doi.org/10.1061/(ASCE)CP.1943-5487.0000065.
Yang, L., J. Qi, D. Song, J. Xiao, J. Han, and Y. Xia. 2016. “Survey of robot 3D path planning algorithms.” J. Control Sci. Eng. 2016 (Jul): 1–22. https://doi.org/10.1155/2016/7426913.
Yeoh, J. K. W., and D. K. H. Chua. 2017. “Optimizing crane selection and location for multistage construction using a four-dimensional set cover approach.” J. Constr. Eng. Manage. 143 (8): 04017029. https://doi.org/10.1061/(ASCE)CO.1943-7862.0001318.
Zhang, C., and A. Hammad. 2012. “Improving lifting motion planning and re-planning of cranes with consideration for safety and efficiency.” Adv. Eng. Inf. 26 (2): 396–410. https://doi.org/10.1016/j.aei.2012.01.003.
Information & Authors
Information
Published In
Journal of Construction Engineering and Management
Volume 147 • Issue 5 • May 2021
Copyright
© 2021 American Society of Civil Engineers.
History
Received: Mar 13, 2020
Accepted: Nov 23, 2020
Published online: Mar 13, 2021
Published in print: May 1, 2021
Discussion open until: Aug 13, 2021
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.