Showing 1-21 of 21 results
- Sort
Filter Results
Show
Sort By
Results
The Forward-Reverse Greedy Algorithm for Distributed Submodular Maximization
2024 IEEE 63rd Conference on Decision and Control (CDC)
Year: 2024 | Conference Paper |
This work addresses submodular maximization problems, a widely-used mathematical tool to model many real-world decisions. Though this set of problems is NP-Hard, a well-known result is that a distributed greedy algorithm, wherein agents sequentially make greedy decisions, is guaranteed to approximate the optimal solution with a multiplicative factor of 1/2. This work explores whether running the g...Show More
A Matrix Inverse Algorithm based on Bi-Directional Graph Search
2024 IEEE 63rd Conference on Decision and Control (CDC)
Year: 2024 | Conference Paper |
We present an algorithm to estimate a single entry of the inverse of a matrix; it is derived using a bidirectional search on a flow graph. This method has immediate application in analyzing dynamical system destabilization attacks, where previous research quantifies system node-to-node vulnerability in terms of a matrix inverse. We present evidence that the expected $\infty$-norm error, the number...Show More
Automated Red-teaming for Securing Critical Infrastructures against Instability Attacks
Justin Tackett;Brian Brown;Benjamin L. Francis;Tyler N. Burrows;Mark K. Transtrum;David Grimsman;Sean Warnick
2024 IEEE Power & Energy Society General Meeting (PESGM)
Year: 2024 | Conference Paper |
Here we present a novel methodology for end-to-end analysis of instability in power systems. Our methodology uses a modeling representation known as the Dynamical Structure Function (DSF) to identify how linear time-varying attacks propagate through the exposed portions of the system. We show how the DSF of a cyber-physical system can be used as a way to model the attack surface. We present a metr...Show More
Optimal Utility Design of Greedy Algorithms in Resource Allocation Games
Designing fast, distributed algorithms for multiagent problems is vital for many novel application domains. Greedy algorithms have been shown in many multiagent contexts to be an efficient approach to arrive at good solutions quickly. In this work, we ask the following: Is there any way to improve the performance of greedy algorithms without sacrificing the linear run-time guarantees? For this, we...Show More
Who Gets the Whip? How Supplier Diversification Influences Bullwhip Effect in a Supply Chain
2023 62nd IEEE Conference on Decision and Control (CDC)
Year: 2023 | Conference Paper |
Cited by: Papers (1)
To navigate the evolving terrain of Supply Chains (SC), firms require new tools with broader applicability. Current research ignores the forest in favor of trees, with focal firms and serial networks assumed. This paper explicates a novel and scalable model for SC study at a broad level. We utilize the core of the model to observe the effect of structure and policy on demand disturbance in a SC as...Show More
Trajectories for the Optimal Collection of Information
Matthew R. Kirchner;David Grimsman;João P. Hespanha;Jason R. Marden
2023 IEEE Aerospace Conference
Year: 2023 | Conference Paper |
We study a scenario where an aircraft has multiple heterogeneous sensors collecting measurements to track a target vehicle of unknown location. The measurements are sampled along the flight path and our goals to optimize sensor placement to minimize estimation error. We select as a metric the Fisher Information Matrix (FIM), as “minimizing” the inverse of the FIM is required to achieve small estim...Show More
The Impact of Measurement Passing in Sensor Network Measurement Selection
David Grimsman;Matthew R. Kirchner;João P. Hespanha;Jason R. Marden
This article considers a set of sensors, which, as a group, are tasked with taking measurements of the environment and sending a small subset of the measurements to a centralized data fusion center, where the measurements will be used to estimate the overall state of the environment. The sensors’ goal is to send the most informative set of measurements so that the estimate is as accurate as possib...Show More
Valid Utility Games with Information Sharing Constraints
2022 IEEE 61st Conference on Decision and Control (CDC)
Year: 2022 | Conference Paper |
Cited by: Papers (1)
The use of game theoretic methods for control in multiagent systems has been an important topic in recent research. Valid utility games in particular have been used to model real-world problems; such games have the convenient property that the value of any decision set which is a Nash equilibrium of the game is guaranteed to be within 1/2 of the value of the optimal decision set. However, an impli...Show More
Developing Ecological Sensors for Real-Time Interpretation of Honeybee Communication
2022 IEEE Conference on Control Technology and Applications (CCTA)
Year: 2022 | Conference Paper |
This paper reports early success in using systems theoretic approaches to develop a real-time interpreter for honeybee communication. Foraging Western honeybees share location information of prime food sources through a particular dance. In this work we develop algorithms that translate time-series data of the dancing bees' locations into parameter estimates of the relevant food sources. The resul...Show More
In this work, we study the multi-agent decision problem where agents try to coordinate to optimize a given system-level objective. While solving for the global optimum is intractable in many cases, the greedy algorithm is a well-studied and efficient way to provide good approximate solutions - notably for submodular optimization problems. Executing the greedy algorithm requires the agents to be or...Show More
Game theoretic approaches have gained traction as robust methodologies for designing distributed local algorithms that induce a desired overall system configuration in multi-agent settings. However, much of the emphasis in these approaches is on providing asymptotic guarantees on the performance of a network of agents, and there is a gap in the study of efficiency guarantees along transients of th...Show More
The Cost of Denied Observation in Multiagent Submodular Optimization
David Grimsman;Joshua H. Seaton;Jason R. Marden;Philip N. Brown.
2020 59th IEEE Conference on Decision and Control (CDC)
Year: 2020 | Conference Paper |
Cited by: Papers (4)
A popular formalism for multiagent control applies tools from game theory, casting a multiagent decision problem as a cooperation-style game in which individual agents make local choices to optimize their own local utility functions in response to the observable choices made by other agents. When the system-level objective is submodular maximization, it is known that if every agent can observe the...Show More
The Impact of Message Passing in Agent-Based Submodular Maximization
David Grimsman;Matthew R. Kirchner;João P. Hespanha;Jason R. Marden
2020 59th IEEE Conference on Decision and Control (CDC)
Year: 2020 | Conference Paper |
Cited by: Papers (4)
Submodular maximization problems are a relevant model set for many real-world applications. Since these problems are generally NP-Hard, many methods have been developed to approximate the optimal solution in polynomial time. One such approach uses an agent-based greedy algorithm, where the goal is for each agent to choose an action from its action set such that the union of all actions chosen is a...Show More
We consider a two-player zero-sum network routing game in which a router wants to maximize the amount of legitimate traffic that flows from a given source node to a destination node and an attacker wants to block as much legitimate traffic as possible by flooding the network with malicious traffic. We address scenarios with asymmetric information, in which the router must reveal its policy before ...Show More
The submodular maximization problem is widely applicable in many engineering problems where objectives exhibit diminishing returns. While this problem is known to be NP-hard for certain subclasses of objective functions, there is a greedy algorithm which guarantees approximation at least 1/2 of the optimal solution. This greedy algorithm can be implemented with a set of agents, each making a decis...Show More
Model Boundary Approximation Method as a Unifying Framework for Balanced Truncation and Singular Perturbation Approximation
Philip E. Paré;David Grimsman;Alma T. Wilson;Mark K. Transtrum;Sean Warnick
We show that two widely accepted model reduction techniques, balanced truncation (BT) and balanced singular perturbation approximation (BSPA), can be derived as limiting approximations of a carefully constructed parameterization of linear time invariant systems by employing the model boundary approximation method (MBAM) [1]. We also show that MBAM provides a novel way to interpolate between BT and...Show More
The Impact of Information in Distributed Submodular Maximization
David Grimsman;Mohd. Shabbir Ali;João P. Hespanha;Jason R. Marden
The maximization of submodular functions is an NP-Hard problem for certain subclasses of functions, for which a simple greedy algorithm has been shown to guarantee a solution whose quality is within 1/2 of the optimal. When this algorithm is implemented in a distributed way, agents sequentially make decisions based on the decisions of all previous agents. This work explores how limited access to t...Show More
Strategic Information Sharing in Greedy Submodular Maximization
2018 IEEE Conference on Decision and Control (CDC)
Year: 2018 | Conference Paper |
Cited by: Papers (4)
Submodular maximization is an important problem with many applications in engineering, computer science, economics and social sciences. Since the problem is NP-Hard, a greedy algorithm has been developed, which gives an approximation within 1/2 of the optimal solution. This algorithm can be distributed among agents, each making local decisions and sharing that decision with other agents. Recent wo...Show More
Impact of information in greedy submodular maximization
David Grimsman;Mohd. Shabbir Ali;João P. Hespanha;Jason R. Marden
2017 IEEE 56th Annual Conference on Decision and Control (CDC)
Year: 2017 | Conference Paper |
Cited by: Papers (11)
The maximization of submodular functions is a well-studied topic due to its application in many common engineering problems. Because this problem has been shown to be NP-Hard for certain subclasses of functions, much work has been done to develop efficient algorithms to approximate an optimal solution. Among these is a simple greedy algorithm, which has been shown to guarantee a solution within 1/...Show More
Deadbeat-like approximations for sequencing non-rigid heaps
2016 IEEE 55th Conference on Decision and Control (CDC)
Year: 2016 | Conference Paper |
Cited by: Papers (1)
This paper demonstrates how the property of deadbeat controllers that drives discrete-time systems to their equilibria in a finite number of steps can be effectively used to develop systematic approximations of a certain class of heap systems, modeled here as input-quantized systems defined over the max-plus algebra. These systems are used to describe a class of flexible batch manufacturing proces...Show More
A case study of a systematic attack design method for critical infrastructure cyber-physical systems
D. Grimsman;V. Chetty;N. Woodbury;E. Vaziripour;S. Roy;D. Zappala;S. Warnick
2016 American Control Conference (ACC)
Year: 2016 | Conference Paper |
As cyber-physical systems continue to become more prevalent in critical infrastructures, security of these systems becomes paramount. Unlike purely cyber systems, cyber-physical systems allow cyber attackers to induce physical consequences. The purpose of this paper is to design a general attack methodology for cyber-physical systems and illustrate it using a case study of the Sevier River System ...Show More
IEEE Account
Purchase Details
Profile Information
Need Help?
- US & Canada: +1 800 678 4333
- Worldwide: +1 732 981 0060
- Contact & Support
- About IEEE Xplore
- Contact Us
- Help
- Accessibility
- Terms of Use
- Nondiscrimination Policy
- Sitemap
- Privacy & Opting Out of Cookies
A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity.
© Copyright 2025 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.