Path-Planning Algorithm for Automated Pavement Crack Sealing Based on Postman Problems
Publication: Journal of Transportation Engineering, Part B: Pavements
Volume 150, Issue 4
Abstract
Cracks exist in many civil infrastructures, such as road and bridge deck surfaces, parking lots, and building surfaces. To prevent crack growth and further deterioration, it is necessary to fill these cracks with appropriate materials in a timely manner. To improve maintenance efficiency, many machines that automatically complete sealing work have been developed in construction and maintenance areas. However, most current path-planning algorithms used in machines are based on transverse and longitudinal cracks with relatively simple shape. This article presents a new path-planning algorithm for complex cracks that is used for automatic pavement crack-sealing systems. Information about the crack binary map is extracted from the actual crack image using our previous research work as a guide. Crack information is extracted and complex cracks are classified based on graph theory. The path-planning problem of connected cracks is then simplified to the Chinese Postman Problem, and the path-planning problem of unconnected cracks is simplified to the Rural Postman Problem. Finally, the feasibility of using the algorithm to deal with complex cracks is verified at the software level. The results indicate that the proposed algorithm has lower complexity and greater efficiency.
Get full access to this article
View all available purchase options and get full access to this article.
Data Availability Statement
All data, models, or code that support the findings of this study are available from the corresponding author upon reasonable request.
Acknowledgments
The study presented in this article was partially supported by the National Key Research and Development Program of China (2021YFB2601000), National Natural Science Foundation of China (52078049 and 52378431), Natural Science Foundation of Shaanxi Province (2022JM193), Fundamental Research Funds for the Central Universities, CHD (300102210302 and 300102210118), and the 111 Project of Sustainable Transportation for Urban Agglomerations in Western China (B20035).
References
Awuah, F. K. A., and A. Garcia-Hernández. 2022. “Machine-filling of cracks in asphalt concrete.” Autom. Constr. 141 (Sep): 104463. https://doi.org/10.1016/j.autcon.2022.104463.
Bennett, D. A., X. Feng, and S. A. Velinsky. 2003. “Robotic machine for highway crack sealing.” Transp. Res. Rec. 1827 (1): 18–26. https://doi.org/10.3141/1827-03.
Edmonds, J. 1965. “The Chinese postman problem.” Oper. Res. 13 (1): 373.
Edmonds, J., and E. L. Johnson. 1973. “Matching, Euler tours and the Chinese postman.” Math. Program. 5 (1): 88–124. https://doi.org/10.1007/BF01580113.
Feng, X., R. Mathurin, and S. A. Velinsky. 2005. “Practical, interactive, and object-oriented machine vision for highway crack sealing.” J. Transp. Eng. 131 (6): 451–459. https://doi.org/10.1061/(ASCE)0733-947X(2005)131:6(451).
Gasparetto, A., P. Boscariol, A. Lanzutti, and R. Vidoni. 2015. “Path planning and trajectory planning algorithms: A general overview.” In Motion and operation planning of robotic systems, 3–27. Cham, Switzerland: Springer.
Haas, C. 1996. “Evolution of an automated crack sealer: A study in construction technology development.” Autom. Constr. 4 (4): 293–305. https://doi.org/10.1016/0926-5805(95)00010-0.
Haas, C., and C. Hendrickson. 1990. “Computer based model of pavement surfaces.” Transp. Res. Rec. 1206 (1): 91–98.
Haas, C., C. Hendrickson, S. McNeil, and D. Bullock. 1992. “A field prototype of a robotic pavement crack sealing system.” In Proc., 9th ISARC Int. Symp. on Automation and Robotics in Construction, 313–322. Edinburgh, UK: International Association for Automation and Robotics in Construction. https://doi.org/10.22260/ISARC1992/0040.
Hart, P., N. Nilsson, and B. Raphael. 1968. “A formal basis for the heuristic determination of minimum cost paths.” IEEE Trans. Syst. Sci. Cybern. 4 (2): 100–107. https://doi.org/10.1109/TSSC.1968.300136.
Hilditch, C. J. 1969. “Linear skeletons from square cupboards.” In Machine intelligence 4, edited by B. Meltzer and D. Michie, 403–420. Edinburgh, UK: Edinburgh University Press.
Holmberg, K. 2010. “Heuristics for the rural postman problem.” Comput. Oper. Res. 37 (5): 981–990. https://doi.org/10.1016/j.cor.2009.08.004.
Kayhani, N., H. Taghaddos, A. Mousaei, S. Behzadipour, and U. Hermann. 2021. “Heavy mobile crane lift path planning in congested modular industrial plants using a robotics approach.” Autom. Constr. 122 (Feb): 103508. https://doi.org/10.1016/j.autcon.2020.103508.
Kim, S., H. Jin, M. Seo, and D. Har. 2019. “Optimal path planning of automated guided vehicle using dijkstra algorithm under dynamic conditions.” In Proc., 7th Int. Conf. on Robot Intelligence Technology and Applications (RiTA), 231–236. New York: IEEE.
Kim, Y. S., and C. T. Haas. 2000. “A model for automation of infrastructure maintenance using representational forms.” Autom. Constr. 10 (1): 57–68. https://doi.org/10.1016/S0926-5805(99)00028-X.
Kim, Y. S., H. S. Yoo, J. H. Lee, and S. W. Han. 2009. “Chronological development history of X–Y table based pavement crack sealers and research findings for practical use in the field.” Autom. Constr. 18 (5): 513–524. https://doi.org/10.1016/j.autcon.2009.02.007.
Kim, Y.-S., and C. T. Haas. 2002. “A man-machine balanced rapid object model for automation of pavement crack sealing and maintenance.” Can. J. Civ. Eng. 29 (3): 459–474. https://doi.org/10.1139/l02-018.
Kim, Y.-S., C. T. Haas, and R. Greer. 1998. “Path planning for machine vision assisted, teleoperated pavement crack sealer.” J. Transp. Eng. 124 (2): 137–143. https://doi.org/10.1061/(ASCE)0733-947X(1998)124:2(137).
Kirsch, C., and C. Röhrig. 2011. “Global localization and position tracking of an automated guided vehicle.” IFAC Proc. Vol. 44 (1): 14036–14041. https://doi.org/10.3182/20110828-6-IT-1002.01245.
Lawrence, S., C. L. Giles, A. C. Tsoi, and A. D. Back. 1997. “Face recognition: A convolutional neural-network approach.” IEEE Trans. Neural Networks 8 (1): 98–113. https://doi.org/10.1109/72.554195.
Lee, J.-H., H.-S. Yoo, Y.-S. Kim, J.-B. Lee, and M.-Y. Cho. 2006. “The development of a machine vision-assisted, teleoperated pavement crack sealer.” Autom. Constr. 15 (5): 616–626. https://doi.org/10.1016/j.autcon.2005.06.018.
Li, H., D. Song, Y. Liu, and B. Li. 2019. “Automatic pavement crack detection by multi-scale image fusion.” IEEE Trans. Intell. Transp. Syst. 20 (6): 2025–2036. https://doi.org/10.1109/TITS.2018.2856928.
Liu, J., X. Yang, S. Lau, X. Wang, S. Luo, V. C. S. Lee, and L. Ding. 2020. “Automated pavement crack detection and segmentation based on two-step convolutional neural network.” Comput.-Aided Civ. Infrastruct. Eng. 35 (11): 1291–1305. https://doi.org/10.1111/mice.12622.
Liu, J., X. Yang, X. Wang, and J. W. Yam. 2021. “A laboratory prototype of automatic pavement crack sealing based on a modified 3D printer.” Int. J. Pavement Eng. 23 (9): 2969–2980. https://doi.org/10.1080/10298436.2021.1875225.
Mousa, M., M. A. Elseifi, M. Bashar, Z. Zhang, and K. Gaspard. 2018. “Field evaluation and cost effectiveness of crack sealing in flexible and composite pavements.” Transp. Res. Rec. 2672 (12): 51–61. https://doi.org/10.1177/0361198118767417.
Orloff, C. S. 1974. “A fundamental problem in vehicle routing.” Networks 4 (1): 35–64. https://doi.org/10.1002/net.3230040105.
Seokjoo, Y., K. Kyu Hyuk, S. Min Hoi, Y. John Seon Keun, O. Semin, S. Jong Tae, J. Eui-Jung, and Y. Byung-Ju. 2012. “Path planning of a four-legged robot system for crack diagnosis of rib structure of airplane wings.” In Proc., 9th Int. Conf. on Ubiquitous Robots and Ambient Intelligence (URAI), 332–334. New York: IEEE.
Simonyan, K., and A. Zisserman. 2015. “Very deep convolutional networks for large-scale image recognition.” Preprint, submitted September 4, 2014. http://arxiv.org/abs/11409.1556.
Stentz, A. 1994. “Optimal and efficient path planning for partially-known environments.” In Vol. 4 of Proc., IEEE Int. Conf. on Robotics and Automation, 3310–3317. New York: IEEE.
Tsai, Y., V. Kaul, and A. Yezzi. 2013. “Automating the crack map detection process for machine operated crack sealer.” Autom. Constr. 31 (May): 10–18. https://doi.org/10.1016/j.autcon.2012.11.033.
Vargas-Nordcbeck, A., and F. Jalali. 2020. “Life-extending benefit of crack sealing for pavement preservation.” Transp. Res. Rec. 2674 (1): 272–281. https://doi.org/10.1177/0361198120902703.
Velinsky, S. A. 1993. “Heavy vehicle system for automated pavement crack sealing.” Int. J. Heavy Veh. Syst. 1 (1): 114–128. https://doi.org/https://doi.org/10.1504/IJHVS.1993.054653.
Velinsky, S. A., X. Feng, and D. A. Bennett. 2003. “Operator controlled, vehicle-based highway crack-sealing machine.” Int. J. Heavy Veh. Syst. 10 (3): 145–166. https://doi.org/10.1504/IJHVS.2003.003204.
Yoo, H.-S., and Y.-S. Kim. 2012. “Development of an optimal trajectory planning algorithm for an automated pavement crack sealer.” J. Constr. Eng. Project Manage. 2 (1): 35–44. https://doi.org/10.6106/JCEPM.2012.2.1.035.
Zhang, A., K. C. P. Wang, B. Li, E. Yang, X. Dai, Y. Peng, Y. Fei, Y. Liu, J. Q. Li, and C. Chen. 2017. “Automated pixel-level pavement crack detection on 3D asphalt surfaces using a deep-learning network.” Comput.-Aided Civ. Infrastruct. Eng. 32 (10): 805–819. https://doi.org/10.1111/mice.12297.
Zhang, H.-Y., W.-M. Lin, and A.-X. Chen. 2018. “Path planning for the mobile robot: A review.” Symmetry 10 (10): 450. https://doi.org/10.3390/sym10100450.
Zhang, J., X. Yang, W. Wang, J. Guan, L. Ding, and V. C. S. Lee. 2023. “Automated guided vehicles and autonomous mobile robots for recognition and tracking in civil engineering.” Autom. Constr. 146 (Feb): 104699. https://doi.org/10.1016/j.autcon.2022.104699.
Zhu, G., et al. 2019. “Design and implementation of a manipulator system for roadway crack sealing.” In Proc., IEEE 9th Annual Int. Conf. on CYBER Technology in Automation, Control, and Intelligent Systems (CYBER), 1327–1331. New York: IEEE.
Information & Authors
Information
Published In
Copyright
© 2024 American Society of Civil Engineers.
History
Received: Sep 22, 2023
Accepted: Feb 3, 2024
Published online: Sep 23, 2024
Published in print: Dec 1, 2024
Discussion open until: Feb 23, 2025
ASCE Technical Topics:
- Algorithms
- Automation and robotics
- Bridge components
- Bridge decks
- Bridge engineering
- Construction engineering
- Construction equipment
- Construction methods
- Continuum mechanics
- Cracking
- Decks
- Engineering fundamentals
- Engineering mechanics
- Equipment and machinery
- Fracture mechanics
- Gravels
- Infrastructure
- Mathematics
- Pavement condition
- Pavements
- Sealing
- Solid mechanics
- Structural engineering
- Structural systems
- Systems engineering
- Transportation engineering
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.