Electrical & Computer Engineering Theses and Dissertations
Permanent URI for this collectionhttp://hdl.handle.net/1903/2765
Browse
8 results
Search Results
Item Safe Navigation of Autonomous Vehicles in Structured Mixed-Traffic Environments(2023) Tariq, Faizan Muhammad; Baras, John S; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The primary driving force behind autonomous vehicle (AV) research is the prospect of enhancing road safety by preventing accidents caused by human errors. To that end, it seems rather improbable that AVs will replace all human-driven vehicles in the near future. The more plausible scenario is that AVs will gradually be introduced on public roads and highways in the presence of human-driven vehicles, leading to mixed-traffic scenarios. In addition to the existing challenges associated with autonomous driving stemming from various uncertainty factors associated with sensing, prediction, control, and computation, these situations pose further difficulties pertaining to the variability in human driving patterns. Therefore, to ensure widespread public acceptance of AVs, it is crucial to develop planning and decision-making algorithms, while benefiting from modern sensing, computation, and control methods, that can deliver safe, efficient, and reliable performance in mixed-traffic situations. Considering the need to cater to the behavior variability of human drivers, we address the joint decision-making and motion planning problem in structured environments with a multi-timescale navigation architecture. Specifically, we design algorithms for commonly encountered highway driving scenarios that require effective real-time decision-making, reliable motion prediction of on-road entities, behavior consideration of on-road agents, and attention to safety as well as passenger comfort. The specific problems addressed in this dissertation include bidirectional highway overtaking, highway maneuvering in traffic, and crash mitigation on highways. In the proposed framework, we first identify and exploit the different timescales involved in the navigation architecture. Then, we propose algorithmic modules while pursuing systematic complexity (data and computation) reduction at different timescales to gain immediate performance improvements in inference and action/response delay minimization. This leads to real-time situation assessment, computation, and action/control, allowing us to satisfy some of the key requirements for autonomous driving algorithms. Notably, the algorithms proposed in this dissertation ensure that the safety of the overall system is a fundamental constraint built into the system. Distinctive features of the proposed approaches include real-time operation capability, consideration for behavior variability of on-road agents, modularity in design, and optimality with respect to various metrics. The algorithms developed and implemented as part of this dissertation fundamentally rely upon the application of optimization techniques in a receding horizon fashion which allows for optimality in performance while explicitly accounting for actuation limits, vehicle dynamics, and safety. Even though the modularity of the proposed navigation framework allows for the incorporation of modern prediction and control methods, we develop various prediction modules for the trajectory prediction of on-road agents. We further benefit from risk evaluation methodologies to ensure robustness to behavior variability of human drivers on the road and handle collision-prone situations. In the spirit of emulating real-world situations, we place special emphasis on utilizing realistic driving simulations that capture the effects of communication delays between different modules, limitations in computation resources, and randomization of scenarios. For the developed algorithms, we evaluate the performance in comparative singular case studies as well as randomized Monte Carlo simulations with respect to several metrics to assess the efficacy of the developed methods.Item OPTIMIZATION ALGORITHMS USING PRIORS IN COMPUTER VISION(2018) Shah, Sohil Atul; Goldstein, Tom; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Over the years, many computer vision models, some inspired by human behavior, have been developed for various applications. However, only handful of them are popular and widely used. Why? There are two major factors: 1) most of these models do not have any efficient numerical algorithm and hence they are computationally very expensive; 2) many models, being too generic, cannot capitalize on problem specific prior information and thus demand rigorous hyper-parameter tuning. In this dissertation, we design fast and efficient algorithms to leverage application specific priors to solve unsupervised and weakly-supervised problems. Specifically, we focus on developing algorithms to impose structured priors, model priors and label priors during the inference and/or learning of vision models. In many application, it is known a priori that a signal is smooth and continuous in space. The first part of this work is focussed on improving unsupervised learning mechanisms by explicitly imposing these structured priors in an optimization framework using different regularization schemes. This led to the development of fast algorithms for robust recovery of signals from compressed measurements, image denoising and data clustering. Moreover, by employing re-descending robust penalty on the structured regularization terms and applying duality, we reduce our clustering formulation to an optimization of a single continuous objective. This enabled integration of clustering processes in an end-to-end feature learning pipeline. In the second part of our work, we exploit inherent properties of established models to develop efficient solvers for SDP, GAN, and semantic segmentation. We consider models for several different problem classes. a) Certain non-convex models in computer vision (e.g., BQP) are popularly solved using convex SDPs after lifting to a high-dimensional space. However, this computationally expensive approach limits these methods to small matrices. A fast and approximate algorithm is developed that directly solves the original non-convex formulation using biconvex relaxations and known rank information. b) Widely popular adversarial networks are difficult to train as they suffer from instability issues. This is because optimizing adversarial networks corresponds to finding a saddle-point of a loss function. We propose a simple prediction method that enables faster training of various adversarial networks using larger learning rates without any instability problems. c) Semantic segmentation models must learn long-distance contextual information while retaining high spatial resolution at the output. Existing models achieves this at the cost of computationally expensive and memory exhaustive training/inference. We designed stacked u-nets model which can repeatedly process top-down and bottom-up features. Our smallest model exceeds Resnet-101 performance on PASCAL VOC 2012 by 4.5% IoU with ∼ 7× fewer parameters. Next, we address the problem of learning heterogeneous concepts from internet videos using mined label tags. Given a large number of videos each with multiple concepts and labels, the idea is to teach machines to automatically learn these concepts by leveraging weak labels. We formulate this into a co-clustering problem and developed a novel bayesian non-parametric weakly supervised Indian buffet process model which additionally enforces the paired label prior between concepts. In the final part of this work we consider an inverse approach: learning data priors from a given model. Specifically, we develop numerically efficient algorithm for estimating the log likelihood of data samples from GANs. The approximate log-likelihood function is used for outlier detection and data augmentation for training classifiers.Item Optimization-based Robustness and Stabilization in Decentralized Control(2017) Alavian, Alborz; Rotkowitz, Michael C; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)This dissertation pertains to the stabilization, robustness, and optimization of Finite Dimensional Linear Time Invariant (FDLTI) decentralized control systems. We study these concepts for FDLTI systems subject to decentralizations that emerge from imposing sparsity constraints on the controller. While these concepts are well-understood in absence of an information structure, they continue to raise fundamental interesting questions regarding an optimal controller, or on suitable notions of robustness in presence of information structures. Two notions of stabilizability with respect to decentralized controllers are considered. First, the seminal result of Wang & Davison in 1973 regarding internal stabilizability of perfectly decentralized system and its connection to the decentralized fixed-modes of the plant is revisited. This seminal result would be generalized to any arbitrary sparsity-induced information structure by providing an inductive proof that verifies and shows that those mode of the plant that are fixed with respect to the static controllers would remain fixed with respect to the dynamic ones. A constructive proof is also provided to show that one can move any non-fixed mode of the plant to any arbitrary location within desired accuracy provided that they remain symmetric in the complex plane. A synthesizing algorithm would then be derived from the inductive proof. A second stronger notion of stability referred to as "non-overshooting stability" is then addressed. A key property called "feedthrough consistency" is derived, that when satisfied, makes extension of the centralized results to the decentralized case possible. Synthesis of decentralized controllers to optimize an H_Infinity norm for model-matching problems is considered next. This model-matching problem corresponds to an infinite-dimensional convex optimization problem. We study a finite-dimensional parametrization, and show that once the poles are chosen for this parametrization, the remaining problem of coefficient optimization can be cast as a semidefinite program (SDP). We further demonstrate how to use first-order methods when the SDP is too large or when a first-order method is otherwise desired. This leaves the remaining choice of poles, for which we develop and discuss several methods to better select the most effective poles among many candidates, and to systematically improve their location using convex optimization techniques. Controllability of LTI systems with decentralized controllers is then studied. Whether an LTI system is controllable (by LTI controllers) with respect to a given information structure can be determined by testing for fixed modes, but this gives a binary answer with no information about robustness. Measures have already been developed to determine how far a system is from having a fixed mode when one considers complex or real perturbations to the state-space matrices. These measures involve intractable minimizations of a non-convex singular value over a power-set, and hence cannot be computed except for the smallest of the plants. We replace these problem by equivalent optimization problems that involve a binary vector rather than the power-set minimization and prove their equality. Approximate forms are also provided that would upper bound the original metrics, and enable us to utilize MINLP techniques to derive scalable upper bounds. We also show that we can formulate lower bounds for these measures as polynomial optimization problems,and then use sum-of-squares methods to obtain a sequence of SDPs, whose solutions would lower bound these metrics.Item Optimality of Event-Based Policies for Decentralized Estimation over Shared Networks(2016) Vasconcelos, Marcos Muller; Martins, Nuno C; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Cyber-physical systems often consist of multiple non-collocated components that sense, exchange information and act as a team through a network. Although this new paradigm provides convenience, flexibility and robustness to modern systems, design methods to achieve optimal performance are elusive as they must account for certain detrimental characteristics of the underlying network. These include constrained connectivity among agents, rate-limited communication links, physical noise at the antennas, packet drops and interference. We propose a new class of problems in optimal networked estimation where multiple sensors operating as a team communicate their measurements to a fusion center over an interference prone network modeled by a collision channel. Using a team decision theoretic approach, we characterize jointly optimal communication policies for one-shot problems under different performance criteria. First we study the problem of estimating two independent continuous random variables observed by two different sensors communicating with a fusion center over a collision channel. For a minimum mean squared estimation error criterion, we show that there exist team-optimal strategies where each sensor uses a threshold policy. This result is independent of the distribution of the observations and, can be extended to vector observations and to any number of sensors. Consequently, the existence of team-optimal threshold policies is a result of practical significance, because it can be applied to a wide class of systems without requiring collision avoidance protocols. Next we study the problem of estimating independent discrete random variables over a collision channel. Using two different criteria involving the probability of estimation error, we show the existence of team-optimal strategies where the sensors either transmit all but the most likely observation; transmit only the second most likely observation; or remain always silent. These results are also independent of the distributions and are valid for any number of sensors. In our analysis, the proof of the structural result involves the minimization of a concave functional, which is an evidence of the inherent complexity of team decision problems with nonclassical information structure. In the last part of the dissertation, the assumption on the cooperation among sensors is relaxed, and we show that similar structural results can also be obtained for systems with one or more selfish sensors. Finally the assumption of the independence is lifted by introducing the observation of a common random variable in addition to the private observations of each sensor. The structural result obtained provides valuable insights on the characterization of team-optimal policies for a general correlation structure between the observed random variables.Item Thermal Tracking and Estimation for Microprocessors(2016) Zhang, Yufu; Srivastava, Ankur; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Due to increasing integration density and operating frequency of today's high performance processors, the temperature of a typical chip can easily exceed 100 degrees Celsius. However, the runtime thermal state of a chip is very hard to predict and manage due to the random nature in computing workloads, as well as the process, voltage and ambient temperature variability (together called PVT variability). The uneven nature (both in time and space) of the heat dissipation of the chip could lead to severe reliability issues and error-prone chip behavior (e.g. timing errors). Many dynamic power/thermal management techniques have been proposed to address this issue such as dynamic voltage and frequency scaling (DVFS), clock gating and etc. However, most of such techniques require accurate knowledge of the runtime thermal state of the chip to make efficient and effective control decisions. In this work we address the problem of tracking and managing the temperature of microprocessors which include the following sub-problems: (1) how to design an efficient sensor-based thermal tracking system on a given design that could provide accurate real-time temperature feedback; (2) what statistical techniques could be used to estimate the full-chip thermal profile based on very limited (and possibly noise-corrupted) sensor observations; (3) how do we adapt to changes in the underlying system's behavior, since such changes could impact the accuracy of our thermal estimation. The thermal tracking methodology proposed in this work is enabled by on-chip sensors which are already implemented in many modern processors. We first investigate the underlying relationship between heat distribution and power consumption, then we introduce an accurate thermal model for the chip system. Based on this model, we characterize the temperature correlation that exists among different chip modules and explore statistical approaches (such as those based on Kalman filter) that could utilize such correlation to estimate the accurate chip-level thermal profiles in real time. Such estimation is performed based on limited sensor information because sensors are usually resource constrained and noise-corrupted. We also took a further step to extend the standard Kalman filter approach to account for (1) nonlinear effects such as leakage-temperature interdependency and (2) varying statistical characteristics in the underlying system model. The proposed thermal tracking infrastructure and estimation algorithms could consistently generate accurate thermal estimates even when the system is switching among workloads that have very distinct characteristics. Through experiments, our approaches have demonstrated promising results with much higher accuracy compared to existing approaches. Such results can be used to ensure thermal reliability and improve the effectiveness of dynamic thermal management techniques.Item Model Based Optimization and Design of Secure Systems(2013) Malik, Waseem Ansar; Martins, Nuno C; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)ABSTRACT Title of dissertation: MODEL BASED OPTIMIZATION AND DESIGN OF SECURE SYSTEMS Waseem Ansar Malik, Doctor of Philosophy, 2013 Dissertation directed by: Prof. Nuno C. Martins Department of Electrical and Computer Engineering University of Maryland, College Park Dr. Ananthram Swami Computational and Information Sciences Directorate Army Research Laboratory Control systems are widely used in modern industry and find wide applications in power systems, nuclear and chemical plants, the aerospace industry, robotics, communication devices, and embedded systems. All these systems typically rely on an underlying computing and networking infrastructure which has considerable security vulnerabilities. The biggest threat, in this age and time, to modern systems are cyber attacks from adversaries. Recent cyber attacks have practically shut down government websites affecting government operation, undermined financial institutions, and have even infringed on public privacy. Thus it is extremely important to conduct studies on the design and analysis of secure systems. This work is an effort in this research direction and is mainly focused on incorporating security in the design of modern control systems. In the first part of this dissertation, we present a linear quadratic optimal control problem subjected to security constraints. We consider an adversary which can make partial noisy measurements of the state. The task of the controller is to generate control sequences such that the adversary is unable to estimate the terminal state. This is done by minimizing a quadratic cost while satisfying security constraints. The resulting optimization problems are shown to be convex and the optimal solution is computed using Lagrangian based techniques. For the case when the terminal state has a discrete distribution the optimal solution is shown to be nonlinear in the terminal state. This is followed by considering the case when the terminal state has a continuous distribution. The resulting infinite dimensional optimization problems are shown to be convex and the optimal solution is proven to be affine in the terminal state. In the next part of this dissertation, we analyze several team decision problems subjected to security constraints. Specifically, we consider problem formulations where there are two decision makers each controlling a different dynamical system. Each decision maker receives information regarding the respective terminal states that it is required to reach and applies a control sequence accordingly. An adversary makes partial noisy measurements of the states and tries to estimate the respective terminal states. It is shown that the optimal solution is affine in the terminal state when it is identical for both systems. We also consider the general case where the terminal states are correlated. The resulting infinite dimensional optimization problems are shown to convex programs and we prove that the optimal solution is affine in the information available to the decision makers. Next, a stochastic receding horizon control problem is considered and analyzed. Specifically, we consider a system with bounded disturbances and hard bounds on the control inputs. Utilizing a suboptimal disturbance feedback scheme, the optimization problem is shown to be convex. The problem of minimizing the empirical mean of the cost function is analyzed. We provide bounds on the disturbance sample size to compute the empirical minimum of the problem. Further, we consider the problem where there are hard computational constraints and complex on-line optimization is not feasible. This is addressed by randomly generating both the control inputs and the additive disturbances. Bounds on sample sizes are provided which guarantee a notion of a probable near minimum. Model uncertainty is also incorporated into the framework and relevant bounds are provided which guarantee a probable near minimax value. This work finds many applications in miniature devices and miniature robotics. In the final part of this dissertation, we consider a centralized intrusion detection problem with jointly optimal sensor placement. A team of sensors make measurements regarding the presence of an intruder and report their observations to a decision maker. The decision maker solves a jointly optimal detection and sensor placement problem. For the case when the number of sensors is equal to the number of placement points, we prove that uniform placement of sensors is not strictly optimal. We introduce and utilize a majorization based partial order for the placement of sensors. For the case when the number of sensors is less than or equal to six, we show that for a fixed local probability of detection (probability of false alarm) increasing the probability of false alarm (probability of detection) results in optimal placements that are higher on a majorization based partial order.Item Throughput Evaluation and Optimization in Wireless Networks(2007-12-10) Rentz, Nicolas; Baras, John S; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)While wireless communication is progressively replacing wired technology, methods for the implementation of Wireless Ad-Hoc Networks are currently under development. As these methods do not require centralized coordination, they are particularly adapted to environments such as disaster recovery and military communication and are, therefore, of great interest. Despite the potential advantages, no reliable methodologies for the design of Wireless Ad-Hoc Networks have been proposed. This condition is largely due to the complexity of analysis of a wireless channel in comparison to that of a wired channel. In this thesis, we discuss the implementation of a tool for wireless network design. Taking a set of nodes and the corresponding characteristics, this tool computes the routes between each source-destination pair. The tool then computes the throughput for each connection and, finally, proposes a method for the optimization of throughput based on probabilistic routing via sensitivity analysis.Item Network flow optimization and distributed control algorithms(2006-11-21) Chen, Huigang; Baras, John S; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)This thesis concerns the problem of designing distributed algorithms for achieving efficient and fair bandwidth allocations in a resource constrained network. This problem is fundamental to the design of transmission protocols for communication networks, since the fluid models of popular protocols such as TCP and Proportional Fair Controller can be viewed as distributed algorithms which solve the network flow optimization problems corresponding to some fairness criteria. Because of the convexity of the optimization problem as well as its decoupling structure, there exist classical dual algorithm and primal/dual algorithm which are both distributed. However, the main difficulty is the possible instability of the dynamics of these algorithms caused by transmission delays. We use customized Lyapunov-Krasovskii functionals to obtain the stability conditions for these algorithms in networks with heterogeneous time-varying delays. There are two main features of our results. The first is that these stability conditions can be enforced by a small amount of information exchange among relevant users and links. The second is that these stability conditions only depend on the upper bound of delays, not on the rate of delay variations. We further our discussion on scalable algorithms with minimum information to maintain stability. We present a design methodology for such algorithms and prove the global stability of our scalable controllers by the use of Zames-Falb multipliers. Next we extend this method to design the first scalable and globally stable algorithm for the joint multipath routing and flow optimization problem. We achieve this by adding additional delays to different paths for all users. Lastly we discuss the joint single path routing and flow optimization problem, which is a NP hard problem. We show bounded price of anarchy for combined flow and routing game for simple networks and show for many-user networks, simple Nash algorithm leads to approximate optimum of the problem.