- -

Recursive Rewarding Modified Adaptive Cell Decomposition (RR-MACD): A Dynamic Path Planning Algorithm for UAVs

RiuNet: Institutional repository of the Polithecnic University of Valencia

Share/Send to

Cited by


Recursive Rewarding Modified Adaptive Cell Decomposition (RR-MACD): A Dynamic Path Planning Algorithm for UAVs

Show full item record

Samaniego-Riera, FE.; Sanchís Saez, J.; Garcia-Nieto, S.; Simarro Fernández, R. (2019). Recursive Rewarding Modified Adaptive Cell Decomposition (RR-MACD): A Dynamic Path Planning Algorithm for UAVs. Electronics. 8(3):1-21. https://doi.org/10.3390/electronics8030306

Por favor, use este identificador para citar o enlazar este ítem: http://hdl.handle.net/10251/144574

Files in this item

Item Metadata

Title: Recursive Rewarding Modified Adaptive Cell Decomposition (RR-MACD): A Dynamic Path Planning Algorithm for UAVs
Author: Samaniego-Riera, Franklin Eduardo Sanchís Saez, Javier Garcia-Nieto, Sergio Simarro Fernández, Raúl
UPV Unit: Universitat Politècnica de València. Departamento de Ingeniería de Sistemas y Automática - Departament d'Enginyeria de Sistemes i Automàtica
Issued date:
[EN] A relevant task in unmanned aerial vehicles (UAV) flight is path planning in 3D environments. This task must be completed using the least possible computing time. The aim of this article is to combine methodologies ...[+]
Subjects: UAV , Path planning , Adaptive discrete mesh , Octree
Copyrigths: Reconocimiento (by)
Electronics. (eissn: 2079-9292 )
DOI: 10.3390/electronics8030306
Publisher version: https://doi.org/10.3390/electronics8030306
Project ID:
The authors would like to acknowledge the Spanish Ministry of Economy and Competitiveness for providing funding through the project DPI2015-71443-R and the local administration Generalitat Valenciana through the project ...[+]
Type: Artículo


Valavanis, K. P., & Vachtsevanos, G. J. (Eds.). (2015). Handbook of Unmanned Aerial Vehicles. doi:10.1007/978-90-481-9707-1

20 Great UAV Applications Areas for Droneshttp://air-vid.com/wp/20-great-uav-applications-areas-drones/

Industry Experts—Microdroneshttps://www.microdrones.com/en/industry-experts/ [+]
Valavanis, K. P., & Vachtsevanos, G. J. (Eds.). (2015). Handbook of Unmanned Aerial Vehicles. doi:10.1007/978-90-481-9707-1

20 Great UAV Applications Areas for Droneshttp://air-vid.com/wp/20-great-uav-applications-areas-drones/

Industry Experts—Microdroneshttps://www.microdrones.com/en/industry-experts/

Li, J., & Han, Y. (2017). Optimal Resource Allocation for Packet Delay Minimization in Multi-Layer UAV Networks. IEEE Communications Letters, 21(3), 580-583. doi:10.1109/lcomm.2016.2626293

Stuchlík, R., Stachoň, Z., Láska, K., & Kubíček, P. (2015). Unmanned Aerial Vehicle – Efficient mapping tool available for recent research in polar regions. Czech Polar Reports, 5(2), 210-221. doi:10.5817/cpr2015-2-18

Pulver, A., & Wei, R. (2018). Optimizing the spatial location of medical drones. Applied Geography, 90, 9-16. doi:10.1016/j.apgeog.2017.11.009

Claesson, A., Svensson, L., Nordberg, P., Ringh, M., Rosenqvist, M., Djarv, T., … Hollenberg, J. (2017). Drones may be used to save lives in out of hospital cardiac arrest due to drowning. Resuscitation, 114, 152-156. doi:10.1016/j.resuscitation.2017.01.003

Reineman, B. D., Lenain, L., Statom, N. M., & Melville, W. K. (2013). Development and Testing of Instrumentation for UAV-Based Flux Measurements within Terrestrial and Marine Atmospheric Boundary Layers. Journal of Atmospheric and Oceanic Technology, 30(7), 1295-1319. doi:10.1175/jtech-d-12-00176.1

LaValle, S. M. (2006). Planning Algorithms. doi:10.1017/cbo9780511546877

Elbanhawi, M., & Simic, M. (2014). Sampling-Based Robot Motion Planning: A Review. IEEE Access, 2, 56-77. doi:10.1109/access.2014.2302442

Hernandez, K., Bacca, B., & Posso, B. (2017). Multi-goal Path Planning Autonomous System for Picking up and Delivery Tasks in Mobile Robotics. IEEE Latin America Transactions, 15(2), 232-238. doi:10.1109/tla.2017.7854617

Kohlbrecher, S., von Stryk, O., Meyer, J., & Klingauf, U. (2011). A flexible and scalable SLAM system with full 3D motion estimation. 2011 IEEE International Symposium on Safety, Security, and Rescue Robotics. doi:10.1109/ssrr.2011.6106777

Aguilar, W., & Morales, S. (2016). 3D Environment Mapping Using the Kinect V2 and Path Planning Based on RRT Algorithms. Electronics, 5(4), 70. doi:10.3390/electronics5040070

Aguilar, W. G., Morales, S., Ruiz, H., & Abad, V. (2017). RRT* GL Based Optimal Path Planning for Real-Time Navigation of UAVs. Lecture Notes in Computer Science, 585-595. doi:10.1007/978-3-319-59147-6_50

Yao, P., Wang, H., & Su, Z. (2015). Hybrid UAV path planning based on interfered fluid dynamical system and improved RRT. IECON 2015 - 41st Annual Conference of the IEEE Industrial Electronics Society. doi:10.1109/iecon.2015.7392202

Yan, F., Liu, Y.-S., & Xiao, J.-Z. (2013). Path Planning in Complex 3D Environments Using a Probabilistic Roadmap Method. International Journal of Automation and Computing, 10(6), 525-533. doi:10.1007/s11633-013-0750-9

Yeh, H.-Y., Thomas, S., Eppstein, D., & Amato, N. M. (2012). UOBPRM: A uniformly distributed obstacle-based PRM. 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems. doi:10.1109/iros.2012.6385875

Denny, J., & Amatoo, N. M. (2013). Toggle PRM: A Coordinated Mapping of C-Free and C-Obstacle in Arbitrary Dimension. Algorithmic Foundations of Robotics X, 297-312. doi:10.1007/978-3-642-36279-8_18

Li, Q., Wei, C., Wu, J., & Zhu, X. (2014). Improved PRM method of low altitude penetration trajectory planning for UAVs. Proceedings of 2014 IEEE Chinese Guidance, Navigation and Control Conference. doi:10.1109/cgncc.2014.7007587

Ortiz-Arroyo, D. (2015). A hybrid 3D path planning method for UAVs. 2015 Workshop on Research, Education and Development of Unmanned Aerial Systems (RED-UAS). doi:10.1109/red-uas.2015.7440999

Thanou, M., & Tzes, A. (2014). Distributed visibility-based coverage using a swarm of UAVs in known 3D-terrains. 2014 6th International Symposium on Communications, Control and Signal Processing (ISCCSP). doi:10.1109/isccsp.2014.6877904

Qu, Y., Zhang, Y., & Zhang, Y. (2014). Optimal flight path planning for UAVs in 3-D threat environment. 2014 International Conference on Unmanned Aircraft Systems (ICUAS). doi:10.1109/icuas.2014.6842250

Fang, Z., Luan, C., & Sun, Z. (2017). A 2D Voronoi-Based Random Tree for Path Planning in Complicated 3D Environments. Advances in Intelligent Systems and Computing, 433-445. doi:10.1007/978-3-319-48036-7_31

Khuswendi, T., Hindersah, H., & Adiprawita, W. (2011). UAV path planning using potential field and modified receding horizon A* 3D algorithm. Proceedings of the 2011 International Conference on Electrical Engineering and Informatics. doi:10.1109/iceei.2011.6021579

Chen, X., & Zhang, J. (2013). The Three-Dimension Path Planning of UAV Based on Improved Artificial Potential Field in Dynamic Environment. 2013 5th International Conference on Intelligent Human-Machine Systems and Cybernetics. doi:10.1109/ihmsc.2013.181

Rivera, D. M., Prieto, F. A., & Ramirez, R. (2012). Trajectory Planning for UAVs in 3D Environments Using a Moving Band in Potential Sigmoid Fields. 2012 Brazilian Robotics Symposium and Latin American Robotics Symposium. doi:10.1109/sbr-lars.2012.26

Liu Lifen, Shi Ruoxin, Li Shuandao, & Wu Jiang. (2016). Path planning for UAVS based on improved artificial potential field method through changing the repulsive potential function. 2016 IEEE Chinese Guidance, Navigation and Control Conference (CGNCC). doi:10.1109/cgncc.2016.7829099

Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271. doi:10.1007/bf01386390

Verscheure, L., Peyrodie, L., Makni, N., Betrouni, N., Maouche, S., & Vermandel, M. (2010). Dijkstra’s algorithm applied to 3D skeletonization of the brain vascular tree: Evaluation and application to symbolic. 2010 Annual International Conference of the IEEE Engineering in Medicine and Biology. doi:10.1109/iembs.2010.5626112

Hart, P., Nilsson, N., & Raphael, B. (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107. doi:10.1109/tssc.1968.300136

Ferguson, D., & Stentz, A. (s. f.). Field D*: An Interpolation-Based Path Planner and Replanner. Robotics Research, 239-253. doi:10.1007/978-3-540-48113-3_22

De Filippis, L., Guglieri, G., & Quagliotti, F. (2011). Path Planning Strategies for UAVS in 3D Environments. Journal of Intelligent & Robotic Systems, 65(1-4), 247-264. doi:10.1007/s10846-011-9568-2

Gautam, S. A., & Verma, N. (2014). Path planning for unmanned aerial vehicle based on genetic algorithm & artificial neural network in 3D. 2014 International Conference on Data Mining and Intelligent Computing (ICDMIC). doi:10.1109/icdmic.2014.6954257

Maturana, D., & Scherer, S. (2015). 3D Convolutional Neural Networks for landing zone detection from LiDAR. 2015 IEEE International Conference on Robotics and Automation (ICRA). doi:10.1109/icra.2015.7139679

Iswanto, I., Wahyunggoro, O., & Imam Cahyadi, A. (2016). Quadrotor Path Planning Based on Modified Fuzzy Cell Decomposition Algorithm. TELKOMNIKA (Telecommunication Computing Electronics and Control), 14(2), 655. doi:10.12928/telkomnika.v14i2.2989

Duan, H., Yu, Y., Zhang, X., & Shao, S. (2010). Three-dimension path planning for UCAV using hybrid meta-heuristic ACO-DE algorithm. Simulation Modelling Practice and Theory, 18(8), 1104-1115. doi:10.1016/j.simpat.2009.10.006

He, Y., Zeng, Q., Liu, J., Xu, G., & Deng, X. (2013). Path planning for indoor UAV based on Ant Colony Optimization. 2013 25th Chinese Control and Decision Conference (CCDC). doi:10.1109/ccdc.2013.6561444

Zhang, Y., Wu, L., & Wang, S. (2013). UCAV Path Planning by Fitness-Scaling Adaptive Chaotic Particle Swarm Optimization. Mathematical Problems in Engineering, 2013, 1-9. doi:10.1155/2013/705238

Goel, U., Varshney, S., Jain, A., Maheshwari, S., & Shukla, A. (2018). Three Dimensional Path Planning for UAVs in Dynamic Environment using Glow-worm Swarm Optimization. Procedia Computer Science, 133, 230-239. doi:10.1016/j.procs.2018.07.028

YongBo, C., YueSong, M., JianQiao, Y., XiaoLong, S., & Nuo, X. (2017). Three-dimensional unmanned aerial vehicle path planning using modified wolf pack search algorithm. Neurocomputing, 266, 445-457. doi:10.1016/j.neucom.2017.05.059

Wang, G.-G., Chu, H. E., & Mirjalili, S. (2016). Three-dimensional path planning for UCAV using an improved bat algorithm. Aerospace Science and Technology, 49, 231-238. doi:10.1016/j.ast.2015.11.040

Aghababa, M. P. (2012). 3D path planning for underwater vehicles using five evolutionary optimization algorithms avoiding static and energetic obstacles. Applied Ocean Research, 38, 48-62. doi:10.1016/j.apor.2012.06.002

Mac, T. T., Copot, C., Tran, D. T., & De Keyser, R. (2016). Heuristic approaches in robot path planning: A survey. Robotics and Autonomous Systems, 86, 13-28. doi:10.1016/j.robot.2016.08.001

Szirmay-Kalos, L., & Márton, G. (1998). Worst-case versus average case complexity of ray-shooting. Computing, 61(2), 103-131. doi:10.1007/bf02684409

Berger, M. J., & Oliger, J. (1984). Adaptive mesh refinement for hyperbolic partial differential equations. Journal of Computational Physics, 53(3), 484-512. doi:10.1016/0021-9991(84)90073-1

Min, C., & Gibou, F. (2006). A second order accurate projection method for the incompressible Navier–Stokes equations on non-graded adaptive grids. Journal of Computational Physics, 219(2), 912-929. doi:10.1016/j.jcp.2006.07.019

Hasbestan, J. J., & Senocak, I. (2018). Binarized-octree generation for Cartesian adaptive mesh refinement around immersed geometries. Journal of Computational Physics, 368, 179-195. doi:10.1016/j.jcp.2018.04.039

Pantano, C., Deiterding, R., Hill, D. J., & Pullin, D. I. (2007). A low numerical dissipation patch-based adaptive mesh refinement method for large-eddy simulation of compressible flows. Journal of Computational Physics, 221(1), 63-87. doi:10.1016/j.jcp.2006.06.011

Ryde, J., & Hu, H. (2009). 3D mapping with multi-resolution occupied voxel lists. Autonomous Robots, 28(2), 169-185. doi:10.1007/s10514-009-9158-3

Samet, H., & Kochut, A. (s. f.). Octree approximation an compression methods. Proceedings. First International Symposium on 3D Data Processing Visualization and Transmission. doi:10.1109/tdpvt.2002.1024101

Samaniego, F., Sanchis, J., Garcia-Nieto, S., & Simarro, R. (2017). UAV motion planning and obstacle avoidance based on adaptive 3D cell decomposition: Continuous space vs discrete space. 2017 IEEE Second Ecuador Technical Chapters Meeting (ETCM). doi:10.1109/etcm.2017.8247533

Skoldstam, M., Akesson, K., & Fabian, M. (2007). Modeling of discrete event systems using finite automata with variables. 2007 46th IEEE Conference on Decision and Control. doi:10.1109/cdc.2007.4434894

Yang, Y.-H. E., & Prasanna, V. K. (2011). Space-time tradeoff in regular expression matching with semi-deterministic finite automata. 2011 Proceedings IEEE INFOCOM. doi:10.1109/infcom.2011.5934986

Normativa Sobre Drones en España [2019]—Aerial Insightshttp://www.aerial-insights.co/blog/normativa-drones-espana/

Disposición 15721 del BOE núm. 316 de 2017 - BOE.eshttps://www.boe.es/boe/dias/2017/12/29/pdfs/BOE-A-2017-15721.pdf

Velasco-Carrau, J., García-Nieto, S., Salcedo, J. V., & Bishop, R. H. (2016). Multi-Objective Optimization for Wind Estimation and Aircraft Model Identification. Journal of Guidance, Control, and Dynamics, 39(2), 372-389. doi:10.2514/1.g001294

Vanegas, G., Samaniego, F., Girbes, V., Armesto, L., & Garcia-Nieto, S. (2018). Smooth 3D path planning for non-holonomic UAVs. 2018 7th International Conference on Systems and Control (ICSC). doi:10.1109/icosc.2018.8587835

Samaniego, F., Sanchis, J., Garcia-Nieto, S., & Simarro, R. (2018). Comparative Study of 3-Dimensional Path Planning Methods Constrained by the Maneuverability of Unmanned Aerial Vehicles. 2018 7th International Conference on Systems and Control (ICSC). doi:10.1109/icosc.2018.8587810




This item appears in the following Collection(s)

Show full item record