Implementation of UAV Smooth Path Planning by Improved Parallel Genetic Algorithm on Controller Area Network
Publication: Journal of Aerospace Engineering
Volume 35, Issue 2
Abstract
Unmanned aerial vehicle (UAV) path planning is an essential branch in UAVs research. This paper presents the hardware implementation of the UAV path planning problem using an improved parallel genetic algorithm (GA) in a multi-microcontroller environment. A controller area network (CAN) bus is a robust bus designed to allow microcontrollers to communicate with each other in applications without a host computer. The CAN bus is used to communicate between the microcontrollers and solve the path planning problem with the parallel algorithm. The data exchange on this network is by the multi-master model, so it is possible to implement an asynchronous and multi-master parallel algorithm using CAN bus. Also, we use the 32-bit ARM Cortex-M3 microcontroller (with CPU clock up to 100 MHz) for hardware implementation. The comparison of both single and parallel GA shows that a multi-microcontroller structure produces better results on the CAN bus, and the parallel version experiences significantly faster speeds than the sequential version.
Get full access to this article
View all available purchase options and get full access to this article.
Data Availability Statement
Some or all data, models, or code that support the findings of this study are available from the corresponding author upon reasonable request.
References
Abhishek, B., S. Ranjit, T. Shankar, G. Eappen, P. Sivasankar, and A. Rajesh. 2020. “Hybrid PSO-HSA and PSO-GA algorithm for 3D path planning in autonomous UAVs.” SN Appl. Sci. 2 (11): 1805. https://doi.org/10.1007/s42452-020-03498-0.
Anderson, J. D. 2008. Introduction to flight. 6th ed. New York: McGraw-Hill Higher Education.
Anderson, J. D. 2005. Introduction to flight. New York: McGraw-Hill Higher Education.
CAN Primer. 2012. “Hybrid PSO-HSA and PSO-GA algorithm for 3D path planning in autonomous UAVs.” Accessed December 11, 2021. http://www.keil.com/download/docs/385.asp.
Cantú-Paz, E., and D. E. Goldberg. 2003. “Are multiple runs of genetic algorithms better than one?” In Genetic and evolutionary computation—GECCO 2003, edited by E. Cantú-Paz, et al., 801–812. Berlin: Springer.
Dong, J., and J. Vegners. 2004. “Parallel evolutionary algorithms for UAV path planning.” In Proc., AIAA 1st Intelligent Systems Technical Conf. Chicago: American Institute of Aeronautics and Astronautics.
Duan, H., and L. Huang. 2014. “Imperialist competitive algorithm optimized artificial neural networks for UCAV global path planning.” Adv. Neural Net. Res. Appl. 125 (Feb): 166–171.
Goel, U., S. Varshney, A. Jain, S. Maheshwari, and A. Shukla. 2018. “Three dimensional path planning for UAVs in dynamic environment using glow-worm swarm optimization.” In Proc., Procedia Computer Science, Int. Conf. on Robotics and Smart Manufacturing (RoSMa2018), 230–239. Gwalio, India: Indian Institute of Information Technology and Management.
Gong, Y.-J., W.-N. Chen, Z.-H. Zhan, J. Zhang, Y. Li, Q. Zhang, and J.-J. Li. 2015. “Distributed evolutionary algorithms and their models: A survey of the state-of-the-art.” Appl. Soft Comput. 34 (Sep): 286–300. https://doi.org/10.1016/j.asoc.2015.04.061.
Jamshidi, V., V. Nekoukar, and M. H. Refan. 2020a. “Analysis of asynchronous distributed multi-master parallel genetic algorithm optimization on CAN bus.” Evol. Syst. 11 (4): 673–682. https://doi.org/10.1007/s12530-020-09337-2.
Jamshidi, V., V. Nekoukar, and M. H. Refan. 2020b. “Analysis of parallel genetic algorithm and parallel particle swarm optimization algorithm UAV path planning on controller area network.” J. Control Autom. Electr. Syst. 31 (1): 129–140. https://doi.org/10.1007/s40313-019-00549-9.
Jamshidi, V., V. Nekoukar, and M. H. Refan. 2021. “Real time UAV path planning by parallel grey wolf optimization with align coefficient on CAN bus.” Cluster Comput. 24 (3): 2495–2509.
John, H. H. 1975. Adaptation in natural and artificial systems. Cambridge, UK: MIT Press.
Kamali Janfada, B., and M. R. Ghasemi. 2020. “Optimal design of steel moment frame structures using the GA-based reduced search space (GA-RSS) technique.” Int. J. Optim. Civ. Eng. 10 (4): 611–627.
Kennedy, J., and R. Eberhart. 1995. “Particle swarm optimization.” In Proc., ICNN’95—Int. Conf. on Neural Networks, 1942–1948. New York: IEEE.
Konatowski, S., and P. Pawłowski. 2018. “Ant colony optimization algorithm for UAV path planning.” In Proc., 2018 14th Int. Conf. on Advanced Trends in Radioelecrtronics, Telecommunications and Computer Engineering (TCSET), 177–182. New York: IEEE.
Labonté, G. 2010. Mathematical relations to analyze aircraft performance for trajectory planning. Ottawa: Defense Research and Development.
Mirjalili, S., S. M. Mirjalili, and A. Lewis. 2014. “Grey wolf optimizer.” Adv. Eng. Software 69 (Mar): 46–61. https://doi.org/10.1016/j.advengsoft.2013.12.007.
Mufti, S. 2019. “Path planning algorithm for multiple unmanned aerial vehicles with parallel implementation on a graphics processing unit.” Master of Applied Science in Computer Engineering, Dept. of National Defence, Royal Military College of Canada.
Nikolos, K. I., K. P. Valavanis, and N. C. Tsourveloudis. 2003. “Evolutionary algorithm based offline/online path planner for UAV navigation.” IEEE Syst. Man Cyber. Soc. 33 (6): 898–912.
Özalp, N., and O. K. Sahingoz. 2013. “Optimal UAV path planning in a 3D threat environment by using parallel evolutionary algorithms.” In Proc., 2013 Int. Conf. on Unmanned Aircraft Systems (ICUAS), 308–317. New York: IEEE.
Pehlivanoglu, Y. V. 2012. “A new vibrational genetic algorithm enhanced with a Voronoi diagram for path planning of autonomous UAV.” Aerosp. Sci. Technol. 16 (1): 47–55. https://doi.org/10.1016/j.ast.2011.02.006.
Pérez-Carabaza, S., J. Scherer, B. Rinner, J. A. López-Orozco, and E. Besada-Portas. 2019. “UAV trajectory optimization for minimum time search with communication constraints and collision avoidance.” Eng. Appl. Artif. Intell. 85 (Oct): 357–371. https://doi.org/10.1016/j.engappai.2019.06.002.
Prajindra Sankar, K., S. K. Tiong, and S. P. Johnny Koh. 2009. “Parallel distributed computational microcontroller system for adaptive antenna downlink transmitter power optimization.” Int. J. Electr. Comput. Eng. 4 (11): 604–608.
Roberge, V., M. Tarbouchi, and G. Labonte. 2013. “Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning.” IEEE Trans. Ind. Inf. 9 (1): 132–141. https://doi.org/10.1109/TII.2012.2198665.
Roberge, V., M. Tarbouchi, and G. Labonté. 2018. “Fast genetic algorithm path planner for fixed-wing military UAV using GPU.” IEEE Trans. Aerosp. Electron. Syst. 54 (5): 2105–2117. https://doi.org/10.1109/TAES.2018.2807558.
Robert Bosch GmbH. 1991. CAN specification version 2.0. London: Bosch.
Saeidian, B., M. S. Mesgari, and M. Ghodousi. 2016. “Evaluation and comparison of Genetic Algorithm and Bees Algorithm for location–allocation of earthquake relief centers.” Int. J. Disaster Risk Reduct. 15 (Mar): 94–107. https://doi.org/10.1016/j.ijdrr.2016.01.002.
Scholz, A., T.-H. Hsiao, J.-N. Juang, and C. Cherciu. 2018. “Open source implementation of ECSS CAN bus protocol for CubeSats.” Adv. Space Res. 62 (12): 3438–3448. https://doi.org/10.1016/j.asr.2017.10.015.
Shorakaei, H., M. Vahdani, B. Imani, and A. Gholami. 2016. “Optimal cooperative path planning of unmanned aerial vehicles by a parallel genetic algorithm.” Robotica 34 (4): 823–836. https://doi.org/10.1017/S0263574714001878.
Sonmez, A., E. Kocyigit, and E. Kugu. 2015. “Optimal path planning for UAVs using genetic algorithm.” In Proc., 2015 Int. Conf. on Unmanned Aircraft Systems (ICUAS), 50–55. New York: IEEE.
Tharwat, A., M. Elhoseny, A. E. Hassanien, T. Gabel, and A. Kumar. 2018. “Intelligent Bézier curve-based path planning model using Chaotic Particle Swarm Optimization algorithm.” Cluster Comput. 22 (2): 4745–4766.
Wilburn, B. K., M. G. Perhinschi, and J. N. Wilburn. 2014. “A modified genetic algorithm for UAV trajectory tracking control laws optimization.” Int. J. Intell. Unmanned Syst 2 (2): 58–90.
Xia, J., C. Zhang, R. Bai, and L. Xue. 2013. “Real-time and reliability analysis of time-triggered CAN-bus.” Chin. J. Aeronaut. 26 (1): 171–178. https://doi.org/10.1016/j.cja.2012.12.017.
Yan, P., Z. Yan, H. Zheng, and J. Guo. 2018. “A fixed wing UAV path planning algorithm based on genetic algorithm and Dubins Curve Theory.” In Proc., MATEC Web of Conf. New York: Web of Conferences.
YongBo, C., M. YueSong, Y. JianQiao, S. XiaoLong, and X. Nuo. 2017. “Three-dimensional unmanned aerial vehicle path planning using modified wolf pack search algorithm.” Neurocomputing 266: 445–457. https://doi.org/10.1016/j.neucom.2017.05.059.
Zhang, G., R. Wang, H. Lei, T. Zhang, W. Li, and Y. Song. 2021. “UAV path planning based on variable neighborhood search genetic algorithm.” In Advances in swarm intelligence, edited by Y. Tan and Y. Shi, 205–217. Cham, Switzerland: Springer.
Zhao, Y., Z. Zheng, and Y. Liu. 2018. “Survey on computational-intelligence-based UAV path planning.” Knowl.-Based Syst. 158 (Oct): 54–64. https://doi.org/10.1016/j.knosys.2018.05.033.
Information & Authors
Information
Published In
Copyright
© 2021 American Society of Civil Engineers.
History
Received: Apr 1, 2020
Accepted: Nov 10, 2021
Published online: Dec 28, 2021
Published in print: Mar 1, 2022
Discussion open until: May 28, 2022
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.
Cited by
- Hankun Jiang, Kaiyuan Chen, Runqi Chai, Jin Yu, Chun Guo, Yuanqing Xia, Trajectory Planning and Control of Multiple Quadcopters for Mars Exploration, Journal of Aerospace Engineering, 10.1061/JAEEEZ.ASENG-5270, 37, 4, (2024).