Month: July 2012

Knowledge Unsupervised Search for populating
Concepts on Ontologies

KUSCO is a system which aims to assign semantic annotations to places. These annotations are automatically extracted by applying natural language processing and information extraction techniques that have been thoroughly applied and tested using the World Wide Web as primary source. This process is formally named Semantic Enrichment of Places. In our case, we are particularly focused on extracting information that allows an interpreter to distinguish a place from other places that are spatially or conceptually close. In other words, the meaning of a place is a function of its most salient features, present in the textual descriptions found in on-line resources about that place. In our case, places correspond to Points Of Interest (POIs), as these are abundant in the Web. By definition, a POI is a place with meaning to someone and, if it is available on-line, it is likely that its interest is shared by many people. In our approach, we first crawl the Web to get a large quantity of POIs and then analyze each of them in order to obtain their individual Semantic Index: the set of words that best define each of them. Besides analyzing POIs, we also propose the application of such approach in several different contexts and we integrate them in a multi-faceted view of place.

Understanding urban land use from digital footprints of crowds

The established view on semantic organization of space is based on the concept of “land use”, which corresponds to an aggregate perspective on the use of an area (e.g. agriculture, residential, business, etc.). The characterization of urban block is built on the human activities that happen there, however a more disaggregated and dynamic view is now possible due to availability of new techniques and technologies. In fact, this should become a more natural way to profile the places.

Understanding population dynamics by type, neighborhood, or region would enable customized services (and advertising), as well as the accurate timing of urban service provisions, such as scheduling transit service based on daily, weekly, or monthly mobility demand. In general, more synchronous management of service infrastructures clearly could play an important role in urban mobility management. Traditionally, urban planning relies on census survey conducted every 5-10 years and has shortcomings both in terms of spatial and temporal scale. The wide deployment of pervasive computing devices (cell phone, smart card, GPS devices and digital cameras) provide unprecedented digital footprints, telling where and when people are. In former projects, we developed a methodology for detecting the presence and movement of crowds through their digital traces (flickr photo, cell phone logs, smart card record and taxi/bus GPS traces).

This fine grained analysis, up to the level of the establishment, makes a big leap in terms of understanding the use of space for the purposes of urban planning and management. In recent work, we have presented several perspectives on extracting semantics of the place from online information. A further step shapes on the intersection of such generic information about space with other digital footprints, such as cell phone usage or taxi demand. An essential scientific contribution of this proposal will be on development of new techniques for land use analysis supported on semantic enriched POIs.

COllaborative System for Mobility Optimization

We are nowadays observing a rapidly growing availability of route planning devices, and it is expectable that they soon become an indispensable driving assistance technology (as happened with ABS, Airbags or ESP). On the other hand, the importance of congestion in cities throughout the world is rising for a number of reasons, especially those linked to carbon emissions and oil prices. A well known issue that consistently leads to congestions is the natural “selfishness” of each driver: each individual is following the “theoretically” fastest route. Even with the highly sophisticated support of systems such as “TomTom IQ routes”, every query for the same route from point A to B at the same time window will lead to the same result. The massive use of such a system will lead, inevitably, to congestion. Different from this extreme scenario, a more realistic expectation is that the majority of the users will only use their route planners when faced with novel origins-destinations. Since less information is used and the same path tends to be repeated, it will even worsen the situation. Thus, solutions need to be sought that compensate the effects of driver selfishness and lack of information.

In this project we propose to look at the city as a Complex System, where each citizen/driver is an agent with a local vision of the environment. The principle is to use heterogeneous information collected on city mobility (GSM, GPS, Road Sensors, Information Services, Historical data) to exercise influence on the individual agent behavior in order to optimize the city efficiency (e.g. energy consumption). This way, when reaching pre-congestion levels of network charge, individual drivers will be lead to collaborate in alternative, and minimally competing, routes. In this scenario, several research challenges are raised:

• How to predict distributed network load? In order to prevent the appearance of congestions, these situations have to be detected in early phase of their formation, and the individual behavior of the agents should be led to a synchronized collaborative behavior in a way that increases the whole system efficiency.

• How to fairly synchronize drivers? The system cannot favor one driver over the other more than within reasonable limits. Mutual dependencies will increase considerably the complexity of the choice.

• How to communicate with individual drivers? Will it be realistic to assume that high quality wireless access will be available in every vehicle? Or would the traditional Variable Message Signs become a proper option? If so, where should these signs be placed?

These challenges will be tackled from the perspective of Complex Systems, Ubiquitous Computing and Intelligent Transport Systems, which are three areas in which the research team already has or is acquiring strong knowledge.

The main purpose of this project is to study these issues and develop a collaborative traffic routing/control system. The system should use the collected information to predict realistic traffic network load and present advice to users, by providing individually tailored network loads, in order for them to have a less selfish behavior. The developed system is to be applied in a controlled micro simulation environment, which will allow the testing and validation of the various aspects of research, as well as the study the behavior of the system according to a number of dimensions, including driver adherence rate, link capacity, driver profiles and synchronism model. The project is divided into three main tasks (not performed necessarily in sequential order, and revisited when necessary):

• Realistic setting build-up: A traffic micro-simulation platform must be chosen (e.g. MITSIMLab, SUMO), as well as a number of network scenarios. Aside from the academic ones (e.g. grid, spider web), we expect to use the networks of Lisbon, Porto and Coimbra. Realistic Origin-Destination matrices are also needed from these cities, in order to obtain believable predictions.

• Algorithm design: Starting with traditional and state of the art solutions, the project team will seek for the best solutions both in terms of efficiency and in terms of precision. The long experience of the team in Vehicle Routing, Evolutionary Computation, Map Matching, Geo-referenced applications and Advanced Programming techniques will certainly be precious in this search.

• Experimentation and tuning: After functional testing of the system, and when it reveals robustness, the experimentation phase will take place focusing on comparing the simulation results with other approaches and with traditional models from Transport Demand Management theory, namely the four steps model of transport forecasting (see literature review).

The team will comprise two experts in Complex Systems with strong experience in Route Planning and Vehicle Routing Problem research (Francisco B. Pereira, ISEC; Jorge Tavares, MIT), one from Ambient Intelligence and Intelligent Transport Systems (Francisco C. Pereira, FCTUC) and one from Artificial Intelligence (F. Penousal Machado, FCTUC).