Abstract
The mission of future parcel delivery will be performed by unmanned aerial vehicles (UAVs). However, the localization of global navigation satellite systems (GNSS) in urban areas experiences the notorious multipath effect and non-line-of-sight (NLOS) reception which could potentially generate approximately 50 meters of positioning error. This misleading localization result can be hazardous for UAV applications in GNSS-challenged areas. Due to multipath complexity, there is no general solution to eliminate this effect. A solution to guide UAV operation is to plan an optimal route that smartly avoids the area with a strong multipath effect. To achieve this goal, the impact of the multipath effect in terms of positioning error at different locations must be predicted. This paper proposes to simulate the reflection route by a ray-tracing technique, aided by predicted satellite positions and the widely available 3D building model. Thus, the multipath effect in the pseudorange domain can be simulated using the reflection route and multipath noise envelope according, according to specific correlator designs. By constructing the multipath-biased pseudorange domain, the predicted positioning error can be obtained using a least square positioning method. Finally, the predicted GNSS error distribution of a target area can be further constructed. A new A* path planning algorithm is developed to combine with the GNSS error distribution. This paper designs a new cost function to consider both the distance to the destination and the positioning error at each grid. By comparing the conventional and the proposed path planning algorithms, the planned paths of the proposed methods experienced fewer positioning errors, which can lead to safer routes for UAVs in urban areas.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Erdelj, M., Natalizio, E.: UAV-assisted disaster management: applications and open issues. In: 2016 International Conference on Computing, Networking and Communications (ICNC) (2016)
Cistone, J.: Next century aerospace traffic management: the sky is no longer the limit. J. Aircraft 41(1), 36–42 (2004)
Chiang, K.-W., Duong, T., Liao, J.-K.: The performance analysis of a real-time integrated INS/GPS vehicle navigation system with abnormal GPS measurement elimination. Sensors 13(8), 10599 (2013)
Kaplan, E., Hegarty, C.: Understanding GPS: Principles and Applications. Artech House (2005)
Hsu, L.T., et al.: Multiple faulty GNSS measurement exclusion based on consistency check in Urban Canyons. IEEE Sensors J. 17(6), 1909–1917 (2017)
Christian, E., Lasse, K., Heiner, K.: Real-time single-frequency GPS/MEMS-IMU attitude determination of lightweight UAVs. Sensors 15(10), 26212–26235 (2015)
Birk, A., et al.: Safety, security, and rescue missions with an unmanned aerial vehicle (UAV). J. Intell. Robot. Syst. 64(1), 57–76 (2011)
Song, Y., et al.: Towards autonomous control of quadrotor unmanned aerial vehicles in a GPS-denied urban area via laser ranger finder. Optik.-Int. J. Light Electron Opt. 126(23), 3877–3882 (2015)
Leishman, R., McLain, T., Beard, R.: Relative navigation approach for vision-based aerial GPS-denied navigation. J. Intell. Robot. Syst. 74(1), 97–111 (2014)
Zhu, H., Xin, H., Zheng, C.: Research on UAV path planning. Appl. Mech. Mater. 58–60, 2351 (2011)
Medeiros, F., Silva, J.: Computational modeling for automatic path planning based on evaluations of the effects of impacts of UAVs on the ground. J. Intell. Robot. Syst. 61(1), 181–202 (2011)
Moon, S., Oh, E., Shim, D.: An integral framework of task assignment and path planning for multiple unmanned aerial vehicles in dynamic environments. J. Intell. Robot. Syst. 70(1), 303–313 (2013)
Dong, Z., et al.: A Hybrid Approach of virtual force and A* search algorithm for UAV path re-planning. In: 2011 6th IEEE Conference on Industrial Electronics and Applications (2011)
Khuswendi, T., Hindersah, H., Adiprawita, W.: UAV Path planning using potential field and modified receding horizon A* 3D algorithm. In: Proceedings of the 2011 International Conference on Electrical Engineering and Informatics (2011)
Lin, C.L., et al.: Flight path planning for mini rotor UAVs. In: 11th IEEE International Conference on Control & Automation (ICCA) (2014)
Meister, O., et al.: Adaptive path planning for a VTOL-UAV. In: 2008 IEEE/ION Position, Location and Navigation Symposium (2008)
Filippis, L., Guglieri, G., Quagliotti, F.: Path planning strategies for UAVS in 3D environments. J. Intell. Robot. Syst. 65(1), 247–264 (2012)
Xia, L., et al.: Path planning for UAV based on improved heuristic A* algorithm. In: 2009 9th International Conference on Electronic Measurement & Instruments (2009)
Ten Harmsel, A.J., Olson, I.J., Atkins, E.M.: Emergency flight planning for an energy-constrained multicopter. J. Intell. Robot Syst (2016)
De Filippis, L., Guglieri, G., Quagliotti, F.: A minimum risk approach for path planning of UAVs. J. Intell. Robot. Syst. 61(1), 203–219 (2011)
Tseng, F.H., et al.: A star search algorithm for civil UAV path planning with 3G communication. In: 2014 Tenth International Conference on Intelligent Information Hiding and Multimedia Signal Processing (2014)
Krawiec, B., Kochersberger, K., Conner, D.: Autonomous aerial radio repeating using an A*-based path planning approach. J. Intell. Robot. Syst. 74(3), 769–789 (2014)
Hawa, M.: Light-assisted a* path planning. Eng. Appl. Artif. Intell. 26(2), 888–898 (2013)
Sun, X., Cai, C., Shen, X.: A new cloud model based human-machine cooperative path planning method. J. Intell. Robot. Syst. 79(1), 3–19 (2015)
Zhan, W., et al.: Efficient UAV path planning with multiconstraints in a 3D large battlefield environment. Math. Probl. Eng. 2014, 1–12 (2014). https://www.hindawi.com/journals/mpe/2014/597092/cta/
Kunchev, V., et al.: Path Planning and Obstacle Avoidance for Autonomous Mobile Robots: a Review International Conference on Knowledge-Based and Intelligent Information and Engineering Systems. Springer (2006)
Chen, X., Zhang, J.: The three-dimension path planning of UAV based on improved artificial potential field in dynamic environment. In: 2013 5Th International Conference on Intelligent Human-Machine Systems and Cybernetics (2013)
Montiel, O., Sepúlveda, R., Orozco-Rosas, U.: Optimal path planning generation for mobile robots using parallel evolutionary artificial potential field. J. Intell. Robot. Syst. 79(2), 237–257 (2015)
Mac, T.T., et al.: Improved potential field method for unknown obstacle avoidance using UAV in indoor environment. In: 2016 IEEE 14th International Symposium on Applied Machine Intelligence and Informatics (SAMI) (2016)
Raja, P., Pugazhenthi, S.: Optimal path planning of mobile robots: a review. Int. J. Phys. Sci. 7(9), 1314–1320 (2012)
Allaire, F., et al.: FPGA Implementation of genetic algorithm for UAV real-time path planning. J. Intell. Robot. Syst. 54(1), 495–510 (2009)
Roberge, V., Tarbouchi, M., Labonté, G.: Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning. IEEE Trans. Ind. Inf. 9(1), 132–141 (2013)
Ismail, A., Sheta, A., Al-Weshah, M.: A mobile robot path planning using genetic algorithm in static environment. J. Comput. Sci. 4(4), 341–344 (2008)
Tsai, C.-C., Huang, H.-C., Chan, C.-K.: Parallel elite genetic algorithm and its application to global path planning for autonomous robot navigation. IEEE Trans. Ind. Electron. 58(10), 4813–4821 (2011)
Frontera, G., et al.: Approximate 3D Euclidean shortest paths for unmanned aircraft in urban environments. J. Intell. Robot Syst (2016)
Kim, J.-H., Sukkarieh, S., Wishart, S.: Real-time navigation, guidance, and control of a UAV using low-cost sensors. In: Yuta, S.I., et al. (eds.) Field and Service Robotics: Recent Advances in Reserch and Applications, pp 299–309. Springer, Berlin (2006)
Jan, S.S., et al.: Improving GPS-based landing system performance using an empirical barometric altimeter confidence bound. IEEE Trans. Aerosp. Electron. Syst. 44(1), 127–146 (2008)
Albéri, M., et al.: Accuracy of flight altitude measured with low-cost GNSS, radar and barometer sensors: Implications for airborne radiometric surveys. Sensors 17(8), 1889 (2017)
Zhang, G., Hsu, L. -T.: A new path planning algorithm based on GNSS localization error map. In: ION GNSS + , Portland (2017)
Misra, P., Enge, P.: Global Positioning System: Signals, Measurements and Performance, 2nd edn. Ganga-Jamuna Press, Massachusetts (2006)
Parkinson, B.W., Enge, P.K.: Differential gps. Global Positioning. Syst. Theor. Appl. 2, 3–50 (1996)
Veitsel, V.A., Zhdanov, A.V., Zhodzishsky, M.I.: The mitigation of multipath errors by strobe correlators in GPS/GLONASS receivers. GPS Solut. 2(2), 38–45 (1998)
Hsu, L.-T., Gu, Y., Kamijo, S.: 3D building model-based pedestrian positioning method using GPS/GLONASS/QZSS and its reliability calculation. J. Global Navig. Satell. Syst. 20(3), 413–428 (2016)
Hsu, L.-T.: Analysis and modeling GPS NLOS effect in highly urbanized area. GPS Solutions 22(1), 7 (2017)
Dierendonck, A.J., Fenton, P., Ford, T.: Theory and performance of narrow correlator spacing in a GPS receiver. Navigation 39(3), 265–283 (1992)
Garin, L., van Diggelen, F., Rousseau, J.-M.: Strobe and edge correlator multipath mitigation for code. In: ION GPS-96 (1996)
Acknowledgments
The authors acknowledge the fund of “Fundamental Research on Free Exploration Category of Shenzhen Municipal Science and Technology Innovation Committee (Project No. JCYJ20170818103653507)” to support this research.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Zhang, G., Hsu, LT. A New Path Planning Algorithm Using a GNSS Localization Error Map for UAVs in an Urban Area. J Intell Robot Syst 94, 219–235 (2019). https://doi.org/10.1007/s10846-018-0894-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10846-018-0894-5