Indoor Human Navigation Systems: A Survey <s> Path Planning <s> This paper presents the research for the development of a new travel aid to increase the independent mobility of blind and elderly travellers. This aid will build on the technologies of geographical information systems (GIS) and the Global Positioning System (GPS). The MOBIC Travel Aid (MOTA) consists of two interrelated components : the MOBIC Pre-journey System (MOPS) to assist users in planning journeys and the MOBIC Outdoor System (MooDs) to execute these plans by providing users with orientation and navigation assistance during journeys. The MOBIC travel aid is complementary to primary mobility aids such as the long cane or guide dog. Results of a study of user requirements are presented and their implications for the initial design of the system are discussed. <s> BIB001 </s> Indoor Human Navigation Systems: A Survey <s> Path Planning <s> Drishti is a wireless pedestrian navigation system. It integrates several technologies including wearable computers, voice recognition and synthesis, wireless networks, Geographic Information System (GIS) and Global positioning system (GPS). Drishti augments contextual information to the visually impaired and computes optimized routes based on user preference, temporal constraints (e.g. traffic congestion), and dynamic obstacles (e.g. ongoing ground work, road blockade for special events). The system constantly guides the blind user to navigate based on static and dynamic data. Environmental conditions and landmark information queried from a spatial database along their route are provided on the fly through detailed explanatory voice cues. The system also provides capability for the user to add intelligence, as perceived by, the blind user, to the central server hosting the spatial database. Our system is supplementary to other navigational aids such as canes, blind guide dogs and wheel chairs. <s> BIB002 </s> Indoor Human Navigation Systems: A Survey <s> Path Planning <s> The position-tracking accuracy of a location-aware mobile system can change dynamically as a function of the user’s location and other variables specific to the tracker technology used. This is especially problematic for mobile augmented reality systems, which ideally require extremely precise position tracking for the user’s head, but which may not always be able to achieve the necessary level of accuracy. While it is possible to ignore variable positional accuracy in an augmented reality user interface, this can make for a confusing system; for example, when accuracy is low, virtual objects that are nominally registered with real ones may be too far off to be of use. To address this problem, we describe the early stages of an experimental mobile augmented reality system that adapts its user interface automatically to accommodate changes in tracking accuracy. Our system employs different technologies for tracking a user’s position, resulting in a wide variation in positional accuracy: an indoor ultrasonic tracker and an outdoor real-time kinematic GPS system. For areas outside the range of both, we introduce a dead-reckoning approach that combines a pedometer and orientation tracker with environmental knowledge expressed in spatial maps and accessibility graphs. We present preliminary results from this approach in the context of a navigational guidance system that helps users to orient themselves in an unfamiliar environment. Our system uses inferencing and path planning to guide users toward targets that they choose. <s> BIB003 </s> Indoor Human Navigation Systems: A Survey <s> Path Planning <s> The design of mobile navigation systems adapting to limited resources will be an important future challenge. Since typically several different means of transportation have to be combined in order to reach a destination, the user interface of such a system has to adapt to the user's changing situation. This applies especially to the alternating use of different technologies to detect the user's position, which should be as seamless as possible. This article presents a hybrid navigation system that relies on different technologies to determine the user's location and that adapts the presentation of route directions to the limited technical resources of the output device and the limited cognitive resources of the user. <s> BIB004 </s> Indoor Human Navigation Systems: A Survey <s> Path Planning <s> Walking is the most fundamental means of human transportation. Unlike travel by car, walking is not planar, but rather stereoscopic. We therefore developed a real navigation system for pedestrian point-to-point navigation. We propose herein a method of 3D pedestrian navigation, in which position detection is driven mainly by dead reckoning. The proposed method enables ubiquitous round-the-clock 3D positioning, even inside buildings or between tall buildings. In addition, pedestrian navigation is customized by changing the costs of the road network links. Finally, a positioning data accumulation system is implemented so that we can log tracks and easily incorporate new roads or attributes in the future. <s> BIB005 </s> Indoor Human Navigation Systems: A Survey <s> Path Planning <s> We present a robot-assisted wayfinding system for the visually impaired in structured indoor environments. The system consists of a mobile robotic guide and small passive RFID sensors embedded in the environment. The system is intended for use in indoor environments, such as office buildings, supermarkets and airports. We describe how the system was deployed in two indoor environments and evaluated by visually impaired participants in a series of pilot experiments. We analyze the system's successes and failures and outline our plans for future research and development. <s> BIB006 </s> Indoor Human Navigation Systems: A Survey <s> Path Planning <s> Location-based mobile services have been in use, and studied, for a long time. With the proliferation of wireless networking technologies, users are mostly interested in advanced services that render the surrounding environment (i.e., the building) highly intelligent and significantly facilitate their activities. In this paper our focus is on indoor navigation, one of the most important location services. Existing approaches for indoor navigation are driven by geometric information and neglect important aspects, such as the semantics of space and user capabilities and context. The derived applications are not intelligent enough to catalytically contribute to the pervasive computing vision. In this paper, a novel navigation mechanism is introduced. Such navigation scheme is enriched with user profiles and the adoption of an ontological framework. These enhancements introduce a series of technical challenges that are extensively discussed throughout the paper. <s> BIB007 </s> Indoor Human Navigation Systems: A Survey <s> Path Planning <s> The Context sensitive Indoor Navigation System (CoINS) implements an architecture to develop context-aware indoor user guidance services and applications. This paper presents a detailed discussion on algorithms and architectural issues in building an indoor guidance system. We first start with the World Model and required mapping to 2D for the process of path calculation and simplification. We also compare several algorithm optimizations applied in this particular context. The system provides the infrastructure to support different techniques of presenting the path and supporting user orientation to reach a certain destination in indoor premises. <s> BIB008 </s> Indoor Human Navigation Systems: A Survey <s> Path Planning <s> This paper describes, path planning and following algorithms for use in indoor navigation for the blind and visually impaired. Providing indoor navigational assistance for this type of users presents additional challenges not faced by conventional guidance systems, due to the personal nature of the interactions. The algorithms are part of an overall Indoor Navigation Model that is used to provide assistance and guidance in unfamiliar indoor environments. Path planning uses the A* and Dijkstra's shortest path algorithms, to operate on an "Intelligent Map", that is based on a new data structure termed "cactus tree" which is predicated on the relationships between the different objects that represent an indoor environment. The paths produced are termed "virtual hand rails", which can be used to dynamically plan a path for a user within a region. The path following algorithm is based on dead reckoning, but incorporates human factors as well as information about the flooring and furnishing structures along the intended planned path. Experimental and simulating results show that the guiding/navigation problem becomes a divergent mathematical problem if the positional information offered by the positioning and tracking systems does not reach a certain requirement. This research explores the potential to design an application for the visually impaired even when to- date 'positioning and tracking' system cannot offer reliable position information that highly required by this type of application. <s> BIB009 </s> Indoor Human Navigation Systems: A Survey <s> Path Planning <s> Almost 2 million Japanese citizens use Navitime, a mobile phone-based navigation service that incorporates various modes of transportation. User experiences reveal implications for designing urban-computing services. Location-based services are a key pervasive computing application that could deeply influence urban spaces and their inhabitants. Recent advances in mobile phones, GPS, and wireless networking infrastructures are making it possible to implement and operate large-scale location- based services in the real world. <s> BIB010 </s> Indoor Human Navigation Systems: A Survey <s> Path Planning <s> In this paper, a novel tour-guiding system is introduced, based on our space-identifying ubiquitous infrastructure, where positioning devices are deployed ubiquitously to identify the place of users. In this infrastructure, we can flexibly construct information service related to the places of interest in the city by modeling the space of the real world as a set of relations among the discrete places, and attaching space-identifying devices to them. Our developed tour-guiding system introduces many art works in a large commercial complex in Japan. Based on the benefit of the infrastructure, this system can provide detailed navigation service as well as art introduction service in both indoor and outdoor environments, and can guide the users to reach their interested art works. Currently, this system is already used in practice for a commercial service. In this paper, the design of this system is described and its navigation capability is verified through a user test in the real environment to discuss the effectiveness of our approach. <s> BIB011 </s> Indoor Human Navigation Systems: A Survey <s> Path Planning <s> A location and tracking system becomes very important to our future world of pervasive computing, where information is all around us. Location is one of the most needed information for emerging and future applications. Since the public use of GPS satellite is allowed, several state-of-the-art devices become part of our life, e.g. a car navigator and a mobile phone with a built-in GPS receiver. However, location information for indoor environments is still very limited. Several techniques are proposed to get location information in buildings such as using a radio signal triangulation, a radio signal (beacon) emitter, or signal fingerprinting. Using radio frequency identification (RFID) tags is a new way of giving location information to users. Due to its passive communication circuit, RFID tags can be embedded almost anywhere without an energy source. The tags stores location information and gives it to any reader that is within a proximity range which can be up to 10-15 meters for UHF RFID systems. We propose an RFID-based system for navigation in a building for blind people or visually impaired. The system relies on the location information on the tag, a userpsilas destination, and a routing server where the shortest route from the userpsilas current location to the destination. The navigation device communicates with the routing server using GPRS networks. We build a prototype based on our design and show some results. We found that there are some delay problems in the devices which are the communication delay due to the cold start cycle of a GPRS modem and the voice delay due to the file transfer delay from a MMC module. <s> BIB012 </s> Indoor Human Navigation Systems: A Survey <s> Path Planning <s> Previous studies suggest that humans rely on geometric visual information (hallway structure) rather than non-geometric visual information (eg doors, signs, and lighting) for acquiring cognitive maps of novel indoor layouts. In this study we asked whether visual impairment and age affect reliance on non-geometric visual information for layout learning. We tested three groups of participants—younger (<50 years of age) normally sighted; older (50–70 years of age) normally sighted; and low-vision (people with heterogeneous forms of visual impairment ranging in age from 18 to 67 years). Participants learned target locations in building layouts using four presentation modes: a desktop virtual environment (VE) displaying only geometric cues (sparse VE); a VE displaying both geometric and non-geometric cues (photorealistic VE); a map; and a real building. Layout knowledge was assessed by map drawing and by asking participants to walk to specified targets in the real space. Results indicate that low-vision and ol... <s> BIB013 </s> Indoor Human Navigation Systems: A Survey <s> Path Planning <s> This paper proposes a framework to enable intuitive navigation guidance for complex buildings which are huge in size and their space boundaries contain non-convex shape including non-navigable areas inside. Our approach utilizes ‘topological’ way-finding method to generate paths. This can be done by means of the integration of building information model (BIM) with our new algorithm to subdivide the spaces. The second main principle is to improve the visual information by using a new method to render all three dimensional views possibly observed in a building beforehand. This has been realized by imaging serviced using client-server architecture with supercomputer computation power. <s> BIB014
In addition to localizing users, a navigation system can provide directions from the user's current location to a user-specified destination. This involves planning a path and turning it into easy to follow directions. As the user follows directions, the system will dynamically updates its estimation of the user's location and generate a new direction once the previous direction has been completed. Since the user might fail to follow instructions and veer from the planned path, the system should be able to detect this situation and re-plan the path. Though planning different routes to a destination or dynamically updating the path is a common feature for car navigation systems, only a few human navigation systems  BIB011 BIB012 BIB006 offer this feature. Most human navigation systems seem to primarily focus on localization, which allows users to freely explore an environment. Path planning is an important part of the navigation, which can affect the overall performance of the system. The path needs to be planned in such a way to maximize the usability and success rate while minimizing the chance of the user getting lost. A smarter path planning technique needs to consider users' requirements and customize the path accordingly. Shortest path or shortest travel time is desirable for majority of users and most of the current navigation systems BIB011 BIB012  use the shortest path algorithms but this might not be suitable for everyone, for example, tourists might prefer a longer path which takes them along interesting landmarks. A planning technique might minimize the cognitive load BIB004 considering the complexity of a path and the directions provided, to help elderly or individuals with cognitive problems. For individuals with visual impairments a path that goes along walls reduces the chance of the user getting lost and a path which avoids low ceilings is much safer. Figure 1 illustrates a case where the shortest path results in high uncertainty. Such systems try to find the path with the least hazard BIB002 BIB006 BIB001 BIB009 . Accessibility of the path might be considered when planning the path for wheelchair users or elderly such that stairs are avoided and the slope of each path is considered BIB005 BIB001 . A flexible system might let the user to set preferences based on their needs BIB010 BIB005 BIB001 BIB007 . Path planning algorithms use graphs or grids to represent the environment. To plan a path using graph based approaches, the environment is divided into sets of nodes and edges connecting these nodes. Depending on the path planning algorithm and constraints, these nodes might be any type of object, such as hallway intersections, doors, or obstacles. Edges connect these nodes together based on the environment map and if one node is accessible from the other one. In this case each edge might have a weight assigned to it based on different criteria for the path planning. In case of the gridbased approach, the environment is divided to small parts called cells. Each cell contains information regarding the objects at that location and environment description. Cells might have weights associated with them similar to edges in case of the graph based approach. The grid based approach might have a resolution problem, as if the cells are big, multiple object might reside in the same cell and each cell needs to have a structure to hold the details. While using smaller cells increases the computation required for planning a path and many cells might not have any valuable information or an object might reside in multiple cells. A graph-based approach has the advantage of creating the nodes only if there are objects. Edges are created only if objects are accessible from each other, but in complicated environments with many objects, the graph might become big and decreases the performance of the path-planning algorithm. The weight associated with edges or cells play an important role when customizing a path, for example, in case of a path that should avoid stairs, the edges with stairs receive higher weights, or edges with low ceiling have higher weights when planning a path for individuals with visual impairments. Most of current navigation systems use either Dijkstra BIB003 BIB005 BIB014 BIB008 or A* BIB003 BIB001 BIB009 for path planning.  Many indoor navigation systems are developed for users with visual impairments, who could benefit from "smarter" path planning techniques. Because the identification of tactile landmarks already plays a significant role in how users with visual impairments navigate familiar spaces  BIB013 , indoor navigation systems should incorporate this by planning paths that go along easily identifiable landmarks as to increase the successful completion of a path. Though veering is less of a problem for indoor environments than it is for outdoor environments, systems should also avoid large open indoor spaces for users with visual impairments and instead lead users along a wall to assure they arrive at the desired destination. Navigation systems could also plan smarter paths for users with different disabilities. For example, wheelchair users could benefit from paths that do not involve stairs or ramps.