Mass-market GPS applications have mainly focused on car navigation over the last five years. A wide range of applications can be foreseen for pedestrians as well: multimodal navigation, local search, and social networking are a few. But the rollout of most accuracy-critical applications like e-tourism has been slowed by the difficulties of GPS-based positioning for pedestrians in urban areas.
Multipath and masking effects of urban canyons degrade the accuracy of GPS ranging and increase geometric dilution of precision in receivers that operate in dense urban areas. In the case of GPS applications designed for vehicles, the effects of these phenomena on accuracy can be reduced, thanks to the velocity of the user that contributes in averaging multipath and thanks to the use of map matching. But pedestrians do not benefit from the same circumstances, and GPS-based positioning for pedestrians in dense urban areas suffers from inadequate accuracy and integrity. Tests performed in downtown urban areas over a variety of mass-market terminals with integrated GPS receivers show 95% circular error probable (CEP) performances between 50 and 100 meters.
This article presents a novel approach: a GIS database that contains the geometrical description of buildings is used in the location computation process. Raw data are extracted from the GPS receiver and used in combination with the description of surrounding buildings. The method involves restricting the area of possible locations, mitigating multipath effects, matching GPS measurements with the environment, and using motion models to compute accurate fixes. Unlike usual map matching, the solution maintains the intrinsic freedom of the pedestrian, keeping track of the actual trajectory across squares, courtyards, and gardens.
Dense urban environments
The well-known urban canyon effect on GPS positioning does not equally affect car drivers and pedestrians. At higher speeds, acquisition algorithms, tracking loops, and Kalman filters all better manage to reject or smooth effects resulting from multipath. The different behaviors of pedestrians and cars also contribute to different accuracy results, even in the same places. For instance, pedestrians use sidewalks close to buildings: this reduces satellite visibility, resulting in horizontal dilution of precision (HDOP) degradation.
Tests performed in the center of Toulouse, France, illustrate the discrepancy in accuracy performances between receivers operated by pedestrians and receivers operated by car drivers. Tests were run in an area where streets are approximately 5 to 20 meters wide and 15 to 20 meters high; smartphones with built-in GPS receivers were used. The car was driving at speeds between 30 and 50 km.h-1. More than 30,000 position fixes were collected in car mode and more than 15,000 in pedestrian mode.
The test environment was not extremely challenging in the tests we performed. Overall results had reasonable performances during tests. In more challenging environments, car drivers still experience inaccurate GPS positioning when in deep canyons, in the presence of highly reflective buildings, or when driving at low speed, but this topic will not be covered in this article.
New GIS products coming onto the market offer opportunities to bring answers to the problem with a market-ready approach.
Map-snapping limitations
Traditionally, map matching is used by a navigation application to move the current fix to the most likely road described by the application's geographical database, taking into account last positions. In this article, we refer to this technique as map snapping.
Map snapping provides good results in most cases of vehicle navigation, but suitability and performance for pedestrians is limited. Pedestrians not only walk on streets; they also cross squares, enter courtyards, wander in parks; pedestrians stop, turn around, and cross streets perpendicularly to the street axis.
Today, navigation applications use different solutions for pedestrian navigation: either they inactivate any map snapping when the user configures the application in pedestrian mode, or they implement 'smart map snapping,' which dynamically activates or inactivates map snapping depending on whether the application feels that the user follows a street or walks outside of the road network - a solution with only limited success.
Navigation algorithm overlay
New GIS products from major players describe the two-dimensional (2D) footprint of buildings in major cities and elevation. In addition, they have begun to describe building heights and 3D shapes. This opens the door to new algorithm opportunities. 2D footprints describe the real space where pedestrians can or cannot stand: they can be used to derive a priori probability of presence or of transition depending on the area. Building descriptions can be used to understand what effects GPS signals experienced before reception by the receiver, or to estimate what the GPS signal should be at the antenna or what measurements the receiver is expected to produce. This information can be used to select, weigh, or correct measurement data provided by the measurement engine of the GPS receiver.
We developed an algorithm to make use of these principles. The algorithm is based on a Bayesian inference framework, meaning that GPS measurements are used every second to update the probability of presence on a collection of positions. As a first step, the algorithm targets narrow street environments, focusing on diffuse multipath.
A key aspect of our study was to show that the concept could work with state-of-the-art databases and hardware. For this reason, the algorithm was limited to the use of 2D databases, considering that 3D databases have reduced coverage. The algorithm was developed to be able to operate with today's GPS chipsets integrated in mass-market devices.
Our prototype above was developed for Windows Mobile platforms, and integrated into several smartphones available on the market. This software, the navigation algorithm overlay (NAO), uses measurements provided by some GPS chipsets. From a functional point of view, NAO replaces the navigation engine of the GPS chipset. In terms of architecture, NAO is a software middleware that comes under the embedded application, in this case a navigation application, and provides the latter with position fixes in NMEA 0183 format on a virtual COM port. The NAO software uses a local database, referred to as NAO database, which bears data extracted from a GIS source that describes the 2D footprint of buildings.
Performance assessment
We tested NAO on a variety of targets: three types of smartphones and one PDA with a Bluetooth GPS add-on module. These devices either used standalone GPS receivers or GPS receivers aided by long-term ephemeris solutions. We selected a narrow urban canyon area in Toulouse for intensive tests. For these tests, the NAO database was generated from a GIS database produced by the Toulouse municipality.
We planned trajectories on the Google Earth Pro tool, which offers high-resolution pictures all over the city; trajectories were defined as collections of segments marked by waypoints. The bias between Google Earth and the NAO database was removed using geodetic references.
In all, 17 test cases were defined, 52 iterations were run, and 15,129 fixes were collected.
Over these tests, NAO showed an average cross-track error improvement by a factor of 3 over GPS, when the GPS chipset was able to compute a fix. In cases where the GPS chipset was only able to track two satellites, NAO was also able to compute a fix, whereas the GPS chipset did not, thus increasing availability.
We analyzed the improvement factor depending on the number of satellites used in fixes computed by the GPS receiver, and found that the smaller the number of satellites, the better the improvement brought by the algorithm. This can be easily understood by the fact that with higher numbers of usable satellites, the GPS chipset manages smoothing ranging errors better than with a small number of satellites, leaving less room for improvement by the algorithm. Note that in environments with long-range specular multipath such as skyscraper areas, the situation might be different: the algorithm may have a strong added value even when the receiver tracks a large number of satellites. Further tests are required to analyze these cases.
Sample results
Sample results in a test show, the GPS fix in the wrong street starting from the beginning; the NAO algorithm on its side selects the appropriate street. After following the appropriate bearing, the GPS receiver loses some satellites; this results in a significant drift of the position towards the south, as far as crossing the next parallel street. The NAO algorithm stays in the right street during this time. After having reached the appropriate street for some time, the receiver experiences oscillations, which prevent the user from deciding in what street he is actually standing. The NAO algorithm performs the right choice after a slight hesitation on the crossroad.
One could argue that GPS errors could be corrected by map snapping. We tested several off-the-shelf navigation applications in replay mode based on the GPS track logged during tests. Result of this test show output positions that were completely out of the path followed by the tester and do not even indicate any consistent trajectory; the receiver is 'lost.' Map snapping would not help GPS positioning in this case without the help of the NAO algorithm.
As the algorithm does not force fixes into streets, the trajectory computed by the algorithm sometimes crosses building areas, especially when GPS measurements are really noisy. Because of this, we tested using the same map-snapping solution as before, on top of the NAO algorithm. The results show accurate positioning and bearing for the combination of NAO with map snapping. In comparison, map snapping without NAO experiences low positioning accuracy, lack of availability (no output provided for GPS fix number 2) and bearing issues. The improvement brought by the NAO algorithm helps additional map-snapping algorithms relocate fixes in the appropriate street most of time, whereas map snapping on standalone GPS would have put fixes in the wrong street.
NAO significantly improves positioning results. However, the algorithm output does not perfectly fit in the street followed by the user. Map snapping was applied on top of both tracks to test whether map snapping was able to correct the raw GPS track, and whether NAO helped improve map snapping. Results show that map snapping is not able to correct the raw GPS track, but it perfectly matches the street when applied on top of NAO.
Improved accurgcy
A fusion algorithm between GPS measurements and GIS data that describe 2D footprints of buildings brought special improvements when the GPS receiver was tracking a small number of satellites, containing accuracy drifts experienced by the GPS receiver in such cases. The algorithm was even capable of computing accurate fixes with only two satellites over a short duration, after initialization was completed.
Apart from filtering noise and spurious multipath, the NAO algorithm adds coherency between computed fixes and maps seen by users. The algorithm proved its ability to be used as a map-matching solution for pedestrians. As the NAO algorithm does not force position fixes to be located on streets, we also showed the interest of using smart map snapping on top of the NAO algorithm: the NAO algorithm improves GPS accuracy such that it helps the map-snapping algorithm match fixes into appropriate streets.
Jean-Baptiste Prost is chief technology officer at Pole Star
Baptiste Godefroy is responsible for the Innovation & Engineering department at Pole Star
Stephane Terrenoir is R&D engineer at Pole Star
This article originally appeared in GPS World