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.htmlEmail: marstonj@geog.ucsb.edu
Web site: http://www.geog.ucsb.edu/~marstonj