He, Tong (2020) UAS Flight Path Planning and Collision Avoidance Based on Markov Decision Process. Masters thesis, Concordia University.
Preview |
Text (application/pdf)
6MBHe_MASc_F2020.pdf - Accepted Version |
Abstract
The growing interest and trend for deploying unmanned aircraft systems (UAS) in civil applications require robust traffic management approaches that can safely integrate the unmanned platforms into the airspace. Although there have been significant advances in autonomous navigation, especially in the ground vehicles domain, there are still challenges to address for navigation in a dynamic 3D environment that airspace presents. An integrated approach that facilitates semi-autonomous operations in dynamic environments and also allows for operators to stay in the loop for intervention may provide a workable and practical solution for safe UAS integration in the airspace.
This thesis research proposes a new path planning method for UAS flying in a dynamic 3D environment shared by multiple aerial vehicles posing potential conflict risks. This capability is referred to as de-confliction in drone traffic management. It primarily targets applications such as UAM [1] where multiple flying manned and/or unmanned aircraft may be present. A new multi-staged algorithm is designed that combines AFP method and Harmonic functions with AKF and MDP for dynamic path planning. It starts with the prediction of aircraft traffic density in the area and then generates the UAS flight path in a way to minimize the risk of encounters and potential conflicts. Hardware-in-the-loop simulations of the algorithm in various scenarios are presented, with an RGB-D camera and Pixhawk Autopilot to track the target. Numerical simulations show satisfactory results in various scenarios for path planning that considerably reduces the risk of conflict with other static and dynamic obstacles. A comparison with the potential field is provided that illustrates the robust and fast of the MDP algorithm.
| Divisions: | Concordia University > Gina Cody School of Engineering and Computer Science > Mechanical, Industrial and Aerospace Engineering |
|---|---|
| Item Type: | Thesis (Masters) |
| Authors: | He, Tong |
| Institution: | Concordia University |
| Degree Name: | M.A. Sc. |
| Program: | Mechanical Engineering |
| Date: | 1 October 2020 |
| Thesis Supervisor(s): | Xie, Wenfang and Iraj, Mantegh |
| ID Code: | 987580 |
| Deposited By: | Tong He |
| Deposited On: | 23 Jun 2021 16:27 |
| Last Modified: | 23 Jun 2021 16:27 |
References:
[1] Shamiyeh M., Rothfeld R. and Hornung M. (Sep 14, 2018). "A Performance Benchmark of Recent Personal Air Vehicle Concepts for Urban Air Mobility". icas.org. Retrieved Aug 20, 2019.[2] Latombe, Claude J., (1991) Robot Motion Planning The Springer International Series in Engineering and Computer Science.
[3] Nakamura H., Harada K. and Oura Y., (2018) "UTM concept demonstrations in Fukushima; overview of demonstration and lesson learnt for operation of multiple UAS in the same airspace," 2018 International Conference on Unmanned Aircraft Systems (ICUAS), Dallas, TX, pp.222-228, Doi: 10.1109/ICUAS.2018.8453425.
[4] Albaker, B.M., Rahim, N.A., (Dec. 2009) "A survey of collision avoidance approaches for unmanned aerial vehicles," in Technical Postgraduates (TECHPOS), 2009 Int. Conf. for, vol., no., pp.1-7, 14-15.
[5] Gupta D.K.，Jaiswal A.K., (May 2013) "Path Planning with Real Time Obstacle Avoidance" Int, J. of Computer Applications (0975 –8887) Volume 70–No.5.
[6] Li A., Luo P., (2012) "Introduction to A* From Amit’s Thoughts on Pathfinding". theory. stanford.edu.
[7] Xue Q. and Chen Y. (1995) "Determining the path search graph and finding a collision-free path by the modified A* algorithm for a 5-link closed chain Applied Artificial Intelligence", vol. 92.
[8] Lavalle, S.M. (1998). "Rapidly-exploring random trees: A new tool for path planning", Computer Science Dept, Iowa State University, Tech. Rep. TR: 98–11. Retrieved 2008-06-30. S.
[9] Kala R., Warwick K., (Sep. 2011)" Planning of Multiple Autonomous Vehicles using RRT", IEEE Int’l Conf. on Cybernetic Intelligent Systems (CIS), pp.20-25.
[10] Dale L., Amato N. (2001) "Probabilistic roadmaps – Putting it all together", Proc. IEEE Int. Conf. on Robotics and Automation, pp. 1940–1947.
[11] Karaman, S. and Frazzoli, E. (2011) "Sampling-based Algorithms for Optimal Motion Planning", Int. Journal of Robotics Research, vol. 30, no. 7, pp. 846–894.
[12] Garcia, I., How, J. P. (2005) "Improving the efficiency of Rapidly- exploring Random Trees Using a Potential Function Planner", Proc. of 44th IEEE Conf. on Decision and Control, and the European Control Conference, pp. 7965–7970.
[13] Khanmohammadi S., Mahdizadeh A. (2008) "Density Avoided Sampling: An Intelligent Sampling Technique for Rapidly-Exploring Random Trees", Eight Int. Conf. on Hybrid Intelligent Systems, HIS, pp.672–677.
[14] Kuffner, J., LaValle, S. M. (Apr. 2000) "An efficient approach to single-query path planning", in Proc. of IEEE Intl. Conf. on Robotics and Automation, pp. 995–1001.
[15] Lydia E.K., Petr S., Jean-Claude L., Mark H.O. (Aug. 1996) "Probabilistic roadmaps for path planning in high-dimensional configuration spaces", IEEE Trans. on Robotics and Automation, vol. 12, pp. 566–580.
[16] Hsu, D., Latombe, J.-C., and Motwani, R. (1999) "Path planning in expansive configuration spaces", Int. J. of Computational Geometry and Applications, vol. 9, no. 4/5, pp. 495–512.
[17] LaValle, S. M. and Kuffner, J. J. (2001) "Randomized kinodynamic planning" Intl. J. of Robotics Research, vol. 17, no. 5, pp. 378–400.
[18] Şucan, I. and Kavraki, L. E. (2012) "A sampling-based tree planner for systems with complex dynamics", IEEE Trans. on Robotics, vol. 28, no. 1, pp.116–131.
[19] Wang X., Li X., Guan Y., Song J. and Wang R., (2019)"Bidirectional Potential Guided RRT* for Motion Planning," in IEEE Access, vol. 7, pp. 95046-95057.
[20] Ecodyne rada,weblink: https://echodyne.com/
[21] TrueView, weblink: https://fortemtech.com/products/trueview-radar/
[22] Hu J., Niu Y., Wang Z., (2017) "Obstacle Avoidance Methods for Rotor UAVs Using RealSense Camera", Chinese Automation Congress (CAC), pp.7151-7155.
[23] Beyeler A., Zufferey J.C., Floreano D, (April, 2007) "3D vision-based navigation for indoor microflyers". In Proc of the 2007 IEEE Int. Conf. on Robotics and Automation, Roma, Italy, 10–14 pp. 1336–1341.
[24] Khatib, (1985) "Real-time obstacle avoidance for manipulators and mobile robots, " in Proc of the IEEE Int. Conf. on Robotics and Automation (ICRA '85), vol. 2, pp. 500–505.
[25] Park M.G., Lee M.C. (2002) "Experimental Evaluation of Robot Path Planning by Artificial Potential Field Approach with Simulated Annealing", SICE 2002. Aug.5-7, Osaka.
[26] Temizer S., Mykel J., Leslie P.K., James K., (Aug. 2010) "Collision avoidance for unmanned aircraft using Markov decision processes", Proc of the AIAA Guidance Navigation and Control Conf.
[27] Barraquand J., Langlois J., and Latombe J. C. (1989) "Numerical potential field techniques for robot path planning". Technical Report ST.4N-CS-89-1285, Stanford University.
[28] Mantegh, M.R.M. Jenkin A.A. Goldenberg, (1998) "A modular and less complex environment representation algorithm [for mobile robots]", Industrial Electronics 1998. Proc. ISIE '98. IEEE Int. Symposium on, vol. 2, pp. 668-673 vol.2.
[29] Mantegh, M. R. M. Jenkin and A. A. Goldenberg, (1997) "Solving the find-path problem: a complete and less complex approach using the BIE methodology," Proc 1997 IEEE Int. Symposium on Computational Intelligence in Robotics and Automation CIRA'97. 'Towards New Computational Principles for Robotics and Automation', Monterey, CA, USA, 1997, pp. 115-121.
[30] Ahmad A.M., (July, 2010)"Motion planning with gamma-harmonic potential fields" 2010 IEEE/ASME Int. Conf. on Advanced Intelligent Mechatronics pp.297-302.
[31] Motonakah K., Watanabe1 K., Maeyama1 S., (2014) "3-Dimensional Kino-dynamic Motion Planning for an X4-Flyer Using 2-Dimensional Harmonic Potential Fields " 2014 14th Int. Conf. on Control, Automation and Systems (ICCAS 2014) pp.1181-1184.
[32] Panagiotis V., Constantinos V., Charalampos P. B., Kostas J. K., (2019) "Orientation-Aware Motion Planning in Complex Workspaces using Adaptive Harmonic Potential Fields," 2019 Int. Conf. on Robotics and Automation (ICRA), Montreal, QC, Canada, 2019, pp. 8592-8598.
[33] Mantegh I., Liao J., and He J., (2020) "Integrated Collision Avoidance for Unmanned Aircraft Systems with Harmonic Potential Field and Haptic Input". Proc. of the IEEE-Int. Symposium of System Integration 2020, Honolulu, Hawaii.
[34] Park J.W., Kwak H.J., Kang Y., and Dong W. K., (2016) "Advanced Fuzzy Potential Field Method for Mobile Robot Obstacle Avoidance" Computational Intelligence and Neuroscience, vol. 2016, Article ID 6047906, 13 pages, 2016.
[35] Takagi T. and Sugeno M., (1985) "Fuzzy identification of systems and its applications to modeling and control" IEEE Trans on Systems, Man, and Cybernetics, vol. 15, no. 1, pp. 116–132.
[36] Davison A., Reid I., Molton N., and Stasse O,. (2007) MonoSLAM: Real-time single camera SLAM. TPAMI 2007.
[37] Klein G. and Murray D., (2007) "Parallel Tracking and Mapping for Small AR Workspaces". ISMAR 2007.
[38] Klein G. and Murray D., (2008) "Improving the Agility of Keyframe-based SLAM". ECCV 2008.
[39] Klein G. and Murray D., (2009) "Parallel Tracking and Mapping on a Camera Phone". ISMAR 2009.
[40] Raul M., Montiel J. M. M., and Juan D. T. (2015) "ORB-SLAM: A Versatile and Accurate Monocular SLAM System". IEEE Transactions on Robotics 2015.
[41] LiM., Mourikis A. (2013) "High-Precision, Consistent EKF-based Visual-Inertial Odometry". International Journal of Robotics Research 2013 CO, pp. 221–228.
[42] Ma X., Yao X., and Ding R., (April, 2020) "Influence of IMU’s quality on VIO: based on MSCKF method", Proc. SPIE 11455, Sixth Symposium on Novel Optoelectronic Detection Technology and Applications.
[43] Hornu A., Kai M.W., Bennewitz W., (2013) "OctoMap: an efficient probabilistic 3D mapping framework based on octrees" Autonomous Robots volume 34, pp.189–206.
[44] Fukushima K., Murakami S., Matsushima J., Kato M. (1980) "Vestibular Responses and Branching of Interstitiospinal Neurons" Brain Res pp.131-145.
[45] Ling Q., Yan J., Li F., and Zhang Y., (2014) "A background modeling and foreground segmentation approach based on the feedback of moving objects in traffic surveillance systems", Journal of Neuro Computing, Elsevier. pp.1158–1179.
[46] Zhong B., Yuan X., Ji R., Yan Y., Cui Z., Hong X., Chen Y., Wang T., Chen D., and Yu J., (2014) "Structured Partial Least Squares for Simultaneous Object Tracking", Journal of Neurocomputing, Elsevier.
[47] Wu J., Liu N., Geyer C. and James M. R., (2013) "C4: A Real-time Object Detection Framework", IEEE Transaction on Image Processing.
[48] Jasper R.R. T. Gevers, A., (2012) "Selective Search for Object Recognition" International Journal of Computer Vision 104(2):154-171.
[49] Lin T ., Goyal P., Girshick R., He K ., Dollár P., (Oct. 2017) "Focal Loss for Dense Object Detection" 2017 IEEE International Conference on Computer Vision (ICCV), 22-29.
[50] https://docs.px4.io/v1.9.0/en/flight_controller/pixhawk.html
[51] https://www.raspberrypi.org/products/raspberry-pi-4-model-b/specifications/
[52] https://www.intelrealsense.com/zh-hans/depth-camera-d435i/
[53] https://mavlink.io/en
[54] Paul Z., Howard M., (2000). "Fundamentals of Kalman Filtering: A Practical Approach. American Institute of Aeronautics and Astronautics, Incorporated". ISBN 978-1-56347-455-2.
[55] Hesam K.F., Faria S., Bak C., (2016)"A performance comparison between extended Kalman Filter and unscented Kalman Filter in power system dynamic state estimation" 51st International Universities Power Engineering Conference (UPEC).
[56] Hargrave P.J. (Feb. 1989) "A tutorial introduction to Kalman filtering" IEE Colloquium on Kalman Filters: Introduction, Applications and Future Developments.
[57] He Q., Wei C., Xu Y., (2017) "An improved adaptive Kalman filtering algorithm for balancing vehicle" 2017 Chinese Automation Congress (CAC) pp. 5721-5725.
[58] David S., Ross j., (2010) "Visual Object Tracking using Adaptive Correlation Filters". In CVPR.
[59] Citysim, a GAZEBO model for urban area, Weblink:https://www.wilselby.com/2019/05/ouster-os-1-ros-gazebo-simulation- in-mcity-and-citysim/
[60] Iris, a GAZEBO model for Iris drone: Weblink:https://dev.px4.io/master/en/simulation/
[61] Yu X., Zhou X., Zhang Y., (2019) "Collision-Free Trajectory Generation and Tracking for UAVs Using Markov Decision Process in a Cluttered Environment". J Intell Robot Syst 93, 17–32.
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.
Repository Staff Only: item control page
Download Statistics
Download Statistics