Autonomous Vehicle Path Planning using Signal Reliability Maps
Sonya Ragothaman, Mahdi Maaref, and Zak (Zaher) M. Kassas
Though global navigation satellite system (GNSS) technology has been the primary tool for navigation over the last few decades, these systems can be challenged in urban environments. High-rise structures block and shadow signals from satellites, thereby limiting geometric diversity in line of sight (LOS) satellites. In addition, GNSS signals suffer from severe multipath in urban environments. With the rise of autonomous vehicles, resilient systems for navigating in GNSS-challenged environments are necessary, particularly in the presence of multipath.
To improve reliability and availability in urban environments, one may choose to include signals of opportunity (SOPs), e.g., digital television (DTV), Wi-Fi, and cellular 2G/3G/4G. Some have proposed receiver designs to extract pseudoranges from these signals [1-4]. Cellular signals are particularly attractive SOPs due to their abundance, geometric diversity, and high received signal power . Though these qualities complement those of satellite signals, cellular signals can suffer severe multipath errors primarily due to low elevation angles in urban environments. In some cases (e.g., LTE signals of 20 MHz bandwidth), line-of-sight (LOS) signals can be differentiated from reflected signals depending on the surrounding geometry.
This paper considers the following problem. An autonomous ground vehicle (AGV) drives in an urban environment. The vehicle is equipped with GNSS and cellular SOP receivers as well as a three-dimensional (3D) building map. The AGV desires to reach a specified destination. In order to improve the navigation solution, the vehicle requires knowledge of the regions where high errors due to multipath are expected for SOPs, either to mitigate the error or avoid such regions. It also requires information about areas with LOS to GNSS signals. The vehicle will use the building map to plan trajectories based on best geometric dilution of precision (GDOP) in the measurements, or access to a specified number of transmitters. To this end, this paper focuses on building and using the reliability maps in Opportunistic Navigation (OpNav) environments.
?A reliability map is a map of areas where an SOP signal is expected to produce large pseudorange errors due to multipath. It is computed based on a 3D building map. The proposed reliability maps will have many applications in SOP-based navigation, such as autonomous vehicle safety, selection of tracking strategies, and optimal path planning. For an AGV, the proposed reliability maps can be used to determine regions that should be avoided due to poor signal coverage or geometric diversity. The reliability maps may also be used to predict areas where multipath mitigation techniques are necessary. In order to create reliability maps for an AGV, it is assumed that the 3D building map and cellular tower locations are fully known. In , it is shown that the pseudorange error can be parametrized by the relative path delay and relative signal power. Therefore, the proposed approach defines thresholds for path delay and signal power and evaluates the boundaries on the ground plane. This helps create the SOP reliability maps efficiently. The reliability maps can then be combined with GNSS LOS maps for path planning.
Research in multipath mitigation often involves surrounding geometry. In the work of N. I. Ziedan  an approach to use pattern recognition to create a tracking strategy selector based on signal condition is proposed. M. Ulmschneider et al. [7,8] treat LTE multipath reflections as an opportunity for more transmitters by using reflections and scattering points as virtual transmitters. In addition, research in multipath mitigation using surrounding geometry and ray tracing is rising due to the increasing availability of 3D maps. Y. Gu et al.  proposed the 3D-GNSS method, which uses building maps to correct the pseudorange delay caused by up to two reflections. N. I. Ziedan  proposed three algorithms to predict path delay, one of which used 3D maps and her accelerated ray tracing algorithm. These methods are concerned with a single receiver locations. Research in path-planning in urban environments based on GNSS satellite geometry consider multiple receiver locations when building maps. C. Yin et al.  defines a safety metric for multiple objective path planning, where the safety measure is the area of the intersection between a building and a constant uncertainty ellipse of the vehicle. Paul Ross Mathews  patented a path planning method based on GNSS signal obstructions and a dilution of precision (DOP) metric.
The topics of multipath and path-planning in urban environments are well studied for GNSS, but do not account for the differences in SOPs. The proposed maps could aid an SOP strategy selector by anticipating areas where one may require multipath mitigation or virtual transmitter techniques. The proposed reliability maps can improve path planning in urban environments that use SOPs by providing a safety measure (e.g., regions of poor GDOP from reliable signals). Additionally, SOP reliability needs to be assessed differently from GNSS reliability. The complexity arises as cellular SOP transmitters can improve geometric diversity through low elevation angles , but also suffer from severe multipath for the same reason. Also, the high bandwidth of some LTE signals (e.g. up to 20 MHz) tightens the threshold on path delay.
?The contributions of this paper are as follows. First, the paper introduces a computationally efficient framework to create SOP reliability maps, which contain regions where a signal is expected to produce large errors due to multipath based on a 3D building map. Second, the paper proposes a method to combine the proposed reliability maps with GNSS obstruction maps using a metric such as GDOP for path-planning purposes.
A preliminary test was conducted using a 3D building map of Portland, Oregon, U.S. An area with 23 buildings was considered, and a single 20 MHz transmitter was placed in the center. The thresholds, which were found through simulation, were set to 5e-8 seconds for relative path delay and 6 dB for relative power. The map produced from the proposed algorithm was compared to one produced in Wireless InSite from the same thresholds. Though the code is unoptimized, the proposed reliability map was produced in under 1.81 seconds when the algorithm was implemented in ArcGIS. Preliminary results from the comparison indicate that the map is 95.2% accurate in areas with access to the direct signal compared to the map produced by Wireless Insite. The proposed paper will include a simulation of an AGV generating paths with minimal pseudorange errors given a specified destination. The map will be experimentally validated in a ground vehicle by collecting LTE signals in downtown Riverside, California, U.S. with a known 3D building map and comparing the pseudorange errors for selected paths.
 C. Yang , T. Nguyen, D. Qiu, J. Casper and M. Quigley, "Positioning with Mixed Signals of Opportunity," Proceedings of the 24th International Technical Meeting of The Satellite Division of the Institute of Navigation (ION GNSS 2011), Portland, OR, September 2011, pp. 447-456.
 M. Rabinowitz and J. Spilker Jr., “A new positioning system using television synchronization Signals,” IEEE Transactions on Broadcasting, vol. 51, no. 1, pp. 51–61, March 2005.
 J. Khalifeh, Z. Kassas, and S. Saab, “Indoor localization based on floor plans and power maps: non-line of sight to virtual line of sight,” ION Global Navigation Satellite Systems Conference, September 14-18, 2015, Tampa, FL, pp. 2291-2300
 K. Shamaei and Z. Kassas, “Computationally Efficient Receiver Design for Mitigating Multipath for Positioning with LTE Signals,” ION Global Navigation Satellite Systems Conference, September 25-29, 2017, Portland, OR.
 K. Pesyna, Z. Kassas, J. Bhatti, and T. Humphreys, “Tightly-coupled opportunistic navigation for deep urban and indoor positioning,” Proceedings of ION GNSS Conference, September 2011, pp. 3605–3617.
 N. I. Ziedan, "Multipath Channel Estimation and Pattern Recognition for Environment-Based Adaptive Tracking," Proceedings of the 25th International Technical Meeting of The Satellite Division of the Institute of Navigation (ION GNSS 2012), Nashville, TN, September 2012, pp. 394-407.
 C. Gentner, T. Jost, W. Wang, S. Zhang, A. Dammann and U. C. Fiebig, "Multipath Assisted Positioning with Simultaneous Localization and Mapping," in IEEE Transactions on Wireless Communications, vol. 15, no. 9, pp. 6104-6117, September 2016.
 M. Ulmschneider and C. Gentner, "Multipath assisted positioning for pedestrians using LTE signals," IEEE/ION Position, Location and Navigation Symposium (PLANS), Savannah, GA, 2016, pp. 386-392.
 Y. Gu and S. Kamijo, "GNSS positioning in deep urban city with 3D map and double reflection," European Navigation Conference (ENC), Lausanne, May 2017, pp. 84-90.
 N. I. Ziedan, "Urban Positioning Accuracy Enhancement Utilizing 3D Buildings Model and Accelerated Ray Tracing Algorithm," Proceedings of the 30th International Technical Meeting of The Satellite Division of the Institute of Navigation (ION GNSS+ 2017), Portland, Oregon, September 2017.
 C. Yin, Z. Xiao, X. Cao, X. Xi, P. Yang and D. Wu, "Offline and Online Search: UAV Multi-Objective Path Planning under Dynamic Urban Environment," IEEE Internet of Things Journal, vol. PP, no. 99, pp. 1-1.
 P. Matthews, “Path planning based on obstruction mapping,” US Patent Application Publication 3,064,964, September 7th, 2016.
 J. Morales, J. Khalife, and Z. Kassas, “GNSS vertical dilution of precision reduction using terrestrial signals of opportunity,” in Proceedings of ION International Technical Meeting, January 2016, Monterey, CA, pp. 664-669