Electrical & Computer Engineering
Permanent URI for this communityhttp://hdl.handle.net/1903/2234
Browse
8 results
Search Results
Item CONTROLLER SYNTHESIS UNDER INFORMATION AND FINITE-TIME LOGICAL CONSTRAINTS(2018) Maity, Dipankar; Baras, John S; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)In robotics, networks, and many related fields, a typical controller design problem needs to address both logical and informational constraints. The logical constraints may arise due to the complex task description or decision making process, while the information-related constraints emerge naturally as a consequence of the limitations on communication and computation capabilities. In the first part of the thesis, we consider the problem of synthesizing an event-based controller to address the information-related constraints in the controller design. We consider dynamical systems that are operating under continuous state feedback. This assumes that the measurements are continuously transmitted to the controller in order to generate the input and thus, increases the cost of communication by requiring huge communication resources. In many situations, it so happens that the measurement does not change fast enough that continuous transmission is required. Taking motivation from this, we consider the case where instead continuous feedback we seek an intermittent-feedback. As a result, the system trajectory will deviate from its ideal behavior. However, the question is how much would it deviate? Given the allowed bound on this deviation, can we design some controller that requires fewer measurements than the original controller and still manages to keep the deviation within this prescribed bound? Two important questions remain: 1) What will be the structure of the (optimal) controller? 2) How will the system know the (optimal) instances to transmit the measurement? When the system sends out measurement to controller, it is called as an ``event". Thus, we are looking for an event-generator and a controller to perform event-based control under the constraints on the availability of the state information. The next part focuses on controller synthesis problems that have logical, spatio-temporal constraints on the trajectory of the system; a robot motion planning problem fits as a good example of these kind of finite-time logically constrained problems. We adopt an automata-based approach to abstract the motion of the robot into an automata, and verify the satisfaction of the logical constraints on this automata. The abstraction of the dynamics of the robot into an automata is based on certain reachability guarantee of the robot's dynamics. The controller synthesis problem over the abstracted automata can be represented as a shortest-path-problem. In part III, we consider the problem of jointly addressing the logical and information constraints. The problem is approached with the notion of robustness of logical constraints. We propose two different frameworks for this problem with two different notions of robustness and two different approaches for the controller synthesis. One framework relies on the abstraction of the dynamical systems into a finite transition system, whereas the other relies on tools and results from prescribed performance control to design continuous feedback control to satisfy the robust logical constraints. We adopt an hierarchical controller synthesis method where a continuous feedback controller is designed to satisfy the (robust) logical constraints, and later, that controller is replaced by a suitable event-triggered intermittent feedback controller to cope with informational constraints.Item Compressed Sensing Beyond the IID and Static Domains: Theory, Algorithms and Applications(2017) Kazemipour, Abbas; Wu, Min; Babadi, Behtash; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Sparsity is a ubiquitous feature of many real world signals such as natural images and neural spiking activities. Conventional compressed sensing utilizes sparsity to recover low dimensional signal structures in high ambient dimensions using few measurements, where i.i.d measurements are at disposal. However real world scenarios typically exhibit non i.i.d and dynamic structures and are confined by physical constraints, preventing applicability of the theoretical guarantees of compressed sensing and limiting its applications. In this thesis we develop new theory, algorithms and applications for non i.i.d and dynamic compressed sensing by considering such constraints. In the first part of this thesis we derive new optimal sampling-complexity tradeoffs for two commonly used processes used to model dependent temporal structures: the autoregressive processes and self-exciting generalized linear models. Our theoretical results successfully recovered the temporal dependencies in neural activities, financial data and traffic data. Next, we develop a new framework for studying temporal dynamics by introducing compressible state-space models, which simultaneously utilize spatial and temporal sparsity. We develop a fast algorithm for optimal inference on such models and prove its optimal recovery guarantees. Our algorithm shows significant improvement in detecting sparse events in biological applications such as spindle detection and calcium deconvolution. Finally, we develop a sparse Poisson image reconstruction technique and the first compressive two-photon microscope which uses lines of excitation across the sample at multiple angles. We recovered diffraction-limited images from relatively few incoherently multiplexed measurements, at a rate of 1.5 billion voxels per second.Item Joint Optimization for Social Content Delivery in Wireless Networks(2016) Weng, Xiangnan; Baras, John S; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Over the last decade, success of social networks has significantly reshaped how people consume information. Recommendation of contents based on user profiles is well-received. However, as users become dominantly mobile, little is done to consider the impacts of the wireless environment, especially the capacity constraints and changing channel. In this dissertation, we investigate a centralized wireless content delivery system, aiming to optimize overall user experience given the capacity constraints of the wireless networks, by deciding what contents to deliver, when and how. We propose a scheduling framework that incorporates content-based reward and deliverability. Our approach utilizes the broadcast nature of wireless communication and social nature of content, by multicasting and precaching. Results indicate this novel joint optimization approach outperforms existing layered systems that separate recommendation and delivery, especially when the wireless network is operating at maximum capacity. Utilizing limited number of transmission modes, we significantly reduce the complexity of the optimization. We also introduce the design of a hybrid system to handle transmissions for both system recommended contents ('push') and active user requests ('pull'). Further, we extend the joint optimization framework to the wireless infrastructure with multiple base stations. The problem becomes much harder in that there are many more system configurations, including but not limited to power allocation and how resources are shared among the base stations ('out-of-band' in which base stations transmit with dedicated spectrum resources, thus no interference; and 'in-band' in which they share the spectrum and need to mitigate interference). We propose a scalable two-phase scheduling framework: 1) each base station obtains delivery decisions and resource allocation individually; 2) the system consolidates the decisions and allocations, reducing redundant transmissions. Additionally, if the social network applications could provide the predictions of how the social contents disseminate, the wireless networks could schedule the transmissions accordingly and significantly improve the dissemination performance by reducing the delivery delay. We propose a novel method utilizing: 1) hybrid systems to handle active disseminating requests; and 2) predictions of dissemination dynamics from the social network applications. This method could mitigate the performance degradation for content dissemination due to wireless delivery delay. Results indicate that our proposed system design is both efficient and easy to implement.Item GENERALIZED DISTRIBUTED CONSENSUS-BASED ALGORITHMS FOR UNCERTAIN SYSTEMS AND NETWORKS(2010) Matei, Ion; Baras, John S; Martins, Nuno C; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)We address four problems related to multi-agent optimization, filtering and agreement. First, we investigate collaborative optimization of an objective function expressed as a sum of local convex functions, when the agents make decisions in a distributed manner using local information, while the communication topology used to exchange messages and information is modeled by a graph-valued random process, assumed independent and identically distributed. Specifically, we study the performance of the consensusbased multi-agent distributed subgradient method and show how it depends on the probability distribution of the random graph. For the case of a constant stepsize, we first give an upper bound on the difference between the objective function, evaluated at the agents' estimates of the optimal decision vector, and the optimal value. In addition, for a particular class of convex functions, we give an upper bound on the distances between the agents' estimates of the optimal decision vector and the minimizer and we provide the rate of convergence to zero of the time varying component of the aforementioned upper bound. The addressed metrics are evaluated via their expected values. As an application, we show how the distributed optimization algorithm can be used to perform collaborative system identification and provide numerical experiments under the randomized and broadcast gossip protocols. Second, we generalize the asymptotic consensus problem to convex metric spaces. Under minimal connectivity assumptions, we show that if at each iteration an agent updates its state by choosing a point from a particular subset of the generalized convex hull generated by the agents current state and the states of its neighbors, then agreement is achieved asymptotically. In addition, we give bounds on the distance between the consensus point(s) and the initial values of the agents. As an application example, we introduce a probabilistic algorithm for reaching consensus of opinion and show that it in fact fits our general framework. Third, we discuss the linear asymptotic consensus problem for a network of dynamic agents whose communication network is modeled by a randomly switching graph. The switching is determined by a finite state, Markov process, each topology corresponding to a state of the process. We address both the cases where the dynamics of the agents are expressed in continuous and discrete time. We show that, if the consensus matrices are doubly stochastic, average consensus is achieved in the mean square and almost sure senses if and only if the graph resulting from the union of graphs corresponding to the states of the Markov process is strongly connected. Fourth, we address the consensus-based distributed linear filtering problem, where a discrete time, linear stochastic process is observed by a network of sensors. We assume that the consensus weights are known and we first provide sufficient conditions under which the stochastic process is detectable, i.e. for a specific choice of consensus weights there exists a set of filtering gains such that the dynamics of the estimation errors (without noise) are asymptotically stable. Next, we develop a distributed, sub-optimal filtering scheme based on minimizing an upper bound on a quadratic filtering cost. In the stationary case, we provide sufficient conditions under which this scheme converges; conditions expressed in terms of the convergence properties of a set of coupled Riccati equations. We continue by presenting a connection between the consensus-based distributed linear filter and the optimal linear filter of a Markovian jump linear system, appropriately defined. More specifically, we show that if the Markovian jump linear system is (mean square) detectable, then the stochastic process is detectable under the consensus-based distributed linear filtering scheme. We also show that the optimal gains of a linear filter for estimating the state of a Markovian jump linear system, appropriately defined, can be used to approximate the optimal gains of the consensus-based linear filter.Item Primal-dual interior-point algorithms for linear programs with many inequality constraints(2010) Winternitz, Luke; Tits, Andre L; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Linear programs (LPs) are one of the most basic and important classes of constrained optimization problems, involving the optimization of linear objective functions over sets defined by linear equality and inequality constraints. LPs have applications to a broad range of problems in engineering and operations research, and often arise as subproblems for algorithms that solve more complex optimization problems. ``Unbalanced'' inequality-constrained LPs with many more inequality constraints than variables are an important subclass of LPs. Under a basic non-degeneracy assumption, only a small number of the constraints can be active at the solution--it is only this active set that is critical to the problem description. On the other hand, the additional constraints make the problem harder to solve. While modern ``interior-point'' algorithms have become recognized as some of the best methods for solving large-scale LPs, they may not be recommended for unbalanced problems, because their per-iteration work does not scale well with the number of constraints. In this dissertation, we investigate "constraint-reduced'' interior-point algorithms designed to efficiently solve unbalanced LPs. At each iteration, these methods construct search directions based only on a small working set of constraints, while ignoring the rest. In this way, they significantly reduce their per-iteration work and, hopefully, their overall running time. In particular, we focus on constraint-reduction methods for the highly efficient primal-dual interior-point (PDIP) algorithms. We propose and analyze a convergent constraint-reduced variant of Mehrotra's predictor-corrector PDIP algorithm, the algorithm implemented in virtually every interior-point software package for linear (and convex-conic) programming. We prove global and local quadratic convergence of this algorithm under a very general class of constraint selection rules and under minimal assumptions. We also propose and analyze two regularized constraint-reduced PDIP algorithms (with similar convergence properties) designed to deal directly with a type of degeneracy that constraint-reduced interior-point algorithms are often subject to. Prior schemes for dealing with this degeneracy could end up negating the benefit of constraint-reduction. Finally, we investigate the performance of our algorithms by applying them to several test and application problems, and show that our algorithms often outperform alternative approaches.Item Measurement-based Optimal Routing Strategies on Overlay Architectures(2006-06-05) Guven, Tuna; Shayman, Mark A.; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)In this thesis, we seek optimal, yet practical, multipath routing algorithms that can minimize the network congestion by exploiting the locally collected measurement data. We first develop a distributed measurement-based routing algorithm to load balance intradomain traffic along multiple paths for multiple unicast sources. Multiple paths are established using overlay nodes. The algorithm is derived from simultaneous perturbation stochastic approximation (SPSA) and does not assume that the gradient of an analytical cost function is known. Instead, it relies on (potentially) noisy estimates from local measurements. We formulate the traffic mapping problem in an optimization framework and show through an analytical model that the algorithm converges to the optimal solution almost surely under a decreasing step size policy. Motivated by practical concerns, we next consider the constant step size case, for which we establish weak convergence. In the second part of this thesis, we consider the problem of load balancing of multicast traffic sessions and generalize our unicast routing algorithm to route both types of traffic simultaneously. We consider three network models that reflect different sets of assumptions regarding multicast capabilities of the network. In addition, we investigate the benefits acquired from implementing additional multicast capabilities by studying the relative performance of the generalized algorithm under the three network models. Throughout this thesis, we rely on an overlay architecture to establish multiple paths between a source and its destination(s) in an IP network. As the performance of the routing algorithms depends on the quality of paths provided by the overlay nodes, it is of interest to carefully locate a limited number of overlay nodes in the network. The final part of this thesis makes use of the discrete stochastic optimization methods and presents an optimal solution based on Stochastic Comparison (SC) algorithm to locate overlay nodes given a set of sources and their corresponding destination(s). Motivated by the impracticality of stochastic comparison algorithm in an online setting due to its computational complexity, we provide a computationally efficient heuristic solution. We show through a detailed simulation study that the performance obtained by the heuristic solution is comparable to that of optimal algorithm.Item Design Space Re-Engineering for Power Minimization in Modern Embedded Systems(2006-06-01) Yuan, Lin; Qu, Gang; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Power minimization is a critical challenge for modern embedded system design. Recently, due to the rapid increase of system's complexity and the power density, there is a growing need for power control techniques at various design levels. Meanwhile, due to technology scaling, leakage power has become a significant part of power dissipation in the CMOS circuits and new techniques are needed to reduce leakage power. As a result, many new power minimization techniques have been proposed such as voltage island, gate sizing, multiple supply and threshold voltage, power gating and input vector control, etc. These design options further enlarge the design space and make it prohibitively expensive to explore for the most energy efficient design solution. Consequently, heuristic algorithms and randomized algorithms are frequently used to explore the design space, seeking sub-optimal solutions to meet the time-to-market requirements. These algorithms are based on the idea of truncating the design space and restricting the search in a subset of the original design space. While this approach can effectively reduce the runtime of searching, it may also exclude high-quality design solutions and cause design quality degradation. When the solution to one problem is used as the base for another problem, such solution quality degradation will accumulate. In modern electronics system design, when several such algorithms are used in series to solve problems in different design levels, the final solution can be far off the optimal one. In my Ph.D. work, I develop a {\em re-engineering} methodology to facilitate exploring the design space of power efficient embedded systems design. The direct goal is to enhance the performance of existing low power techniques. The methodology is based on the idea that design quality can be improved via iterative ``re-shaping'' the design space based on the ``bad'' structure in the obtained design solutions; the searching run-time can be reduced by the guidance from previous exploration. This approach can be described in three phases: (1) apply the existing techniques to obtain a sub-optimal solution; (2) analyze the solution and expand the design space accordingly; and (3) re-apply the technique to re-explore the enlarged design space. We apply this methodology at different levels of embedded system design to minimize power: (i) switching power reduction in sequential logic synthesis; (ii) gate-level static leakage current reduction; (iii) dual threshold voltage CMOS circuits design; and (iv) system-level energy-efficient detection scheme for wireless sensor networks. An extensive amount of experiments have been conducted and the results have shown that this methodology can effectively enhance the power efficiency of the existing embedded system design flows with very little overhead.Item NETWORK AND DOMAIN AUTOCONFIGURATION: A UNIFIED FRAMEWORK FOR LARGE MOBILE AD HOC NETWORKS(2005-11-15) Manousakis, Kyriakos; Baras, John S.; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Configuration management is critical to correct and efficient operation of large networks. In those cases where the users and networks are dynamic and ad hoc, manual configuration quickly becomes too complex. The combination of the sheer number of nodes with the heterogeneity and dynamics makes it almost impossible for the system administrator to ensure good configuration or even ensure correct operation. To achieve the vision of pervasive computing, nodes must automatically discover their environment and self-configure, then must automatically reconfigure to adapt to changes. Protocols such as DHCP, DDNS and mDNS provide some degree of host autoconfiguration, but network administrators must still configure information such as address pools, routing protocols, or OSPF routing areas. Only limited progress has been made to automate the configuration of routers, servers and network topology. This dissertation proposes the autoconfiguration of most host, router and server information, including the automatic generation and maintenance of hierarchy, under the same architectural, algorithmic and protocol framework. The proposed unified framework consists of modules (DRCP, DCDP, YAP, ACA) responsible for the entity autoconfiguration and from a modified and well adjusted general optimization (Simulated Annealing) based algorithm for the domain autoconfiguration. Due to the generality of the optimization algorithm, the generated hierarchy can improve dynamically selected network performance aspects represented by appropriately designed objective functions and constraints. An indicative set related to the physical characteristics of the domains and node mobility is provided. Even though SA has been adjusted for faster convergence, it may still be unable to capture the dynamics of rapidly changing networks. Thus, a faster but suboptimal distributed hierarchy generation mechanism that follows the design philosophy of SA-based mechanism has also been introduced. Inevitably, due to network dynamics, the quality of the hierarchy will degrade. In such scenarios, the frequent reapplication of the expensive optimization based hierarchy generation is prohibitive. Hence, for extending the domain formation framework, distributed maintenance mechanisms have been proposed for reconstructing the feasibility and quality of the hierarchy by enforcing localized decisions. The proposed framework has been applied to provide solutions on some realistic network problems related to hierarchical routing and topology control.