Hostname: page-component-78c5997874-fbnjt Total loading time: 0 Render date: 2024-11-12T19:42:11.024Z Has data issue: false hasContentIssue false
  • English
  • Français

Efficient and Safe Motion Planning for Quadrotors Based on Unconstrained Quadratic Programming

Published online by Cambridge University Press:  19 June 2020

Yanhui Li Open the ORCID record for Yanhui Li [Opens in a new window]  and
Chao Liu Open the ORCID record for Chao Liu [Opens in a new window]
Yanhui Li*
Affiliation:
Key Laboratory of Dynamics and Control of Flight Vehicle, Ministry of Education, School of Aerospace Engineering, Beijing Institute of Technology, Beijing, 100081, P.R. China
Chao Liu
Affiliation:
Key Laboratory of Dynamics and Control of Flight Vehicle, Ministry of Education, School of Aerospace Engineering, Beijing Institute of Technology, Beijing, 100081, P.R. China
*
*Corresponding author. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Summary

An autonomous motion planning framework is proposed, consisting of path planning and trajectory generation. Primarily, a spacious preferred probabilistic roadmap algorithm is utilized to search a safe and short path, considering kinematics and threats from obstacles. Subsequently, a minimum-snap and position-clearance polynomial trajectory problem is transformed into an unconstrained quadratic programming and solved in a two-step optimization. Finally, comparisons with other methods based on statistical simulations are implemented. The results show that the proposed method achieves computational efficiency and a safe trajectory.

Keywords

Path planningTrajectory generationProbabilistic roadmapTwo-step optimization
Type
Articles
Information
Robotica , Volume 39 , Issue 2 , February 2021 , pp. 317 - 333
Copyright
Copyright © The Author(s), 2020. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Likhachev, M., Gordon, G. and Thrun, S., “ARA*: Anytime A* with Provable Bounds on Sub-Optimality,” Advances in Neural Information Processing Systems (2004) pp. 767–774 Google Scholar
Harabor, D. and Grastien, A., “Online Graph Pruning for Path Finding on Grid Maps,” Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence (2011) pp. 1114–1119.Google Scholar
Dolgov, D., Thrun, S., Montemerlo, M. and Diebel, J., “Path planning for autonomous vehicles in unknown semi-structured environments. Int. J. Robot. Res. 29(5), 485–501 (2010).CrossRefGoogle Scholar
Liu, S., Atanasov, N., Mohta, K. and Kumar, V., “Search-based Motion Planning for Quadrotors using Linear Quadratic Minimum Time Control,” Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (2017) pp. 2872–2879.Google Scholar
Liu, S., Mohta, K., Atanasov, N. and Kumar, V., “Search-based motion planning for aggressive flight in SE(3),” IEEE Robot. Autom. Mag. 3(3), 2439–2446 (2017).CrossRefGoogle Scholar
Liu, S., Mohta, K., Atanasov, N. and Kumar, V., “Towards Search-based Motion Planning for Micro Aerial Vehicles,” arXiv:1810.03071 (2018).Google Scholar
Gao, F., Wu, W., Lin, Y. and Shen, S., “Online Safe Trajectory Generation for Quadrotors Using Fast Marching Method and Bernstein Basis Polynomial,” Proceedings of the IEEE International Conference on Robotics and Automation (ICRA) (2018) pp. 344–351.Google Scholar
Ding, W., Gao, W., Wang, K. and Shen, S., “Trajectory Replanning for Quadrotors Using Kinodynamic Search and Elastic Optimization,” arXiv:1903.01139 (2019).Google Scholar
LaValle, S. M., “Rapidly-exploring random trees: A new tool for path planning,” Technical Report (1998) pp. 1–4.Google Scholar
Lavalle, S. M., “Rapidly-exploring random trees: A new tool for path planning,” (1998).Google Scholar
Karaman, S. and Frazzoli, E., “Sampling-based Motion Planning with Deterministic u-Calculus Specifications,” Proceedings of the IEEE Conference on Decision and Control (CDC) (2009) pp. 2222–2229.Google Scholar
Gao, F. and Shen, S., “Online Quadrotor Trajectory Generation and Autonomous Navigation on Point Clouds,” Proceedings of the IEEE International Symposium on Safety, Security, and Rescue Robotics (SSRR) (2016) pp. 139–146.Google Scholar
Lin, Y., Gao, F., Qin, T., Gao, W., Liu, T., Wu, W., Yang, Z., and Shen, S., “Autonomous aerial navigation using monocular visual-inertial fusion,” J. Field. Robot. 35(1), 23–51 (2017).Google Scholar
Karaman, S. and Frazzoli, E., “Sampling-based algorithms for optimal motion planning,” Int. J. Robot. Res. 30(7), 846–894 (2011).CrossRefGoogle Scholar
Richter, C., Bry, A. and Roy, N., “Polynomial Trajectory Planning for Aggressive Quadrotor Flight in Dense Indoor Environments,” Proceedings of the International Symposium on Robotics Research (ISRR) (2016) pp. 649–666.Google Scholar
Pu, X., Ou, M. and Zhen, Z., “A Bio-inspired Approach for UAV Landing and Perching,” Proceedings of AIAA Guidance, Navigation, and Control (2013).Google Scholar
Zhen, Z., Pu, X. and Ou, M., “Bio-inspired Trajectory Generation for Uav Perching,” Proceedings of the International Conference on Advanced Intelligent Mechatronics (2013) pp. 997–1002.Google Scholar
Zhen, Z., Zhang, S., Pu, X. and Ou, M., “Bioinspired 4D trajectory generation for a UAS rapid point-to-point movement,” J. Bionic. Eng. 11(1), 72–81 (2014).Google Scholar
Yang, Z., Zhou, F. and Ping, L., “A Bio-inspired Collision-free 4D Trajectory Generation Method for Unmanned Aerial Vehicles Based on Tau Theory,” Proceedings of the Control Conference (2015) pp. 6961–6968.Google Scholar
Yang, Z., Fang, Z. and Li, P., “Decentralized 4D trajectory generation for uavs based on improved intrinsic tau guidance strategy,” Int. J. Adv. Robot. Syst. 13(3), 1–13 (2016).CrossRefGoogle Scholar
Mellinger, D. and Kumar, V., “Minimum Snap Trajectory Generation and Control for Quadrotors,” Proceedings of the IEEE International Conference on Robotics and Automation (2011) pp. 2520–2525.Google Scholar
Mellinger, D., Kushleyev, A. and Kumar, V., “Mixed-integer Quadratic Program Trajectory Generation for Heterogeneous Quadrotor Teams,” Proceedings of the IEEE International Conference on Robotics and Automation (2012) pp. 477–483.Google Scholar
Tang, S. and Kumar, V., “Mixed Integer Quadratic Program Trajectory Generation for a Quadrotor with a Cable-suspended Payload,” Proceedings of the International Conference on Robotics and Automation (2015) pp. 2216–2222.Google Scholar
Deits, R. and Tedrake, R., “Efficient Mixed-integer Planning for Uavs in Cluttered Environments,” Proceedings of the IEEE International Conference on Robotics and Automation (ICRA) (2015) pp. 42–49.Google Scholar
Oleynikova, H., Burri, M., Taylor, Z., Nieto, J. and Galceran, E., “Continuous-Time Trajectory Optimization for Online UAV Replanning,” Proceedings of the IEEE/RSJ International Conference on Intelligent Robots Systems (2016) pp. 5332–5339.Google Scholar
Oleynikova, H., Taylor, Z., Millane, A., Siegwart, R. and Nieto, J., “A Complete System for Vision-Based Micro-Aerial Vehicle Mapping, Planning, and Flight in Cluttered Environments,” arXiv:1812.03892 (2018).Google Scholar
Oleynikova, H., Taylor, Z., Siegwart, R. and Nieto, J., “Sparse 3D Topological Graphs for Micro-Aerial Vehicle Planning,” arXiv:1803.04345 (2018).CrossRefGoogle Scholar
Lai, S., Lan, M., Chen, B. M., “Optimal Constrained Trajectory Generation for Quadrotors through Smoothing Splines,” Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (2018) pp. 4743–4750.Google Scholar
Gao, F., Wu, W., Gao, W. and Shen, S., ”Flying on point clouds: Online trajectory generation and autonomous navigation for quadrotors in cluttered environments,” J. Field. Robot. 36(4), 710–733 (2019).Google ScholarGoogle Scholar
Gao, F., Wu, W., Gao, W. and Shen, S., “’Flying on point clouds: Online trajectory generation and autonomous navigation for quadrotors in cluttered environments,” J. Field. Robot. 36(4), 710–733 (2019).CrossRefGoogle Scholar
Liu, S., Watterson, M., Mohta, K., Sun, K., Bhattacharya, C. J. T. S. and Kumar, V., “Planning dynamically feasible trajectories for quadrotors using safe flight corridors in 3-d complex environments,” IEEE Robot. Autom. Mag. 2(3), 1688–1695 (2017).CrossRefGoogle Scholar
Huh, J., Arslan, O. and Lee, D., “Probabilistically Safe Corridors to Guide Sampling-Based Motion Planning,” arXiv:1901.00101 (2019).Google Scholar
Oleynikova, H., Taylor, Z., Fehr, M., Siegwart, R. and Nieto, J., “Voxblox: Incremental 3D Euclidean Signed Distance Fields for On-board Mav Planning,” Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (2017) pp. 1366–1373.Google Scholar
Mainprice, J., Sisbot, E., Jaillet, L. and Cortes, J., “Planning Human-Aware Motions Using a Sampling-Based Costmap Planner,” Proceedings of the IEEE International Conference on Robotics and Automation (2011) pp. 5012–5017.Google Scholar
Oleynikova, H., https://github.com/ethz-asl/mav_voxblox_planning.Google Scholar
Geraerts, R., “Planning Short Paths with Clearance Using Explicit Corridors,” Proceedings of the IEEE International Conference on Robotics and Automation (2010) pp. 1997–2004.Google Scholar