Reward-based deterministic path planning for discrete 3D environments
DOI:
https://doi.org/10.37135/ns.01.12.10Keywords:
optimal path, path planning 3D, UAVAbstract
Several branches of study and research arise from uncrewed aerial vehicle (UAV) technology. A relevant in-flight task focuses on path planning in 3D, which implies a high computational cost and, consequently, must be achieved by improving the response time. This work aims to optimize the computation time and determine a complete 3D path. In this sense, a 3D flight environment as a 3D adaptive discrete mesh is considered subjected to minimal refinement in search of collision-free spaces. With the construction of the discrete mesh, a cost response methodology is applied in the manner of the discrete deterministic finite automaton (DDFA), which results in a set of optimal partial responses (recursively computed) that indicate the collision-free spaces in the final 3D path for the UAV flight. As a result, the path-planning 3D algorithm saves computational time and memory resources compared to classical techniques.
Downloads
References
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.
