A Wireless Indoor Navigation Aid for Visually Impaired People using UWB Localization Infrastructure and an Original Wayfinding Algorithm

This is the description of a work in progress for the development of a wireless indoor wayfinding system to aid visual impaired people navigating unknown environment with fixed and moving obstacles. Based on a commercial, state of the art Ultra Wideband (UWB) time of flight localization infrastructure, the system can find the best way for connecting a starting and a destination point in an indoor scenario while giving to the vision impaired people the hints to move on the surface avoiding obstacles. A typical example application of the system is for aiding visual impaired people navigate an unknown train station guiding him from descending the train to the bus stop (or taxi stop, or toilettes, or bar, or ticket counter, or other connecting trains, or the like). The present paper addresses the problem of identifying free paths to navigate into an area full of obstacles. This is the typical situation encountered in robotic guidance or blind people navigation assistance in complex indoor environments. Taking apart the problems of localization and tracking, here we are only concerned about the identification of the optimal path to be followed, given a preexistent binary map of obstacles, to connect the start and destination points in a given area. Notwithstanding the varous algorithms proposed so far, there is still a need for a very fast, robust, scalable and precise technique to be used in real time for the purpose. The implementation described in the following is made of a series of steps for obtaining the exact path from the preliminary knowledge of the obstacles (recorded as a simple binary map of the floor, clear, walkable, area) and the two positions of start and destination. The binary image of the floor is preliminarily treated with a thinning algorithm for obtaining all the possible paths on the area. The chosen thinning algorithm is the Safe-Point Thinning Algorithm (SPTA), which was custom modified for imposing passing by the start and destination points. Afterwards, the resulting path binary map is heuristically treated for identifying the nodes and connecting arcs and eliminating all the dead-ending branches while saving only the start and destination branches. The resulting graph is then used to feed the Dijkstra algorithm for finding the shortest path between the start and destination nodes. The result is the optimized path to follow for connecting two places in an unfamiliar environment. In the absence of standard environments able to objectively test the different algorithms, we tested our algorithm with various simulated situations of growing complexity to explore the performances in various cases. The algorithm was implemented in Visual BASIC and proved fast enough for real time use provided the entity to assist in navigation has a normal human speed of movement. We plan to use this algorithm in the implementation of a commercial navigation assistance system for blind people where localization and tracking will be provided by an UWB real time location system.
Adjunct Proceedings of the 14th International Conference on Location Based Services