Complexity-reduced FootSLAM for indoor pedestrian navigation

FootSLAM or simultaneous localization and mapping (SLAM) for pedestrians is a technique that addresses the indoor positioning and mapping problem based on human odometry (aka pedestrian dead reckoning), e.g. with a foot-mounted inertial sensor. FootSLAM follows the FastSLAM factorization, using a Rao-Blackwellized particle filter to simultaneously estimate the building layout and the pedestrian´s pose - his position and orientation. To that end, FootSLAM divides the 2D space into a grid of uniform and adjacent hexagons and counts the number of times each particle crosses the edges of the hexagons it visits. As we shall show, the complexity of FootSLAM grows quadratically with time, preventing the mapping of large areas.