Crowd Sourced Pedestrian Dead Reckoning and Mapping of Indoor Environments using Smartphones

Christian Gentner, Rostislav Karasek and Martin Schmidhammer

Abstract: The proliferation of smartphones has made positioning technologies available to a wide range of users. For outdoor localization, global navigation satellite systems (GNSSs) are the most elaborated and widely used technologies for positioning. In open sky conditions, GNSSs provide sufficient position accuracies for most mass market applications. However, for GNSS-denied environments, such as indoors and urban canyons, GNSS positioning accuracies are drastically reduced. In these environments, the received GNSS signals can be blocked, affected by multipath effects or received with low power. To enhance the positioning performance, alternative methods and sensor systems provide position information to support or even replace GNSSs. Most of the indoor positioning systems use local infrastructure like positioning with radio frequency identification (RFID), mobile communication base-stations, wireless local area network (WLAN) and ultra-wideband (UWB) systems. Since WLAN infrastructure is widely deployed, WLAN-based indoor positioning approaches are most common. Today, the majority of smartphones feature a micro-electro-mechanical system (MEMS) inertial measurement unit (IMU). An IMU is an electronic device that provides inertial measurements by using a combination of accelerometers and gyroscopes. The accelerometers measure the linear accelerations and the gyroscopes measure the turn rates. Numerical integrations of the inertial measurements allow to continuously compute position and attitude for inertial navigation: double integrating the acceleration yields to the position change; integrating the turn rate yields to the attitude change. IMUs are classically built as mechanical devices which consist of precision mechanical gyroscopes and accelerometers used in e.g. airplanes. In recent years, MEMS IMUs became popular with sub-cm size. However, compared to the mechanical IMUs, MEMS IMUs are not able to provide the same precision or long term stability. Because the position calculation involves double integrations, even small measurement errors quickly cause drifts, which lead to an unreliable position solution over time. Pedestrian dead reckoning (PDR) refers to the process of estimating the pose (3D position and heading) of a pedestrian at each step by integrating the cumulative change in pose since the last step. In other words, PDR is the process of estimating the individual steps of the pedestrian while moving. To estimate steps, PDR primarily relies on inertial sensors and also on additional sensors, e.g. the magnetometer which is typically used to correct the biases of the gyroscope. The basic pattern of human walking is cyclical. Hence, the acceleration data measured by the accelerometers carried by pedestrians are cyclical, too. Making use of the cyclical characteristics of human walking, PDR calculates the traveled distance by counting the steps and estimating each step length through inertial sensors. Heading can be estimated with magnetometers together with accelerometers and/or gyroscopes. The disadvantage of PDR systems is that the measurement error (drift) grows unboundedly over time. Processing the measurements in a way that additional information such as zero velocity updates (ZUPTs) from stance detection can be used, the error growth of inertial navigation can be reduced from cubic to linear. However, this typically requires mounting the IMU close to the foot. Many researchers are working on the difficult problem of calculating PDR from sensors at different body placements, such as pocket, wrist, and hand-held. Additionally, in order to calculate a global position, PDR relies on a known initial position, like outside buildings typically obtained with GNSS. However, if the positioning mode is switched on in GNSS-denied environments, e.g. inside a building, where no accurate global position is available, it is not possible to obtain an accurate position by PDR. Therefore, this paper addresses four aspects: 1. We present a novel step length estimation algorithm for smartphones which are carried in the hand or located in the pocket. The step detection algorithm incorporates walking direction changes for the step length estimation. Hence, in addition to the acceleration measurement, the proposed algorithm uses gyroscope measurements. Measurements showed that pedestrians are slowing down during walking curves. Thus, the step length estimation algorithm incorporates the heading changes. We compare the novel algorithm to state-of-the-art algorithms. Most other publications determine the accuracy of the PDR model by evaluating a whole walk of a pedestrian. Hence, the error is determined based on the whole walked distance. Contrarily, we evaluate the different algorithms by determining the accuracy of each step. 2. As mentioned before, in PDR the positioning error grows unbounded. In order to decrease the error we show a novel PDR which is able to compensate the error by detecting different courses of movement. By nature, human take the shortest possible path to get over a certain distance, which implies that pedestrian are mainly walking straight. By recognizing this human behavior, the error drift of the gyroscope and accelerometer can be corrected similarly to ZUPT. 3. Maps of building further allow reducing the positioning error. In order to obtain a map of an indoor area, we propose a simultaneous localization and mapping (SLAM) algorithm. The SLAM algorithm addresses the estimation of the pose of the moving pedestrian within an unknown environment by simultaneously estimating the map of the environment as the pedestrian moves. The estimated map is based on previously visited locations of the pedestrian (or other pedestrians). Hence, as soon as the pedestrian returns to an already mapped position, information of the previous movements at this position can be reused to obtain better predictions for the further movement. Similarly to previous publications, we propose a map that represents visited receiver positions by a two-dimensional hexagonal grid. 4. By generating a map of the pedestrian movement, we additionally map information of WLAN stations (RSS, IDs), Bluetooth anchor points, and mobile communication stations. This allows building an accurate database of the building which can be used for fingerprinting. Thereby, the database can help to improve the overall positioning accuracy for each pedestrian. Additionally, based on the database an accurate initial position estimate can be obtained, when the positioning device is switched on indoors. To verify the refined algorithm, the evaluations are based on measurement data of moving pedestrians. A Google Pixel 3 is used for recording the sensor data and used for all walks/pedestrians. The measurements are carried out inside and outside of an office building. The proposed algorithm estimates the position of the pedestrians in a local coordinate system. For the measurements we assume that at least one pedestrian is starting outdoors before entering the building. Hence, the GNSS receiver is used to initialize the position of the pedestrian outdoors in order to fix the coordinate system. The evaluations show that the horizontal positioning error of the developed positioning algorithm is around 2m for the first pedestrian. After multiple pedestrian shared there obtained map, the position accuracy of the pedestrian decreases below one meter.
Published in: Proceedings of the 32nd International Technical Meeting of the Satellite Division of The Institute of Navigation (ION GNSS+ 2019)
September 16 - 20, 2019
Hyatt Regency Miami
Miami, Florida
Pages: 299 - 347
Cite this article: Gentner, Christian, Karasek, Rostislav, Schmidhammer, Martin, "Crowd Sourced Pedestrian Dead Reckoning and Mapping of Indoor Environments using Smartphones," Proceedings of the 32nd International Technical Meeting of the Satellite Division of The Institute of Navigation (ION GNSS+ 2019), Miami, Florida, September 2019, pp. 299-347.
Full Paper: ION Members/Non-Members: 1 Download Credit
Sign In