Current GIS based navigation systems lack specific landmarks blind pedestrian use. To address this issue we present a data structure for landmark-based navigation. The data structure supports definition of specific landmarks such as surface, acoustic, olfactory properties of environment same as definition of important landmarks along a route. Routing algorithm takes in account specific preferences and abilities of blind travelers such as inability to cross large open spaces or preference to use underpass from unmarked pedestrian crossing. Resulting step-by-step navigation instructions enable users to navigate independently along the route.