2.1. Definitions

Pedestrian navigation has a short history when compared with sea and air navigation where many standards and specifications have been defined for a long time (Tiemeyer, Reference Tiemeyer2002). However the basic concept of navigation does not really change from one domain to another and the definitions of navigation's parameters remain similar. They just require specific adaptation to the context of positioning and guidance of persons. Therefore pedestrian navigation can also be assessed with four essential criteria: accuracy, continuity, integrity and availability (Federal Radionavigation Plan, 2005). The accuracy is the difference between the estimated or the measured position of a person and its true position at a given time. The continuity is the capability of the system to perform without unscheduled interruptions during the intended operation. The integrity is the measure of the trust that can be placed in the correctness of the information supplied by a navigation system. It includes the ability of the system to provide timely warnings to users when the system should not be used for navigation purposes. The availability of a navigation system is the percentage of time that the services of the system are usable and are delivered with the required accuracy, continuity and integrity within the specified coverage area. Availability is a function of both the physical characteristics of the environment and the technical capabilities of the navigation system itself.

2.2. Critical issues

This section introduces some typical situations where the navigation performances do not now match the users' requirements. The main critical issues are presented within the context of urban and indoor navigation. A large part of navigation systems exploits the characteristics of radio propagation to locate the mobile user but indoor and urban environments are hostile to broadcast signals.

Buildings are full of obstacles that affect the propagation of electromagnetic waves. The term obstacle designates any possible element that may reflect, block or diffract a signal. As such, building infrastructure (walls, floors and ceilings), facilities equipments (lifts, escalators, pipelines and ventilations) and even mobile furniture (shelves and lamps) are all obstacles. Because they induce artificial time delays in the propagation of radio waves, the navigation performances are strongly reduced. Globally those challenging environments lead to poor signal availability. Each time the signal propagates through a material, it fades. After successive attenuations, the signal might even be too weak to be tracked. For pedestrian location, another factor of fading is the human body (Renaudin, Reference Renaudin2009). Because human biological tissues are essentially made of salted water, they attenuate the strength of any signal that propagates through them. Depending on the receiver's placement, this phenomenon represents an additional limitation to navigation.

In urban zones that are full of electronic devices, the risk from multi-interferences to a signal is high. They result from fixed infrastructures and also from mobile devices carried by users. The number and the variety of these equipments are growing rapidly, which complicates any attempt to contain their impact on navigation. A classical illustration of interferences is the jumbling of radio signals, but electronic devices also induce other perturbations. Magnetic field perturbations resulting from manmade objects can also corrupt compass measurements. A mobile phone is a classical illustration of a magnetic perturbations source. These perturbations are hardly detectable and will introduce a bias leading to a systematic and large error in the estimation of position.

Another critical issue is the dependency to pre-installed infrastructure for communication and location services. Firstly, it is impossible to imagine that all buildings will be equipped with devices dedicated to navigation due to their cost. Secondly, some applications require a complete independence from any pre-installed equipment. The typical example is the intervention of emergency agents. In the case of a fire, navigation systems used by fire-fighters cannot rely on any equipment attached to buildings, as it might collapse.

Furthermore, indoors, the requirements in positioning accuracy are higher than outdoors. The smaller scale of indoor environments explains this fact. Pedestrians walk in rooms and corridors whose sizes are small. If we consider that the typical width of a corridor is between 2 and 3 metres, the positioning accuracy has to be better than 2 metres, just to locate the user in the right corridor or room.

Finally, navigation solutions produce data that are always related to maps that were designed mainly for the representation of the land and the sea containing specific routes. Because most of the navigable maps have been created based on the users' requirements, their design offers significant advantages to support existing navigation technology and route guidance. However a walking pedestrian is not attached to a specific network of “transportation” and he feels free to move anywhere. Therefore mapping these environments for pedestrians, without completely creating new maps, is also a critical issue.

3.1. The use of an absolute geographical reference

When localisation systems are not reliable, for some of the reasons described previously, the need for an absolute reference is crucial. Geographical maps, databases or waypoints are typical examples of absolute references. They are necessary to assess the reliability and the accuracy of the navigation solution, but also to recalibrate any technology affected by existing or propagated errors.

3.2. The hybridisation of complementary technologies

The availability of reliable measurements is a critical issue in challenging environments. The hybridisation of uncorrelated and complementary technologies increases the probability of having useful data. A classical illustration of fusion comes from navigation in transport where high grade inertial data are combined with GPS observations. For pedestrian navigation similar hybridisation is possible. It is interesting to couple Micro Electro Mechanical Systems (MEMS) data, mechanized in a dead reckoning mode, with any localisation system providing an absolute position. Radio based sensors network is one of the ideal candidates. RFID (Radio-frequency identification), WiFi (Wireless Fidelity) and UWB (Ultrawide Band) belong to this category.

3.3. Specific motion models

We have seen that because challenging environments are full of obstacles, the probability of recording biased data is really high. Therefore before using any signal as an observation in the navigation algorithms, it is important to estimate the reliability of the data. An interesting possibility consists of using motion models to assess the quality of the observations. Depending on the application and user's requirements, it is possible to design different models that express the specific movements of the mobile unit. For example, a biomechanical domain describes the standard walking cycle of a pedestrian. Classical mechanization equations are given by a dead-reckoning navigation process. This knowledge enables the definition of a motion model adequate for a pedestrian and the associated conditions equations. Contrary to a car or a plane, a pedestrian cannot drastically change his walking speed during very small time intervals. Consequently, the speed of the walker can be considered as constant over a very short period and the corresponding acceleration equals to zero. Here we have defined a condition equation for the pedestrian motion model. Based on available measurements, it is possible to estimate the parameters of the chosen motion model and to estimate the reliability of them thanks to the condition equations. This process, illustrated by the RANSAC paradigm (Fischler Reference Fischler and Bolles1981), acts as a filter to test the reliability of the observations. It is worth noting that working with motion models means treating differential data. As a consequence, any filtering based on this model will be able to process data that are coherent between each other during a specific time interval but might be affected by a systematic error. The last increases the amount of data available in environments where data availability is a critical parameter for the success of navigation solutions, as it enables in some cases the process of biased data.

3.4. System concept

Based on the three identified key elements, a new concept dedicated to the design of robust pedestrian navigation systems is proposed. This concept, illustrated in Figure 1, couples three processes: localisation algorithms, the use of geographical references and human motion models.

Figure 1. Scheme of the proposed concept for the design of robust pedestrian navigation systems.

Several positioning systems, in yellow in Figure 1, output data that feed the hybridisation process. Raw or pre-processed observations are used in different localisation algorithms and coupled together. The green part represents the absolute references. Geographical maps and waypoints are distinguished. While the first category corresponds to geographical data available as vector or raster format, the second category consists of a list of coordinates describing the footpath. Finally the blue box represents the use of pre-existing knowledge about the human movements. It combines the observations from the different localisation technologies with some parametric motion models to assess the reliability of the data and feeds back the global hybridisation filter.

Combining these three key elements in the design of a pedestrian navigation system is the proposed concept to improve and guarantee the quality of the final solution in terms of integrity, availability, continuity and accuracy. The developed concept is illustrated through two different pedestrian navigation scenarios.

4.1. Users' needs

Blind people face mobility issues in their daily lives, especially in complex environments like a shopping mall or a railway station. They acquire autonomy in their displacements after a long learning process. Their needs are commonly based on two main concepts that define the ability to move independently (Quéré, Reference Quéré and Relieu2001).

• • The orientation is the knowledge of his/her spatial position at a given time relative to specific locations.

• • The locomotion is the ability to move or the voluntary displacement in a given area. The locomotion can be direct (by foot) on indirect (public transportation, car).

For blind people, the learning techniques of locomotion are very important tools to increase their autonomy in mobility. Some of the important learning steps are the discovery of new environments, the ability to move safely with a white cane and the use of an educated guide dog. The discovery of a new area is performed with a professional of locomotion who describes the characteristics of the path to the blind person. During this learning phase, the person makes a mental map of the trail and its environment. Some additional tools can be used to explore a specific area, for example a scale city model with specific attributes written in Braille (streets names, main point of interest). Recently some technological developments have improved the mobility of blind people. Although they must be regarded only as an auxiliary aid, some of these systems are already available on the market: e.g. white cane with close range sensors, online guidance systems at bus stops, vocal and tactile orientation and pedestrian navigation systems.

The analysis of blind people's behaviour in complex infrastructures is necessary to understand the way people move and the associated strategy to localise and orient themselves. Our Institute has initiated a research project in pedestrian navigation for blind people (Gilliéron et al, Reference Gilliéron, Chazal, Delavy, Flamm, Von der Mühll and Ruzicka-Rossier2008). One of the goals of this project was to study the locomotion of a blind person walking in a railway station. The following observations have been made:

• • The noise sources are key factors for the orientation: the person can identify the noise of an escalator, the noise of a walking group of people (flow of persons).

• • A blind person is sensitive to the spatial environment. The phenomenon of echolocation (the capacity to evaluate the distance to a wall) provides useful information about the size and the shape of corridors, halls and staircases.

• • In a corridor, the person walks mainly in the middle of the lane which is normally free of obstacles or standing people.

• • Blind people use a white cane to detect close obstacles and as a courtesy to other people. This mobility tool is also used to detect staircases. The handrails in the staircases are not always used.

• • The use of hands to recognise objects is very limited: to detect the direction of an escalator.

• • When available, use of special marking on the ground for guidance can be useful.

Based on this experiment, objects which are relevant for the displacement of blind people in complex infrastructure have been identified. The objects' list is introduced later with the database concept.

4.2. Criteria to choose a route

The main motivation to introduce navigation systems for blind people is to provide route guidance instructions based on a pre-defined path. The criteria to select a route dedicated to blind people differ greatly from those used for a non-handicapped pedestrian. Contrary to classical approaches, the selection process is not based solely on the shortest path. Criteria have been discussed with a professional in locomotion for blind people and are taken into account in the following order of importance (Delavy, Reference Delavy2008).

• • Safety: the dangerous links must be avoided (e.g. crossing a road with heavy traffic)

• • Pedestrian flow: the area with a high flow of pedestrians must be encouraged. Moving in such an area is a safety advantage for blind people.

• • Shortest path: the length of a route can be taken into account, but it is not the most relevant criteria.

• • Presence of relevant objects for orientation: routes with relevant objects (e.g. escalators, staircases, doors) for orientation must be encouraged.

• • Presence of specific marks for visually impaired people: the presence of specific marks can be a criterion of choice. Often these facilities, such as guidance strips, are not used by blind people because they are unaware that marks are available.

The association of specific objects (e.g. marks, staircases and doors) with a pre-defined route is essential to improve the accuracy of localisation and orientation. Those remarkable points must be considered as waypoints for localisation operations based on maps, but also as reference points for the blind person. Effectively, the presence of a linear object, like a corridor or a staircase, informs a person about their localisation and orientation within the built environment.

4.3. Semantic model for pedestrian navigation

Most of the databases for buildings' maintenance are based on 2D graphical representation inherited from design plans. Such databases contain many useful objects (corridor, room, and elevator) for localisation purposes that are modelled with primary features like shapes, arcs and circles. However, a deeper knowledge of the map objects with additional information about their topological relationships is required to propose a suitable indoor navigation (Gilliéron et al, Reference Gilliéron, Büchel, Spassov and Merminod2004). A typical example was proposed by the automotive industry with the standard format called Geographic Data Files (GDF, ISO 14825). Car navigation systems are based on a link/node view of the street network offering significant advantages in supporting navigation. These models are optimised for providing guidance instruction based on the features of the road network. Similarly, the definition of a network for pedestrians within urban and indoor environments can be used to develop databases for blind people. Recently the main providers of navigable maps have proposed a pedestrian navigation extension of their models. However the last includes neither the description of indoor buildings and main infrastructures, nor the specific attributes required for the navigation of visually impaired people. To build a new model, a first approach consists of describing the semantic definition of the main objects and their roles in the navigation process. Table 1 presents the main objects with a semantic definition.

Table 1. Semantic definitions of objects for pedestrian navigation.

The Table shows two groups of objects: the layer navigation contains all elements used for route guidance and navigation and the layer context contains additional information about the spatial environment. Contextual information is very useful while providing instructions and warnings to the users. The proposed model clearly separates the navigation network and its related context because the dynamic of the contextual information can change rapidly and may be updated in real time (traffic conditions due to specific event). This distinction enables the construction of a more robust and stable navigation network which can be easily combined with other information sources.

4.4. Conceptual scheme

Before implementing the model, a conceptual scheme is designed to describe the relationships between layers and objects. The proposed scheme is similar to the main models of transportation networks. Figure 2 shows a graphical representation of the model in UML (Unified modelling language) format. The basics elements of the navigation layer are links and nodes, which are used to construct a 2D network containing the topological relationships between the main objects described in Table 1. The contextual layer is composed of the basic elements contextual node forming the polylines used in the description of linear objects (barrier) and areas.

Figure 2. Conceptual scheme of the navigation model for pedestrians.

4.5. Experimental assessment of the proposed navigation solution

The mobility of blind people is really challenging in complex urban areas. To test the validity of the proposed navigation solution for visually impaired people in real conditions, one specific trajectory has been chosen in a railway station. The trajectory starts from the train platform, continues through corridors, an open space, and finally reaches a terminal for urban public transport. This challenging case study was selected within a research project (Gilliéron et al, Reference Gilliéron, Chazal, Delavy, Flamm, Von der Mühll and Ruzicka-Rossier2008). Geneva railway station offered all required aspects to implement the proposed pedestrian navigation model. The navigation layer was digitised thanks to geographical data issued by the City of Geneva. Figure 3 illustrates both layers: the navigation network and the contextual elements of the railway station with two main areas: in green the one for the pedestrian flow and in red the one for cars and buses. Figure 4 introduces a typical scenario of a pedestrian localised in front of the railway station. The person has to avoid the dense traffic area (red) and must be guided into the safety zone (green). In this context, a concept of geo-fencing (electronic boundary) can be integrated in the navigation systems to avoid crossing dangerous areas.

Figure 3. Case study of the railway station Geneva (Delavy, Reference Delavy2008) with the element of context in (a) and the navigation network in (b).

Figure 4. Example of navigable map.

4.6. Absolute geographical reference for visually impaired people

This first challenging application demonstrates the key role played by the absolute geographical reference in robust positioning for visually impaired people. The use of a specific database is crucial to introduce navigation systems dedicated to blind people because they use these systems as auxiliary tools, which have to be reliable and user friendly. The database's prototype demonstrated that using waypoints brought vital information to assist the user. Nowadays, such detailed databases are not available. However the main providers of navigation data will improve their navigable maps for indoor areas. This is supported by the fact that increasingly more maps are created for large buildings, especially for safety reason as shown in the next section.

5.1. Emergency agents needs in case of a fire

Operational fire-fighters have to rescue people in distress and to extinguish fire. While moving indoors, they face unfamiliar and complex environments. Especially when dealing with a fire, the building infrastructure might collapse causing damage that could impair their deployment faculties. Consequently, localisation systems cannot rely on pre-existing installation and have to be deployed during the operation. When the heat and the dust are intense, we can often compare the firemen with blind people. Under these circumstances, the use of any visual guidance system is compromised. A fire-fighter commander, located outdoors, is in charge of the tactical procedure. He needs to see, in real time, the location of all firemen in the operation to manage any critical incident. He also communicates with his troops, sending voice messages to the agents.

Firemen carry heavy equipment, like fire hoses and breathing apparatus, whose weight affects their movements. Only light, and waterproof navigation systems capable of operating under high temperature are suitable candidates for emergency intervention. Firemen usually work in teams of two following the same footpath while penetrating the indoors of a building and returning to the start point. Sometimes they even use ropes to avoid being separated. Therefore the navigation system coverage can be limited to the specific route defined by the first team of firemen. Finally, the typical expected horizontal accuracy is 1 to 3 metres, whereas for the vertical information only the floor identification is required. For rescue purposes, additional information like postures or some medical parameters (heart rate, skin temperature) are useful. They supply any alarm system that would start a medical assistance intervention, but they also directly contribute to navigation, e.g. if the posture is lying on the floor, then the navigation system can interpret the position of the user as being static. During fire interventions continuity, integrity and availability are even more important than accuracy. The reliability of the navigation solution should be close to 100%.

5.2. Global Response

A fully auto-deployable system based on the hybridization of complementary technologies has been proposed to assist the agents. It combines MEMS sensors with RFID tags. The fairy tale ‘Hop o'my thumb’ inspired the solution. Like the young boy who dropped white pebbles all along his way, RFID tags are installed while emergency agents are progressing indoors. Each time the 1^st team passes a door, it attaches an RFID to the top of it. Doors have been chosen because fire-fighters are usually able to identify when they change rooms, even in smoky environments. Geographical coordinates are associated to the tag ID based on the MEMS-based approximated position and a geographical database. Once the RFID is located, its coordinates are used to relocate the dead reckoning trajectory. As illustrated in Figure 5, the proposed response combines the three key elements presented in our concept. The following section describes the content of each key element in the case of a fire-fighters intervention.

Figure 5. Illustration of the agents deploying RIFD related to the Tag Database.

5.3. Hybrid positioning system

The proposed solution exploits two uncorrelated and complementary technologies. The MEMS solution is the closest technology to the firemens' requirements. It is independent from the infrastructure and offers a continuous solution, but the localisation performance is affected by large errors typical of these low cost sensors. Consequently without any external information, the position of the agent will drift. The error will accumulate over time and typically reach 2 to 5% of the distance travelled. The second technology consists of RFID tags. It is an automatic identification process relying on passive or active tags. They are made of silicon electronic chips with an antenna and the identification request is based on radio signals. This network of sensors provides the user's location when it passes close to a tag. It offers only punctual information, thus the absolute coordinates of waypoints, but no real tracking capacity. The hybridisation of these two technologies in an Extended Kalman Filter guarantees the high quality level of the navigation solution (Renaudin, Reference Renaudin, Yalak, Tomé and Merminod2007). Experimental results, presented at the end of this section, assess the performance of the hybridised navigation solution.

5.4. Evacuation map and absolute reference

The reliability of the navigation solution is one of the most critical issues in systems dedicated to firemen. In our response, the absolute reference is the geographical database consisting of waypoints. It can easily be built from digitised evacuation emergency maps and serves as a background to display the locations of the agents on the commander's control unit. This geographical map offers a first possibility to visually assess the quality of the localisation algorithms. A second level of assessment is done when the hybridisation process couples the agent's position with the waypoint's coordinates. Practically, each time a new RFID has been attached and the algorithm has associated coordinates from the database with the tag, it uses the latest information to correct the navigation position of the agent.

5.5. Motion model

Fire-fighters movements are different from those of standard people. Even in clear conditions, the fire hoses and breathing apparatus affect their movements. The use of motion models is crucial to insure the quality of the estimated agent's location. To cope with the complexity of the firemen in motion, a distributed architecture of MEMS sensors was proposed (Figure 6). It enables the use of complex motion models to analyse the postures and movements in real time. Sensors, fixed on the trunk and the thigh, assess the sitting, standing and lying postures. This information improves the security as it is used to raise an alarm when a fireman is identified as motionless. The user's displacements are estimated with the sensors placed on the shank. The horizontal displacement corresponds to the step size of an agent walking forward. It is evaluated during a specific phase of the gait cycle. The vertical displacement is estimated when the agent is climbing or descending stairs. It is interesting to notice that for security reasons, fire-fighters always descend stairs backwards. This defines a motion pattern specific to the firemen. The condition equations come essentially from the type of movements that occur during a fire intervention and from the limitations induced by the carried equipment. In fact, the agent will move very slowly due to the heavy equipment and the motion will slow down when the temperature increases. Looking at the specific of the fire-fighters displacements, it appeared really interesting to adapt the motion models to this specific application.

Figure 6. MEMS distributed architecture worn by the agent.

5.6. Experimental results

The proposed navigation system has been tested in the Ecole Polytechnique Fédérale de Lausanne facilities. The test follows a realistic emergency scenario where an agent enters a building and walks in corridors to reach the fire location. During the test, a person equipped with MEMS, MTx modules from Xsens containing tri-axis accelerometers, gyroscopes and magnetometers that are distributed on the body as described earlier, walked at a steady pace along a predefined route. Raw data have been recorded on a laptop and post-processed. The installation of RFID tags was simulated by doing the specific movements required to stick the tags at the top centre of each doorjamb. The database containing the coordinates of each door was created thanks to the available campus map. These positions were also used to evaluate the performances of the proposed localisation system.

Figure 7 shows the experimental test results plotted on an extract of the campus map. The main entrance is situated in the South and the fire is in the North. The areas in red represent the second floor of the building whereas the areas in grey correspond to the first floor. The red crosses locate the simulated RFID positions. Each time an agent passes close to an RFID tag, the hybridisation algorithm relocates the navigation solution. These results show that the coupled solution, plotted in green, always outperforms the MEMS-based only solution, plotted in blue. Maximum errors occur just before the agent crosses a door, meaning that the accuracy of the location estimation depends on the density of the RFID tags. When targeting an accurate auto-deployable solution, a compromise between the density of waypoints and the dependency to the building infrastructure must be made.

Figure 7. Coupled and MEMS-based only results for the test campaigns in the EPFL facilities.

For the hybridised solution, the statistical analysis shows that 90% of the horizontal errors remain below 5 metres. The mean error for the MEMS-based only solution is about 19 metres with a 10 metres standard deviation. The statistical analysis confirms the graphical interpretation of the navigation performances during the experiment. The total length of the path walked by the emergency agent is about 500 metres. It is interesting to notice that the 5 metres inaccuracy computed for the coupled navigation solution corresponds only to 1% of the total walked distance. This test campaign proves that creating a solution based on the concept presented in section 2.4 significantly improves the performances of navigation systems dedicated to pedestrian applications in challenging environments.