Muti-Representation and Generalisation Based Webmapping Approach Using Multi-Agent System

Abstract

Over the last decade, an enormous demand for digital maps in different disciplines and fields was stated. Geographical information is currently available at anytime, from anywhere on the surface of the earth, by any person connected to internet. Some applications of design, implementation, generation and dissemination of maps on the Web are recognized as Webmapping. It uses among other things, a Geographic Data Base (GDB) and must be able to provide a fast response time (quasi-real time) and a high quality of visualized information. We propose in this paper, a Webmapping approach which is based on two principles; (1) exploiting an hybrid approach Multiple Representation and Generalisation in storing, handling and generating geographic data and (2) integrating Multi-Agent technology, in all steps of the Webmapping process. The effectiveness assessment of our webmapping approach is performed in ArcGIS environnement 9.3. We present some results of our experimentation which focused on the road network theme.

Keywords

• Geographical Information
• Webmapping
• Multi Representation Data Base (MRDB)
• Automatic Generalisation Process
• Multi Agent Systems

-

The large amount of handled geographical information comes mostly, from various GDBs designed independently of each other, although they relate to the same location. They are developed according two factors: (1) Level of Detail(LoD) which corresponds to map scale concept and (2)Point of View (PoV) that expresses the perceiving way of a real entity located on the surface of the earth. Producers and suppliers of cartographic data have deemed useful to exploit these different GDBs acquired with a very high cost. Thus, the same phenomenon may have multiple representations. One of developed approaches to model and manage such information is the integration of these DBs associated with the same location into an integrated one [ 1, 2 ] called for this purpose Multiple Representation Data Base (MRDB). In the MRDB, representations associated with a same geographic phenomenon are linked by explicit relationships. We emphasize that in this context, we consider two multiplicity factors; LoD and PoV. We have also, distinguished the concept of Multiple Representation (MR) associated to a MRDB as previously described, from that corresponding to results of generalisation process. We characterize the first by relevant because they are close to the real representation. Also, automatic generalisation process allows generating as many representations as expressed needs from a very detailed GDB (high LoD). It is concerned with the transformation of a representation of a part of the world. Despite the efforts, the automation of this process doesn’t achieve, it keeps improving [ 3–5 ] since its inception thirty years ago. The agent-based approaches [ 6, 7 ] have attempted to imitate the cartographer reasoning who considers objects in their global context that is the purpose of the map. It represents the common goal to agents that interact by coordinating their actions and cooperating to achieve this goal. Webmapping is so, an application in which the web represent an important platform in dissemination of geographical information and offers several advantages such as accessibility and timeliness. However it requires a real-time map delivery.

Pre-designed and stored within a MRDB or generated by triggering a map generalisation process, the contents of these maps must be adapted and personalized according to a given user query and context. But are users pleased with their displayed maps?! Have they felt any impatience in waiting the visualization of required maps? How about its quality? Many researchers have addressed these issues with the aim to develop a Webmapping applications devoted to the management and delivery of geographical information on the web via generalisation services or geographic web services [ 8 ] and webmapping application [ 9–11 ]. In [ 12 ], the authors present a clear distinction between webmapping applications and geographic web services. [ 13 ] provides a synthesis of research orientations in this area based on the use of multiple representation and generalization, stating that the web already occupies a place which is developing all the time.

We propose in this paper, a Webmapping approach based on multiple representation and generalisation which remains an active research area [ 13, 14 ]. We use Multi-Agent Technology in all steps of our approach in order to reduce the map generalization process complexity by exploiting firstly, the autonomy of agents and secondly, the communication between agents to resolve conflicts over space use. We were inspired by some works developed in this context that we introduce in the next section. In section three we focuses on our contribution, it’s organized on some subsections, in which we highlight our approach principles. A tool implementing our approach is presented in section four. Finally, we conclude the paper with a summary of the essential addressed points and make suggestions for future progress. 2

Related Works

Many research works have addressed webmapping globally or partly by focusing on specific tasks, which once integrated into the process, they ensure its proper performance, such, is the case of the generalisation process. It is mainly the reason which has led researchers to develop variant of generalisation process according to various approaches. The agent-based generalization approach has been developed and improved during last years [ 14 ]. In the web context [ 15 ] talk about on-the-fly-generalisation which denotes the use of automated generalisation techniques in real time. Multiple representation, automatic generalisation and Multi-Agent System (MAS) are so, the three basic pillars of most works in webmapping. All these works have the same objective which consists of developing an automatic generalisation system adapted to the web. It must reduce the complexity and the cumbersome of the earlier systems based on different approaches (algorithmic approaches, knowledge based approaches, etc). It is therefore necessary to exploit the powerful features of agents such as, autonomy and communication. Thus, they have started from the basic idea, which is assigning a software agent to each object and/or group of objects. They are differentiated by the number and types of used agents according to the addressed themes such as meso, macro, micro and submicro agents in [ 7, 16 ] and agents or groups of agents which act upon three levels of data (the initial map, layers of interest and final generated map)in [ 11 ].

However, these approaches face agents number explosion in the case of a dense Area (urban area). Indeed, the number of created agents becomes huge, what makes communication between agents very complex and increases the likelihood of having a deadlock. These approaches are so, considered useful and efficient in low dense Area processing (rural area). In our approach we overcome this problem in a potential way. On the one hand, the generalisation process used is conditioned by search in the R-MRDB which allows moving towards the level of detail requested if it is available. On the other hand, we introduce the map area concept which leads to process a dense map. Map area represent a sublocation of a map. Each sublocation is handled by an agent meso. More details on our approach are presented in next section. 3

Webmapping proposed approach

To carry out our research work, we have set some assumptions; the Relevant MRDB(R-MRDB) is associated to an Area. It contains exclusively geographical data acquired through reliable process; it isn’t the result of generalisation process. We use vector data with several LoDs and PoVs. The implemented generalisation process depends on some constraints like resolution interval and generalisation rate. Due to space limitations we don’t address this aspect in this paper; more details are in [ 2, 5 ] 3.1

General description of proposed approach

Our approach is entirely based on a multi-agent system which supports the principle tasks as described in figure1: query Analysis, selection of the layers of interest and generation of the final map. A query initiated by a user is primarily analyzed in order to extract the defining features of the requested map that is the

Seleocftiinotneroefsltasyers

Generation of final map Extraction of Geographical FroimnfothremRat-iMonRDB (b)

Activation of optimized generalisation process

(c) LoDi and PoVj (module (a) in figure 1). Some layers of interest are so selected and a driven search process through the web platform is triggered. This process begins with a search in the R-MRDB; if requested information associated with LoDi and PoVj is explicitly stored in the R-MRDB, it will be directly returned in a real response time (module(b)in figure 1). Otherwise, a generalization process is enabled to produce the requested Map (module(c)in figure 1). We also note that the terminology used in the description of different types of agents (Coordinator, Macro, Meso and Micro) of our system is inspired by [ 11 ] and [ 14 ]. The role and functionality of each of them is detailed in the following section.

Query

Analysis of query and selection of layer of interest

Agents macro selection of layers

Agent coodinator Our MAS consists of different types of agents, specific tasks are assigned for each of them. These agents interact with each other to ensure a smooth running of process. The sequencing tasks to be performed in generating final map is directly related to the triggering of hierarchical types of agents: Coordinator, Macro, Meso and Micro. Restitution of result is done in the reverse (see figure 4). Agent coordinator : The agent coordinator is responsible of two tasks :(1) analyzing a user query in order to identify the layers of interest according to a LoD and a PoV(aim of the map) and (2) assigning agent macro to each layer of interest. Each agent macro, must decide the suitable processing for its layer. It so, initiates its inference engine while having as input parameters the LoD and the PoV. This is either a direct extraction of R-MRDB (module (b)in figure 1), or a triggering of a generalisation process (module (c) in figure 1) by triggering other type of agent (meso, micro) in a hierarchical way. And so on the processing is completed. The result (final map) is delivered to the coordinator agent (see figure 2).We emphasize that in developing the query analysis module, we restricted to two classes of users: (1) professional user who have depth knowledge in cartography and, (2) occasional user who shall be assisted during the process. We also manage a list of keywords related to the application domain (urban design) that we have chosen during the experimentation phase.

Layer of interest

Agent Macro Agent Macro : The Agent Macro continues the path of the process by accessing to the R-MRDB. If the requested map content corresponds to a LoDi and PoVj explicitly stored in the specified DB, it proceeds by direct extraction, the response time would be very efficient. Otherwise a generalisation process is triggered(see figure 3). As stated previously, our approach overcomes the map density problem (explosion of agents number), by introducing the concept of map area. The layer is so partitioned into areas, to each of them is assigned an agent meso. Thus, our approach may be adapted to the processing of any geographical location with a high density (large number of objects) or low density. Thus, the preliminary search in the R-MRDB, map area concept and parallel processing provided by developed MAS allow leading to a great process with a real-time response.

Agent Meso/Micro : The agent Meso assigns to each object in its own map area, an agent Micro. Micro Agents are responsible for the accomplishment of the generalisation process. We state that in the context of this work, we focused on the road network theme, so we have relied on the operator of simplification for conflicts resolution. In [ 5 ], we have described the various conflicts around this theme and constraints to satisfy in their resolution. Intra-conflict is the result of racing agents for the space occupation. They communicate in order to preserve the overall harmony of the map. Communication between agents is based on blackboard technique. It is a space in which each agent has a record (Id -agent, current geometry of the object, state of the agent) visible to other agents in the same area. In figure 4, we present a recapitulative of our approach through an example of application on the road network of an area in north of Algeria with illustration of all processing phases. In this example, we consider the road network theme with its different LoDs (national roads, departmental roads secondary roads, etc) according to the nomenclature of the National Institute of Cartography and Remote Sensing (INCT) of Algeria. We assume that a query initiated by an occasional user contains the keyword ’highway’ such as: I got lost on the highway Algiers-Blida. The query analysis module will extract the location and level of detail associated with the national roads which is directly extracted from the R-MRDB in a real time (case (1) in figure 4). If against, a civil protection officer (professional user) looks for quick access to a location, we invite him to enter information such as visualization scale of requested area which is associated to the highest LoD in R-MRDB. The displayed map will be congested. So, we proceed by generalisation in order to keep only useful information to the officer (case (2) in figure 4). 4

Experimentation

Our Webmapping prototype was developed in the ArcGIS server 9.3 environment. We have also used the platform JADE for the implementation of our MAS. We consider in this paper only simplification operator in generalisation process. Our experimental method and the software tools used are described in figure 5. 4.1

Main interface of our Webmapping Application

This interface is run through a web browser which allows two tasks; configuring, and search (figure 6). The first task presented in figure 7, is secured because it allows access to map generation parameters. The second task concerns customers (professional or occasional). We have configured two user interfaces, one for professional user (see figure8) who can provide valid information and occasional user(see figure 9 ) who hasn’t depth knowledge in the field. We note that in figure 8, the field scale is activated, the user is identified as professional one (See illustrative example above).The LoD of the requested data is determined from the input map scale. However in figure 9 (occasional user) the same field is disactivated. The developed system must be able to define this entity as showed in the example below.

Professional

user Map scale

field

A first result of a running example is presented in figure 10. From a query of an occasional user, two keywords RN6 and RN13 are implicitly or explicitly expressed. The area which contains the specified roads is so identified. The requested LoD corresponding to the layer national roads is available in R-MRDB. Our webmapping system proceeds by direct extraction and the result is delivered in a real time.

Conclusion and future Work

The developed Webmapping approach is based on multiple representation and generalisation, in order to take advantages of the relevance of the first and flexibility of the second. The utilization of multi-agent system technology has provided our approach with parallel processing in automatic generation maps. Indeed, in our developed MAS, an agent is assigned to an object and /or group of object according to a hierarchical organization. These agents act independently while adapting to environment changes and communicate with other agents via the blackboard technique in order to provide the result (final map). Therefore the developed system allows reaching a real-time response required in this web context. As future issues, we suggest firstly to provide some improvements to the current solution specially, the development of spatial query module analysis based on a domain ontology and secondly to improve the supporting map customization preferences and user profiles. This can be done by collecting information on the web and mobile users through questionnaires, or by using a learning system that is able to distinguish between professional and occasional user.

Acknowledgement

The authors are grateful to Bouchenine Yakoub and Abada Lyes Ph.D. students in USTHB University, for the considerable effort carried in achieving this work.

References

1. Vangenot , C. : Multi-representation in spatial databases using the mads conceptual model . ICA Workshop on Generalisation and Multiple Representations , Leicester (August 2004 )

2. Derbal , K.A. , Lejdel , B. , Alimazighi , Z. : A hybrid approach to modeling and managing multiple representation of spatial data (application theme :road network) . International Conference on Information & Communication systems ICICS' 2009 , NYIT JORDAN ( 2009 )

3. McMaster , R. : Automated line generalization. in Cartographica 2 ( 24 ) ( 2006 ) 74 - 111

4. Ruas , A. : Modle de gnralisation de donnes gographiques base de contraints et d'autonomie. Ph.Dthesis , Universit de Marne- la- Valle ( 1999 )

5. Derbal , K.A. , Alimazighi , Z. : Approche de rsolution de l' auto-conflit dans un processus de gnralisation automatique du linaire routier . Veille Stratgique Scientifique et Technologique VSST' 2010 , Toulouse ( 2010 )

6. Duchne , C. : Coordination multi-agents pour la gnralisation automatique . Bulletin d'Information de l' IGN (74) (Mars 2003 )

7. Ruas , A. , Duchne , C. : A prototype generalisation system based on the multiagent system paradigm . Generalisation of Geographic Information: Cartographic Modelling and Applications Elsevier ltd chapitre 14 ( 2007 ) 269 - 284

8. Bergenheim , W. , Sarjakoski , L.T. , Sarjakoski , T. : A web processing service for grass gis to provide on-line generalisation . 12th AGILE International Conference on Geographic Information Science Leibniz Universitt Hannover , Germany

9. Cecconi , A. : Integration of cartographic generalization and multi-scale databases for enhanced web mapping . PhD. Thesis , University of Zurich ( 2003 )

10. Bernier , E. , Bdard , Y. , Hubert , F. : Umapit: An on-demand web mapping tool based on a multiple representation database . 8th ICA WORKSHOP on Generalisation and Multiple Representation , A Corua ( July 2005 )

11. Jabeur , N.: A multi-agents system for on-the-fly web map generation and spatial conflict . PHD thesis . Universit LAVAL, Qubec (Janvier 2006 )

12. Pornon , H. , Yalamas , P. , Pelegris , E.: Services web gographiques, tat de l'art et perspectives . Gomatique Expert ( 65 ) (octobre-novembre 2008 )

13. Burghardt , D. , Petzold , I. , Bobzien , M. : Relation modelling within multiple representation databases and generalisation services . The Cartographic Journal 47 ( 3 ) ( August 2010 ) 238 - 249

14. Duchne , C. : Automatisation de la gnralisation. Sminaire quipe SMA - LIP6

15. Weibel , R. , Burghardt , D. : On-the-fly generalization . Encyclopedia of GIS . Springer science & Business media LLc . ISBN :978-0-387-35973-1 ( 2008 )

16. Gaffuri , J.: Deformation using agents for map generalisation - application to the preservation of relationships between fields and objects . AutoCarto'06 , Vancouver, United-States, 2006 . ACMS. ( 2006 )