Real world design and implementation of pathfinding sewer inspection robot using a-star algorithm
Article Sidebar
Published:
May 30, 2023
Keywords:
A Star Algorithm , Application of Graph Theory , Autonomous Navigationt, Pathfinding Algorithm , Sewer Inspection Robo
Section
Computer Science
Statistics Article
Article View : 264 Times
Main Article Content
Abstract
This paper presents the design and implementation of a sewer inspection robot that utilizes the A-Star algorithm for pathfinding. The robot is intended to provide a more efficient solution for culvert workers in inspecting sewer pipes, particularly in hard-to-reach areas. The A-Star algorithm was chosen due to its ease of implementation and low computational resource requirements, making it suitable for real-time applications. The robot was designed with a modular approach, allowing for flexibility in adapting to different pipe sizes and configurations. It is equipped with various sensors and cameras, allowing for accurate inspection of pipe conditions and identification of potential issues. The A-Star algorithm was used to plan the robot's path through the sewer pipes, minimizing the time required for inspection and reducing the risk of damage to the pipes. The results of the implementation showed that the sewer inspection robot using the A-Star algorithm was able to efficiently navigate through the sewer pipes, reducing the time required for inspection and minimizing the need for manual labor. In order to check the performance, we performed experiments on six test models through simulation. On average, the proposed algorithm showed remarkable results, where all models can generate path planning to find the target from the start position. We obtained an average time completion from Models 1 to 6 with a maximum travel distance of 30 meters of 12.96, 4.47, 18.59, 20.71, 24.93, and 19.34 seconds.
Downloads
Download data is not yet available.
Article Details
How to Cite
Rumaksari, A., Adri Gabriel Sooai, Gloria Song Abimanyu, Gunawan Dewantoro, Hartanto Kusuma Wardana, Budihardja Murtianta and Lukas Bambang Setyawan (2023) “Real world design and implementation of pathfinding sewer inspection robot using a-star algorithm”, Jurnal Mantik, 7(1), pp. 202-215. doi: 10.35335/mantik.v7i1.3702.
References
Aitken, J. M., Evans, M. H., Worley, R., Edwards, S., Zhang, R., Dodd, T., Mihaylova, L., & Anderson, S. R. (2021). Simultaneous Localization and Mapping for Inspection Robots in Water and Sewer Pipe Networks: A Review. In IEEE Access (Vol. 9, pp. 140173–140198). Institute of Electrical and Electronics Engineers Inc. https://doi.org/10.1109/ACCESS.2021.3115981
Alhadi, S., Rianmora, S., & Phlernjai, M. (2021). Conceptual Design and Analysis of Small Power Station for Supporting Unmanned Aerial Vehicle (UAV) Deployment. Engineering Journal, 25(8), 51–71. https://doi.org/10.4186/ej.2021.25.8.51
Alyasin, A., Abbas, E. I., & Hasan, S. D. (2019). An Efficient Optimal Path Finding for Mobile Robot Based on Dijkstra Method. 4th Scientific International Conference Najaf, SICN 2019, 11–14. https://doi.org/10.1109/SICN47020.2019.9019345
Cai, Y., Xi, Q., Xing, X., Gui, H., & Liu, Q. (2019). Path planning for UAV tracking target based on improved A-star algorithm. 1st International Conference on Industrial Artificial Intelligence, IAI 2019, 1–6. https://doi.org/10.1109/ICIAI.2019.8850744
Ciszewski, M., Buratowski, T., & Giergiel, M. (2018). Modeling, Simulation and Control of a Pipe Inspection Mobile Robot with an Active Adaptation System. IFAC-PapersOnLine, 51(22), 132–137. https://doi.org/10.1016/j.ifacol.2018.11.530
Darmawan, A., Ratnadewi, R., & Prijono, A. (2023). Designing a wireless robot plotter as a supporting tool for understanding logical thinking. Jurnal Mantik, 7(1), 155–167. https://doi.org/10.35335/MANTIK.V7I1.3640
Edelkamp, Stefan;Schrödl, S. (2012). Heuristic Search: Theory and Applications (D. Roumeliotis, Rachel; Bevans (Ed.)). Morgan Kaufmann?: Elsevier Inc. https://doi.org/10.1016/C2009-0-16511-X
Gunawan, S. A., Pratama, G. N. P., Cahyadi, A. I., Winduratna, B., Yuwono, Y. C. H., & Wahyunggoro, O. (2019). Smoothed a-star algorithm for nonholonomic mobile robot path planning. 2019 International Conference on Information and Communications Technology, ICOIACT 2019, 654–658. https://doi.org/10.1109/ICOIACT46704.2019.8938467
Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths. In IEEE Transactions on Systems Science and Cybernetics (Vol. 4, Issue 2, pp. 100–107). https://doi.org/10.1109/TSSC.1968.300136
Hu, T. C., Kahng, A. B., & Robins, G. (1993). Optimal Robust Path Planning in General Environments. IEEE Transactions on Robotics and Automation, 9(6), 775–784. https://doi.org/10.1109/70.265921
Ismail, I. M., & Agwu, N. N. (2019, February 4). Influence of heuristic functions on real-time heuristic search methods. 14th International Conference on Electronics Computer and Computation, ICECCO 2018. https://doi.org/10.1109/ICECCO.2018.8634782
Jiang, C., Meng, Q., Xu, B., Gao, W., Wu, P., Guan, L., Li, Z., Zheng, S., Wang, J., Rizos, C., Ding, W., & El-Mowafy, A. (2023). Simultaneous Localization and Mapping (SLAM) for Autonomous Driving: Concept and Analysis. Remote Sensing 2023, Vol. 15, Page 1156, 15(4), 1156. https://doi.org/10.3390/RS15041156
Kim, C., & Kim, C.-J. (2023). Development of Autonomous Driving and Motion Control System for a Patient Transfer Robot. Actuators, 12(3), 106. https://doi.org/10.3390/ACT12030106
Lai, X., Li, J. H., & Chambers, J. (2021). Enhanced Center Constraint Weighted A* Algorithm for Path Planning of Petrochemical Inspection Robot. Journal of Intelligent and Robotic Systems: Theory and Applications, 102(4), 1–15. https://doi.org/10.1007/s10846-021-01437-8
Leng, X., & Chanson, H. (2020). Hybrid modelling of low velocity zones in box culverts to assist fish passage: Why simple is better! In River Research and Applications (Vol. 36, Issue 9, pp. 1765–1777). John Wiley & Sons, Ltd. https://doi.org/10.1002/rra.3710
Li, J., Zhang, W., Hu, Y., Fu, S., Liao, C., & Yu, W. (2023). RJA-Star Algorithm for UAV Path Planning Based on Improved R5DOS Model. Applied Sciences (Switzerland), 13(2). https://doi.org/10.3390/app13021105
Li, X., Hu, X., Wang, Z., & Du, Z. (2020). Path planning based on combination of improved A-STAR Algorithm and DWA algorithm. Proceedings - 2020 2nd International Conference on Artificial Intelligence and Advanced Manufacture, AIAM 2020, 99–103. https://doi.org/10.1109/AIAM50918.2020.00025
Li, Y., Dong, D., & Guo, X. (2020). Mobile robot path planning based on improved genetic algorithm with A-star heuristic method. 1306–1311. https://doi.org/10.1109/ITAIC49862.2020.9338968
Liu, C., Mao, Q., Chu, X., & Xie, S. (2019). An Improved A-star algorithm considering water current, traffic separation and berthing for vessel path planning. Applied Sciences (Switzerland), 9(6), 1057. https://doi.org/10.3390/app9061057
Liu, X., & Gong, D. (2011). A comparative study of A-star algorithms for search and rescue in perfect maze. 2011 International Conference on Electric Information and Control Engineering, ICEICE 2011 - Proceedings, 24–27. https://doi.org/10.1109/ICEICE.2011.5777723
Montes, C., Kapelan, Z., & Saldarriaga, J. (2019). Impact of self-cleansing criteria choice on the optimal design of sewer networks in South America. Water (Switzerland), 11(6), 1148. https://doi.org/10.3390/w11061148
MOUNIS, S. Y. A., AZLAN, N. Z., & ZAKIA, H. (2022). Design and Control of a Robotic Device for Upper Limb Rehabilitation Therapy. Journal of Engineering Science and Technology, 17(2), 1306–1327.
Ni, Y., Yang, X., Cheng, Y., Dong, Z., & Tang, M. (2021). Machine Vision based Grabbing Objects with Manipulator System Design. Engineering Journal, 25(2), 327–334. https://doi.org/10.4186/ej.2021.25.2.327
Ross, R., Stumpf, A., Barnett, D., & Hall, R. (2021). Condition assessment for concrete sewer pipes using displacement probes: A robotic design case study. Robotics, 10(2), 64. https://doi.org/10.3390/robotics10020064
Rumaksari, A. N. (2019). Vehicle Classification using IPCP and EsKNN Algorithm for Surveillance Camera. Techné?: Jurnal Ilmiah Elektroteknika, 18(01), 15–30. https://doi.org/10.31358/techne.v18i01.181
Russell, Stuart; Norvig, P. (2021). Artificial Intelligence: A Modern Approach, 4th US ed. Pearson. http://aima.cs.berkeley.edu/
Sedighi, S., Nguyen, D. Van, & Kuhnert, K. D. (2019). Guided Hybrid A-star Path Planning Algorithm for Valet Parking Applications. 2019 5th International Conference on Control, Automation and Robotics, ICCAR 2019, 570–575. https://doi.org/10.1109/ICCAR.2019.8813752
Shang, E., Dai, B., Nie, Y., Zhu, Q., Xiao, L., & Zhao, D. (2020). A Guide-line and Key-point based A-star Path Planning Algorithm for Autonomous Land Vehicles. 2020 IEEE 23rd International Conference on Intelligent Transportation Systems, ITSC 2020, 1–7. https://doi.org/10.1109/ITSC45102.2020.9294336
Sharif, K., & Gormley, M. (2021). Integrating the design of tall building, wastewater drainage systems into the public sewer network: A review of the current state of the art. In Water (Switzerland) (Vol. 13, Issue 22, p. 3242). Multidisciplinary Digital Publishing Institute. https://doi.org/10.3390/w13223242
Tang, G., Tang, C., Claramunt, C., Hu, X., & Zhou, P. (2021). Geometric A-Star Algorithm: An Improved A-Star Algorithm for AGV Path Planning in a Port Environment. IEEE Access, 9, 59196–59210. https://doi.org/10.1109/ACCESS.2021.3070054
Wayahdi, M. R., Ginting, S. H. N., & Syahputra, D. (2021). Greedy, A-Star, and Dijkstra’s Algorithms in Finding Shortest Path. International Journal of Advances in Data and Information Systems, 2(1), 45–52. https://doi.org/10.25008/ijadis.v2i1.1206
Yeo, M. S. K., Ng, A. Q. B., Ng, T. Y. J., Mudiyanselage, S., Samarakoon, B. P., Muthugala, M. A. V. J., Mohan, R. E., & Ng, D. T. (2021). Robot-Inclusive Guidelines for Drain Inspection. 2021 8th International Conference on Information Technology, Computer and Electrical Engineering, ICITACEE 2021, 7–12. https://doi.org/10.1109/ICITACEE53184.2021.9617537
Zeng, W., & Church, R. L. (2009). Finding shortest paths on real road networks: The case for A. International Journal of Geographical Information Science, 23(4), 531–543. https://doi.org/10.1080/13658810801949850
Zhang, Y., Li, L. L., Lin, H. C., Ma, Z., & Zhao, J. (2019). Development of path planning approach using improved a-star algorithm in AGV system. Journal of Internet Technology, 20(3), 915–924. https://doi.org/10.3966/160792642019052003023
Zhang, Z., Wu, J., Dai, J., & He, C. (2022). Optimal path planning with modified A-Star algorithm for stealth unmanned aerial vehicles in 3D network radar environment. Proceedings of the Institution of Mechanical Engineers, Part G: Journal of Aerospace Engineering, 236(1), 72–81. https://doi.org/10.1177/09544100211007381
Zheng, T., Xu, Y., & Zheng, D. (2019). AGV Path Planning based on Improved A-star Algorithm. Proceedings of 2019 IEEE 3rd Advanced Information Management, Communicates, Electronic and Automation Control Conference, IMCEC 2019, 1534–1538. https://doi.org/10.1109/IMCEC46724.2019.8983841
Alhadi, S., Rianmora, S., & Phlernjai, M. (2021). Conceptual Design and Analysis of Small Power Station for Supporting Unmanned Aerial Vehicle (UAV) Deployment. Engineering Journal, 25(8), 51–71. https://doi.org/10.4186/ej.2021.25.8.51
Alyasin, A., Abbas, E. I., & Hasan, S. D. (2019). An Efficient Optimal Path Finding for Mobile Robot Based on Dijkstra Method. 4th Scientific International Conference Najaf, SICN 2019, 11–14. https://doi.org/10.1109/SICN47020.2019.9019345
Cai, Y., Xi, Q., Xing, X., Gui, H., & Liu, Q. (2019). Path planning for UAV tracking target based on improved A-star algorithm. 1st International Conference on Industrial Artificial Intelligence, IAI 2019, 1–6. https://doi.org/10.1109/ICIAI.2019.8850744
Ciszewski, M., Buratowski, T., & Giergiel, M. (2018). Modeling, Simulation and Control of a Pipe Inspection Mobile Robot with an Active Adaptation System. IFAC-PapersOnLine, 51(22), 132–137. https://doi.org/10.1016/j.ifacol.2018.11.530
Darmawan, A., Ratnadewi, R., & Prijono, A. (2023). Designing a wireless robot plotter as a supporting tool for understanding logical thinking. Jurnal Mantik, 7(1), 155–167. https://doi.org/10.35335/MANTIK.V7I1.3640
Edelkamp, Stefan;Schrödl, S. (2012). Heuristic Search: Theory and Applications (D. Roumeliotis, Rachel; Bevans (Ed.)). Morgan Kaufmann?: Elsevier Inc. https://doi.org/10.1016/C2009-0-16511-X
Gunawan, S. A., Pratama, G. N. P., Cahyadi, A. I., Winduratna, B., Yuwono, Y. C. H., & Wahyunggoro, O. (2019). Smoothed a-star algorithm for nonholonomic mobile robot path planning. 2019 International Conference on Information and Communications Technology, ICOIACT 2019, 654–658. https://doi.org/10.1109/ICOIACT46704.2019.8938467
Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths. In IEEE Transactions on Systems Science and Cybernetics (Vol. 4, Issue 2, pp. 100–107). https://doi.org/10.1109/TSSC.1968.300136
Hu, T. C., Kahng, A. B., & Robins, G. (1993). Optimal Robust Path Planning in General Environments. IEEE Transactions on Robotics and Automation, 9(6), 775–784. https://doi.org/10.1109/70.265921
Ismail, I. M., & Agwu, N. N. (2019, February 4). Influence of heuristic functions on real-time heuristic search methods. 14th International Conference on Electronics Computer and Computation, ICECCO 2018. https://doi.org/10.1109/ICECCO.2018.8634782
Jiang, C., Meng, Q., Xu, B., Gao, W., Wu, P., Guan, L., Li, Z., Zheng, S., Wang, J., Rizos, C., Ding, W., & El-Mowafy, A. (2023). Simultaneous Localization and Mapping (SLAM) for Autonomous Driving: Concept and Analysis. Remote Sensing 2023, Vol. 15, Page 1156, 15(4), 1156. https://doi.org/10.3390/RS15041156
Kim, C., & Kim, C.-J. (2023). Development of Autonomous Driving and Motion Control System for a Patient Transfer Robot. Actuators, 12(3), 106. https://doi.org/10.3390/ACT12030106
Lai, X., Li, J. H., & Chambers, J. (2021). Enhanced Center Constraint Weighted A* Algorithm for Path Planning of Petrochemical Inspection Robot. Journal of Intelligent and Robotic Systems: Theory and Applications, 102(4), 1–15. https://doi.org/10.1007/s10846-021-01437-8
Leng, X., & Chanson, H. (2020). Hybrid modelling of low velocity zones in box culverts to assist fish passage: Why simple is better! In River Research and Applications (Vol. 36, Issue 9, pp. 1765–1777). John Wiley & Sons, Ltd. https://doi.org/10.1002/rra.3710
Li, J., Zhang, W., Hu, Y., Fu, S., Liao, C., & Yu, W. (2023). RJA-Star Algorithm for UAV Path Planning Based on Improved R5DOS Model. Applied Sciences (Switzerland), 13(2). https://doi.org/10.3390/app13021105
Li, X., Hu, X., Wang, Z., & Du, Z. (2020). Path planning based on combination of improved A-STAR Algorithm and DWA algorithm. Proceedings - 2020 2nd International Conference on Artificial Intelligence and Advanced Manufacture, AIAM 2020, 99–103. https://doi.org/10.1109/AIAM50918.2020.00025
Li, Y., Dong, D., & Guo, X. (2020). Mobile robot path planning based on improved genetic algorithm with A-star heuristic method. 1306–1311. https://doi.org/10.1109/ITAIC49862.2020.9338968
Liu, C., Mao, Q., Chu, X., & Xie, S. (2019). An Improved A-star algorithm considering water current, traffic separation and berthing for vessel path planning. Applied Sciences (Switzerland), 9(6), 1057. https://doi.org/10.3390/app9061057
Liu, X., & Gong, D. (2011). A comparative study of A-star algorithms for search and rescue in perfect maze. 2011 International Conference on Electric Information and Control Engineering, ICEICE 2011 - Proceedings, 24–27. https://doi.org/10.1109/ICEICE.2011.5777723
Montes, C., Kapelan, Z., & Saldarriaga, J. (2019). Impact of self-cleansing criteria choice on the optimal design of sewer networks in South America. Water (Switzerland), 11(6), 1148. https://doi.org/10.3390/w11061148
MOUNIS, S. Y. A., AZLAN, N. Z., & ZAKIA, H. (2022). Design and Control of a Robotic Device for Upper Limb Rehabilitation Therapy. Journal of Engineering Science and Technology, 17(2), 1306–1327.
Ni, Y., Yang, X., Cheng, Y., Dong, Z., & Tang, M. (2021). Machine Vision based Grabbing Objects with Manipulator System Design. Engineering Journal, 25(2), 327–334. https://doi.org/10.4186/ej.2021.25.2.327
Ross, R., Stumpf, A., Barnett, D., & Hall, R. (2021). Condition assessment for concrete sewer pipes using displacement probes: A robotic design case study. Robotics, 10(2), 64. https://doi.org/10.3390/robotics10020064
Rumaksari, A. N. (2019). Vehicle Classification using IPCP and EsKNN Algorithm for Surveillance Camera. Techné?: Jurnal Ilmiah Elektroteknika, 18(01), 15–30. https://doi.org/10.31358/techne.v18i01.181
Russell, Stuart; Norvig, P. (2021). Artificial Intelligence: A Modern Approach, 4th US ed. Pearson. http://aima.cs.berkeley.edu/
Sedighi, S., Nguyen, D. Van, & Kuhnert, K. D. (2019). Guided Hybrid A-star Path Planning Algorithm for Valet Parking Applications. 2019 5th International Conference on Control, Automation and Robotics, ICCAR 2019, 570–575. https://doi.org/10.1109/ICCAR.2019.8813752
Shang, E., Dai, B., Nie, Y., Zhu, Q., Xiao, L., & Zhao, D. (2020). A Guide-line and Key-point based A-star Path Planning Algorithm for Autonomous Land Vehicles. 2020 IEEE 23rd International Conference on Intelligent Transportation Systems, ITSC 2020, 1–7. https://doi.org/10.1109/ITSC45102.2020.9294336
Sharif, K., & Gormley, M. (2021). Integrating the design of tall building, wastewater drainage systems into the public sewer network: A review of the current state of the art. In Water (Switzerland) (Vol. 13, Issue 22, p. 3242). Multidisciplinary Digital Publishing Institute. https://doi.org/10.3390/w13223242
Tang, G., Tang, C., Claramunt, C., Hu, X., & Zhou, P. (2021). Geometric A-Star Algorithm: An Improved A-Star Algorithm for AGV Path Planning in a Port Environment. IEEE Access, 9, 59196–59210. https://doi.org/10.1109/ACCESS.2021.3070054
Wayahdi, M. R., Ginting, S. H. N., & Syahputra, D. (2021). Greedy, A-Star, and Dijkstra’s Algorithms in Finding Shortest Path. International Journal of Advances in Data and Information Systems, 2(1), 45–52. https://doi.org/10.25008/ijadis.v2i1.1206
Yeo, M. S. K., Ng, A. Q. B., Ng, T. Y. J., Mudiyanselage, S., Samarakoon, B. P., Muthugala, M. A. V. J., Mohan, R. E., & Ng, D. T. (2021). Robot-Inclusive Guidelines for Drain Inspection. 2021 8th International Conference on Information Technology, Computer and Electrical Engineering, ICITACEE 2021, 7–12. https://doi.org/10.1109/ICITACEE53184.2021.9617537
Zeng, W., & Church, R. L. (2009). Finding shortest paths on real road networks: The case for A. International Journal of Geographical Information Science, 23(4), 531–543. https://doi.org/10.1080/13658810801949850
Zhang, Y., Li, L. L., Lin, H. C., Ma, Z., & Zhao, J. (2019). Development of path planning approach using improved a-star algorithm in AGV system. Journal of Internet Technology, 20(3), 915–924. https://doi.org/10.3966/160792642019052003023
Zhang, Z., Wu, J., Dai, J., & He, C. (2022). Optimal path planning with modified A-Star algorithm for stealth unmanned aerial vehicles in 3D network radar environment. Proceedings of the Institution of Mechanical Engineers, Part G: Journal of Aerospace Engineering, 236(1), 72–81. https://doi.org/10.1177/09544100211007381
Zheng, T., Xu, Y., & Zheng, D. (2019). AGV Path Planning based on Improved A-star Algorithm. Proceedings of 2019 IEEE 3rd Advanced Information Management, Communicates, Electronic and Automation Control Conference, IMCEC 2019, 1534–1538. https://doi.org/10.1109/IMCEC46724.2019.8983841
Copyright and Licensing
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.