Abstract

In this thesis, the development of a novel compliant modular robot is proposed for deploy- ment in Urban Search And Rescue(USAR) scenarios. In the light of the recent natural disasters in India and Japan, there is a renewed interest in developing rough terrain robots that can aid in search and rescue efforts by navigating through the rubble to search for trapped victims and dispense basic first-aid. Specifically, USAR scenarios are very challenging for robots. Each disaster is unique and the terrain knowledge gained from one may not be useful in the other. Additionally, the obstacles are so varied in size, shape and rigidity that a single block mobile robot is often limited in its ability to traverse due to either its size or its limited internal freedom to naturally deform along the obstacles. Keeping this in view, we propose the use of a modular design. Each robot module consists of a link and a wheel pair, that are capable of traversing on their own. The wheels are powered to provide propulsion for the robot. The modules are combined to form a snake-like structure and a joint, called link joint, is created between every module pair to allow free rotation (pitch) in the sagittal plane. In the literature, these type of robots are called snake-like robots and more specifically Active Wheel-Passive Joint (AW-PJ) type of robots. These robots typically have a passive articulation mechanism due to the absence of motors at the link joints to control the internal configuration of the robot. While these robots have better ability to navigate through tight pockets, they are also limited in their ability to climb heights greater than one module length due to the problem of tip-over. The primary contribution of this thesis is to enable these robots to climb bigger obstacles and develop a methodology to estimate the number of modules required to climb any given height. Initial work focused on the development of a semi-active modular robot. The robot had five modules and it was minimally equipped with two motors, one each at the second and fourth link joints, respectively. The idea was to use the passive mechanism for climbing steps of smaller heights and motor only while climbing steps of bigger heights. A model-based controller was designed for the active link joints to achieve big-step climbing. The robot therefore had the ad- vantage of height-independent climbing motion as in the case of passive mechanism along with the extra freedom of active joints for maintaining vehicle stability, when necessary. Efficacy of the mechanism was exhibited through simulations on steps of various heights. However, it was realized that this approach was useful to climb heights only upto twice the individual module length. To climb bigger heights, the robot would need motors at all its link joints, leading to a more bulkier design. Generally, motors at the link joints are also susceptible to damage due to impact loads during traversal, making such designs less durable. In order to overcome this disadvantage, the use of compliant joints is proposed. Motors are no longer used at the link joints for posture control. Instead, springs are designed such that they are stiff enough to restrict modules from tipping over while offering sufficient compliance to maneuver on uneven terrains. Spring stiffness for such joints is estimated by formulating an optimization problem over the static equilibrium equations of the robot. The optimization ob- jective is to minimize all link joint moments at every instant of its climbing maneuver. This is one of the key novelties of the proposed work. A design methodology is also proposed for de- veloping an n-module compliant robot for climbing given height on a surface with prescribed coefficient of friction. The performance of the proposed formulation is illustrated for climbing big obstacles and traversing uneven terrains, using both numerical and experimental validation on 3- and 5-module robots. The robot is successfully able to climb maximum heights of 17 cm and 36 cm using 3 and 5 modules, respectively. As a secondary contribution, an optimal wheel-torque based controller is developed to min- imize wheel slip. This helps in reducing odometric error and maximizing energy efficiency. Wheel actuators are the only actively controllable elements of this robot, as the modules are connected using passive compliant joints. Wheel-slip offers a lot of hindrance while traversing on uneven terrains. Therefore, minimizing wheel-slip is crucial to augment its performance. Here, the optimization objective is to minimize the traction-to-normal force ratios at all the wheels. It is shown both numerically and experimentally that the proposed controller not only minimizes slip but also reduces the mean torque requirement for traversing on uneven terrains.

Abstract

Tweets are at most 140 character messages sent by millions of users and dissemination services to provide almost real-time state of affairs in the world starting from an individual level to the issues affecting the complete world. Tweets can be processed to determine events, trends, and to provide multiple services. In this thesis, we address the problem of determining the concepts covered in a tweet automatically, and do away with any manual inspection for various tweet mining tasks. Annotation of tweets with concepts can also be useful for different analyses on tweets at the semantic level such as event analysis, trend analysis etc. We present SCAT, a system which does not require any training data, to annotate tweets with concepts by utilizing the available context information along with the named entities present in it. We present the results of our solution by associating relevant Wikipedia articles and words from WordNet to a tweet. SCAT is able to expand the 140 character tweet with concepts from Wikipedia and WordNet for further semantic processing to state what the tweet is all about. We show that the concepts with which the tweets are annotated using SCAT is able to match the true concepts of the tweets most of the time.

Abstract

In places of reverence, wherein large crowds gather to have small duration of time for individual solace, there is a long queue of people waiting for their turn. A typical example of this scenario is a temple wherein each person visiting the temple, would want to spend a small amount of time to offer prayers in front of a deity. During auspicious occasions there will be hundreds of thousands or more anxious people queuing at the temple wanting to pray. Some other examples would be long shopping queues and queuing at ticketing counters for large crowd gathering events (like sports, music concerts). A crowd management force (that is police or security) at such events, are present to monitor the crowd and prevent any crowd disasters. Yet, there have been cases of stampedes with significant loss of life and trauma in such occasions because of lack of efficiency in the management of crowds. This presents us with a scenario where a multi-agent based system can be used to help improve the efficiency of crowd management at temples. In this thesis, we develop a multi-agent based system for simulating the scenario of crowding in long queues at temples. We focus on how introducing external agents in this scenario would help manage the crowd better. First, we introduce MAMAC (Multi-Agent MAnagement of Crowd), a set of robotic agents that can move at a height above the queue, (i) to provide direction and monitor the crowds, and (iii) to avoid occurrences of stampedes. We then focus on increasing the efficiency of the robotic agents. A method of movement has been developed that can be used by these robotic agents to ensure smooth flow of the crowd. Finally, we present a solution that uses only the required number of robotic agents that can manage the crowd to achieve a stampede free flow. We evaluate the efficiency of crowd management by conducting various experiments on the multi-agent simulation showing the results of robotic-agents avoiding the possibility of stampedes to occur.

Abstract

Online websites have become an important source of information. Most of the information pertaining to different fields of interest can be searched on the World Wide Web. Given the many number of websites relevant for a topic of interest, which one will be preferred by the user, is the question. Research has shown that the usability and the perception of credibility are key factors that make a website successful and influence the user's preference for choosing and using a website. Usability refers to how easy a website is to use. A website with a high degree of usability allows faster and easier navigation, while Credibility (or the perception of Credibility) refers to the degree to which a website could be believed upon. In this research we have focused on these two factors. The research problems addressed are i) How can the Credibility and Usability of website be assessed? ii) How could we automate the process of usability and credibility assessment, so as to benefit the user and/or designer? We started with a review of available usability testing methods and focused on the Cognitive Models (CoLiDeS - Comprehension-based Linked Model of Deliberate Search and its variants). These models use latent semantic analysis technique for finding the similarity between user goal and the website content. The Cognitive Walk-through for Web (CWW) method is a usability inspection method that allows objective evaluation of a website by predicting navigation patterns and finding problematic headings and links. We applied the CWW using CoLiDeS+Pic (Comprehension-based Linked Model of Deliberate Search with Pictures) and found the usability problems (ambiguous links) for a given website. The results can be validated using behavioral studies. The usability problems identified using the CWW simulation can be compared with the actual user navigation patterns observed. We illustrate an example pilot study for the same. Further we focused on the moment of processing of pictures on web pages using eye tracking taking the position of pictures and relevance to the website content into account. The motivation behind this study was that the cognitive model CoLiDeS+Pic used previously for usability inspection, assumes that pictures are processed during the Attention phase (which is the first processing phase). The results showed the assumption of CoLiDeS+Pic model holds true. It was also found that the relevance and the position of pictures on the webpage play an important role in how they are processed. Left side and highly relevant pictures are paid more attention by the user. Thus, the results of this experiment are helpful in making a website better, by having an adequate usage of pictures on the same. As more usable websites allow faster navigation, an automated navigation support tool was developed which is based on a combination of two cognitive models CoLiDeS+Pic (considers pictures) and CoLiDeS+ (considers structural dimensions). The tool is partially automated as the semantics of pictures have still to be obtained manually. An experiment was also conducted to measure the effectiveness of the tool. A significant difference was observed in terms of accuracy, (dis)orientation and time needed to perform the search tasks, between tool-supported and no-support groups in favor of the support tool. Apart from the usability of a website, credibility is also a pre-requisite for its success. So we further studied the user's perception and various factors influencing credibility, based on the previous research. An automated tool was developed to generate credibility scores for websites based on few factors: type of website, date of last updation, sentiments, web traffic data, reputation and review data. We evaluated the tool by relating the tool generated scores and ratings of human judges. A significant positive correlation was observed, which indicates that the tool is compatible with the credibility judgments of users. In the concluding remarks we discussed further improvements in this research area, which include complete automation of the navigation support tool, incorporating more credibility factors and user feedback through machine learning techniques to improve the performance of the credibility assessment tool.

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.