Flight plan optimization for multiple drones in construction sites
DOI:
https://doi.org/10.26439/interfases2023.n017.6230Keywords:
dynamic programming, flight planner, surveillance drones, genetic alorithmAbstract
The construction sector is searching for new technologies, such as drones, that prove helpful for the surveillance and supervision of construction sites, especially in pandemic situations. This research proposes designing flight planning models to optimize flight time and speed. The main objective is to develop a model that allows multiple drones to carry out supervision tasks in construction areas. In this regard, it presents a dynamic programming model and a metaheuristic based on genetic algorithms, both applied for optimizing flight plans with multiple drones. The development process involves planning the route that the drones will follow by formulating the problem with the corresponding parameters. The next step is to generate a model for the dynamic programming algorithm, which is then validated using a genetic algorithm. The proposals implemented in Python were tested in 14 scenarios, gradually increasing in complexity. The dynamic programming-based model significantly improves planning time in all scenarios, achieving an average difference of 281,34 seconds or 4 minutes and 47 seconds, 98,01 % better than the genetic algorithm. Additionally, there is a considerable improvement in segment speeds, as the results show. A paired test evaluated these advancements. The hypothesis is supported with a p-value of 0,0031 for time and 0,0071 for the gain obtained by the objective function in both cases. This confirms the superiority of the dynamic programming algorithm compared to the genetic algorithm.
Downloads
References
Albeaino, G., & Gheisari, M. (2021). Trends, benefits, and barriers of unmanned aerial systems in the construction industry: A survey study in the United States. Journal of Information Technology in Construction, 26, 84-111. https://doi.org/10.36680/j.itcon.2021.006
Balfour Beatty. (2017, 12 de mayo). Flying into the future of bridge inspections. https://www.balfourbeatty.com/news/flying-into-the-future-of-bridge-inspections/
Bouman, P., Agatz, N., & Schmidt, M. (2018). Dynamic programming approaches for the traveling salesman problem with drone. Networks, 72(4), 528-542. https://doi.org/10.1002/net.21864
Criado, R. M., & Rodríguez Rubio, F. (2015). Autonomous path tracking control design for a comercial quadcopter. IFAC-PapersOnLine, 48(9), 73-78. https://doi.org/10.1016/j.ifacol.2015.08.062
Decreto Supremo 011-2019-TR [Ministerio de Trabajo y Promoción del Empleo]. Decreto Supremo que aprueba el Reglamento de Seguridad y Salud en el Trabajo para el Sector Construcción. 11 de julio del 2019. Diario oficial El Peruano. https://cdn.www.gob.pe/uploads/document/file/341232/decreto-supremo-n-011-2019-tr-1787274-4.pdf?v=1562856062
DJI. (2020). Mavic 2 Pro/Zoom. User Manual. DJI.
Doole, M., Ellerbroek, J., & Hoekstra, J. (2020). Estimation of traffic density from drone-based delivery in very low level urban airspace. Journal of Air Transport
Management, 88, 101862. https://doi.org/10.1016/j.jairtraman.2020.101862
Fan, J., & Saadeghvaziri, M. A. (2019). Applications of drones in infrastructures: Challenges and opportunities. World Academy of Science, Engineering and Technology International Journal of Mechanical and Mechatronics Engineering, 13(10), 649-655. https://doi.org/10.5281/zenodo.3566281
Fu, S.-Y., Han, L.-W., Tian, Y., & Yang, G.-S. (2012). Path planning for unmanned aerial vehicle based on genetic algorithm. En 2012 IEEE 11th International Conference on Cognitive Informatics and Cognitive Computing (pp. 140-144). IEEE. https://doi.org/10.1109/ICCI-CC.2012.6311139
Hrishikeshavan, V., & Chopra, I. (2017). Refined lightweight inertial navigation system for micro air vehicle applications. International Journal of Micro Air Vehicles, 9(2), 124-135. https://doi.org/10.1177/1756829316682534
Hromkovič, J. (2013). Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Springer Science & Business Media.
Khan, S. I., Qadir, Z., Munawar, H. S., Nayak, S. R., Budati, A. K., Verma, K. D., & Prakash, D. (2021). UAVs path planning architecture for effective medical emergency response in future networks. Physical Communication, 47, 101337. https://doi.org/10.1016/j.phycom.2021.101337
Lee, D., & Cha, D. (2020). Path optimization of a single surveillance drone based on reinforcement learning. International Journal of Mechanical Engineering and Robotics Research, 9(12), 1541-1547. https://doi.org/10.18178/ijmerr.9.12.1541-1547
Li, Y., Liu, H., Zheng, X., Han, Y., & Li, L. (2019). A top-bottom clustering algorithm based on crowd trajectories for small group classification. IEEE Access, 7, 29679-29698. https://doi.org/10.1109/ACCESS.2019.2902310
Ministerio de Vivienda, Construcción y Saneamiento. (2020). Lineamientos de prevención y control frente a la propagación del COVID-19 en la ejecución de obras de construcción. https://cdn.www.gob.pe/uploads/document/file/671272/Lineamiento_de_Prevencion_y_Control_del_COVID-19_en_Obras_Construccion.pdf
Nguyen, M. A., Dang, G. T.-H., Hà, M. H., & Pham, M.-T. (2022). The min-cost parallel drone scheduling vehicle routing problem. European Journal of Operational Research, 299(3), 910-930. https://doi.org/10.1016/j.ejor.2021.07.008
Palomino, J., Hennings, J., & Echevarría, V. (2017). Análisis macroeconómico del sector construcción en el Perú. Quipukamayoc, 25(47), 95-101. https://doi.org/10.15381/quipu.v25i47.13807
Poikonen, S., Golden, B., & Wasil, E. A. (2019). A branch-and-bound approach to the traveling salesman problem with a drone. INFORMS Journal on Computing, 31(2), 335-346. https://doi.org/10.1287/ijoc.2018.0826
Sando. (2021, 2 de agosto). Sando logra la habilitación para operar drones en espacios aéreos controlados, zonas urbanas y vuelos nocturnos. Sando blog. https://www.sando.com/es/drones-sando-aesa-operar-zonas-urbanas-nocturnas/
Schermer, D., Moeini, M., & Wendt, O. (2020). The traveling salesman drone station location problem. En H. Le Thi, H. Le & T. Pham Dinh (Eds.), Optimization of
Complex Systems: Theory, Models, Algorithms and Applications. WCGO 2019 (pp. 1129-1138). Springer. https://doi.org/10.1007/978-3-030-21803-4_111
Wankmüller, C., Truden, C., Korzen, C., Hungerländer, P., Kolesnik, E., & Reiner, G. (2020). Optimal allocation of defibrillator drones in mountainous regions. OR Spectrum, 42(3), 785-814. https://doi.org/10.1007/s00291-020-00575-z
Yi, W., & Sutrisna, M. (2021). Drone scheduling for construction site surveillance. Computer-Aided Civil and Infrastructure Engineering, 36(1), 3-13. https://doi.org/10.1111/mice.12593
Downloads
Published
Issue
Section
License
Authors who publish with this journal agree to the following terms:
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under an Attribution 4.0 International (CC BY 4.0) License. that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
Last updated 03/05/21
