Abstract

Autonomous driving is a long-standing problem in robotics, interest in which has spiked in recent years due to the series of DARPA Grand Challenges. One of the basic components in the operation of such autonomous vehicles is the capability to autonomously navigate in terrains particularly in ex- ploratory applications, the robots must deal with terrains whose models at best are only partially-known. On-road navigation is a crucial component of autonomous navigation outdoors and presents interesting challenges, the prominent among those being the ability to discern the traversability of a terrain patch. Modified cars became the new platform in robotics for outdoor navigation which has the possibility to travel longer distances, carry more sensors and thus being more suitable for mapping larger areas. This offers the opportunity to address robotic tasks on a larger scale but on the other hand requires efficient solutions to common problems like mapping or localization. The objective of the work is to develop. simulate and test a terrain modelling system based on laser range data for slow moving vehicles. The terrain modelling system will enable the unmanned ground vehicle to identify the next best way-point to reach. More formally, given a laser range finder fitted on a vehicle moving largely on flat terrain and a pose measurement system that is accurate enough up to a bounded error, develop a terrain modelling system based on laser range data for the vehicle. Robot must possess that enable it to perceive the outside world. We have used three sensors namely GPS, IMU and LIDAR for estimating pose of the vehicle, its orientation and the range measurements respectively. All these devices are mounted on top of a vehicle to acquire data from the sensors. After processing and applying transformations over the data, we will get the map representation in the form of point cloud. Two algorithms for terrain classification for a single tilted laser are developed and extensively tested. One algorithm is plane extraction which will represent the local terrain of the vehicle in terms of planes and points to discern the traversable region. Efficient detection and plane parametrization from scan-line data obtained incrementally to discern the navigable and non-navigable regions confirms the efficacy of the proposed method. However, plane detection is less convincing when dealing with certain structures that arise in natural environments like poles etc. Another algorithm is Spatio-temporal classification which is not too constrained by the nature of the structure of the environment. The essential assumption is that corresponding laser readings in two successive scans are correlated and in general see neighbouring areas. An obstacle or non-navigable region is detected when the sequence indicates decreasing laser distances with corresponding increase in height.This method needs extra rules like searching neighbourhood, relative thresholding to classify obstacles that are not in the frontal viewing cone of the laser. The map obtained is too sparse as we have used a single LIDAR. So, the techniques we have used were not able to overcome few sensor noises. Also, AHRS was giving angle errors while the vehicle pitches and rolls over bumps. This work has lot of future scope by deploying state of the art sensors and multiple laser scanners.

Abstract

In web search, understanding the intent behind a user query can help in tasks such as placing of ads relevant to the query, routing the query to an appropriate vertical search to enrich web search results and building a user profile for personalization. Such an intent could be represented by categories of the information a user is looking for, often expressed through a short query. Here, we consider the categorical representation of the intent. That is, the intent behind the query is represented as a set of pre-defined categories. In this work, we address query categorization, which involves classifying a given query into one or more pre-defined categories. Such a categorization gives web search engines a means of quantizing the user’s information need as expressed through a query. As an example, consider the query “serena williams”. This query belongs to “sports” category, or more specifically “sports/tennis”. Such an understanding of the query can have many applications as far as web search engines are concerned. First, knowing the categories of a query can help in determining the sources of evidence for vertical selection by web search engines. Advertisements relevant to the user query can be placed on the search results page, thus enriching the users search experience. Other areas which can benefit from query categorization include personalization—for building user profiles to personalize the search results, analysis of user behavior over time, among many others. We propose an information retrieval based approach similar to document retrieval to solve query categorization. To carry out categorization, we first represent a category by a set of web documents (from Open Directory Project) that best describes the semantics of the category. This results in a corpus where each document is categorized. For a given query, we do a simple “idf” based query expansion and we retrieve and rank the categories just as in document retrieval, effectively resulting in query categorization. These categories may have to be mapped to the categories of the application under consideration. Unlike previous works, the simplicity and the unsupervised nature of this proposed approach makes it practical in a web search scenario, while achieving performance comparable with other systems, when evaluated on KDD Cup 2005 data set. Further, we investigate if we can learn the category rankings for the queries by applying “learning to rank” techniques. We show improvements on two datasets: a popular search engine’s dataset of 7K classified queries and publicly available KDD Cup dataset. Our experiments suggest that learning to rank could be a key in improving precision of query categorization systems for applications such as federated search where precision is important.

Abstract

The main goal of data visualization is to communicate information clearly and effectively through images. Data visualization can help user to: understand the output better, compare alternative results, and evaluate the results. Importance of data visualization, in the process of knowledge discovery, is accepted and acknowledged. Heidi is a high dimensional data visualization system that captures and visualizes the closeness of points across various subspaces of the dimensions; thus, helping the users to understand the distribution of data in different subspaces. Heidi has certain issues: (i) can not handle large data sets, (ii) Heidi images use too many colors, and (iii) restricted to displaying clustering results. In this thesis, we propose techniques to address the issues: (i) scaling up Heidi visualization for large number of dimensions and large number of points, (ii) Heidi images use too many colors, which are reduced by highlighting only prominent colors, and (iii) customizing Heidi to display other hierarchical multi dimensional structure like R-Tree index structures and subspace clusters. Heidi is enhanced in terms of memory and efficiency through an implementation over the MapReduce framework. Through our empirical study, we demonstrate that Heidi++ (our new system) achieves virtually linear speedup. For very large data sets, a new representative Heidi visualization is proposed which is more scalable and efficient. High dimensional index structures are used to efficiently answer range queries in large databases. Visualization of such index structures helps in: (i) visualization of the data set in a structured format of the index structure, (ii) “explorative querying” on the data set, (iii) index structure diagnostics: visualizing the structure along with its performance statistics enables the user to determine values of parameters for index structure for better performance. Heidi++ could be extended for various other applications of presenting interesting visualizations about multi-dimensional index structures. In this thesis, we demonstrate the use of Heidi++ Visualization over the R-Tree and R*-Tree.

Abstract

Designing Radio Frequency Identification (RFID) tag antenna for metallic objects is a challenging task. The reason is that the antenna parameters like gain and radiation pattern are highly affected by metallic surface. This thesis presents two different designs of miniature RFID tag antenna for metallic objects. They can be used for different tag Integrated Circuits (ICs) having different input impedances simply by varying slot length and keeping other dimensions intact. The proposed antennas are designed specifically to eliminate interference effect caused due to metallic objects. By eliminating this limitation the tag proves to be a uniquely good solution that enables the use of UHF RFID efficiently for metallic applications like aerospace or automobile industry. In this thesis firstly a slotted RFID tag antenna is designed whose size is 33 mm x 16 mm x 3.2 mm, and secondly a modified slotted RFID tag antenna is designed whose size is 64 mm x 24 mm x 1.6 mm. The proposed slotted RFID tag antenna design contains three metallic layers. Top layer consists of two metallic rectangular patches which are electrically connected to the ground plane through copper vias. Multiple slots are created on metallic patches and a non-connected metallic plate is placed between the ground and the patches. The antenna design is simulated, fabricated and its performance is analyzed in an Anechonic Chamber. The read range of the proposed slotted RFID tag antenna for a slot length of 7 mm, mounted on the metallic surface is approximately 80 cm when. Next we presented a modified slotted RFID tag antenna with lower antenna thickness. This design contains two metallic layers. Top layer consists of two coplanar metallic patches with two slots on each patches and bottom layer is a ground layer. In this design copper vias are placed at extreme end corners of the patches. Experimental results show that the same antenna can be used for metallic as well as for non-metallic cases because the read range of the proposed design is 1.7 m when the tag is mounted on a metallic sheet and 1.1 m without any metal sheet. In this work we also proposed a mathematical model for slotted as well as for non-slotted RFID tag antenna to enhance the computation speed of antenna design. RLC circuit model proposed in this thesis can be used to develop slotted as well as for unslotted RFID tag antenna for various frequencies and for different tag ICs having different input impedances. This work is expected to contribute to improvement in antenna design automation.

Abstract

Pounding between adjacent structures is commonly observed phenomenon during major earthquakes which may cause both architectural and structural damages. To satisfy the functional requirements, the adjacent buildings are constructed with equal and unequal heights, which may cause great damage to structures during earthquakes. To mitigate the amount of damage from pounding, the most simplest and effective way is to provide minimum separation distance. Generally most of the existing buildings in seismically moderate regions are built without codal provisions. Past earthquakes have shown an evidence that the buildings are more vulnerable to pounding. Building codes provide a set of guidelines for the practice of structural engineering and play an important role of transferring technology from research to practice. In numerical modeling, different combination of structures are considered for doing the analysis using Applied Element Method (AEM). The separation distance between the structures is provided according to various codes from different countries and are subjected to ten different ground motions. Some codal provisions failed to satisfy the requirements. The shortcomings in codal provisions are identified and provided with proper suggestions to them

Abstract

We consider a distributed setting where a subset of nodes are under the control of a malicious ad- versary with unbounded computational powers. The problem of simulating a directed reliable channel from a sender S to a receiver R in the absence of a true physical point to point channel is fundamental to the area of Distributed Computing and is popularly known as ”Unconditionally Reliable Message Transmission” (URMT). Analogous to randomized sequential algorithms, we distinguish between two variants of reliability: while the weaker variant allows R to output an incorrect message with small probability (Monte Carlo), the stronger variant allows the protocol to only abort with a small probability but never output an incor- rect message (Las Vegas). We consider these variants in two popular timing models: synchronous and asynchronous. The former has a fixed upper bound on the amount of time it takes to transmit a message over any physical channel of the network whereas the latter doesn’t have any such upper bound. We focus on the possibility of Las Vegas and Monte Carlo protocols by modeling the network as a synchronous or asynchronous directed graph. Unlike the approach taken in literature where a digraph is abstracted as a collection of disjoint wires and the nodes along the wires are mere routers, we consider digraphs in their entirety – every node can potentially do arbitrary computations on the messages i.e. every node is as powerful as a Turing Machine. In this work, we establish a novel hierarchy with respect to the minimum connectivity requirements for the existence of synchronous Las Vegas, asynchronous Monte Carlo and asynchronous Las Vegas protocols for URMT. We show that, with respect to URMT, the (minimum) connectivity requirements for the existence of synchronous Las Vegas protocols are the same as those for asynchronous Monte Carlo protocols i.e. one is possible if and only the other is possible – a pleasantly surprising equivalence between two very different models. Furthermore, the connectivity requirements for asynchronous Las Vegas URMT (which are strictly higher than those for Monte Carlo URMT) are the same as those required for perfect protocols over synchronous networks! While it is well-known that, in synchronous networks, the minimum connectivity requirements for Monte Carlo URMT protocols to exist is strictly less than those where for perfect protocols, we establish the fact that the connectivity requirements for the case of Las Vegas URMT are strictly more than that of Monte Carlo URMT. We further improve our insight (into URMT) by studying how sparse a digraph that permits URMT can be. Specifically, we say that an edge is critical if its removal renders the graph insufficiently con- nected for URMT protocols (though before its removal the connectivity was sufficient). Ironically, it turns out that for digraphs over n nodes, the number of critical edges is always O(n) for perfect pro- tocols whereas for the “easier” randomized protocols (the ones demanding lesser connectivity require- ments compared to the perfect ones), we give a family of digraphs with Ω(n2) critical edges! Hence, establishing an interesting interplay, for the case of URMT.

Abstract

The classical music traditions of the Indian subcontinent, Hindustani and Carnatic, offer an excellent ground on which to test the limitations of the current music information research approaches. At the same time, their study can shed light on how to solve new and complex music modeling problems. Both traditions have very distinct characteristics, specially compared with western ones: they have developed their own instruments, musical forms, performance practices, social uses and context. In this thesis, we focus on the Carnatic music tradition of south India, especially on its melodic characteristics. Raaga is the spine of Indian classical music. It is the single most crucial element of the melodic framework on which the music of the subcontinent thrives. Naturally, automatic raaga recognition is an important step in computational musicology as far as Indian music is considered. It has several applications like indexing Indian music, automatic note transcription, comparing, classifying and recommending tunes, and teaching to mention a few. Simply put, it is the first logical step in the process of creating computational methods for Indian classical music. In this thesis, we investigate the properties of a raaga and the natural process by which people identify the raaga. We survey the past raaga recognition techniques correlating them with human techniques, in both Hindustani and Carnatic music systems. We identify the main drawbacks and propose minor, but multiple improvements to the state-of-the-art raaga recognition technique. Music is said to evoke emotions. After the advent of advanced signal processing techniques and easily accessible computational resources, the scientists and engineers have been trying to understand the nature of music in this very context. In this context, one of the several aspects of Indian music which interests us is the traditional association of emotions with raagas. Besides the ancient scriptures like Natyasastra, the recent articles of several scholars also associate the raagas with emotions. A part of our work is dedicated to the investigation of the origin of this association. We discuss the term extit{rasa}, often mistaken as emotion. We also report the results of a survey conducted to study the aforementioned raaga-emotion association. We also overview the other theoretical aspects that are relevant for music information research and discuss the scarce computational approaches developed so far. We put emphasis on the limitations of the current methodologies and we present some open issues that have not yet been addressed and that we believe are important to be worked on.

Abstract

Wireless Sensor Networks (WSNs) has been a research topic for more than a decade, and the range of potential applications has spanned beyond the military domain into commercial domains such as industrial/building/home automation, lighting control, energy management, to name a few. Emerging wireless technologies such as Zigbee and IEEE 802.15.4 have enabled the development of interoperable commercial products, which is important to meet the scalability and low cost requirements. A key feature for current WSN solutions is operation in unlicensed frequency bands, for instance, the worldwide available 2.4 GHz band. However, the same band is shared by other very successful wireless applications, such as Wi- Fi and Bluetooth, as well as other proprietary technologies. There is evidence that unlicensed spectrum is becoming overcrowded. As a result, coexistence issues in unlicensed bands have been subject of extensive research, and in particular, it has been shown that IEEE 802.11 networks can significantly degrade the performance of Zigbee/802.15.4 networks when operating in overlapping frequency bands. Till now WSNs are working in fixed spectrum allocation strategy. Using this strategy makes WSNs to interfere with other technologies in the same band. Studies sponsored by the Federal Communications Commission (FCC) pointed out that the current static spectrum allocation has led to overall low spectrum utilization where up to 70% of the allocated spectrum remains unused (called white space) at any one time even in a crowded area. The white space is defined by time, frequency and maximum transmission power at a particular location. Consequently, Dynamic Spectrum Access (DSA) has been proposed so that unlicensed spectrum users or Secondary Users (SU)s are allowed to use the white space of licensed users or Primary Users (PU)s spectrum, conditional on the interference to the PU being below an acceptable level. This function is realized using Cognitive Radio (CR) technology that enables an SU to change its transmission and reception parameters including operating frequencies. There are two prominent features of CR. Firstly, sensing is performed across a wide range of spectrum to identify the white space. Secondly, data packets are allocated opportunistically to the white space at different channels. This means that whenever a PU accesses a channel which has been regarded as white space by the SUs, the SUs must vacate the spectrum as soon as possible. Cognitive Radio based Sensor Networks (CRSN) are introduced to use DSA. In this networks sensor node is aided with cognitive radio. In CRSN SUs are WSN. WSN operates on battery power. Once they drain out of batter it is very difficult to replace them. Hence energy efficiency is more crucial in CRSN. This thesis addresses the problem of reducing energy consumption in Cognitive Radio based Sensor Networks (CRSN). For energy efficiency in CRSN, a spectrum aware architecture is proposed. In proposed architecture spectrum sensing network is decoupled from data aggregating network. Data gathering network is Wireless Sensor Networks (WSN). For data gathering Network energy efficient routing protocol and TDMA based MAC (Medium Access Control) protocol is proposed. In addition to this, a Fault Repair Algorithm using Localization and Controlled mobility to fill Network Holes is proposed. A cross layer design for routing and MAC layer, by using a light weight token-packet passing is proposed. A routing protocol by placing uniform virtual grid for topology aware WSN is also proposed. All these protocols are shown energy efficient when compared to existing protocols. On top of this, energy efficient network architecture for WSN using a novel Non-Uniform Sampling technique is proposed.

Abstract

A truly autonomous robot should be able to build a representation of the environment on its own and be able to navigate between any two points in the environment based on the representation it has built. Also, it should be able to determine its location in the environment from its sensor readings. The representation built by the robot is called a map, and there are different mapping paradigms, which vary from capturing the topology of the environment, to getting fine metric details. Each paradigms have their own pros and cons. To build the map on its own, the robot has to explore. The exploration strategy should be such that the robot builds the map completely in reasonable amount of time. Exploration is a vital cog in the automation of the mapping process. The effectiveness of the exploration strategy affects the quality of the maps produced. This thesis explores the merits of using the higher level knowledge called semantics during the pro- cess of exploration. The semantics is also incorporated in the map begin produced, thereby producing a three level hybrid map. The hybrid level mapping is especially interesting from the Personal Robotics stand point as it is now possible to interact with the robot at a higher semantic level, rather then a metric level. For eg; by the understanding that the environment consists of labs, offices and corridors, the robot can be asked to move from Lab A to office A, rather than saying move from Point A to Point B. This definitely decreases the difficulty in interacting with the robot by many folds. But at the same time, the map needs to have metric properties to enable safe navigation. Semantic understanding alone is not sufficient for the robot to carry out all the tasks. Hence the map should have all the properties which can ease human robot interaction as well as support safe navigation. A hybrid map is needed incorporating both metric and semantic properties and this thesis presents such a hybrid mapping framework. At the top level the map is a graph of semantic constructs. Each node in the graph is a semantic con- struct or label such as a room or a corridor, the edge represented by a transition region such as a doorway that links the two semantic constructs. Each semantic node embeds within it a topological graph that constitutes the map at the middle level. The topological graph is a set of nodes, each node representing an image of the higher semantic construct. At the low level the topological graph embeds metric values and relations, where each node embeds the pose of the robot from which the image was taken and any two nodes in the graph are related by a transformation consisting of a rotation and translation. The exploration algorithm explores a semantic construct completely before moving or branching onto a new construct. Within each semantic construct it uses a local feature based exploration algorithm that uses a combination of local and global decisions to decide the next best place to move. During the process of exploring a semantic construct it identifies transition regions that serve as gateways to move from that construct to another. The exploration is deemed complete when all transition regions are marked vis- ited. Loop detection happens at transition regions and graph optimization techniques are used to close loops when detected to obtain a consistent metric embedding of the robot poses. Semantic constructs are labeled using a visual bag of words(VBOW) representation with a probabilistic SVM classifier.

Abstract

Transfer Grammar Component is a major module in Rule-based Machine Translation (MT) systems. This module handles various levels of structural differences between the source and target languages. The objective of our system is to provide help to language experts for developing transfer grammar rules for various language pairs. The rule structure varies from shallow parsed, partial parsed to fully parsed structures. So, the aim here is to provide a notation and system which is rich enough to state rules using various levels of information. In this thesis we describe Transfer Grammar Engine (TGE) tool which is a major component of Sampark MT system, an MCIT, Govt. of India funded project for developing bidirectional MT systems for nine Indian language pairs. Further in this thesis we try to handle reordering in English-Hindi Statistical MT (SMT). “Reordering” is a sub part of Transfer Grammar Component which is a common phenomenon in language pairs of distant origins. In statistical machine translation (SMT) it has been an important topic since the beginning of the era. During recent developments syntax-based reordering have seen improvements in translation quality. We follow a pre-translation approach that adjusts the source sentence order to resemble the target order prior to translation. We describe an automated approach for learning reorder rules using the syntactic information of the source side training corpus with the word alignment information in a phrase-based SMT system. Later the source side of the training and the test corpus are reordered and given to the SMT system. Although the approach is examined within a pre-translation reordering framework, it easily extends to other frameworks. We demonstrate the effectiveness of our rules on English→Hindi translation task using EILMT tourism corpus. These reordering rules can be used in both statistical and transfer based MT systems. Major contributions of this thesis are (a) designing a working system for capturing structural differences using various syntactic information (b) an approach for learning reordering rules used for both statistical and rule based systems. The framework and methods presented in this thesis are independent of the language pair.