LibraryPhysical Science & MathComputer Science

Automated Generation of Geometrically-Precise and Semantically-Informed Virtual Geographic Environments Populated with Spatially-Reasoning Agents

by Mehdi Mekni

e-Book PDF
Institution: Laval University
Advisor(s): Bernard Moulin and Phil Graniero
Degree: Ph.D. in Computer Science and Software Engineering
Year: 2010
Volume: 234 pages
ISBN-10: 1599423715
ISBN-13: 9781599423715


Multi-Agent Geo-Simulation (MAGS) is a modelling paradigm which has attracted a growing interest from researchers and practitioners for the study of various phenomena in a variety of domains such as traffic simulation, urban dynamics, environment monitoring, as well as changes of land use and cover, to name a few. These phenomena usually involve a large number of simulated actors (implemented as software agents) evolving in, and interacting with, an explicit spatial environment representation commonly called Virtual Geographic Environment (VGE). Since a geographic environment may be complex and large-scale, the creation of a VGE is difficult and needs large quantities of geometrical data originating from the environment characteristics (terrain elevation, location of objects and agents, etc.) as well as semantic information that qualifies space (building, road, park, etc.).

CurrentMAGS approaches usually consider the environment as a monolithic structure, which considerably reduces the capacity to handle largescale, real world geographic environments as well as agent's spatial reasoning capabilities. Moreover, the problem of path planning in MAGS involving complex and large-scale VGEs has to be solved in real time, often under constraints of limited memory and CPU resources. Available path planners provide agents with obstacle-free paths between two located positions in the VGE, but take into account neither the environment's characteristics (topologic and semantic) nor the agents' types and capabilities. In addition, agents evolving in a VGE lack for mechanisms and tools that allow them to acquire knowledge about their virtual environment in order to make informed decisions.

In this thesis, we propose a novel approach to automatically generate a semantically-enriched and geometrically-precise representation of the geographic environment that we call Informed Virtual Geographic Environment (IVGE). Our IVGE model efficiently organizes the geographic features, precisely captures the real world complexity, and reliably represents large-scale geographic environments. We also provide a new hierarchical path planning algorithm which leverages the enriched description of the IVGE in order to support agents' reasoning capabilities while optimising computation costs and taking into account both the virtual environment's characteristics and the agents' types and capabilities. Finally, we propos an environment knowledge management approach to support the agents' spatial decision making process while interacting with the IVGE.

About The Author

Dr. Mehdi Mekni received his B.Eng. (2000) degree from the department of information sciences at the University of Tunis (Tunisia), and his Ph.D. (2010) and M.Sc. (2006) degrees from the department of computer sciences at Laval University (Quebec City, Quebec, Canada). He is now a postdoctoral fellow at INRS (Institut national de la recherche scientifique). His main interests include multi-agent systems, agent-based geosimulation, and application of AI techniques on modeling and simulation of software agents.