A study on a system for guiding of the optimal route with a hybrid network and grid data structure.

(Translated from Japanese)



Kei-ichi OKUNUKI, Richard CHURCH, & James MARSTON

Keyword: Hybrid network and grid data, Guiding system,

optimal route


1. Introduction

Current guiding systems deal with only "line" space

such as street networks and railroad networks.In real environments, however, there is much "area" space expanding two-dimensionally such as parks. In this study, we propose a new guiding system which can deal with a mixed space made up of lines and areas.


Routes in an area must be a matter of great importance especially when we consider the system guiding behaviors in a building such as museums, big department stores, or traffic facilities. Because they invariably have areas such as lobbies, courtyards, or concourses.


A simple way to deal with an area is to represent such continuous space approximately as discrete space by dividing it into grids. Once it is represented as grid data, we can handle a route in those spaces in the same way as handling a route in lines by constructing networks of grids.

In this study, we develop the guiding system with the hybrid data structure, in which lines are represented as network data and areas are represented as grid data, and its prototype is presented. There is little study so far on a guiding system with such a hybrid data structure.


2. Routes in areas

First, we describe the way to handle a route in an area. A simple method is to divide an area into grids (Fig. 1), and next, to construct a network in which each node is the center point of each grid, and then, to handle a route on the network (for other methods, see Chen et al.(1991) or Xiong et al. (1992)).

When an area is approximated as discrete grids, there arises the discrepancy between the route connecting two points in an area and the route approximated on the grid. The extent of such discrepancy depends on the way the network is constructed, not on the size of grids (Iri,1998). The more each node is linked to different directions, the more precision of approximation improves. Although precision of approximation reaches a maximum when each and every node is linked with each other, then the calculation load turns into an issue.


The best way to prevent the calculation load from rising is to keep the number of links low. According to Huber(1985), when each node links only with adjacent nodes like as Fig.2(a), the discrepancy is 40% in the worst case. When diagonally adjacent nodes are added (Fig.2 (b)), the discrepancy becomes 10%. When nodes located in a knight’s jump arrangement are added (Fig.2(c)), discrepancy falls to 3%. Huber(1985) applied these kinds of linkages to practice in the route problem in Maryland, and found that the case (c) showed the best precision/calculation-load ratio. Therefore, we adopt this pattern of linkage in our system.


Once grids are transformed into a network by using this method, we can apply the route searching algorithm such as Dijkstra's(1959) or others to the network. (In the case of the linkage pattern like Fig.2(a), Kanchanasut's (1994) method can be applied.)


3. Guiding system with the hybrid data structure

In this section, we describe an actual guiding system dealing with a mixed space made up of lines and areas.

The space taken up as a subject is a building, named

Ellison Hall, on the campus of the University of California, Santa Barbara. This building has a shape like a letter "H" (Fig.3), and has a courtyard surrounded by walls on three sides. People might go through this courtyard when they move from one location to another in the building. Therefore it is essential to deal with this space when we develop the guiding system applied to the building. We represent this courtyard space as grid data, and the space inside the building as network data.

First, the network data of the space inside the building is prepared. In this network, corridors, stairs, and elevators are represented as links, and offices, doors of lavatories, elevators, doors to stairs, entrances of the building, drinking fountains, and telephone booths are represented as nodes. Networks for each floor are connected to each other through stair-links or elevator-links and we construct a global network having about 900 nodes.


Next, the grid data of the space outside the building, that is the courtyard, is prepared by dividing the space (about 900 sq m) into 40 grids with each side 1.5 m long. The size of the grid was decided with reference to the width of a corridor in the building. As the width of a corridor is about 2 m, it is expected that we can get better precision than the network for the space inside the building by setting the smaller value than the width of a corridor on the width of grid.


From the grid data, then, a network in which each node is the center point of each grid is constructed by connecting them in the manner illustrated in Fig. 2(c).By connecting this network to the network for the space inside the building, we can get a comprehensive network for the entire space at issue.


In the route searching process, we find the optimal route (the shortest route) to a destination by applying Dijkstra's(1959) algorithm to the comprehensive network.Fig. 4 depicts an example of a display outputted from a prototype of this system.


4. The guiding system in the future

In the future, the range of application of guiding system will be enlarged to the direction of more micro-scale environment. The most popular guiding system so far may be the car navigation system that handles routes in city scale. But in the near future, the need for the guiding system for pedestrians, not for car drivers, will become higher (already we hear the word " walk navigation"), and it will be inevitable for such systems to deal with routes in micro-scale environment which we have little thought about.


To put it concretely, places which require a guiding system dealing with micro-scale information will be large public facilities such as museums, department stores, stations and so on. Those facilities are open to the general public who might not visit them often, are unfamiliar with them and they are relatively complex in structure. Therefore visitors have a hard time finding locations of the destinations and the routes to it. They need to be guided.


The most important feature of the guiding system for those highly public facilities should be the preparation of the care for senior citizen and disabled people. Those people needs not only help to navigate in the building, but also the provision of information prior to visiting. It is very important for physically disabled people to get information about the place where they are going (for example, are there any rest rooms for a wheelchair, and where are they?) in advance of the visit, because such information can reduce their anxiety about going out. Actually our system is designed to provide information for wheelchair users through the Internet before they visit the building.


One of the obstacles to improving the guiding system adequately for the senior and the disabled is the fact that there is great diversity in the disabled community. Even when we consider only visually disabled people, some are congenitally completely blind and some are adventitiously partially impaired. We should not regard them as a uniform group. When we develop the future guiding system, a universal design in which all kinds of people are considered as users will be needed.


As a matter concerning universal design of guiding systems, we take up the problem which the system for blind people have to solve. In such a system, it is necessary to devise equipment for information transmission. For example, to make it possible to use tactile map as a representation tool for space, current computer displays must be replaced by the new equipment which could cope with such information.


5 Conclusion

In this study, a new guiding system with the hybrid network and grid data structure was developed. In the future, the range of application of the guiding system will be enlarged to the direction of more micro-scale environment. Our system can be applicable as a prototype of such micro-scale guiding systems.



The accesible building route guidance system describes the framework for this work on disability accss and also has links to the route planner. The prototype (Ellison Hall Guidance System) can be also directlyexperienced at

http://www.ncgia.ucsb.edu/~nuki / EllisonRep.html and http://www.ncgia.ucsb.edu/~nuki/EllisonMenu.html

Email: marstonj@geog.ucsb.edu  

Web site: http://www.geog.ucsb.edu/~marstonj