This paper presents a method to determine if a usable wheelchair accessible route in a facility exists using motion-planning techniques. We use a`performance-based' approach to predict the performance of a facility design against requirements of a building code. This approach has advantages over the traditional`prescriptive' code-based approach for assessing acceptability of designs, which is normal practice today for assessing wheelchair accessibility. The prescriptive method can be ambiguous, contradictory, complex, and unduly restrictive in practice, and it can be ad hoc and dif®cult to implement as a computer application. The performance-based approach directly models the actual possible behaviors of an artifact (in this case, wheelchair motion) that are related to the functional intent of the designed system (a building) and (hopefully) to the speci®cation of a prescriptive building code. This paper presents example cases from architectural practice to illustrate the use of robot motion-planning techniques for wheelchair accessibility analysis. This application is an example of using modern computational methods in support of knowledge-intensive engineering. The simulation method has broad applicability within engineering design. We illustrate and discuss how to analyze virtual simulations of the detailed behavior of a designed artifact in order to assess its use by intended users. q 2001 Elsevier Science Ltd. All rights reserved. Keywords: Motion planning; Disabled access; Wheelchair accessibility; Performance-based analysis This paper develops a method to determine if a usable wheelchair accessible route in a facility exists using computer-based motion-planning techniques. One concern for designing a facility is the extent to which it satis®es a set of usability objectives. In the US, wheelchair access in private facilities is often an important objective, and certain wheelchair accessibility is a constraint that is mandated by law for most public facilities. The Americans with Disabilities Act Accessibility Guidelines (ADAAG) contaiǹ prescriptive' speci®cations for determining the existence of a valid wheelchair accessible route as well as other objectives for disabled access Advantages of using prescriptive provisions include straightforward evaluation of a design using the prescribed parameters, and such evaluation often does not need highlevel engineering knowledge about the speci®c analysis. However, prescriptive-based codes can be ambiguous, contradictory, complex, and restrictive [6] . Solutions constrained by prescriptive-based codes such as the ADAAG address only a fraction of the possible solutions that meet the design intent or objectives of these codes. Since it often is implicit, it is often dif®cult for both designers and code checkers to discern the design intent and objectives of a building code or code provision. However, in the case of the ADAAG, the intent is clearly stated as ª¼scoping and technical requirements for accessibility to buildings and facilities by individuals with disabilities¼º Furthermore, instances exist in which adhering to these prescriptive provisions produces a design that may not be usable. As a partial solution to the problems of prescriptive-based building codes, many jurisdictions have adopted or are moving toward the adoption of`performance-based' codes. We use the term`performance-based' to imply the performance computed by simulating behavior of models (in this case, a wheelchair in the con®guration of a facility). For example, California provides a performance-based alternative to its prescriptive-based energy codes [2] . As opposed to prescriptive-based codes that provide solutions  abstracted from the design intent or objective of a building code, performance-based codes attempt to directly capture the behaviors that conform to the intent of the design codes or regulations. This direct performance-based approach accepts design solutions that satisfy the usability constraints, including those solutions that do not comply with the prescriptive-based constraints speci®ed by a design code. When a performance-based approach accurately models usability, this approach will identify and reject design solutions that are not usableÐsome unusable designs may be accepted using the prescriptive-based constraints speci®ed by a design code. This paper presents the methods developed for accessible route analysis using motion-planning simulation to capture the behavior of a moving wheelchair. First, we give a brief overview of motion planning and the technique adopted in this work. We then provide a de®nition of an accessible route and its components. Methodologies for the analysis of accessible components are then discussed. Application examples are provided to demonstrate the bene®ts of the performance-based approach. Application of the approach for the analysis of a¯oor plan is also given. Finally, this paper concludes with a short summary and discussion for future considerations. In basic motion-planning, a robot A moves through a Euclidean space W (the workspace) represented as R N where R is the set of real numbers, and N 2 or 3 is the spatial dimension. The motion planner for the wheelchair assumes a two-dimensional space where N 2: The space W is populated with obstacles represented as B 1 , B 2 ,¼, B q , and the motion planner parameters are de®ned by the shape, position, and orientation of A, the B i s, and W. Given the initial and goal positions and their orientations, the objective of the motion planner is to determine if a path exists from the initial to the goal positions and, if so, to generate a continuous path t through the workspace W for the robot A avoiding the obstacles B i s. To ®nd a path in a space, the method ®rst approximates the wheelchair by a disc. Then, it grows the obstacles isotropically by the radius of this disc. Finally, the motion planner computes paths between given points of the resulting free space. The remainder of this section elaborates the way we applied the approach for the wheelchair problem. The motion planner generates a con®guration space C from the geometric properties of A, the B i s, and W, and it attempts to construct a path in this con®guration space. In the new space C, the motion planner transforms robot A to a point object, and the motion-planning problem becomes one of generating the path t in C. For a 2-dimensional space W, the dimension m of the con®guration space C is 3. For example, a robot A restricted to move in the xy-plane W R 2 has three degrees of freedom: translations in the x and y directions and the orientation u . Working in the con®gura-tion space C instead of the workspace W, the constraints become more explicit. If the motion planner works directly with the workspace W, it would have to perform operations such as collision checking at each proposed path position in C, the collision-checking operation has already been addressed for all possible robot positions. As the motion-planner maps or`shrinks' A to a point object, an obstacle B i maps to the C-obstacle CB i bỳ growing' its shape based on the geometric parameters of A and B i as shown in Fig. 1 . The basic algorithm establishes a reference point with respect to the robot A and tracing A around the obstacle B i . The path circumscribed by A describes the C-obstacle CB i . If A can freely rotate, the shape of CB i depends on A's orientation. Fig. 1 illustrates the transformation of an obstacle to a C-obstacle, given a ®xed orientation of A. By generating the con®guration space C, the motion planner transforms the path-planning problem into the problem of ®nding a smooth curve within C. Now, the motion planner must guide the robot from the initial point to the goal point through C. Latombe [7] notes that using some type of`potential ®eld' is the most successful method for guiding the robot A. The generated potential ®eld guides A lden A by forcing it down the gradient from the initial point to the goal point. The motion planner discretizes C by de®ning a grid over the space and generates the potential ®eld values for each grid cell. Since the motion planner knows the geometric parameters of A, the B i s, and W a priori, it can generate potential ®elds free of local minima. The accessible route analysis developed in this paper uses a potential-®eld-generating algorithm NF1 as described by Ref. [7] , which can be shown to be free of local minima. The algorithm creates a potential ®eld that guides the robot A from the initial point to the goal point on a path t that grazes the C-obstacles. The ADAAG de®nes an accessible route as: Provision 3.5 De®nitions. Accessible Route. A continuous unobstructed path connecting all accessible elements and spaces of a building or facility¼ In addition to the above de®nition, the ADAAG prescribes measurements that de®ne accessibility for various building elements (such as doors and toilets) along an accessible route. An accessible route can thus be described as a sequence of accessible route segments and, if needed, adequate clearance at the openings of critical components of a space. Our motion planning technique determines accessible route segments in a space between building elements (such as doors and toilets). In addition, individual elements are checked for geometric clearances. A complete accessible route includes many accessible components (including openings and route segments). The route is considered accessible if all components in the route are accessible. The following de®nitions de®ne the terms that we use in the performance based accessibility analysis: The motion planner generates a path between an initial point and a goal point. Building components along the accessible route graph map to the R nodes: R open nodes map to initial and goal points, R init nodes map to initial points, and R goal nodes map to goal points. The arcs of the graph (the R seg components) map to the generated path between the R nodes. Fig. 2 shows the potential accessible route segments and components of a bathroom facility and the associated accessible graph. Route segments (arcs) are established between adjacent building elements. It is interesting to note that there are two established goal nodes (and two route segments) for the toilet at K because the algorithm models access to the toilet using either a side or a diagonal transfer. Furthermore, nodes A and B are potential accessible openings but the doorways at C and D are eliminated as potential R open node since they do not have suf®cient clearance requirements. Also note that each opening R open and each route segment R seg can be evaluated independently. In the following, we ®rst discuss the application of a motion planner for determining the existence of an accessible route segment R seg . We then discuss the compliance checking of the component openings, R open . Finally, the determination of the initial and goal positions of various building elements is discussed. Although the goal of this study is to directly model the motion of a wheelchair through a space using the actual wheelchair geometry, the motion planner ®rst tries to verify A lden the existence of a`comfortable' width along the route. To determine an accessible route segment within a space, the motion planner performs two basic tasks: 1. Verify the existence of adequate clearance width along the route. 2. Determine if a wheelchair user can negotiate this route given the assumed geometric and behavioral constraints of the wheelchair. The existence of an accessible route is intended to ensure the usability of a facility for wheelchair-bound users, and in most cases, the wheelchair user should be able to negotiate the accessible route using only forward motion. The ADAAG provision below prescribes the width parameters of the route. For the ®rst pass, we focus on the general 36 in. (915 mm) requirement on the accessible route. The exception rule for turn around will be discussed later for constructing the second pass. The general 36 in. (915 mm) width rule does not represent the width of a wheelchair but prescribes a`comfortable' width for the wheelchair user to negotiate. To satisfy the provision, the motion planner uses a 36 in. (915 mm) disc to describe the geometry of the robot A 36 . Given the workspace W as determined by the¯oor space and the building components, the motion planner generates the con®guration space C 36 given A 36 and W. The path generated by this planner is not subject to geometric and physical constraints (such as turning radius) of a robotÐthe robot simply slips and slides down the potential gradient. This type of planner is known as a holonomic planner [7] . Fig. 3 illustrates the C 36 con®guration space for a bathroom facility example. The white (nonshaped) areas represent legal positions for the A 36 disc robot and are ensured to provide a 36 in. (915 mm) clearance. Note that the motion planner treats a doorway with the door in the closed position, and, hence, in the con®guration space between the entry door and the accessible toilet is discontinuous. For this pass, the motion planner does not actually generate the path. It simply generates the potential ®eld from the goal points to the initial points. If the potential-®eld generation cannot reach the initial point, there is no 36 in. (915 mm) width path between the two points, and an accessible wheelchair route between the points does not exist. If, however, the potential-®eld generation does reach the initial point signifying that a 36 in. (915 mm) wide path does exist between the two points, the motion planner proceeds to the second pass. Fig. 4 illustrates the actual potential ®eld generated between the entry door and a urinal using a  To closely examine exceptional rules, e.g. the clear width of an accessible route around an obstruction, we need to be able to capture the behavior of wheelchair motion. Fig. 5 illustrates the two ADAAG ®gures (Fig. 7(a) and (b)) referenced by Provision 4.3.3 of the ADAAG. Note that in the prescriptive width de®nition, the exceptional rules and the associated ®gures do not address all possible turn-around con®gurations. In order to provide accessibility check on all possible con®gurations, the route planner models, as closely as possible, the behavior of wheelchair motion as to the level of detail set by the guidelines. In the second pass, in addition to the C 36 con®guration A lden space generated in the ®rst pass, con®guration spaces are also generated using the actual wheelchair robot denoted as A wc . Fig. 6 shows the reference wheelchair dimensions as given in the ADAAG, and Fig. 7 illustrates the geometry of the wheelchair robot which has its width less than 36 in. (915 mm) wide. The potential ®elds within the con®gura-tion spaces generated by the planner are used as a guide to determine the path t for A wc . Since A wc is not a disc, the motion planner must keep track of the robot's orientation while generating a path, and the motion planner must check each wheelchair position and orientation against the obstacles in the space. The motion planner discretizes the rotation space into n con®g-uration spaces C wc0 ¼C wcn where the angle (in radians) between two consecutive orientations A wc is equal to 2p/ n. Now, the motion planner can check the wheelchair position and orientation x; y; u against each appropriate con®g-uration space C wci . The motion planner generates a nonholonomic path [8] by restricting A wc to three moves: a left turn, a right turn, and a straight-ahead move. Fig. 8 illustrates these three options. For the left and right turns, the motion planner describes the vertex of the turning angle as the perpendicular length r from the centerpoint between the major wheelchair wheels. The motion planner records the actual position of A wc at the centerpoint of the halfdodecagon at the front of the robot. The displacement distance D from either turn (which is dependent on r) dictates the translation of A wc . The performance-based accessible route path planner employs two values r 1 and r 2 for the turning radius r to allow adjustment for maneuvering the wheelchair. The larger turning radius r 1 is employed to move the wheelchair robot to the goal point. As the wheelchair user nears a goal, the user naturally slows down allowing ®ner maneuvering with a smaller turning radius r 2 . In this study, when the wheelchair has moved within an 18 in. (460 mm) locus of the goal point, the motion planner switches to the smaller turning radius r 2 to try to maneuver A wc to the goal point with an acceptable orientation. In determining the value for the turning radius, a larger value represents a larger turning circle and a more comfortable path t for the wheelchair user. The largest possible value for r 1 was determined using a trial and error process using the two turning-around-an-obstruction con®gurations based the ADAAG Provision 4.3.3 shown in Fig. 5. Figs. 9 and 10 illustrate the ®rst legal paths with an r 1 -value that works for both turning-around-an-obstruction con®gura-tions produced by a trial-and-error process. Through this process, we selected 24 in. (610 mm) as the value of the larger turning radius r 1 . As with the determination of r 1 , a trial-and-error process was employed to determine the smaller turning radius r 2 based on Provision 4.2.3 of the ADAAG: Provision 4.2.3 Wheelchair Turning Space. The space required for a wheelchair to make a 1808 turn is a clear space of 60 in (1525 mm) diameter (see Fig. 3(a) ) or a Tshaped space (see Fig. 3(b) ). This space is usually satisfactory for turning around, but many people will not be able to turn without repeated tries and bumping into surrounding objects. The space shown in Fig. A2 will allow most wheelchair users to complete U-turns without dif®culty. Fig. A2 ) illustrates an acceptable clearance oval, and the turning movement as shown in Fig. 11 ®ts into the suggested oval geometry. The motion planner uses the potential ®eld in the con®g-uration space C 36 to guide the wheelchair robot A wc as follows: starting from the initial position and orientation A lden q init , the motion planner examines the move options for left, right, and straight ahead (denoted as q left , q right , and q straight , respectively) using r 1 as the turning radius for the robot. 1. If q left resides in the C 36 and appropriate C wci con®gura-tion space, the motion planner compares the position x; y associated with q left with the position x; y associated with q goal . 2. If the two positions are not the same, the motion planner looks up the potential ®eld of the position and inserts the node into a priority queue, which prioritizes the nodes by their potential ®eld value (the lower the value, the higher the priority). 3. Finally, the motion planner inserts a pointer to the previous position (in this case, q init ) in the node and marks q left in the appropriate C wci con®guration space potential ®eld as having been already visited. The motion planner repeats this procedure for q right and q straight . The motion planner continues the iterative process by removing the highest priority node (the node with the lowest potential value) from the priority queue and examining the A lden three move options from the associated position and orientation q. The C wci con®guration spaces include the visited as well as the free space information, and the motion planner treats a visited q init as an obstacle. When q is within an 18 in. (460 mm) locus of q goal , the planner starts generating new positions using the smaller turning radius r 2 . When the robot reaches the goal position, the motion planner examines whether the orientation u associated with the current q is within the allowable range of u goal and, if so, it records the path t . The iterative process continues until either the motion planner empties the priority queue (indicating no path t exists) or the position x; y associated with the current q matches with q goal for both position and the acceptable orientation range. Fig. 13 illustrates a generated path from the entry door to the urinal in the bathroom facility. ADAAG prescribes wheelchair clearances at doors and entrances along an accessible route. The R open node of an accessible route graph consists of three clearance components: the clearance of the opening and clearances on either side of the opening. For the opening, the analysis applies a geometric test with the parameters of the required clearance box taken directly from the following provision: Fig. 14 shows the ADAAG ®gure that prescribes wheelchair clearances for doors. Note that the clearance geometries are dependent on the approach of the wheelchair and additional parameters speci®c to the building element. For example, for doors, the clearance geometry may be dependent on the direction of the swing. For a single swinging door, the ADAAG de®nes the side from which the user pulls the door to open it as the pull side and the side from which the user pushes the door to open it as the push side. From each side, the user can approach the opening from the front, hinge side, or latch side of the door: ² For the front pull side approach, the clearance box extends 60 in. (1525 mm) from the wall that contains the opening and the door and covers the width of the opening plus 18 in. (460 mm) on the latch side of the door (left picture of Fig. 14(a) ). ² For the front push side approach, the clearance box extends 48 in. (1220 mm) from the wall and covers the 6 Note that these ®gures are not shown in this paper. Advanced Engineering Informatics ± Model 5 ± Ref style 3 ± AUTOPAGINATION
Han et al. REF employ the Minkowski sum method to outline the accessible areas for wheelchair users.
A performance-based approach to wheelchair accessible route analysis
Advanced Engineering Informatics
Computer Science Engineering