Fly-Navi: A Novel Indoor Navigation System With On-the-Fly Map Generation

Existing studies on indoor navigation often require such a pre-deployment as floor map, localization system and/or additional (customized) hardwares, or human motion traces, making them prohibitive when the situation deviates from these requirements (e.g., navigating a crowd of panicking people where no localization system or motion traces are available). The main observation inspiring our work without reliance on such pre-deployment is that when there are sufficient participants (e.g., a crowd of panicking people), the WiFi signatures collected by participants can serve as the fingerprints (referred to as location fingerprints) of their unknown locations. By computing relative positions of these location fingerprints we can connect them to form a global map. Such a map reflects the topology of the underlying walkable space and thus holds the potential of offering a navigation path for any intended users. Based on this observation, we design Fly-Navi, a crowdsourcing based indoor navigation system via on-the-fly map generation, and primarily designed for indoor environments with rectilinear and narrow corridors. Specifically, each participant uploads sensory data, and the server then generates a global map (on-the-fly map) through a series of operations such as local map generation, local map stitch and edge computation. On top of the global map, Fly-Navi computes a navigation path to the given destination and tracks the progress. We implement the prototype of Fly-Navi and our experiments show that Fly-Navi can quickly generate a correct global map with the 80-percentile of between-fingerprint distance error less than 3 meters, which is important for computing turning points of the map and hereon offering turn-by-turn instructions, and correctly navigate the intended users to their destinations.