Planificación de trayectoria determinista basado en recompensas para entornos discretos 3D

Autores/as

DOI:

https://doi.org/10.37135/ns.01.12.10

Palabras clave:

Planificación de trayectoria 3D, trayectoria óptima, UAV

Resumen

Diversas ramas de estudio e investigación surgen de la tecnología de los vehículos aéreos no tripulados (UAV). Una tarea relevante en vuelo UAV se centra en la planificación de trayectorias tri-dimensional (3D), tarea que implica un alto costo computacional, en consecuencia, debe ser resuelta mejorando el tiempo de respuesta. El objetivo de este trabajo es optimizar el tiempo de cálculo y determinar una trayectoria completa de vuelo 3D. En este sentido, se considera un entorno de vuelo 3D como una malla discreta adaptativa 3D, la cual se somete a un refinamiento mínimo en busca de espacios libres de colisiones. Con la construcción de la malla discreta 3D, se aplica una metodología de coste-respuesta a modo de un Autómata Finito Determinista Discreto (DDFA), metodología que da como resultado un conjunto de respuestas óptimas parciales (calculadas recursivamente) que indican los espacios libres de colisión en la trayectoria 3D final para el vuelo del UAV. Como resultado, el algoritmo de planificación de trayectorias 3D ha mostrado un ahorro en tiempo computacional y recursos de memoria en comparación con las técnicas clásicas.

Descargas

Los datos de descargas todavía no están disponibles.

Citas

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

Amorim, Rafhael, Huan Nguyen, Preben Mogensen, István Z. Kovács, Jeroen Wigard, y Troels B. Sørensen. (2017). Radio Channel Modeling for UAV Communication over Cellular Networks. IEEE Wireless Communications Letters 6(4):514-17. doi: 10.1109/LWC.2017.2710045

Archdeacon, Dan. (1996). Topological Graph Theory. A survey. Congressus Numerantium 115(18):5-54, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.1728

Armesto, Leopoldo, Gloria Vanegas, y Vicent Girbés-Juan. (2022). Elementary Clothoid-Based Three-Dimensional Curve for Unmanned Aerial Vehicles. Journal of Guidance, Control, and Dynamics 45(12):2421-31, https://doi.org/10.2514/1.G006935

Berger, Marsha J., y Joseph Oliger. (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

Chivers, Ian, Jane Sleightholme, Ian Chivers, y Jane Sleightholme. (2015). An introduction to Algorithms and the Big O Notation. Introduction to Programming with Fortran: With Coverage of Fortran 90, 95, 2003, 2008 and 77 359-64, https://doi.org/10.1007/978-3-319-17701-4_23

Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik 1(1):269-71, https://doi.org/10.1145/3544585.3544600

Gautam, S. Aditya, y Nilmani Verma. (2014). Path planning for unmanned aerial vehicle based on genetic algorithm & artificial neural network in 3D. Pp. 1-5 en 2014 International Conference on Data Mining and Intelligent Computing (ICDMIC). IEEE, https://doi.org/10.1109/ICDMIC.2014.6954257

Girbés, Vicent, Gloria Vanegas, y Leopoldo Armesto. (2019). Clothoid-Based Three-Dimensional Curve for Attitude Planning. Journal of Guidance, Control, and Dynamics 42(8):1886-98. doi: 10.2514/1.G003551.

Goel, Utkarsh, Shubham Varshney, Anshul Jain, Saumil Maheshwari, y Anupam Shukla. (2018). Three Dimensional Path Planning for UAVs in Dynamic Environment using Glow-worm Swarm Optimization. Procedia Computer Science 133:230-39. doi: 10.1016/j.procs.2018.07.028.

Hart, Peter E., y J. Nils. (1968). A formal basis for the Heuristic Determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics 4(2):100-107, https://doi.org/10.1109/TSSC.1968.300136

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

Iswanto, Iswanto, Oyas Wahyunggoro, y Adha Imam Cahyadi. (2016). Quadrotor Path Planning Based on Modified Fuzzy Cell Decomposition Algorithm. ℡KOMNIKA (Telecommunication Computing Electronics and Control) 14(2):655. doi: 10.12928/℡KOMNIKA.v14i1.2989.

Latombe, Jean-Claude, y Jean-Claude Latombe. (1991). Approximate cell decomposition. Robot Motion Planning 248-94, https://doi.org/10.1007/978-1-4615-4022-9_6

LaValle, Steven M. (2006). Planning Algorithms. Cambridge University Press.

Nevalainen, Olli, Eija Honkavaara, Sakari Tuominen, Niko Viljanen, Teemu Hakala, Xiaowei Yu, Juha Hyyppä, Heikki Saari, Ilkka Pölönen, Nilton N. Imai, y Antonio M. G. Tommaselli. (2017). Individual tree detection and classification with UAV-Based photogrammetric point clouds and hyperspectral imaging. Remote Sensing 9(3). doi: 10.3390/rs9030185.

Noborio, Hiroshi, Tomohide Naniwa, y Suguru Arimoto. (1990). A quadtree-based path-planning algorithm for a mobile robot. Journal of Robotic Systems 7(4):555-74, https://doi.org/10.1002/rob.4620070404

Nosrati, Masoud, Ronak Karimi Hojat Allah Hasanvand, y including D. Original. (2012). Investigation of the * (Star) Search Algorithms: Characteristics, Methods and Approaches. World Applied Programming 2(4):251-56.

Samaniego, Franklin, Javier Sanchis, Sergio Garcia-Nieto, y Raul Simarro. (2017). UAV motion planning and obstacle avoidance based on adaptive 3D cell decomposition: Continuous space vs discrete space. Pp. 1-6 en 2017 IEEE Second Ecuador Technical Chapters Meeting (ETCM). IEEE, https://doi.org/10.1109/ETCM.2017.8247533

Samet, H., y A. Kochut. (2002). Octree approximation an compression methods. Pp. 460-69 en Proceedings. First International Symposium on 3D Data Processing Visualization and Transmission. IEEE Comput. Soc, https://dx.doi.org/10.1109/TDPVT.2002.1024101

Skoldstam, Markus, Knut Akesson, y Martin Fabian. (2007). Modeling of discrete event systems using finite automata with variables. Pp. 3387-92 en Decision and Control, 2007 46th IEEE Conference on. IEEE, https://dx.doi.org/10.1109/CDC.2007.4434894

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

Valavanis, Kimon P., y George J. Vachtsevanos. (2015). Handbook of Unmanned Aerial Vehicles. editado por K. P. Valavanis y G. J. Vachtsevanos. Springer Netherlands.

Vanegas, Gloria, Leopoldo Armesto, Vicent Girbés-Juan, y Joaquín Pérez. (2022). Smooth Three-Dimensional Route Planning for Fixed-Wing Unmanned Aerial Vehicles With Double Continuous Curvature. IEEE Access 10:94262-72, https://doi.org/10.1109/ACCESS.2022.3203069

Vanegas, Gloria, Franklin Samaniego, Vicent Girbes, Leopoldo Armesto, y Sergio Garcia-Nieto. (2018). Smooth 3D path planning for non-holonomic UAVs. Pp. 1-6 en 2018 7th International Conference on Systems and Control (ICSC). IEEE, https://doi.org/10.1109/ICoSC.2018.8587835

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

Wang, Gai-Ge, Haicheng Eric Chu, y Seyedali Mirjalili. (2016). Three-dimensional path planning for UCAV using an improved bat algorithm. Aerospace Science and Technology 49:231-38. doi: 10.1016/j.ast.2015.11.040.

Yao, Peng, Honglun Wang, y Zikang Su. (2015). Hybrid UAV path planning based on interfered fluid dynamical system and improved RRT. Pp. 000829-34 en IECON 2015 - 41st Annual Conference of the IEEE Industrial Electronics Society. IEEE, https://doi.org/10.1109/IECON.2015.7392202

YongBo, Chen, Mei YueSong, Yu JianQiao, Su XiaoLong, y Xu Nuo. (2017). Three-dimensional unmanned aerial vehicle path planning using modified wolf pack search algorithm. Neurocomputing 266:445-57. doi: 10.1016/j.neucom.2017.05.059.

Yongqiang, Wang, Steven X. Ding, Ye Hao, Wei Li, Zhang Ping, y Wang Guizeng. (2009). Fault detection of networked control systems with packet based periodic communication. International Journal of Adaptive Control and Signal Processing 23(8):682-98. doi: 10.1002/acs.

Descargas

Publicado

2023-07-14

Cómo citar

Vanegas Zabala, G. I., & Liger Yépez, A. (2023). Planificación de trayectoria determinista basado en recompensas para entornos discretos 3D. Novasinergia, ISSN 2631-2654, 6(2), 151–165. https://doi.org/10.37135/ns.01.12.10

Número

Sección

Artículos de Investigación y Artículos de Revisión