21-01-2013, 12:45 PM
Automatic Geospatial Web Service Composition for Developing a Routing System
1Automatic Geospatial.pdf (Size: 3.45 MB / Downloads: 68)
Abstract
Routing or path finding is one of the most popular services, which is widely used by
citizens and tourists, around the world. These systems, which are generally developed
based on WebGIS provide users with the capability of introducing a start and an end
point and then to observe the optimum (e.g. shortest) path between these two points.
However these systems can only perform analysis for specific areas for which the data is
available in the WebGIS and also can only work based on the specific routing
algorithm(s), by which the system is designed. To increase the flexibility of the system,
an alternative solution could be the availability of a Web-based routing system that works
based on Distributed Geospatial Information System (DGIS) and Automatic Service
Composition techniques. An aim of this research is to design and develop a system for
routing based on automatic service composition.
Introduction
A Geographical Information System (GIS) is a system designed to capture, store,
manipulate, analyze, manage, and present all types of geographical data (Foote & Lynch,
2000).Web GIS enables the communication of all components of GIS to happen through
the web, enabling diverse data, analysis algorithms, users and visualization techniques
that may be hosted at any location on the Web (Avraam, 2010).
Now a day, Web GIS provides citizens with the capability of using GIS and spatial
planning techniques for daily activities. It is generally easy to communicate with
WebGISs through user-friendly interfaces, which are designed for specific purposes such
as map navigation, spatial search or analysis, e.g. finding the shortest path. However,
while using WebGIS applications, users are generally limited to the functionalities and
the data that are supported/provided by a WebGIS system. In other words, if a user’s
request is beyond the scope of the data and the functionalities of a WebGIS, the system is
incapable of responding to that request and hence the user would get no result, although
the required data and functionalities may be still available somewhere on Internet.
Shifting from client-server WebGIS architecture to Distributed Geospatial Information
Services (DGIS) architecture may be a solution to offer more proper GIS services to
citizens. In this case, automatic service composition would be the central technique for
achieving the aim. Service composition is the area of science which looks for proper
processes and tools to chain Web services for fulfilling user’s request (Yue et al., 2007).
These services can interoperate together to fulfill the user’s request. But the main
challenge is still finding solutions on how to chain these services in a proper way and by
which tools.
A typical scenario
Suppose a user asks for the shortest path between a given arbitrary start point to another
arbitrary end point in a city. Instead of connecting to a WebGIS -which is limited
regarding data and functionality- a system based on automatic Web service composition
can exist to which the user can connect and introduce the desired start and end points as
well as routing algorithm.
Thesis structure
This thesis is organized in 6 chapters. After the present chapter, which is an introductory,
in chapter 2 path finding algorithms are reviewed according to their functionalities. Pros
and cons of each method is discussed and some algorithms are described with more
details. Chapter 3 describes the concept of Web service composition and reviews the
most important standards and interfaces for Web service composition in geospatial
community.
In chapter 4 the proposed path finding algorithm and how the algorithm was implemented
is described. In chapter 5 the system architecture, which is used for automatic Web
service composition is described as well as the implementation of the system. Finally the
thesis ends with conclusion and future directions in chapter 6.
Path planning algorithms
There are a variety of path planning algorithms based on the purpose or application of the
planning. The optimum path maybe based on the shortest distance or the fastest travel
time. The path found for a vehicle may go through highways which makes it longer
regarding the total length but makes the traveling time shorter. Most drivers prefer this
comparing to waiting in long traffic lines in downtown streets. Other factors might be
important in other fields. E.g. in robotics, each time a robot wants to make a turn it has to
stop and it consumes considerable effort to make it run again. Here the number of turns
becomes important and it is tried to offer a path with the least number of turns possible
for the robot. To guide the traffic to desired directions in transportation science different
costs could be defined for roads which give each road some weight that makes the road
more proper or less proper for the final path. Some algorithms are proper for vehicles
while other may be better for pedestrians. The concern of this thesis is planning path for
pedestrians and for simplicity the focus is on finding the shortest path.
Algorithms that rely on network structure
These algorithms are mostly used for vehicle navigation systems. They are based on a
graph (network) consisting of nodes and edges/links (Figure 2.1). These algorithms are a
main research question in the field of Geographic Information Systems. Some wellknown
methods are Dijkstra’s algorithm (Dengfeng & Dengrong, 2001), Floyd’s
algorithm (Garcia et al., 2007) and A-star (Hart et al., 1968).