Abstract

Graph theory has become a hot topic in the past two decades as evidenced by the increasing number of citations in research. Its applications are found in many fields, e.g. database, clustering, routing, etc. In this thesis, two novel graph-based algorithms are presented. The first algorithm finds itself in the thriving carsharing service, while the second algorithm is about large graph discovery to unearth the unknown graph before any analyses can be performed. In the first scenario, the automatisation of the fleet planning process in carsharing is proposed. The proposed work enhances the accuracy of the planning to the next level by taking an advantage of the open data movement such as street networks, building footprints, and demographic data. By using the street network (based on graph), it solves the questionable aspect in many previous works, feasibility as they tended to use rasterisation to simplify the map, but that comes with the price of accuracy and feasibility. A benchmark suite for further research in this problem is also provided. Along with it, two optimisation models with different sets of objectives and contexts are proposed. Through a series of experiment, a novel hybrid metaheuristic algorithm is proposed. The algorithm is called NGAP, which is based on Reference Point based Non-dominated Sorting genetic Algorithm (NSGA-III) and Pareto Local Search (PLS) and a novel problem specific local search operator designed for the fleet placement problem in carsharing called Extensible Neighbourhood Search (ENS). The designed local search operator exploits the graph structure of the street network and utilises the local knowledge to improve the exploration capability. The results show that the proposed hybrid algorithm outperforms the original NSGA-III in convergence under the same execution time. The work in smart mobility is done on city scale graphs which are considered to be medium size. However, the scale of the graphs in other fields in the real-world can be much larger than that which is why the large graph discovery algorithm is proposed as the second algorithm. To elaborate on the definition of large, some examples are required. The internet graph has over 30 billion nodes. Another one is a human brain network contains around 1011 nodes. Apart of the size, there is another aspect in real-world graph and that is the unknown. With the dynamic nature of the real-world graphs, it is almost impossible to have a complete knowledge of the graph to perform an analysis that is why graph traversal is crucial as the preparation process. I propose a novel memoryless chaos-based graph traversal algorithm called Chaotic Traversal (CHAT). CHAT is the first graph traversal algorithm that utilises the chaotic attractor directly. An experiment with two well-known chaotic attractors, Lozi map and Rössler system is conducted. The proposed algorithm is compared against the memoryless state-of-the-art algorithm, Random Walk. The results demonstrate the superior performance in coverage rate over Random Walk on five tested topologies; ring, small world, random, grid and power-law. In summary, the contribution of this research is twofold. Firstly, it contributes to the research society by introducing new study problems and novel approaches to propel the advance of the current state-of-the-art. And Secondly, it demonstrates a strong case for the conversion of research to the industrial sector to solve a real-world problem.

Abstract

In this paper we present a novel concept that deals specifically with changing driver behaviour in order to reduce traffic congestion. The project I-GEAR (incentives and gaming environments for automobile routing) aims to understand the motivations that drivers have while undertaking the daily commute and then to provide them with a range of incentives to change their behaviour. A key focus within the project is on ways in which the problem could potentially be solved without recourse to an expensive infrastructure project. Our solution to this problem was to move the problem of traffic management onto everyday mobile devices. In the following paper we outline the background to the problem, concepts relating to pervasive gaming, existing explorations of incentives and gaming approaches as well as our basic concept and project methodology.

Abstract

Over the last few years vehicular traffic density has continuously increased and it is likely that the traffic demand will further increase in the future. In many metropolitan areas the road infrastructure is no longer able to handle the peak traffic demand and the existing road network cannot be easily extended. The best way to improve the traffic situation is to optimise the resources available in the transportation network and to coordinate the traffic demand. The approach that we propose in this paper makes use of a collaborative traffic coordination protocol which collects real-time Floating Car Data (FCD) directly from participating vehicles and suggests dynamic routes in order to minimize travel delay. Information such as speed, position and direction is sent to one or more Traffic Coordination Points (TCPs) where it is aggregated to obtain a global picture of the traffic conditions in real-time. Based on this data, we continuously compute the route that minimizes the travel time to a given destination by applying Wardrop's first principle of equilibrium. Our results show that, by coordinating the vehicles, we are able to better distribute the overall traffic demand throughout the transportation network, reducing the average travel times and accommodating more vehicles.

Abstract

This paper proposes BODYFITR, a fully automatic method to fit a human body model to static 3D scans with complex poses. Automatic and reliable 3D human body fitting is necessary for many applications related to healthcare, digital ergonomics, avatar creation and security, especially in industrial contexts for large-scale product design. Existing works either make prior assumptions on the pose, require manual annotation of the data or have difficulty handling complex poses. This work addresses these limitations by providing a novel automatic fitting pipeline with carefully integrated building blocks designed for a systematic and robust approach. It is validated on the 3DBodyTex dataset, with hundreds of high-quality 3D body scans, and shown to outperform prior works in static body pose and shape estimation, qualitatively and quantitatively. The method is also applied to the creation of realistic 3D avatars from the high-quality texture scans of 3DBodyTex, further demonstrating its capabilities.

Abstract

In this paper, a dataset, named 3DBodyTex, of static 3D body scans with high-quality texture information is presented along with a fully automatic method for body model fitting to a 3D scan. 3D shape modelling is a fundamental area of computer vision that has a wide range of applications in the industry. It is becoming even more important as 3D sensing technologies are entering consumer devices such as smartphones. As the main output of these sensors is the 3D shape, many methods rely on this information alone. The 3D shape information is, however, very high dimensional and leads to models that must handle many degrees of freedom from limited information. Coupling texture and 3D shape alleviates this burden, as the texture of 3D objects is complementary to their shape. Unfortunately, high-quality texture content is lacking from commonly available datasets, and in particular in datasets of 3D body scans. The proposed 3DBodyTex dataset aims to fill this gap with hundreds of high-quality 3D body scans with high-resolution texture. Moreover, a novel fully automatic pipeline to fit a body model to a 3D scan is proposed. It includes a robust 3D landmark estimator that takes advantage of the high-resolution texture of 3DBodyTex. The pipeline is applied to the scans, and the results are reported and discussed, showcasing the diversity of the features in the dataset.

Abstract

Different research communities varying from telecommunication to traffic engineering are working on problems related to vehicular traffic congestion, intelligent transportation systems, and mobility patterns using information collected from a variety of sensors. To test the solutions, the first step is to use a vehicular traffic simulator with an appropriate scenario in order to reproduce realistic mobility patterns. Many mobility simulators are available, and the choice is usually done based on the size and type of simulation required, but a common problem is to find a realistic traffic scenario. In order to evaluate and compare new communication protocols for vehicular networks, it is necessary to use a wireless network simulator in combination with a vehicular traffic simulator. This additional step introduces further requirements for the scenario. The aim of this work is to provide a scenario able to meet all the common requirements in terms of size, realism and duration, in order to have a common basis for the evaluations. In the interest of building a realistic scenario, we decided to start from a real city with a standard topology common in mid-size European cities, and real information concerning traffic demands and mobility patterns. In this paper we show the process used to build the Luxembourg SUMO Traffic (LuST) Scenario, and present a summary of its characteristics together with an overview of its possible use cases.

Abstract

The Smart Cities Mission has been launched in India in 2015 to develop 100 cities, with smart mobility being one of the main topics in the mission. As urban areas are flooded with two (motorcycles) and three wheelers (auto-rickshaws), introducing smart control of such vehicles may reduce the congestions on the roads and the number of accidents. Indeed, over-speeding and drunken driving are common traffic violations. In this project we propose an IoT-based smart mobility system which tracks data, such as the vehicle location, vehicle speed, alcohol level of the driver, etc. efficiently over the internet. Our system has been conceived with CPAL, a high-level language meant to simulate and execute Cyber Physical Systems including IoT applications. A prototype running on ARM mbed IoT hardware, shows the feasibility of our concept. We believe that more efficient and interactive traffic management, more disciplined driving behaviors, reduction in accident rate, more controlled pollution, increased passenger safety can be achieved if systems like the one prototyped in this work deployed contributing to smarter cities.

Abstract

Recent years have seen a proliferation of complex Advanced Driver Assistance Systems (ADAS), in particular, for use in autonomous cars. These systems consist of sensors and cameras as well as image processing and decision support software components. They are meant to help drivers by providing proper warnings or by preventing dangerous situations. In this paper, we focus on the problem of design time testing of ADAS in a simulated environment. We provide a testing approach for ADAS by combining multi- objective search with surrogate models developed based on neural networks. We use multi-objective search to guide testing towards the most critical behaviors of ADAS. Surrogate modeling enables our testing approach to explore a larger part of the input search space within limited computational resources. We characterize the condition under which the multi-objective search algorithm behaves the same with and without surrogate modeling, thus showing the accuracy of our approach. We evaluate our approach by applying it to an industrial ADAS system. Our experiment shows that our approach automatically identifies test cases indicating critical ADAS behaviors. Further, we show that combining our search algorithm with surrogate modeling improves the quality of the generated test cases, especially under tight and realistic computational resources.

Abstract

There are many studies concerning the problem of traffic congestion in cities. One of the best accepted solutions to relieving congestion involves optimization of resources already available, by means of balancing traffic flows to minimize travel delays. To achieve this optimization, it is necessary to collect and process Floating Car Data (FCD) from vehicles. In this paper the authors evaluate the repercussions of partial information on the overall traffic view, and consequently on the outcome of the optimization. The authors study focuses on the role of the user participation rate and the availability of Road Side Units to collect the FCD. By means of simulation the authors quantify the impact of partially-available information on the computation of route optimization, and how it impedes traffic flows. The authors results show that even minor uncertainties can significantly impact routing strategies and lead to deterioration in the overall traffic situation.