Planificación de trayectoria determinista basado en recompensas para entornos discretos 3D
DOI:
https://doi.org/10.37135/ns.01.12.10Palabras clave:
Planificación de trayectoria 3D, trayectoria óptima, UAVResumen
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
Referencias
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.
