Abstract

Motion planning is an important component of robot navigation and manipulation, and it is crucial in applications where the robot operates in full or partial autonomy. Some examples of these are multi-robot exploration, autonomous vehicles, and robot manipulation. In most of these applications, the robot’s state is not directly observable and can only be inferred from erroneous observations. Such situations require the planning algorithms to be robust to the uncertainties in actuation and perception. This thesis investigates the motion planning problem under uncertainty, with specific applications in navigation and path tracking. Applications of these kinds extensively use mathematical routines that solve constraints defined over random variables and are popularly known as chance constraints. Solving for chance constraints is extremely difficult and often intractable. This is primarily due to the fact that non-linear constraints defined over random variables result in a distribution that generally has no parametric form. In this thesis, we focus on constructing mathematical frameworks for solving such intractable optimization routines. This thesis’s key contribution is that we propose a series of formulations that can solve for chance constraints under parametric and non-parametric uncertainties. To achieve this, we construct the mathematical framework systematically over a sequence of stages, wherein each stage improvises over the limitations of the previous. For the first stage, we start with simple sampling-based approaches like the scenario approach. Though conceptually simple, this approach brings an added sample complexity in generating scenarios of the constraint functions. To overcome this limitation of the scenario approach, we proceed to the second stage, where we derive closed-form algebraic equations that would act as a surrogate to the otherwise intractable chance constraint. The novelty in this proposed approach stems from the nature of these surrogate functions, which are simple polynomial functions (mostly quadratic) of control variables and hence greatly simplify complex chance constrained optimization routines. While the proposed framework at this stage did enjoy closed-form algebraic solutions, it relied on the fact that the underlying random variables belonged to parametric forms of distributions (especially Gaussian). Hence we then proceed to the final stage where we solve for chance constraints under non-parametric uncertainties. We construct the proposed algorithm on the possibility of representing arbitrary distributions as functions in Reproducing Kernel Hilbert Space (RKHS). We systematically exploit the kernel trick to reformulate chance constrained optimization routine such that it is tractable and computationally efficient. We detail all the approaches proposed in these three stages over five chapters in this thesis. We primarily apply the proposed formulations on two challenging problems in motion planning: (i) reactive collision avoidance of mobile robots in uncertain dynamic environments and (ii) inverse dynamics based path tracking of manipulators under perception uncertainty. In all these applications, the underlying chance constraints are defined over highly non-linear and non-convex functions of the uncertain parameters, making it highly intractable. We also extend one of the proposed formulations to a multi-robot navigation scenario, where each agent is responsible for computing safe maneuvers, considering perception and ego uncertainty.

Abstract

This work proposes a multi-cloud marketplace model for Infrastructure-as-a-Service (IaaS) layer with multiple cloud providers, intermediate brokers and end users. The brokers service end users subscribed to them by aggregating resources (virtual machines) from cloud providers while maximizing their profits. Similarly cloud providers (producers) allocate their supply of virtual machines to brokers (consumers) so as to maximize their profits. The notion of social welfare in this market structure is defined and two trading schemes are studied. The first scheme involves centralized control which aims at maximizing social welfare. The problem of maximizing the social welfare is formulated as an integer linear programming problem and a greedy algorithm is proposed for the same. However, this scheme may contain unstable producer-consumer pairs who have an incentive to deviate from the current allocation. The second scheme eliminates such unstable pairs by using a generalization of stable matching algorithm but may lead to sub-optimal social welfare. The stable matching algorithm proposed in this work is a particular way of generalizing the original Gale-Shapley deferred acceptance algorithm.

Abstract

Natural Language Generation (NLG) is a research task which addresses the automatic generation of natural language text representative of an input non-linguistic collection of knowledge. Inputs can be of different modalities – databases, structured reports, etc. Traditional NLG systems have been categorized into one of two general approaches: Template based and Pipeline based. In this work, we explore how raw text can be leveraged to automatically extract sub-sentence level templates to generate grammatical sentences. We propose a system for generation of grammatical sentences given a partially ordered partial bagof-words which constrain the generated sentence using a template based approach. As the input, we formulate a lexical level constraint schema as the input constraints which drives the generation process. We view the task as a search problem (a problem of choice) involving combinations of smaller chunk based templates stitched together to construct a complete sentence. To achieve that, we propose a scoring function to determine syntactic correctness of a template sequence which we use in conjunction with an evolutionary algorithm as the search procedure to arrive at a potentially grammatical sentence which satisfies the input constraints.

Abstract

Growth of content and users on internet provides research opportunities in crowdsourcing, search engines and other areas that consume and process web. Lack of clarity in task definition, uncertainty in completion time, concern on data confidentiality, unavailability of workers, cost considerations and quality of output are some of the research opportunities in crowdsourcing. Quality of output is one of the primary concerns in crowdsourcing tasks, as lack of it defeats the objective of using crowd. Researchers are exploring various mechanisms that are based on statistics, machine learning and game theory for acceptable output quality. As part of this work, an online survey conducted on crowdsourcing reiterated importance of quality assurance and quality control of tasks. The online survey along with review of research literature confirmed that quality mechanisms on crowdsourcing tasks benefit from availability of credible knowledge base in a domain. To build domain specific knowledge base, this work proposes a fine grained approach to identify sub-domains in domain and extract related content, an enrichment of a knowledge base in the form of an ontology and credibility assessment based on web genres. The research outcomes on creation and enrichment of knowledge base are used to develop a domain specific search engine. Web pages on internet contain content across domains. Crawler efficiency, sub-domains representation and noise reduction are required to extract domain specific content. A systematic approach to identify sub-domains in a domain is proposed. Further, the work extends metaheuristics based Artificial Bee Colony (ABC) algorithm to extract sub-domains’ URLs. The extended ABC algorithm for crawling performed better than existing industry scale open source crawlers in terms of volume of extracted URLs and usage of compute resources. A metric SeedRel to measure precision of seed URLs based on child URLs presence and content relevance is proposed. The work measured sub-domains coverage with a baseline value of Shannon Diversity Index. In the experiment of this work, about 34,007 seed URLs and 400,726 child URLs of information security sub-domains are extracted. The measured diversity index of 2.10 conforms representation of sub-domains in a domain. The results on URL extraction, seed URL relevance and sub-domain diversity performed better than existing approaches. The extracted domain specific content is an input to build knowledge base. Ontology is a representation of knowledge and provides extensibility, interoperability and reasoning capabilities. To build knowledge base, the work proposes usage of an existing and well accepted seed ontology for enrichment so that a baseline is available, changes are incremental, auto and manual validation can be exercised. It is necessary to validate if an ontology needs to be enriched for any input to avoid unnecessary computation. Similarly, it is necessary to validate if the given ontology represents available domain content. To validate a need for enrichment, a lightweight approach to evaluate ontology sufficiency based on software requirements engineering quality principles is proposed. It is observed from research literature that existing ontology enrichment algorithms that are based on natural language processing and machine learning techniques perform poorly in contextualized extraction of concepts. This necessitated implementation of sequential deep learning architecture that traverse through dependency paths in text and extract concepts embedded in phrases and sentences based on learned path representations. The proposed fine grained ontology enrichment approach (OntoEnricher) exploits both syntactical sentence structures and distributional semantics to identify, extract concepts and instances in unstructured text leveraging Bidirectional LSTMs and pre-trained Universal Sentence Encoder transformer model. The ontology enrichment is experimented with 97,425 keyword phrases and 2.8 GB of Information Security corpus with an accuracy of 80%. The credibility of extracted content enhances usage of knowledge bases. Also, search engine results suffer from non-dominant credibility factors. After a study of existing research articles on ranking and credibility, the work proposes genre based credibility assessment of web page content. An online survey (includes crowdsourcing) is conducted to validate existence and need of web genre for credibility assessment. An exhaustive list of web page features based on surface, content and off-page are identified to validate applicability of genre for credibility assessment. Web page features are used to prepare a dataset to automate genre classification using machine learning based Gradient boosted Decision Tree algorithm with an accuracy 88.75%. An open source framework for credibility assessment of URLs is developed to automate genre classification and credibility assessme

Abstract

High demand for reception of content from multiple users simultaneously enforces usage of intelligent transmission techniques in applications like video-on-demand services, satellite communication, interference management etc. Index coding is one such technique introduced by Birk and Kol in 1998 originally to optimize channel efficiency for satellite communication. The index coding framework consists of a source connected via a broadcast channel to multiple receivers, with each receiver storing locally partial information symbols that is available at the source (this is known as cache or side information). The receivers then demand some new information symbols from the source. An index code is an encoding of the symbols those are demanded by the receivers in such a way that everyone of the receivers can decode their own requested symbols. The goal of index coding is to minimize the number of transmitted symbols (the length or rate of the index code) while ensuring decoding by the receivers. To design the index code with reduced rate, the source makes use of the knowledge of the side-information available at the receivers. Index coding techniques received considerable attention as they can be employed in several engineering applications such as content broadcasting, device-to-device relaying,distributed caching etc. It also has interesting relationships to network coding, distributed storage and guessing games. Several approaches for solving index coding problem have been developed using graph theoretical, linear algebraic methods, interference alignment, linear programming etc. Specifically, in the graph theoretic approach, the side-information and demands of the index coding problem are captured in the form of a graph, and certain properties of the graph are used to construct an index code. Albeit the trials being done in this context, optimal solutions for index coding problems are still open. Index coding problems modelled by circular perfect graphs, which form a strict superclass of the perfect graphs, are studied in the first part of this thesis. We derive schemes that achieve optimal broadcast rate for a constrained class of index coding problems defined by complements of circular perfect graphs. We also proposed a better lower bound on the rate of a optimal solution for any index coding problem. We present lower and upper bounds on the sum and product of vector linear broadcast rates of a graph and its complement. The second part of this dissertation is in the area of coded caching, Consider a network of clients connected via a broadcast channel to one server node which has a number of files. The clients or receivers have caches which allows them to store some parts of the files at the transmitter. The caching system proceeds in two phases: Caching Phase which occurs in non-peak times, and Delivery phase which occurs in peak hours when each client demands some file from the server. By prefetching some parts of the files from the server to the clients during the non-peak hours, the remainders of the demanded files alone can be sent by the server during the peak hours. Thus, caching allows us to offload some traffic from the network during the peak hours, when each client is demanding some file from the transmitter. The paradigm of Coded Caching introduced in [1] further reduces the load during the peak hours by encoding the parts of the files to be communicated. The coded caching problem is similar to the index coding problem in this sense, and hence the goal here also is to minimize the size of the transmissions, i.e., the rate of coded caching. In this thesis, we derive a subpacketization dependent lower bound on the rate of coded caching and compare our results with prior known lower bounds through which we show that our bound performs better than existing lower bounds on the rate of coded caching.

Abstract

What is common between Veg Biryani, Ronaldo and Donald Trump? All of them pretend to be something that they are not. Not Biryani, not the GOAT (Greatest Of All Time) and not human. But again, many a true word is spoken in jest. We pretend just as we breathe. Pretense is observable all around us. Feigning sickness to avoid work, lying to get out of trouble, maintaining a persona or a child joyfully playing his doll are all instances of make-believe. Global platforms of communication have made the world smaller than ever before. With degrees of separation reducing by the day, we can now interact with numerous people almost instantly. More interactions means more dialogue among people, which means more pretense. Sometimes we even pretend about pretending, for example, when applying reverse psychology. The bottom-line is that, pretense is a very important phenomenon in our lives, which we exploit regularly. Therefore, it is only fitting that there be an account which rigorously analyses and explains pretense. No matter how grounded in reality, due to its nature, pretense always involves an element of fantasy. This role is fulfilled by imagination. It provides the necessary content and helps us in guiding an episode of pretense. The nature of this content however is a topic hotly contested in philosophy. Does it comprise of clear or fuzzy images? Or whether images form a part of it at all? Are there different forms of imagination? Moreover, can one even provide a distinction between different types of imagination? We discuss and answer all such questions in Chapter 2, and clear the air up regarding its nature and involvement in pretense. Having gathered all the information needed about imagination as an essential component of pretending, we then move on to the act itself. Pretense involves both mental as well as physical participation of our body. Therefore, an analysis of the cognitive aspects of pretense is necessary to ascertain the precise requirements for pretending. By studying, the two most definitive accounts, viz. metarepresentational account and the behavioural account of pretense we get to know about the important characteristics of pretending. Along the way, we also learn from their shortcomings to bolster our own command of the topic. After strengthening the theoretical backbone needed to properly understand the phenomenon of pretense, we apply our learning from the first three Chapters and proceed towards applying them in a computational paradigm. We are presented by the perfect problem in the shape of Humour and Sarcasm vi vii as two forms of pretense, where we can flex our knowledge and use it to improve the accuracy of existing computational systems. In Chapter 4 we work towards formulating the problem of determining different types of humor as a traditional classification task by feeding positive and negative datasets to a classifier. We develop a model to categorize various kinds of humour based on the mode of delivery, the theme of the joke and the topic of the joke. Then, we illustrate its functionality by applying it on a huge corpus one-liners. Finally, we bring closure to our work in Chapter 5. We make headway in detecting sarcasm by making use of contextual information derived from the history of the participants. Therefore, instead of treating the problem of detecting sarcasm as a mere lexical exercise, we have tried to model a system that tries to build an understanding of the whole process as a human would do.

Abstract

Building sector consumes nearly 75% of electricity sales. And with rapid population and economic expansion, electricity consumption in buildings are projected to be doubled by 2050. The building sector generates one-third of greenhouse gas, two-thirds of halo-carbon and about one-third of black-carbon emissions. This growing energy demands have raised significant concerns around the globe regarding it’s adverse effect on environment. The energy savings potential could reach as high as 30-80% with presently available building technologies. Therefore, importance on development of smart buildings, smart grids are being given which in turn can reduce carbon emissions. Accurate load forecasting is of utmost importance for the development of any modern power system. Hence, accurate building-level load forecasting can help deliver efficient building operations, thus mitigating such adverse effects. Load forecasting helps in real time building control of energy systems, including demand response, demand management, energy transactions, charging/discharging energy storage units. This work presents a robust short-term electrical load forecasting framework that can capture the variations in building operation, regardless of building type and location. Nine different hybrids of recurrent neural networks and clustering are explored. The test cases involve five commercial buildings of five different building types, i.e., academic, research laboratory, office, school and grocery store, located at five different locations in Bangkok-Thailand, Hyderabad-India, Virginia-USA, New York-USA, and Massachusetts-USA. Load forecasting results indicate that the deep learning algorithms implemented in this thesis deliver 20-45% improvement in load forecasting performance as compared to the current state-of-the-art results for both hour-ahead and 24-ahead load forecasting. With respect to sensitivity analysis, it is found that: (i) the use of hybrid deep learning algorithms can take as less as one month of data to deliver satisfactory hour-ahead load prediction, (ii) similar to the clustering technique, 15-minute resolution data, if available, delivers 30% improvement in hour-ahead load forecasting, and (iii) the formulated methods are found to be robust against weather forecasting errors. (iv) the proposed framework are found to be robust to seasonal changes. Lastly, the forecasting results across all five buildings validate the robustness of the proposed deep learning framework for the short-term building-level electrical load forecasting tasks.

Abstract

Negotiation is an important component of the interaction process among humans. With increasing automation, autonomous agents are expected to takeover a lot of this interaction process. Much of automated negotiation literature focuses on agents having a static and known reservation value. Furthermore, a good part of these works focus on negotiation between two agents. In situations involving dynamic environments with multiple agents involved e.g., an agent negotiating on behalf of a human regarding a meeting, agents can have a Reservation Value (RV) that is a function of time. This leads to a different set of challenges that may need additional reasoning about the concession behavior. In this thesis, we build upon Negotiation algorithms such as ONAC (Optimal Non-Adaptive Concession), Time Dependent Techniques such as Boulware and OptimalBidder which work on settings where the reservation value of the agent is fixed and known. Although these algorithms can encode dynamic RV, their concession behavior and hence the properties they were expected to display would be different from when the RV is static, even though the underlying negotiation algorithm remains the same. We therefore propose to use one of Counter, Bayesian Learning with Regression Analysis or LSTM model on top of each algorithm to develop the PredictRV strategy and show that PredictRV indeed performs better on two different metrics tested on two different domains on a variety of parameter settings. We present results for two settings: (a) One involving negotiations between two agents i.e, one agent that use ONAC or Boulware and other with one of these algorithms in combination with one of the PredictRV models leading to 8 (2+2*3) possible agent models and (b) The second for heterogeneous parties of four and five agents i.e., agents that use one of OptimalBidder or Boulware strategies or these two algorithms in combination with one of the 3 PredictRV models leading to 8 (2+2*3) possible agent models .

Abstract

Stereo vision is a technique for depth estimation using two input images taken from slightly displaced cameras at the same time. This has many applications in areas such as robotics, driver-less cars, and 3D scene reconstruction. Semi-Global Matching method for stereo vision is quite popular as it is computationally tractable when compared with other global methods and accurate at the same time. In this thesis, we propose a fully parallel and pipelined architecture for Semi-Global Matching with Census Transform being used underneath. Further, we extend the above streaming architecture so that multiple pixels can be processed in a data parallel fashion. We expose this data parallelism through dependency relaxation. This establishes a trade-off between accuracy and throughput of the hardware. We tested the proposed architecture on Virtex-7 FPGA using KITTI 2012 and KITTI 2015 datasets. On images of resolution 1280x960, with 64 disparity levels, we are able to run our hardware design at 100 MHz. At this frequency, our design is able to process 322 frames per second which is 1.6 times faster than the state-of-the-art SGM implementation on FPGA. Our system can be scaled to a higher resolution image.

Abstract

Image processing has various real-life applications in the world, ranging from agriculture, multimedia security, remote sensing, computer vision, medical applications, biometric verification, and many more. In today’s world, applications like biometric verification or object detection are processed on hardware accelerators to facilitate their real-time needs. While some applications are processed in data centers, others are required to be processed on edge due to security, overall latency, and other issues associated with data centers. With their high speeds, very low power consumption compared to other technologies, and reprogrammability, FPGAs provide a sustainable high-speed solution that can be deployed both in data centers and on edge. Therefore, FPGAs are considered very favorable for accelerating image processing algorithms as they are processed both on edge and in data centers. Not only are they supported by the above claims they also are very capable of exploiting the spatial parallelism (data level) and temporal parallelism (task level) [9] [2] which are inherent in image processing tasks. This thesis will focus on the hardware implementation of Local Laplacian filters used for tone and detail manipulation in images on FPGAs. The algorithm uses simple Gaussian and Laplacian pyramids that can be processed in parallel to speed up it’s processing, making it a strong candidate for acceleration on an FPGA. We propose using the LUTs present on the board to reduce complex computations involved in the algorithm, helping save hardware resources and improve latency. We propose a novel 3-stage pipelined convolution engine to exploit the massive parallelism that the algorithm has to offer. The above proposals help us achieve a good speed up as compared to the original baseline multicore-CPU implementation. We also compare our implementation’s accuracy with the original implementation and find the SNR above 40dB for all cases. To analyze our implementation’s resource usage efficiency, we compute the percentage of active and inactive cycles. We find that because of the design’s low resource utilization, it can be run on lower-end boards like ZedBoard.