1. INTRODUCTION
Individuals’ quality of life within a society is strongly related to their ability to access places and activities that are necessary for their happiness and well-being (Doi et al., Reference Doi, Kii and Nakanishi2008). Unfortunately, the contemporary urban landscape and built environment contain many obstacles that lead to various forms of constraint-based social exclusion, especially for people with disabilities (Preston and Rajé, Reference Preston and Rajé2007). According to Welage and Liu (Reference Welage and Liu2011), improving access to public buildings could enhance the active participation of people with disabilities in the social and economic development of their community. In order to ensure the accessibility of buildings for individuals with different capabilities, several governments and authorities have issued norms and guidelines that aim to ensure the construction of barrier-free environments (US DHUD, 1994; US ATBCB, 1991; International Organization of Standardization, 2011). These norms and guidelines have helped in reducing substantial social exclusions due to the characteristics of the physical environment, where people with disabilities carry out their daily activities. Unfortunately, these norms and standards are generally not fully respected in existing built environments, which makes navigation tasks very hard (Welage and Liu, Reference Welage and Liu2011).
Recent advances in geospatial and wireless communication technologies (Geographic Information Systems (GIS), Global Navigation Satellite Systems (GNSS), Internet, mobile and wireless communication technologies) offer a great opportunity for developing new assistive solutions to help people with disabilities in their indoor or outdoor navigation (Beale et al., Reference Beale, Field, Briggs, Picton and Matthews2006; Karimi and Ghafourian, Reference Karimi and Ghafourian2010; Kostic and Scheider, Reference Kostic and Scheider2015). Some of these solutions are only limited to providing useful descriptions regarding the accessibility of environments (Moussaoui et al., Reference Moussaoui, Pruski and Maaoui2012), whereas others offer navigation instructions that aim to avoid obstacles and use existing facilitators (Han et al., Reference Han, Law, Latombe and Kunz2002; Kostic and Scheider, Reference Kostic and Scheider2015).
In this paper, we present a new Voronoï-based approach that merges assessing accessibility and generating an accessible navigation network to support people moving in wheelchairs in indoor environments. In order to assess the accessibility of buildings, a conceptual model of a spatial database semantically enriched with American with Disabilities Act Accessibility Guidelines (ADAAG) and Indoor Geography Markup Language (IndoorGML) is developed. Then, a Voronoï diagram is generated from the configuration of the spaces of a building in addition to existing furniture. This diagram is very useful for defining barrier-free spaces in which a person can move safely with a wheelchair. After that, the Voronoï diagram is used to create a Three-Dimensional (3D) accessible navigation network which may be used for supporting the navigation of people in wheelchairs in indoor environments.
2. RELATED WORK
2.1. Assessing accessibility in indoor environments
Accessibility is a notion that refers to the degree to which parts of a built environment can be approached, entered or used securely and independently by people with disabilities (Welage and Liu, Reference Welage and Liu2011). The notion of accessibility may be seen as the result of the interaction between the individual's (or group of individuals) functional capacities and the design and demands of the environment (Iwarsson and Stahl, Reference Iwarsson and Stahl2003). This interaction consists of two main aspects; (1) mobility, and (2) reaching and grasping (Moussaoui et al., Reference Moussaoui, Pruski and Maaoui2012).
In order to improve the mobility of individuals (including those with motor disabilities), several navigation assistive solutions have been developed. Initially, such solutions have focused on outdoor environments where precise positioning is available thanks to satellite navigation systems (for example, the Global Positioning System (GPS)). However, recent developments in indoor positioning techniques (such as sensor-based, Bluetooth and Wi-Fi) have extended these solutions to indoor environments (Kostic and Scheider, Reference Kostic and Scheider2015). Indeed, indoor navigation systems are very helpful when people are navigating in unfamiliar buildings, especially those with complex configurations (Krūminaitė and Zlatanova, Reference Krūminaitė and Zlatanova2014). Slingsby and Raper (Reference Slingsby and Raper2007) proposed an approach to produce navigable spaces taking into consideration different pedestrian profiles and different contexts. In addition, Schaap et al. (Reference Schaap, Zlatanova and Van Oosterom2011) extended the concept of navigable spaces to develop a spatial data model to support pedestrian navigation in multimodal transportation networks. Goetz and Zipf (Reference Goetz and Zipf2011) proposed a formal definition of a user-adaptive routing graph which computes accessible routes that are suitable for individuals with different abilities and requirements.
For the specific case of wheelchair users, these assistive solutions could offer relevant information about the quality of access into various facilities of an environment (rooms, toilets, parking, ramps, entrances, etc). Also, these technologies may provide instructions for barrier-free routes from one location to another within a building.
The assessment of accessibility in indoor environments for people moving with wheelchairs has been addressed according to three main approaches (or their combination); (1) Regulatory approach, (2) Ergonomic approach and (3) Motion planning (or Navigation Problem) approach (Moussaoui et al., Reference Moussaoui, Pruski and Maaoui2012).
The first approach consists of a simple enumeration of obstacles and facilitators that exist in the built environment, based on existing standards such as ADAAG (Meyers et al., Reference Meyers, Anderson, Miller, Shipp and Hoenig2002). The ergonomic-oriented approach focuses on ergonomic characteristics of wheelchairs to maximise users’ performance and improve their skills to deal with existing obstacles (manoeuvring and basic daily living skills, obstacle negotiating skills, etc) (Fliess-Douer et al., Reference Fliess-Douer, Vanlandewijck, Manor, Van and Woude2010).
In contrast, the navigation problem (or motion planning) approach focuses more on the ‘Mobility’ aspect of accessibility. In Han et al. (Reference Han, Law, Latombe and Kunz2002), a robot-motion planning method was used to simulate the behaviour of a wheelchair user in an indoor environment. This method consists of two main tasks which are; (1) verifying the existence of areas with appropriate clearance width according to the ADAAG standard and (2) determining if a wheelchair user can negotiate routes within these areas. In Moussaoui et al. (Reference Moussaoui, Pruski and Maaoui2012), the authors developed a virtual reality tool that allows the definition of all possible areas in the environment where a wheelchair user can move without colliding with existing obstacles. Liu and Zlatanova (Reference Liu and Zlatanova2015) proposed an interesting approach based on computing the minimum distance between obstacles. Kostic and Scheider (Reference Kostic and Scheider2015) proposed an agent-based model for mobility affordance derivation that aims to evaluate the possibility of movement of a wheelchair user in an indoor environment. Another interesting approach includes the notion of functional spaces in the computation of non-navigable areas in indoor buildings (Krūminaitė and Zlatanova, Reference Krūminaitė and Zlatanova2014).
Assessing techniques that belong to the family of motion planning generally use methods for the generation of navigation networks. More detail about these methods is presented in the following section.
2.2. Methods for the generation of navigation networks
A navigation network is a graph-based model that is considered as the basis for a data structure to support human navigation; it is composed of a set of edges representing paths of movement and a set of nodes that correspond to decision points such as landmarks or other important locations (Yang and Worboys, Reference Yang and Worboys2015). Methods used to generate navigation networks consist of simplifying and approximating the configuration of the indoor environment. These methods may be classified in five main categories; (1) Regular tessellations, (2) Irregular tessellations, (3) Skeletons, (4) Visibility graphs and (5) Variable Density Networks.
Generating navigation networks based on regular tessellations relies on grid-based structures. In this case, occupiable areas are converted to a grid graph where each cell is considered as a node network and it is connected to its adjacent cells (Kostic and Scheider, Reference Kostic and Scheider2015).
Irregular tessellations used for creating navigation networks are primarily based on Constrained Delaunay Triangulation (CDT) and Voronoï diagrams (the dual structure of Delaunay triangulation) (Afyouni et al., Reference Afyouni, Ray and Claramunt2012). In a CDT, obstacles are considered as constraints when generating triangles that are used to discretise the environment (Nasir et al., Reference Nasir, Lim, Nahavandi and Creighton2014). Regarding Voronoï diagrams, which are the dual structure of Delaunay triangulation, existing obstacles are considered as generator objects (Demyen and Buro, Reference Demyen and Buro2006). Voronoï diagram edges will be considered as the segments of the navigation network. For more details about the mathematical principles and applications of Voronoï Diagrams, the reader is referred to Okabe et al. (Reference Okabe, Boots, Sugihara and Chiu2000).
Skeleton-based methods also allow the generation of navigation networks for indoor environments. To do so, Medial Axis Transformation (MAT) algorithms are used to convert the configuration of an indoor environment into a skeleton.
Navigation networks can also be extracted from a visibility graph. A visibility graph is composed of edges of obstacles in addition to edges that connect mutually visible locations in an indoor environment (Turner et al., Reference Turner, Doxa, O'sullivan and Penn2001).
Finally, Variable Density Networks aim to create a dense tessellation of indoor spaces. They are based on Voronoï diagram tessellation, where doors and concave corners are considered as initial Voronoï vertices. However, these vertices are enriched with additional points to increase the number of cells in the tessellation, which improves the quality of navigation (Boguslawski et al., Reference Boguslawski, Mahdjoubi, Zverovich and Fadli2016).
The above-mentioned methods could be used to generate navigation networks. However, the Voronoï-based methods are more suitable for the accessibility assessment and navigation of wheelchair users as detailed in Section 3.3. Indeed, the effectiveness of regular tessellations is strongly related to the cell size. On one hand, a large cell size could lead to inaccurate results. On the other hand, too small a cell size might excessively increase computation time and demands for allocated memory. For MAT algorithms, they provide interesting navigation networks when buildings have a regular configuration. However, in complex buildings, this kind of algorithm might suggest inappropriate indoor navigation networks (Yang and Worboys, Reference Yang and Worboys2015). Regarding the visibility graph approach, it is similar to human navigation, because humans tend to go straight to their destination. However, in complex buildings, visibility graphs may contain a large number of nodes and edges which may bring unnecessary complexity to the navigation network (Yang and Worboys, Reference Yang and Worboys2015). The main disadvantage of irregular tessellations (CDT and Voronoï) is the construction of many unnecessary nodes which are not suitable for human navigation. This disadvantage is more obvious in Variable Density Networks where more vertices are added. This will also increase the required computation time and memory requirement. To overcome this weakness, a simplification algorithm could be used to reduce unnecessary nodes.
Following the construction of the navigation network, the next step consists of exploiting this network to find the optimal path.
2.3. Discussion
To the best of our knowledge, the majority of existing approaches focus on the spatial configuration of the environment. This may lead to an insufficient assessment of accessibility due to the lack of rich description of this environment. Indeed, in order to effectively evaluate the quality of accessibility, we need to compare the current state of the environment to accessibility standards such as ADAAG. For this reason, it is necessary to have a rich semantic description of the environment. This semantic aspect is fundamental for successful wayfinding and navigation activities (Yang and Worboys, Reference Yang and Worboys2015). Regarding the approaches that generate navigation networks, Voronoï-based methods offer an interesting potential because they take into account existing obstacles to construct navigation edges that correspond to barrier-free spaces. However, existing Voronoï-based approaches consider only walls (and dimension of doors) as the main obstacles. They do not take into consideration room furniture despite the strong impact of furniture on accessibility for people with physical disabilities. In addition, these approaches do not provide a clear methodology for semantically enriching the navigation network in order to assess the level of accessibility in an indoor environment.
There are some interesting standards that aim to provide semantically rich information about Buildings’ components such as Industry Foundation Classes (IFC) for Building Information models (Laakso and Kiviniemi, Reference Laakso and Kiviniemi2012) and CityGML for 3D Geographic Information Systems (Gröger et al., Reference Gröger, Kolbe, Nagel and Häfele2012). However, these standards focus on the description of buildings rather than on navigation purposes. To overcome this limit, the Open Geospatial Consortium (OGC) has developed the indoor navigation standard IndoorGML which is fully compatible with CityGML (Lee et al., Reference Lee, Li, Zlatanova, Kolbe, Nagel and Becker2014). IndoorGML provides an interesting framework to develop indoor navigation solutions although it does not consider the requirements for people moving with wheelchairs.
In the following sections, the proposed methodology to generate semantically enriched Voronoï-based navigation networks for people moving with wheelchairs is detailed. The semantics of this Voronoï-based navigation network are extracted from the ADAAG and IndoorGML standards.
3. PRINCIPLES OF ACCESSVOR APPROACH FOR NAVIGATION ASSISTANCE
The AccessVOR (Accessibility assessment based on VORonoï Diagram) approach proposed in this paper aims to develop a navigation solution for people moving with wheelchairs in an indoor environment. This approach consists of three main phases; (1) developing a semantic database model for wheelchair navigation based on ADAAG and IndoorGML, (2) generating a navigation graph from the Voronoï diagram and (3) assessing the accessibility of the generated Voronoï navigation graph. In the following sections, the methodology adopted for each phase is explained.
3.1. Developing a semantic database model for wheelchair navigation in indoor environments based on ADAAG and IndoorGML standards
3.1.1. The ADAAG standard
The American with Disabilities Act Accessibility Guidelines (ADAAG) is one of the most widely used standards that contains technical requirements for accessibility to buildings and facilities for individuals with disabilities (US ATBCB, 1991). In the case of people moving with a wheelchair, the ADAAG provides detailed specifications regarding the required dimensions for several components of indoor environments. These specifications aim to ensure at least one accessible route that connects the various facilities of a building.
Based on the ADAAG standard, the main classes that should be included in the proposed spatial database are the following:
• Building: A built structure that supports one or many activities. A building consists of one or many floors that contain open and closed spaces.
• Path Segment: An unobstructed area that may be used for navigation among facilities and spaces of a building. These segments may be connected to stairways, elevators, ramps and doors. A Path segment is an abstract class that is classified into two subclasses; Primary Path Segment and Secondary Path Segment.
• Primary Path Segment: A Path segment that is located in the open space of a building (for example, building hall).
• Secondary Path Segment: A Path Segment that is located in closed spaces of a building (for example, toilet, classroom, office …).
• Closed Space: A space defined by walls and one or several access doors. It is possible to move inside this space through secondary path segments. Closed spaces may be classified according to their purpose (for example, toilet, classroom, office …).
• Open Space: A space that allows movement between different closed spaces. One can navigate in an open space through Primary Path Segments. Examples of open spaces include corridors, hallways, etc.
• Door: An area that opens and allows access to a closed space or a building. In the proposed database, a door will be modelled as a point that connects two secondary path segments since the door is used to move between two closed spaces. In the case where it provides access to an open space of the building, the door will connect one secondary path segment with one primary path segment. Finally, if the door gives access to the outside of a building, then it should connect a primary path segment with an outside path segment.
• Stairway: A segment that connects primary path segments belonging to two successive floors of a building (or in some cases, primary path segments that belong to the same floor but have different levels). A stairway is composed of smaller vertical distances called steps.
• Elevator: A segment that connects primary path segments belonging to two successive floors of a building. In contrast to a stairway, an elevator ensures vertical motorised transportation of individuals between building floors.
• Ramps: A segment that allows overcoming some obstacles (such as stairs) where the variation in level is not so significant. A ramp may belong to the same floor, or it can serve as a building entrance. It is mainly characterised by a slope and a width.
• Furniture: A movable object used for activities inside a closed or an open space. The way in which an object is placed may impede the movement of individuals, especially those with a wheelchair.
Based on the classes mentioned above and their attributes that are extracted from the ADAAG specifications, it will be possible to assess the compliance of a building's components with this standard (compare with Section 4.2). For more details regarding specifications of each class included in our spatial database, please refer to the ADAAG standard (US ATBCB, 1991). These classes will be integrated with the IndoorGML standard that is dedicated for navigation solutions in indoor environments.
3.1.2. The IndoorGML standard
IndoorGML is a standard developed by the Open Geospatial Consortium for indoor navigation applications (Lee et al., Reference Lee, Li, Zlatanova, Kolbe, Nagel and Becker2014). It is an application schema of the Geography Markup Language (GML). Referencing IndoorGML to CityGML is very important for navigation purposes because it ensures the correspondence between the navigation network and the building components that are described in detail in Level Of Detail (LOD) 4 of the CityGML Standard.
The IndoorGML data model contains two main types of modules; a Core Module (Figure 1) and Thematic Extension Module. The Core Module includes the basic classes of Indoor spaces (yellow boxes) and the extension module covers a specific thematic field such as navigation applications (for example, pedestrians, wheelchair, etc). The classes of the Indoor Navigation Module are presented as green boxes (Figure 2). The Core Module and the Indoor Navigation Module are linked together through specific relationships. In addition, these two modules are also connected to classes representing the general geometric structures of the GML standard (orange classes). It is important to note that some classes in IndoorGML are similar to those extracted from the ADAAG standard (Table 1). However, other classes do not appear in IndoorGML. Therefore, it is necessary to enrich the IndoorGML standard with additional semantic classes from ADAAG to support the navigation by wheelchair users in indoor environments.
UML diagram of IndoorGML's core module (Lee et al., Reference Lee, Li, Zlatanova, Kolbe, Nagel and Becker2014).
UML diagram of IndoorGML's Navigation module linked to classes from the IndoorGML's Core module (Lee et al., Reference Lee, Li, Zlatanova, Kolbe, Nagel and Becker2014).
Similarities between IndoorGML classes and ADAAG classes.
3.1.3. The conceptual data model of the spatial database for building accessibility assessment
To enrich the IndoorGML standard (Figures 1 and 2) for the purpose of building accessibility assessment, we have linked this standard with relevant classes from the CityGML standard. CityGML allows modelling and exchange of virtual 3D cities (buildings, roads, terrain, etc). In our case, we are interested in the following classes: Building, BuildingFurniture, Room and Door. Hence, BuildingFurniture is linked to IndoorNavi::NavigableSpace (which can be GeneralSpace or TransferSpace). The class Room will be associated to IndoorNavi::GeneralSpace and the class Door will be linked to IndoorNavi::TransferBoundary.
The highlighted similarities between IndoorGML classes and ADAAG classes allow us to semantically enrich the IndoorGML standard. Hence, we will design a semantically enriched spatial database for purposes of navigation and accessibility assessment in an indoor environment. To do so, the ADAAG classes presented in Section 3.1.1 must be linked to the Indoor Navigation Module and CityGML Module. More specifically, Stairway, Elevator, Ramp, PrimaryPathSegment and SecondaryPathSegment will be linked by inheritance relationships with IndoorNavi::RouteSegment. Also, Stairway, Elevator, Ramp and PrimaryPathSegment will be linked to IndoorNavi::TransferSpace. The class SecondaryPathSegment will also be linked to IndoorNavi::GeneralSpace.
Figure 3 illustrates the conceptual data model with UML formalism for the proposed spatial database used for accessibility assessment and the navigation network of buildings based on the ADAAG standard.
UML diagram of the semantic ADAAG classes linked to classes from the IndoorGML's Navigation module and CityGML classes.
3.2. Generation of the navigation graph based on Voronoï diagram
In order to populate the above-mentioned database, a Two-Dimensional (2D) plan can be used as a basis for further analysis. This file should contain the geometry of walls, doors and room furniture that exist on each floor. In addition, it should contain stairways, elevators and ramps, if they exist. Semantic information (such as names, functions, characteristics) that describe building components or the navigation graph should be introduced manually. However, the cost related to each edge of the navigation graph will be calculated automatically based on the barrier-free space as explained in Sections 3.3 and 4.2.
GeneralSpace and TransferSpace classes will be extracted from walls. The Furniture class allows definition of the shape and location of movable objects that may be inside or outside a GeneralSpace. To generate the navigation graph, these three classes (representing obstacles) are considered as generators of the Voronoï diagram. Each Voronoï edge that belongs to the generated diagram has the property of being equidistant to generator objects (obstacles) that share this edge. Hence, Voronoï edges will represent the barrier-free corridor where it is possible to move.
Voronoï segments that belong to General Spaces are assigned to the class Secondary Path Segment, while those assigned to Transfer Spaces are assigned to the class Primary Path Segment. Regarding the class Door, it will be presented as points that link Voronoï Segments. Three cases may occur; (1) if a door ensures a transition between two General Spaces, then the corresponding point will link two Secondary Path Segments. (2) If a door gives access to a Transfer Space, then it will connect a Primary Path Segment with a Secondary Path Segment. (3) A point representing a door that leads to the outside of a building will connect a Primary Path Segment with an Outdoor Path Segment. Finally, in order to complete the creation of the navigation network, the 2D positions of Ramps, Stairways and Elevators (extracted from 2D plans) are converted into 3D lines based on the elevation of each floor. Then, each one of those classes must be linked to at least one Primary Path Segment.
After that, the 3D navigation graph based on a Voronoï diagram will be created. The navigation cost on this graph is calculated based on the accessibility of each component. This cost is used to inform people moving with wheelchairs about the accessibility of the building and to provide an accessible network to support navigation by wheelchair users (compare with Section 4.2).
3.3. Accessibility assessment of the generated Voronoï navigation graph
In order to assess the accessibility of the generated Voronoï navigation graph, it is necessary to calculate the barrier-free space that corresponds to each Path Segment (Primary and Secondary). In the case of a wheelchair user, the ability to move on those segments depends on the smallest barrier-free space corresponding thereto. In fact, it is impossible to continue his/her movement on a segment when reaching a relatively narrow area. Therefore, this narrow area will influence the ability to navigate on the whole segment. Hence, each segment (Voronoï edge) will be associated to its corresponding smallest barrier-free space. This zone is defined by twice the smallest distance of either side of the segment with respect to generator objects (Floor, General Space and furniture) as shown in Figure 4.
The barrier-free space associated to a Voronoï edge.
Once these distances are assigned to each segment, they will be compared to provision 4.3.3 of ADAAG that describes the width parameters of accessible routes (US ATBCB, 1991). Based on ADAAG, we consider that a segment (either primary path segment or secondary path segment) is not accessible if the width is less than 915 mm, badly accessible if the width is between 915 mm and 1,525 mm and fully accessible if the width is more than 1,525 mm. Regarding the accessibility of doors, they are considered as not accessible if the width is less than 815 mm, badly accessible if the width is more than 815 mm but the door hardware requires significant physical effort and, fully accessible if the width is more than 815 mm and the door hardware is easy to use.
A General Space is considered as not accessible if the door does not comply with ADAAG standards regardless of the accessibility of secondary path segments therein. If the door is accessible, then the accessibility of the General Space is mainly related to secondary path segments. In this context, the accessibility of General Spaces may be classified as follows:
– If the door is not accessible, then the General Space is not accessible.
– If the door is accessible, then there are three cases:
• Case 1: If all secondary path segments within the General Space are fully accessible, then this space is fully accessible.
• Case 2: If all secondary path segments within the General Space are not accessible, then this space is not accessible.
• Case 3: If some secondary path segments are fully accessible while others are badly accessible or not accessible, then this space is badly accessible.
For elevators, according to ADAAG, the minimum door opening is 815 mm and the minimum car platform dimensions are 1,730 mm × 1,370 mm (US ATBCB, 1991). Ramps must have a maximum slope of 1:12, a maximum rise of 760 mm, a minimum clear width of 915 mm and minimum landing length of 1,525 mm.
Finally, stairways are considered as not accessible for people moving with a wheelchair. However, people with no or low physical disability (people using crutches) can use stairways for their navigation.
3.4. Generating the optimal path based on the semantic database and the generated Voronoï navigation graph
The generated Voronoï segments are integrated in the enriched semantic database presented as Path Segment (Primary and Secondary). These path segments are necessary to produce navigation itineraries that are accessible for people moving with wheelchairs. In addition, the other semantic classes may be used to provide navigation assistance and instructions. The calculation of the optimal path is based on the well-known Dijkstra (Reference Dijsktra1959) algorithm. Indeed, the Dijkstra algorithm is currently the most used in the field of geographic information systems for calculating the optimal path (Da Silva and De Almeida, Reference Da Silva and De Almeida2007; Izumi et al., Reference Izumi, Kobayashi and Yoshida2008; Huang and Liu, Reference Huang and Liu2010). This algorithm calculates the optimal path in a navigation network based on positive weights that correspond to each segment of that network as follows:
– If a Path Segment is not accessible, then the corresponding weight will be set to infinity.
– If a Path Segment is badly accessible, then the corresponding weight will be set to the required time to move in the segment multiplied by a delay factor.
– If a Path Segment is fully accessible, then the corresponding weight will be set to required time to move in this segment.
For more details on the principles of Dijkstra Algorithm, please refer to Dijkstra (Reference Dijsktra1959) and Yaagoubi et al. (Reference Yaagoubi, Edwards and Badard2018).
4. RESULTS AND DISCUSSION
In this section, a case study that corresponds to a university campus building is presented. First of all, the generation of the 3D navigation graph of the building from a Voronoï diagram is illustrated. Then, the results of accessibility assessment and navigation assistance for people moving with wheelchairs are highlighted. Afterward, the outcomes of implementing the proposed AccessVOR approach are discussed.
4.1. The 3D Voronoï-based navigation graph of the case study building
As mentioned in Section 3.2, the first step consists of generating a 2D navigation graph for each floor based on a Voronoï diagram (Figure 5). For this reason, we consider walls (that define General Spaces and Transfer Spaces) and furniture as generator objects for the Voronoï diagram.
2D navigation graph for the third floor of the case study building.
Once the 2D navigation graph is generated for each floor, the next step is to create 3D segments corresponding to elevators and stairways that connect building floors. Note that the case study building does not contain any ramps inside and therefore this type of object does not appear in Figure 6.
3D segments that correspond to stairways and elevators in the case study building.
Finally, these 3D segments (stairways and elevators) are integrated with 2D Voronoï segments for each floor (primary and secondary segments) in order to produce a 3D Voronoï-based navigation graph. This graph is then used to assess the building accessibility in addition to provide navigation assistance (Figure 7).
3D Voronoï-based navigation graph for the case study building.
4.2. Accessibility assessment and navigation solution for wheelchair users
In order to assess the accessibility of the case study building, primary and secondary segments are first classified based on the clear width as detailed in Section 3.3 (Figure 8). This clear width is related to the distance from walls and furniture. In addition, door accessibility is evaluated by using the criteria mentioned in Section 3.3.
Doors and segments accessibility for the third floor of the case study building.
Following accessibility assessment of doors and segments (primary and secondary), it is possible to evaluate the accessibility of General Spaces in the case study building as explained in Section 3.3 (Figure 9). Note that, as shown in Figure 9, if a General Space has inaccessible doors or where all segments are not accessible, it will be considered as a not accessible General Space. Also, furniture objects are hidden in Figure 9 for purposes of clarity.
General spaces accessibility for the third floor of the case study building.
The cost associated with the Voronoï graph is very useful for providing navigation assistance for wheelchair users. Indeed, inaccessible edges will not be considered as navigable segments because they act as barriers for navigation. In addition, inaccessible General Spaces (such as a room) should not be served by the generated navigation graph (Figure 10).
Navigable Network for the third floor of the case study building.
Accessibility information assigned to each segment of the 3D Voronoï-based navigation graph may be used to provide navigation assistance for people moving with a wheelchair. Indeed, stairways, inaccessible segments and inaccessible doors are considered as non-traversable by wheelchair. Hence, they will not be included in the navigation network used for assistance. Badly accessible segments may be traversable but with additional time for manoeuvring and fully accessible segments are easily traversable. The scenario presented in Figure 11 shows two optimal routes between the same starting point on the first floor and ending point on the fourth floor. The first route (yellow) represents the optimal path for a wheelchair user: it must avoid all non-traversable segments (inaccessible primary and secondary segments, inaccessible doors and stairways). Hence, the proposed path suggests taking the nearest elevator to reach the fourth floor and then the destination point. The second optimal route (blue) is proposed for a person without motor disability, where the cost of displacement is simply the segment length. In this case, the solution suggests the shortest path that passes through stairways to reach the destination point.
Optimal path for a wheelchair user and the shortest path between the same origin and destination points.
4.3. Discussion
In this case study, the AccessVOR approach is implemented in order to assess the accessibility of an indoor environment according to the ADAAG standard in addition to offering a navigation solution for people moving with a wheelchair. Results show that the use of a Voronoï diagram allows automatic generation of navigation segments in addition to their accessibility assessment. Also, it is possible to assess the accessibility of General Spaces, as well as providing 3D navigation assistance for people moving with or without a wheelchair. General Space accessibility is strongly related to furniture arrangements and door characteristics.
2D plans were used as the source of the expected shape and arrangement of General Space furniture, which does not necessarily reflect reality. Hence, for a more accurate accessibility assessment, it is highly recommended to use as-built 3D models as input, which may be derived from advanced acquisition techniques such as Terrestrial Laser Scanning or Close-Range Photogrammetry. However, it is necessary to mention that the processing method, according to the AccessVOR approach, remains exactly the same.
5. CONCLUSION AND FUTURE WORKS
In this paper, the principles of a novel approach named ‘AccessVOR’ for assessing accessibility and navigation solutions for people moving with wheelchairs are presented. This approach aims to evaluate the compliance of the interior of buildings with the ADAAG standard and provides 3D navigation assistance for wheelchair users. The idea behind AccessVOR is to generate a 3D navigation graph based on a Voronoï diagram, where walls and furniture are considered as generator objects. Then a spatial database based on ADAAG and IndoorGML standards is developed for assessing accessibility and supporting navigation assistance to wheelchair users. After that, the accessibility of a building's spaces and a 3D Voronoï-based navigation graph that contains accessibility constraints are produced.
The obtained results are very encouraging in terms of the automatic generation and accessibility assessment of 3D navigation graphs in an indoor environment especially for complex or unfamiliar buildings. In addition, using a Voronoï diagram allows automatic regeneration and reassessment of the navigation network in case of eventual changes in building components or the configuration of building furniture. Also, the proposed approach may be used for a priori assessment of the expected configuration in terms of the navigation requirements of wheelchair users.
Our further investigations will focus on integrating different profiles of physical disabilities in the accessibility assessment process and take them into account in determining the required navigation assistance. This aspect is very important because the perception of obstacles and how they impede navigation depends on the type of disability in addition to the experience of the wheelchair user. Also, it is important to mention that assessment of accessibility is not limited to physical barriers in built environments, it is also related to other aspects such as social context, cognitive and personal abilities, and situational awareness (Yaagoubi and Edwards, Reference Yaagoubi and Edwards2008). Therefore, there is a need for deep investigation on how to integrate these aspects in the process of accessibility assessment in order to provide appropriate navigation assistance.
