Abstract

In large urban cities, traffic congestion is a perennial problem for commuters traveling in vehicles because of the continuous flow of traffic. This continuous flow causes congestion at multiple places as many travelers travel on the same road segments at the same time. Though opting the shortest route may work when traffic is less, it can cause congestion when there are many vehicles along same route. There is high utilization of fewer number of roads along with longer travel times. This is the case when static shortest-path route planning algorithm is used by all travelers. Game theoretic approaches that distribute vehicles has high complexity when there are large number of choices (routes). We need a solution that is easy to implement and decentralized to achieve reduction in traffic congestion. Our solution has less complexity and can adapt to high volume of vehicles. The focus of this work is to enable the traveler to decide on either staying on existing route, or move to a different slightly longer route to reach the destination much sooner. In this work, we formulate the problem and design an algorithm for adaptive dynamic route planning (ADRP) to reduce the time taken by the traveler (by dynamically changing the route) and reach the destination sooner, based on the real time congestion information. We use a multi-agent based simulation where each vehicle is modeled as an autonomous agent. We experimented by simulating real world scenarios of large cities with thousands of interconnected road segments and one million vehicles to study our strategy. With the use of modern technologies of GPS and by probing smartphone users we can capture the real-time traffic information on the road-segments for our algorithm to dynamically compute the shortest time-taking route. Our simulation results on different maps show that by considering the current congestion on roads, the ADRP algorithm determines routes wherein with a small increase in distance travelled, the time taken to reach the destination is significantly reduced and there is significant increase in utilization of larger number of roads. This way rather than concentrating the whole traffic on highly used main roads (which cause congestion), we distribute the traffic across the entire city so that the average time-taken by the vehicles will be reduced significantly and situations of traffic jams or congestion will be minimized, thereby leading to a better traffic management system.

Abstract

The problem of exploration is a well studied problem in field of robotics. The objective of an exploration mission is to gather relevant information about an unknown environment. Exploration finds immense application in useful real world problems like reconnaissance, search and rescue missions. In this work the problem of exploration is studied for multiple agents/robots. Throughout the thesis, term agent" and obot" is used synonymously. A multi robot system offers some relevant advantages over a single robot system like reduction in overall mission time but in turn it requires coordination overhead. In absence of coordination a multi robot system breaks down into multiple single robot systems and most of the advantages disappear. For instance, due to lack of coordination, a part of environment could be explored multiple times by different robots, causing wastage of resources. Various challenges associated with a multi robot exploration are collision free path planning, coordinated localization or mapping, devising an exploration strategy and few others. This work focusses on exploration strategy, i.e a strategy for assigning goal positions to various robots. This problem is multi agent system(MAS) community is commonly known as problem of Task Allocation. A task allocation problem is generally tackled by quantifying tasks i.e determining cost of performing each task. Then accordingly a task of minimum or maximum of cost is chosen. In case of a single robot system, solving this problem is trivial. A simple solution will be to iterate over all tasks and choose the one which maximizes the utility or minimizes the cost, provided number of tasks remain nite. But in the case of a multi agent system, different combinations of allotment are to be considered and with the increase in number of robots or tasks, the size of problem explodes and iterating over every possible case/combination is not feasible. Apart from considering costs, various other factors have to be considered. For instance, continuous communication between agents cannot be assumed all the time. Since, to inculcate coordination, robots need to exchange information among themselves, communication becomes an integral entity in any MAS and a communication constraint has to considered. Besides this, other characteristics like, whether system should be centralized or distributed has to be addressed. The above mentioned constraints are generic to any MAS. In our exploration system, we have introduced other constraints, for instance, allotted goal positions should not be close to each other. This helps in overcoming the problem of information overlap due to large sensor footprint and also spreads the robot far from each other and thus, fully utilizing the advantages of a multi robot system. In this work we propose an Integer Programming(IP) based solution to aforementioned problem . Since the solution requires decision of each robot going to a particular goal or not, the problem of task allocation in our case is formulated as a 0-1 IP problem. We use IP to solve multi robot exploration problem for heterogeneous system of agents. By heterogeneous we mean agents of different sensor and motion capabilities and in our case, we use multiple pairs of Unmanned Ground Vehicles(UGV) and Micro Aerial Vehicles(MAV). These two types of robots compliment each other and overcome each other's shortcomings. The heterogeneous structure allowed us to build 2D augmented maps of the unknown area. We also discuss the necessity of Distribution in a Multi Agent System. The problem of task allocation for ground robots is formulated as a Distributed Constraint Optimization Problem(DCOP). Each agent is responsible of for its own allocation and by exchanging messages according to the rules specified by Max Sum algorithm, a solution which is globally optimal is achieved. The main contribution of this work is to show how different optimization techniques can be utilized efficiently for problem task allocation in a multi robot setting. We show how IP formulation provides a framework for adding multiple necessary constraints in an elegant manner and provides a one shot solution for the problem. We also focus on a Distributed framework. We propose a Distributed and Asynchronous exploration system and show how these characteristics are indeed necessary in a Multi agent setting.

Abstract

This thesis deals with design and development of speech databases for text-to-speech (TTS) in Indian languages, and issues involved in multi-lingual and cross-lingual synthesis. An important issue has been addressed in this thesis is, pronunciation of non-native text (foreign word). In this work, different mapping methods such as phone-phone (P-P) and word-phone (W-P) has been experimented with to incorporate (non-native) foreign word pronunciation in Indian language TTS systems. In P-P mapping, the phones of foreign language are substituted with phones of native language. The results showed that the quality of synthesized output is poor as it contained foreign language accent. This motivates us to use a technique to provide the nativization for foreign word. To achieve this, we used W-P mapping approach. In W-P mapping, non-native word is mapped to a sequence of phones to produce in the form of native speaker pronunciation. Subjective evaluations are conducted and results show that the native speakers prefer the quality of synthesized output. The idea of manual W-P mechanism is a tedious task and it is very difficult to include all the English words in a single lexicon. Here we automatically generate letter-to-sound rules for foreign word. As Indian languages share a common phonetic base, the pronunciation of phones across the languages are similar. The question we would like to ask in this work is, whether a single TTS system is sufficient for multiple language inputs using Indian languages. In cross-lingual synthesis, text of one language is synthesized using a TTS system built for another language. Here the phones of one language is mapped to the phones of another/neighbouring language. Subjective evaluations are conducted with this technique. The results show that the native speakers do not prefer cross-lingual synthesis as durational properties of vowels and geminates, vary across the languages. The usefulness of W-P mapping and study on cross-lingual synthesis with supportive analysis and results are presented in this thesis. The contributions of this work are: (1) Experiment and evidence that appropriate phone mapping could not be used for multi-lingual TTS system. (2) Use of W-P mapping for building multi-lingual TTS system for Indian languages. (3) Study on cross-lingual synthesis using Indian languages.

Abstract

Cloud computing has allowed the consumption of services over internet with subscription based model. Based on the level of abstraction of services, there are different models of cloud computing like Infrastructure-as-a-Service (IaaS), Platform-as-a-Service (PaaS) and Software-as-a-Service (SaaS). This model of service consumption is extremely suitable for many workloads and cloud computing has become phenomenally successful technology. Cloud computing allows users to remove the upfront infrastructure cost and pay-for- what - they-use. Cloud providers multiplexes resource requests from multiple users through use of virtualization. It becomes essential for cloud service providers to operate very efficiently in multiplexing at the scale to remain profitable. The growth of cloud computing has lead to massive data centers with millions of servers. The resource management at this scale is pressing issue. Scheduling is responsible for arbitrating resources and is at the heart of resource management. The issue of efficiency at this scale and emerging model of consumption of cloud services require new approaches and techniques to be applied to the age old problem of scheduling. Virtual machine is the basic unit of scheduling in data centers. In this thesis, we deal with problem of virtual machine scheduling over physical machines. We aim to understand and solve the various aspect of scheduling in cloud environments. Specifically, we leverage various fine grained monitoring information in making better scheduling decisions. We used learning based approach of scheduling in widely different environments. There is increasing concern over energy consumption by cloud data centers and cloud operators are focusing on energy savings through effective utilization of resources. At the same time, maintaining SLAs is also very important for them for the performance of applications running. We propose algorithms which try to minimize the energy consumption in the data center duly maintaining the SLA guarantees. The algorithms try to utilize least number of physical machines in the data center by dynamically rebalancing the physical machines based on their resource utilization. The algorithms also perform an optimal consolidation of virtual machines on a physical machine, minimizing SLA violations. In large virtual data centers, performance of applications is highly dependent on the communication bandwidth available among virtual machines. Traditional scheduling algorithms either are not networkaware or are not practical for large data centers. We address the problem of identifying the virtual machine clusters based on the network traffic and intelligently placing them to improve the application performance and optimize the network usage in large data center. We describe a greedy consolidation algorithm to ensure that the number of migrations are small and the placement decisions even for large data centers. We observed significant improvements in the applications performances and reduced number of migrations on real world data center traces. The wide spread use of mobile devices and cloud services has led to the growth of mobile cloud. Even tough mobile devices are becoming increasingly more powerful, the resource utilization of rich mobile applications can overwhelm resources on these small and battery constrained devices. In this context, ubiquitous connectivity of mobile devices also opens up the possibility of leveraging cloud resources. Automatically running mobile application on cloud instead of mobile device can greatly aid to battery life of the device. We describe a cloud aware scheduler for application offloading from mobile devices to clouds. We used learning based algorithm for predicting the gain attainable using performance monitoring and high level features. We evaluated prototype of our system on various workloads and under various conditions. Big data processing is one of the most popular use case of cloud. Also, the need for multi-cloud frameworks is growing as cloud computing is maturing and organizations are leveraging cloud services from on-premise private cloud as well as from number of cloud providers. We developed a big data multi cloud framework called MultiStack, which supports multiple data processing frameworks running across multiple clouds. We describe architecture and implementation of MultiStack. We also describe how it can support various scheduling policies including quota-based, locality-based, deadline-aware and cost based scheduling. Broadly we focused on using information/data from systems and use learning based approaches to optimize the system performance through better scheduling. We studied scheduling problem in the following settings. Energy Efficiency without compromising SLAs Network awareness Extremely heterogenous resource capabilities between mobile device and cloud Multi-cloud BigData processing

Abstract

Monitoring of the Earth System and its various constituents using both satellite and airborne Remote Sensing techniques is becoming quite widespread, but at the same time posing enormous challenges in managing the acquired data and processing it suitably to derive meaningful products and outcomes that can be used by different research disciplines that study the various components of the earth system. Earth Observation Systems (EOS) provide data at multiple resolutions which has been widely used in studies of environmental changes, natural resource management, and ecosystem and landscape analysis in general. With the development of new remote sensing system, very-high spatial resolution images provide a set of continuous samples of the earth surface from local, to regional scales. The spatial resolution of various satellite sensors ranges from 0.5 meters to 25,000 meters now. The development of efficient analysis methods of using these multi-scale datasets to improve land use/cover mapping, classification accuracies at the local class level and linking coarser and finer resolution datasets to get a complete understanding about the spectral unmixing processes has been the main theme of this thesis work. Image Classification is one of the most widely used approaches in deriving relevant information from remote sensing data by categorizing, either manually or automatically, all the image pixels into the appropriate classes or themes. Over the last four decades, a large number of classification techniques have evolved based on the spectral, spatial and temporal information associated with the satellite image data. While the spectral pattern recognition utilizes the pixel-by-pixel spectral/reflectance information, the spatial pattern recognition involves categorization of image pixels on the basis of their relationship with pixels in the neighborhood, and the temporal pattern recognition uses the change in time as an aid in the feature identification. Each of these approaches provide a certain set of information but are still inadequate in understanding the entire gamut of land cover, its changes and the processes that drive these changes. In the studies focusing on the land cover and land usage change analysis, the availability of very high resolution (VHR)/high resolution (HR) imagery for a particular period and interest region is always a challenge due to sensor revisit time and the high cost of acquisition and therefore, this research work was focused on increasing the utility of the cost and computationally advantageous frequently available lower resolution (LR) imagery. The statistical techniques developed during this research exploit the spectral and spatial information associated with the available multi-resolution satellite datasets and mainly focus on the sub-classification of the datasets at a specific resolution (preferably LR), to obtain sub-regions of high importance within the classified regions, which were validated using the datasets available at a different (preferably HR) spatial resolution.The widespread classification techniques provide us a global estimate of the class accuracies, which limits its utility (in a range of applications) and also limits the identification of sub-class regions which may have higher accuracy than the global class accuracies. In this research work, we initially focused on establishing a relationship between the multi-resolution datasets, with the aim of using them later for carrying out the experiments as well as their validation. The literature in the field of remote sensing has concepts related to pure pixel and mixed pixel regions, although for better understanding we also introduced an idea about the impure pixel regions. With regards to the pixel-classification problem in this thesis work, the classified pure pixel regions have similar ground truth class values as the classified outputs, classified mixed pixel regions match one of the ground truth class values in the obtained classified output and the classified impure pixel regions match none of the ground truth classes in the obtained classified output. Further, we establish the meaning of pure, mixed and impure pixel regions with regards to multi-resolution datasets and also introduce concepts like Near Pure Pixels (NPPs) and Near Purity Measure (NPM) for better understanding of the research areas tackled during the thesis work. We also proposed a Spatio-Spectral Unmixing framework, which reduced the number of approximations to the Linear Spectral Mixing model in Remote Sensing and helped in better analysis and visualization of mixed pixel regions, owing to improved classification accuracies. The results for the proposed methodologies have been shown as a proof of concept, and therefore datasets have been classified into fewer but higher importance class regions. The experiments conducted can be carried out on any available multi-resolution datasets, where the

Abstract

Several attempts have been made in the past for the creation of a comprehensive and structured ontology to enable better and efficient semantic analysis for web related common sense reasoning tasks such as Question Answering, Summarization, Word Sense Disambiguation, Analogy making, Classification, and so on. But, these approaches lack in a strong design paradigm for representation of facts about objects in general and artifacts in specific. Also, whereas the human cognition is ‘purpose’-based, none of the KBs (knowledgebases) built so far have taken the ‘purpose’ perspective into account. To address these lacunae in existing KBs, PurposeNet – a comprehensive KB that addresses all possible information requirements about artifacts with ‘purpose’ as the underlying principle for the design has been engineered. Artifacts have been described as being constituted of relationships and features. The features have been further designated as either a set of descriptions of the various morphological and anatomical characteristics of the artifact, or a set of actions that the artifact participates in during the course of its manufacture, use, and final disposal. Each of these actions has been described using a common generic frame, which is the special feature of our KB. The design is compact, with several directly and indirectly recursive relations among its constituents, which is the basis for networking in the ontology. Generality has been preserved in the design by way of class hierarchy implementing inheritance, and the design of an independent set of generic action frames for artifact-dependent as well as artifact-independent query processing. The design has been implemented on the transport domain using Web Ontology Language. A set of 10,00,000 assertions have been created using the ontology. All issues at development and implementation stages have been discussed. The ontology design has been validated, and the implemented ontology has been evaluated. This work also addresses the issue of detection and extraction methodologies for the relations prescribed in the artifact design. One relation of the artifact – namely, its ‘purpose’ has been taken as an example case for which various machine learning and pattern-matching methodologies described have been applied for detection with encouraging results. Relation extraction has also been implemented using two proven methods – typed dependency parse and surface pattern extraction. The comparative performance of these two methods has been evaluated for the extraction of the ‘purpose’ relation. Finally, this work presents some applications that showcase the usage of PurposeNet - i.e., a QA system, an enhanced expert system, an online web help, and the improvement of comprehension of passages by aiding existing Scripts. Each one of these demonstrates the usefulness of the PurposeNet KB.

Abstract

After a stall in improvement of clock speeds, High Performance Computing(HPC) community is looking for general purpose computing on graphics processing units(GPGPU). Due to their low cost, high performance per watt and evolving programming models they are becoming very popular not only among HPC community, but also for getting good performance on commodity devices like laptops and mobile phones. Unlike the traditional graphics rendering cards, now a days manufacturers are providing many other architectural features like cache and shared memory which make them promising for general purpose computing. A wide range of applications in the scientific and financial domains, benefit from the merits of the GPU architecture. GPUs offer an alternative machine architecture in three ways. GPUs provide, firstly, lots of cycles for independent parallelism, secondly, fast memory access under the right circumstances, and finally, fast mathematical computation at relatively low costs. Because of this different architecture there is a need to reinterpret the applications in a highly threaded manner. This architecture is a good fit for applications which have regular memory access patterns like dense matrix multiplication. But for non regular applications like list ranking, graph algorithms, sparse matrix calculations. Exploring such applications and accelerating them using GPUs is the need of the hour. Also most applications accelerated by GPU tends to use only GPU in computation. CPU’s role limits to just passing the code and data to GPU for computations and accumulating the results back. When GPU is busy executing given code, CPU stays idle. Hence CPU resources are not utilized properly. By carefully designing our applications we can get a significant speedup over the GPU-only implementation. To use both CPUs and GPUs in computation, tasks and data has to be divided efficiently. This partitioning of data is mostly dependent on the underlying CPU and GPU platform specifications. This is also referred to as static load balancing. Static load balancing through empirical or analytical methods have many drawbacks. While analytical methods are not available for most of the applications, empirical methods outputs the partition which is specific to the platform and hence making application hard to port efficiently. In this thesis we explore Aggregate risk analysis which is a stochastic simulation technique for portfolio risk analysis and pricing process using multi-core CPUs and many-core GPUs. Firstly, a sequential aggregate risk analysis algorithm is implemented in C on a CPU, followed by parallel implementations using C and OpenMP on multi-core CPU and using C and CUDA on many-core GPU platforms. Aggregate risk analysis is a form of Monte Carlo simulation performed on a portfolio of risks that a re-insurer holds rather than on individual risks. This involves a high number of simulations with lookups from real world database. These lookups are highly irregular and hence slow down the entire computation. Also there are huge data structures which need to be handled very carefully. Storing them in dense format is quite slow, and sparse formats which are easy to lookup take too much space in memory. We design a hybrid implementation which uses both CPU resource and GPU resource in computation and hence more efficient. The implementation is based on work sharing. We validate our results by comparing them to GPU-only implementations on two different CPU-GPU combinations. The work partition is computed empirically and experimentally for getting maximum efficiency. This partition is platform dependent making the application less portable. To address this challenge we propose an alternate automated hybrid solution, which works well for all CPU-GPU combinations and hence platform independent. This solution adds more portability to the application. We analyzed this automated solution and found it very close to the non-portable hybrid implementation.

Abstract

Measuring inter-document similarity is one of the most essential steps in text document clustering. Most of the document clustering methods rely on the Bag-of-Words (BOW) model for representing the text documents. The BOW model assumes that the terms of a text document are independent of each other. We attempt to explain and address two of the major drawbacks of such single term analysis of the text. First, it completely ignores the underlying (semantic) structure of a document. In the literature, sufficient efforts have been made to enrich BOW representation using phrases and n-grams like bigrams and tri-grams. These approaches take into account dependencies between adjacent terms or a continuous sequence of terms only. However, while some of the dependencies exist between adjacent words, others are more distant. We make an effort to enrich traditional document vector by adding the notion of term-pair features. A Term-Pair feature is a pair of two terms of the same document such that they may be adjacent to each other or distant. We investigate the process of term-pair selection and propose a methodology to select potential term-pairs from the given document. Utilizing term proximity between distant terms also allows some flexibility for two documents to be similar if they are about similar topics but with varied writing styles. Second major drawback of single term analysis of text is that it treats whole document as a single semantic unit and thus, ignores other semantic units like sentences, passages etc. A document is inherently an organized structure consisting of various text segments or passages. We attempt to take advantage of this underlying subtopic structure of text documents and investigate whether clustering of text documents can be improved if text segments of two documents are utilized while calculating similarity between them. We concentrate on examining effects of combining suggested inter-document similarities (based on inter-passage similarities) with traditional inter-document similarities following a simple approach for the same. Experimental results on standard data sets suggest improvement in clustering of text documents for both of the above mentioned approaches.

Abstract

Topic detection in a text corpus is the detection of semantic units from the underlying texts that can function as building blocks of knowledge discovery. Topic detection provides a powerful tool for text summarization and information navigation across a corpus of documents. Topic detection from text documents using statistical models and natural language processing techniques has been extensively studied by the researchers. In the recent years, it has drawn considerable research interest in the field of data mining too. The problem is also interesting and challenging in the domain of academia, considering the ever growing size of academic literature and the fast changing fields of research, which requires the algorithms to be fast and highly scalable in order to efficiently mine research topics and their features over the time-line. In this thesis, we model the topic detection problem through the paradigm of data mining by proposing a closed frequent keyword-set based approach to form topics from a large corpus of research papers. The topics as detected by our algorithm preserves the semantics present in the documents and we experimentally show that our algorithm is fast and effective than the state of art frequent item-set mining algorithms. Our approach also studies the closely linked problem of document clustering by providing a topic-based clustering technique for the research papers by using the detected topics as similarity measure to form hierarchical, overlapping clusters. Our next contribution is to develop an approach to rank the topics on the basis of their importance. The current set of algorithms mostly focus on the detection of topics, and not much effort has been put to order the topics based on their importance in the research community. For a researcher, it becomes a very cumbersome task to go through the entire list of topics and decide upon which topics are the prominent ones. The bibliographic datasets belong to the hyperlinked set of documents, which are connected to each other through citation links. The citation links contain important information in the form of peer votes in the research community, which interestingly has not been utilized by existing models for topic ranking. The current approaches primarily model the popularity index of the topics by considering the frequency of the documents belonging to the topic for ranking them, rather than their importance factor which is better modeled by the peer votes in the community. In this thesis, we propose a time independent modified PageRank algorithm that assigns an authoritative score to each topic by considering the citation links of the sub-graph of the topics, producing a ranked list of topics. We also address the problem of time bias in the hyperlinked environments incurred in calculating the authoritative scores of the topics. It is observed that the newer papers do not get sufficient time to be cited compared to the older papers and thus fall behind in the ranking even if they are important. The use of citation network and the introduction of time invariance in our topic ranking algorithm reveal interesting patterns.

Abstract

We propose a supervised learning technique for associative regression. Assuming frequent patterns quantify correlations in dataset, we constrain the Iterative Scaling (IS) convergence algorithm for Max- imum Entropy (ME) models. We also assume prior probabilities on the ME model as a control on the step size in convergence iteration. We have used the combinations of ME parameters and IS probabilities as discriminative weights to frequent patterns. The weighted frequent patterns then predict the associative regression rules. To find the regression error of our proposal, experiments are conducted on sparse numeric datasets. Our technique is comparable to the standard regression algorithms. We demonstrate the feature extraction and convergence criterion in experiments. Results suggest that con- densed representations of frequent patterns allow parametric models suitable for class association rule mining. Intutively, our idea of information is derived from an objective function expressing number of bits needed to represent data by frequent patterns. Conceptually, our model represents information regarding functional dependencies in a database as weights derived from a binary/fuzzy relation. The elements of the binary/fuzzy relation are indicator functions of an incidence matrix about conditional /joint probability distributions where dataset is taken to be a inmemory contingency table. Our technique has application in incremental semisupervised learning algorithms requiring discriminatory information from clustering, classification and association rule mining.