Abstract
Small Unmanned Aerial Systems (sUAS) such as quadcopters are ideal for aerial surveillance because of their runway independence, terrain-agnostic maneuverability, low cost, and simple hardware. However, battery capacity constraints limit the effective range and endurance of sUASs, requiring human intervention to replace batteries or perform manual recharging for longer operations. To increase their range, an Unmanned Ground Vehicle (UGV) may provide recharging depot as needed. The problem is then to find optimal paths for the UGV and sUASs to visit mission points and sUAS-UGV rendezvous points for recharging. We present a three-tiered heuristics to solve this computationally hard combinatorial optimization problem: (1) K-means clustering is used to find UGV waypoints, (2) a traveling salesman formulation (TSP) is used to solve the optimal UGV route, and (3) vehicle routing problem formulation (VRP) with capacity constraints, time windows, and dropped visits is used to solve for sUAS routes. We use constraint programming for optimization of the TSP and VRP, achieving a solution for 25 mission points and up to 4 sUASs in about a minute on a standard desktop computer. We also found that constraint programming solvers are 7 − 30 times faster, but 4 − 15% sub-optimal compared to mixed-integer solvers, which provide exact solutions. Further, we used constraint programming solvers in a Monte-Carlo approach to evaluate the role of mission spread, number of clusters, and number of sUASs on the optimal solution. Our contribution is the development of heuristics for route selection of sUAS-UGVs that produces high quality solutions as more mission points and sUASs are added without substantially increasing the computational time.
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.
Code Availability
References
Griffiths, S.R.: Remote terrain navigation for unmanned air vehicles (2006)
Altshuler, Y., Pentland, A., Bruckstein, A. M.: Optimal dynamic coverage infrastructure for large-scale fleets of reconnaissance UAVs. In: Swarms and Network Intelligence in Search, pp. 207–238. Springer (2018)
Theile, M., Bayerlein, H., Nai, R., Gesbert, D., Caccamo, M.: UAV coverage path planning under varying power constraints using deep reinforcement learning. arXiv:2003.02609 (2020)
Mersheeva, V.: UAV Routing problem for area monitoring in a disaster situation. Ph.D. thesis (2015)
Freed, M., Fitzgerald, W., Harris, R.: Intelligent autonomous surveillance of many targets with few UAVs. In: Proceedings of the Research and Development Partnering Conference, Department of Homeland Security, Boston, MA (2005)
Khuller, S., Malekian, A., Mestre, J.: To fill or not to fill: The gas station problem. ACM Trans. Alg. (TALG) 7(3), 1–16 (2011)
Kannon, T. E., Nurre, S. G., Lunday, B. J., Hill, R. R.: The aircraft routing problem with refueling. Optim. Lett. 9(8), 1609–1624 (2015)
Levy, D., Sundar, K., Rathinam, S.: Heuristics for routing heterogeneous unmanned vehicles with fuel constraints. Math. Probl. Eng. 2014 (2014)
Sundar, K., Venkatachalam, S., Rathinam, S.: Formulations and algorithms for the multiple depot, fuel-constrained, multiple vehicle routing problem. In: 2016 American Control Conference (ACC), pp. 6489–6494. IEEE (2016)
Song, B. D., Kim, J., Morrison, J. R.: Rolling horizon path planning of an autonomous system of uavs for persistent cooperative service: Milp formulation and efficient heuristics. J. Intell. Robot. Syst. 84(1-4), 241–258 (2016)
Younghoon, C., Youngjun, C., Briceno, S., Mavris, D. N.: Energy-constrained multi-uav coverage path planning for an aerial imagery mission using column generation. J. Intell. Robot. Syst. 97(1), 125–139 (2020)
Radzki, G., Golinska-Dawson, P., Bocewicz, G., Banaszak, Z.: Modelling robust delivery scenarios for a fleet of unmanned aerial vehicles in disaster relief missions. J. Intell. Robot. Syst. 103(4), 1–18 (2021)
Lee, A. C., Dahan, M., Weinert, A. J., Amin, S.: Leveraging suas for infrastructure network exploration and failure isolation. J. Intell. Robot. Syst. 93(1-2), 385–413 (2019)
Albert, A., Imsland, L.: Combined optimal control and combinatorial optimization for searching and tracking using an unmanned aerial vehicle. J. Intell. Robot. Syst. 95(2), 691–706 (2019)
Maini, P., Sundar, K., Rathinam, S., Sujit, P.: Cooperative planning for fuel-constrained aerial vehicles and ground-based refueling vehicles for large-scale coverage. arXiv:1805.04417 (2018)
Manyam, S. G., Casbeer, D. W., Sundar, K.: Path planning for cooperative routing of air-ground vehicles. In: 2016 American Control Conference (ACC), pp. 4630–4635. https://doi.org/10.1109/ACC.2016.7526082 (2016)
Petitprez, E., Georges, F., Raballand, N., Bertrand, S.: Deployment optimization of a fleet of drones for routine inspection of networks of linear infrastructures. In: 2021 International Conference on Unmanned Aircraft Systems (ICUAS), pp. 303–310. https://doi.org/10.1109/ICUAS51884.2021.9476674 (2021)
Liu, Y., Liu, Z., Shi, J., Wu, G., Chen, C.: Optimization of base location and patrol routes for unmanned aerial vehicles in border intelligence, surveillance, and reconnaissance, J. Adv. Transp. 2019 (2019)
Bard, J.F., Jarrah, A.I., Zan, J.: Validating vehicle routing zone construction using monte carlo simulation. European J. Oper. Res. 206(1), 73–85 (2010). https://doi.org/10.1016/j.ejor.2010.01.045
Dondo, R., Cerdá, J.: A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows. European J. Oper. Res. 176(3), 1478–1507 (2007)
Google: Google OR-tools. https://developers.google.com/optimization . Online; accessed Feb 2 2021 (2021)
Ramasamy, S., Reddinger, J. P. F., Dotterweich, J. M., Childers, M. A., Bhounsule, P. A.: Cooperative route planning of multiple fuel-constrained unmanned aerial vehicles with recharging on an unmanned ground vehicle. In: 2021 International Conference on Unmanned Aircraft Systems (ICUAS), pp. 155–164. https://doi.org/10.1109/ICUAS51884.2021.9476848 (2021)
Wilkin, G. A., Huang, X.: K-means clustering algorithms: implementation and comparison. In: Second International Multi-Symposiums on Computer and Computational Sciences (IMSCCS 2007), pp. 133–136. IEEE (2007)
Miller, C. E., Tucker, A., Zemlin, R. A.: Integer programming formulation of traveling salesman problems. J. ACM 7, 326–329 (1960)
Gurobi: Gurobi Optimization LLC. https://www.gurobi.com/. Online; accessed Sep 19 2021 (2021)
Rossi, F., Van Beek, P., Walsh, T.: Handbook of constraint programming. Elsevier (2006)
Shaw, P., Furnon, V., De Backer, B.: A constraint programming toolkit for local search. In: Optimization Software Class Libraries, pp. 219–261. Springer (2003)
De Backer, B., Furnon, V., Shaw, P., Kilby, P., Prosser, P.: Solving vehicle routing problems using constraint programming and metaheuristics. J. Heuristics 6(4), 501–523 (2000)
Tatsch, C. A. A.: Route planning for Long-Term robotics missions west virginia university (2020)
Voudouris, C., Tsang, E. P.: Guided local search. In: Handbook of Metaheuristics, pp. 185–218. Springer (2003)
Voudouris, C., Tsang, E. P., Alsheddy, A.: Guided local search. In: Handbook of Metaheuristics, pp. 321–361. Springer (2010)
Ramasamy, S.: Uav-ugv routing code. https://github.com/subram0212/JINT_paper_codes. Online; Accessed Feb 13 2022 (2022)
Ramasamy, S., Mondal, M., Reddinger, J. P. F., Dotterweich, J. M., Humann, J. D., Childers, M. A., Bhounsule, P. A.: Heterogenous vehicle routing: comparing parameter tuning using genetic algorithm and bayesian optimization. In: 2022 International Conference on Unmanned Aircraft Systems (ICUAS) (2022)
Funding
The work by SR and PAB was funded by Army Research Laboratory grant W911NF-14-S-003.
Author information
Authors and Affiliations
Contributions
Conceptualization, SR, JPR, JD, CM, PAB; methodology, SR and PAB; software and validation, SR; writing—original draft preparation, SR and PAB; writing—review and editing, JPR, JD, CM, PAB; supervision, JPR, JD, CM, PAB; project administration, PAB. All authors have read and agreed to the published version of the manuscript.’
Corresponding author
Ethics declarations
Ethics Approval
Not applicable.
Conflict of Interests
The authors declare no conflict of interest.
Consent for Publication
All authors consent to publication.
Consent to Participate
Not applicable.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This work was supported by ARO grant W911NF-14-S-003
Rights and permissions
Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Ramasamy, S., Reddinger, JP.F., Dotterweich, J.M. et al. Coordinated Route Planning of Multiple Fuel-constrained Unmanned Aerial Systems with Recharging on an Unmanned Ground Vehicle for Mission Coverage. J Intell Robot Syst 106, 30 (2022). https://doi.org/10.1007/s10846-022-01737-7
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s10846-022-01737-7