An Application of Path Planning Algorithms for Autonomous Inspection of Buried Pipes with Swarm Robots

Authors: Richard Molyneux, Christopher Parrott, Kirill Horoshenkov

Abstract:

This paper aims to demonstrate how various algorithms can be implemented within swarms of autonomous robots to provide continuous inspection within underground pipeline networks. Current methods of fault detection within pipes are costly, time consuming and inefficient. As such, solutions tend toward a more reactive approach, repairing faults, as opposed to proactively seeking leaks and blockages. The paper presents an efficient inspection method, showing that autonomous swarm robotics is a viable way of monitoring underground infrastructure. Tailored adaptations of various Vehicle Routing Problems (VRP) and path-planning algorithms provide a customised inspection procedure for complicated networks of underground pipes. The performance of multiple algorithms is compared to determine their effectiveness and feasibility. Notable inspirations come from ant colonies and stigmergy, graph theory, the k-Chinese Postman Problem ( -CPP) and traffic theory. Unlike most swarm behaviours which rely on fast communication between agents, underground pipe networks are a highly challenging communication environment with extremely limited communication ranges. This is due to the extreme variability in the pipe conditions and relatively high attenuation of acoustic and radio waves with which robots would usually communicate. This paper illustrates how to optimise the inspection process and how to increase the frequency with which the robots pass each other, without compromising the routes they are able to take to cover the whole network.

Keywords: Autonomous inspection, buried pipes, stigmergy, swarm intelligence, vehicle routing problem.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.3455725

References:

[1] Ahr, D., Reinelt, G., (2006). A tabu search algorithm for the min-max k-Chinese Postman Problem. Computers and Operations Research. 33, 3403 – 3422.
[2] Aleman, R. E., Zhang, X., Hill, R. R., (2008). An adaptive memory algorithm for the split delivery vehicle routing problem. Springer Science and Business Media – Heuristics. 16, 441 – 473.
[3] Desrochers, M., Desrosiers, J., Solomon, M., (1992). A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows. Operations Research. 40, 199 – 415.
[4] Dorigo, M., Bonabeau, E., Theraulaz, G., (2000). Ant algorithms and stigmergy. Future Generation Computer Systems (online). Volume 16, 851-871. (Last viewed 29/06/2019). Available from: DOI: 10.1016/S0167-739X(00)00042-X. ISSN: 0167-739X.
[5] Johnson, D. B., Maltz, D. A., (2012). Dynamic Source Routing in Ad Hoc Wireless Networks. The Kluwer International Series in Engineering and Computer Science book series (SECS, volume 353).
[6] Loughran, J., (2017). Water leakage from UK pipes rises to over three billion litres a day (online). Engineering and Technology (E&T) (Last viewed 29/06/2019). Available from: https://eandt.theiet.org/content/articles/2017/12/water-leakage-from-uk-pipes-rises-to-over-three-billion-litres-a-day/
[7] Osterhause, A., Mariak, F., (2005). On variants of the k-Chinese Postman Problem. Operations Research and Wirtschaftsinformatik, 30.
[8] Paraskevopoulos, D. C., et al., (2017). Resource constrained routing and scheduling: Review and research prospects. European Journal of Operations Research. 263, 737 – 754.
[9] Pearn, W., Assad, A., Golden, B. L., (1987). Transforming Arc Routing into Node Routing Problems. Great Britain: Pergamon Journals. 14, 285-288.
[10] Perelman, L., Ostfeld, A., (2012). Water-Distribution Systems Simplifications through Clustering. American Society of Civil Engineers (online). Volume 138 (3). (Last viewed 29/06/19). Available from: DOI; 10.1061/(ACSE)WR.1943-5452.0000173.
[11] Scarpa, F., Lobba, A., Becciu, G., (2016). Elementary DMA Design of Looped Water Distribution Networks with Multiple Sources. American Society of Civil Engineers (online). Volume 142 (6). (Last viewed 29/06/19). Available from: DOI: 10.1061/(ACSE)WR.1943-5452.0000639.
[12] Thimbleby, H., (2003). The directed Chinese Postman Problem. Software: Practice and Experience. 33, 1081 – 1096.