Abstract
Large-scale infrastructures are prone to simultaneous faults when struck by a natural or man-made event. The current operating procedure followed by many utilities needs improvement, both in terms of monitoring performance and time to repair. Motivated by the recent technological progress on small Unmanned Aerial Systems (sUAS), we propose a practical framework to integrate the monitoring capabilities of sUAS into standard utility repair operations. A key aspect of our framework is the use of monitoring locations for sUAS-based inspection of failures within a certain spatial zone (called a localization set). This set is defined based on the alerts from fixed sensors or customer calls. The positioning of monitoring locations is subject to several factors such as sUAS platform, network topology, and airspace restrictions. We formulate the problem of minimizing the maximum time to respond to all failures by routing repair vehicles to various localization sets and exploring these sets using sUAS. The formulation admits a natural decomposition into two sub-problems: the sUAS Network Exploration Problem (SNEP); and the Repair Vehicle Routing Problem (RVRP). Standard solvers can be used to solve the RVRP in a scalable manner; however, solving the SNEP for each localization set can be computationally challenging. To address this limitation, we propose a set cover based heuristic to approximately solve the SNEP. We implement the overall framework on a benchmark network.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Angalakudati, M., Balwani, S., Calzada, J., Chatterjee, B., Perakis, G., Raad, N., Uichanco, J.: Business analytics for flexible resource allocation under random emergencies. Manag. Sci. 60(6), 1552–1573 (2014)
Boland, N., Clarke, L., Nemhauser, G., et al.: The asymmetric traveling salesman problem with replenishment arcs. Euro. J. Oper. Res. 123(2), 408–427 (2000)
Bräysy, O., Gendreau, M.: Vehicle routing problem with time windows, part i: route construction and local search algorithms. Transp. Sci. 39(1), 104–118 (2005)
Chabot, D., Craik, S.R., Bird, D.M.: Population census of a large common tern colony with a small unmanned aircraft. PloS one 10(4), e0122,588 (2015)
Chvatal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3), 233–235 (1979)
Clarke, G., Wright, J.W.: Scheduling of vehicles from a central depot to a number of delivery points. Oper. Res. 12(4), 568–581 (1964)
Croes, G.A.: A method for solving traveling-salesman problems. Oper. Res. 6 (6), 791–812 (1958)
Dadkhah, N., Mettler, B.: Survey of motion planning literature in the presence of uncertainty: Considerations for uav guidance. J. Intell. Robot. Syst. 65(1-4), 233–246 (2012)
Dantzig, G.B., Ramser, J.H.: The truck dispatching problem. Manag. Sci. 6(1), 80–91 (1959)
Deng, C., Wang, S., Huang, Z., Tan, Z., Liu, J.: Unmanned aerial vehicles for power line inspection: a cooperative way in platforms and communications. J. Commun. 9(9), 687–692 (2014)
Erdoġan, S., Miller-Hooks, E.: A green vehicle routing problem. Transport Res E-Log 48(1), 100–114 (2012)
Federal Aviation Administration: Unmanned Aircraft Systems (UAS) Operational Approval (N 8900.227). https://www.faa.gov/documentLibrary/media/Notice/N_8900.227.pdf. Accessed: Sept 12, 2017 (2013)
Federal Aviation Administration: Authorizations Granted via Section 333 Exemptions. https://www.faa.gov/uas/beyond_the_basics/section_333/333_authorizations/ (2016)
Floyd, R.W.: Algorithm 97: shortest path. Commun. ACM 5(6), 345 (1962)
Golden, B.L., Levy, L., Vohra, R.: The orienteering problem. Nav. Res. Logist. 34(3), 307–318 (1987)
Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell Labs Tech. J. 45(9), 1563–1581 (1966)
Kentucky Water Resources Research Institute: Water Distribution System Research Database. http://www.uky.edu/WDST/database.html. [Online; accessed February 22, 2017] (2016)
Kopardekar, P., Rios, J., Prevot, T., Johnson, M., Jung, J., Robinson, J.: Unmanned Aircraft System Traffic Management (Utm) Concept of Operations. In: AIAA Aviation Forum (2016)
Krefta, L.: Asset knowledge and integrity management earthquake playbook, gas pipeline integrity management program pacific gas electric company (2015)
Laporte, G., Nobert, Y., Arpin, D.: Optimal Solutions to Capacitated Multidepot Vehicle Routing Problems. Université de Montréal, Centre de recherche sur les transports (1984)
Laporte, G., Semet, F.: Classical Heuristics for the Capacitated Vrp. In: The Vehicle Routing Problem, pp. 109–128. SIAM (2002)
Larson, R.C., Odoni, A.R.: Urban operations research. Monograph Dynamic Ideas (1981)
Leachtenauer, J.C., Driggers, R.G.: Surveillance and reconnaissance imaging systems: modeling and performance prediction. Artech House (2001)
Lusk, R.M., Monday, W.H.: An early survey of best practices for the use of small unmanned aerial systems by the electric utility industry. Manual ORNL/TM-2017/93 oak ridge national laboratory (2017)
Mohan, A., Poobal, S.: Crack detection using image processing: A critical review and analysis. Alexandria Engineering Journal (2017)
Murvay, P.S., Silea, I.: A survey on gas leak detection and localization techniques. J. Loss Prev. Process Ind. 25(6), 966–973 (2012)
Otero, L.: Proof of concept for using unmanned aerial vehicles for high mast pole and bridge inspections (fdot report no. bdv 28 977–02) (2015)
Pipeline and Hazardous Materials Safety Administration: National Pipeline Performance Measures. https://phmsa.dot.gov/pipeline/library/data-stats/performance-measures
Prosser, P., Shaw, P.: Study of greedy search with multiple improvement heuristics for vehicle routing problems (1996)
Rangel, J., Garzón, J., Sofrony, J., Kroll, A.: Gas leak inspection using thermal, visual and depth images and a depth-enhanced gas detection strategy. Revista de Ingeniería 1(42), 8–15 (2015)
Sela Perelman, L., Abbas, W., Koutsoukos, X., Amin, S.: Sensor placement for fault location identification in water networks. Automatica 72(C), 166–176 (2016). https://doi.org/10.1016/j.automatica.2016.06.005
Taillard, É.D., Laporte, G., Gendreau, M.: Vehicle routeing with multiple use of vehicles. J. Oper. Res. Soc. 47(8), 1065–1070 (1996)
Vigo, D.: A heuristic algorithm for the asymmetric capacitated vehicle routing problem. Eur. J. Oper. Res. 89(1), 108–126 (1996)
Ware, J., Roy, N.: An analysis of wind field estimation and exploitation for Quadrotor Flight in the urban canopy layer. In: 2016 IEEE International Conference on Robotics and Automation (ICRA), pp. 1507–1514. IEEE (2016)
Weinert, A., Campbell, S., Vela, A., Schuldt, D., Kurucar, J.: A Well Clear Recommendation for Small Unmanned Aircraft Systems Based on Unmitigated Collision Risk. Tech. rep., MIT Lincoln Laboratory (2017)
Whipple, S.D.: Predictive Storm Damage Modeling and Optimizing Crew Response to Improve Storm Response Operations. Ph.D. thesis, Massachusetts Institute of Technology (2014)
Williams, K.W., Gildea, K.M.: A review of research related to unmanned aircraft system visual observers. Federal Aviation Administration Final Report (2014)
Acknowledgements
A shorter version of this paper was presented at the 2017 International Conference on Unmanned Aircraft Systems (ICUAS). This article elaborates on the overall framework, computational study, and heuristic approach. The work of M. Dahan, S. Amin, and A. Weinert was supported by ICAST: Intelligent Constrained Autonomous Strategic Tasking, which received financial support from MTSI Inc. and MIT MIT Lincoln Laboratory. The project benefited from useful advice by Mike Munizzi. The support of National Science Foundation through grants CNS-1239054 and CNS-1453126 is also greatly acknowledged.
DISTRIBUTION STATEMENT A. Approved for public release. Distribution is unlimited. This material is based upon work supported by the United States Air Force under Air Force Contract No. FA8702-15-D-0001. Any opinions, findings, conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the United States Air Force.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendices
Appendix A: Table of Notations
Appendix B: Results for 7 Localization Sets Using 3 sUAS
Appendix C: Explanation of Big-M Upper Bound for Constraint 13
Rights and permissions
About this article
Cite this article
Lee, A.C., Dahan, M., Weinert, A.J. et al. Leveraging sUAS for Infrastructure Network Exploration and Failure Isolation. J Intell Robot Syst 93, 385–413 (2019). https://doi.org/10.1007/s10846-018-0838-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10846-018-0838-0