A. James Clark School of Engineering
Permanent URI for this communityhttp://hdl.handle.net/1903/1654
The collections in this community comprise faculty research works, as well as graduate theses and dissertations.
Browse
4 results
Search Results
Item Distributed Task Allocation Algorithms for Multi-Agent Systems with Very Low Communication(IEEE, 2022-11-23) Bapat, Akshay; Bora, Bharath Reddy; Herrmann, Jeffrey W.; Azarm, Shapour; Xu, Huan; Otte, Michael W.In this paper we explore the problem of task allocation when communication is very low, e.g., when the probability of a successful message between agents is ≪0.01 . Such situations may occur when agents choose not to communicate for reasons of stealth or when agent-to-agent communication is actively jammed by an adversary. In such cases, agents may need to divide tasks without knowing the locations of each other. Given the assumption that agents know the total number of agents in the workspace, we investigate solutions that ensure all tasks are eventually completed—even if some of the agents are destroyed. We present two task allocation algorithms that assume communication may not happen, but that benefit whenever communications are successful. (1) The Spatial Division Playbook Algorithm divides task among agents based on an area decomposition. (2) The Traveling Salesman Playbook Algorithm considers mission travel distance by leveraging Christofides’ 3/2 approximation algorithm. These algorithms have task completion runtime complexity of O(mlogm) and O(m3) , respectively, where m refers to the total number of tasks. We compare both algorithms to four state-of-the-art task allocation algorithms — ACBBA, DHBA, PIA and GA — across multiple communication levels and multiple numbers of targets, and using three different communication models. The new algorithms perform favorably, in terms of the time required to ensure all targets are visited, in the special case when communication is very low.Item Distributed Load Balancing Algorithm in Wireless Networks(2014) Sheikhattar, Alireza; Kalantari, Mehdi; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)As communication networks scale up in size, complexity and demand, effective distribution of the traffic load throughout the network is a matter of great importance. Load balancing will enhance the network throughput and enables us to utilize both communication and energy resources more evenly through an efficient redistribution of traffic load across the network. This thesis provides an algorithm for balancing the traffic load in a general network setting. Unlike most of state-of-the-art algorithms in load balancing context, the proposed method is fully distributed, eliminating the need to collect information at a central node and thereby improving network reliability. The effective distribution of load is realized through solving a convex optimization problem where the p-norm of network load is minimized subject to network physical constraints. The optimization solution relies on the Alternating Direction Method of Multipliers (ADMM), which is a powerful tool for solving distributed convex optimization problems. A three-step ADMM-based iterative scheme is derived from suitably reformulated form of p-norm problem. The distributed implementation of the proposed algorithm is further elaborated by introducing a projection step and an initialization setup. The projection step involves an inner-loop iterative scheme to solve linear subproblems. In a distributed setting, each iteration step requires communication among all neighboring nodes. Due to high energy consumption of node-to-node communication, it is most appealing to devise a fast and computationally efficient iterative scheme which can converge to optimal solution within a desired accuracy by using as few iteration steps as possible. A fast convergence iterative scheme is presented which shows superior convergence performance compared to conventional methods. Inspired by fast propagation of waves in physical media, this iterative scheme is derived from partial differential equations for propagation of electrical voltages and currents in a transmission line. To perform these iterations, all nodes should have access to an acceleration parameter which relies on the network topology. The initialization stage is developed in order to overcome the last challenging obstacle toward achieving a fully distributed algorithm.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 Using MODIS Satellite Images to Confirm Distributed Snowmelt Model Results in a Small Arctic Watershed(2009) Choy, David F.; Brubaker, Kaye; Civil Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Environmental analysts face the problem of obtaining distributed measurements to evaluate the performance of models with increasingly small spatiotemporal resolution. While U.S. government agencies readily provide both measurement products and data tools for the study of global change occurring over entire seasons and across continental areas, analysts need access to the low-level data that provides the basis for global products. Finally, analysts need to consider sensor errors inherent in low-level products that are accounted for in global, composite products. Hydrologists using tools for managing low-level snow swath measurements, in particular, must consider how measurements are affected by sensor errors like snow-cloud confusion and sensor errors due to low ground illumination at night. This thesis aims to explore the use of remotely sensed snow maps to confirm a time series of model maps. Specifically, snow covered area (SCA) measurements remotely sensed by the National Aeronautics and Space Administration (NASA) are used to confirm SCA predictions modeled by the United States Agriculture Department (USDA). The measurements come from the two Moderate Resolution Imaging Spectroradiometer (MODIS) sensors aboard near-polar, sun-synchronous satellites named Aqua and Terra. The USDA calls the model TOPMODEL-Based Land-Atmosphere Transfer Scheme (TOPLATS). The Upper Kuparuk River Watershed (UKRW) on the North Slope of Alaska acts as the case study location. To meet the map-comparison goal, the Kappa statistic, Kappa statistic variants, and probability density functions expressing measurement uncertainty in discrete scenes all evaluate the ability of MODIS measurements to confirm the accuracy of TOPLATS model maps. Data management objectives to make measured data accessible and comparable to the model output comprise a supporting goal. Results show that individual composite statistics, like the proportion of agreement between two maps, can easily obscure spatiotemporally distributed confirmation information without additional statistics and side-by-side images of measurement maps and model maps. These tools show some promise for using MODIS to confirm model predictions of snowmelt that occur across less than 150 km2 and less than a few days, however, clouds and malfunctioning sensors limit such use.