We consider the problem of decentralized sequential active hypothesis testing (DSAHT), where two transmitting
agents, each possessing a private message, are actively helping
a third agent–and each other–to learn the message pair over
a discrete memoryless multiple access channel (DM-MAC). The
third agent (receiver) observes the noisy channel output, which is
also available to the transmitting agents via noiseless feedback.
We formulate this problem as a decentralized dynamic team,
show that optimal transmission policies have a time-invariant
domain, and characterize the solution through a dynamic program. Several alternative formulations are discussed involving
time-homogenous cost functions and/or variable-length codes,
resulting in solutions described through fixed-point, Bellman-type
equations.
Subsequently, we make connections with the problem of
simplifying the multi-letter capacity expressions for the noiseless
feedback capacity of the DM-MAC. We show that restricting attention to distributions induced by optimal transmission schemes
for the DSAHT problem, without loss of optimality, transforms
the capacity expression, so that it can be thought of as the average
reward received by an appropriately defined stochastic dynamical
system with time-invariant state space.
more »
« less
Optimal Threshold-Based Distributed Control Policies for Persistent Monitoring on Graphs
We consider the optimal multi-agent persistent
monitoring problem defined by a team of cooperating agents
visiting a set of nodes (targets) on a graph with the objective
of minimizing a measure of overall node state uncertainty. The
solution to this problem involves agent trajectories defined both
by the sequence of nodes to be visited by each agent and
the amount of time spent at each node. We propose a class
of distributed threshold-based parametric controllers through
which agent transitions from one node to the next are controlled
by thresholds on the node uncertainty. The resulting behavior
of the agent-target system is described by a hybrid dynamic
system. This enables the use of Infinitesimal Perturbation Analysis
(IPA) to determine on-line optimal threshold parameters
through gradient descent and thus obtain optimal controllers
within this family of threshold-based policies. Simulations are
included to illustrate our results and compare them to optimal
solutions derived through dynamic programming.
more »
« less
- NSF-PAR ID:
- 10122831
- Date Published:
- Journal Name:
- Proceedings of the American Control Conference
- ISSN:
- 0743-1619
- Page Range / eLocation ID:
- 2030-2035
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Inertia from rotating masses of generators in power systems influence the instantaneous frequency change when an imbalance between electrical and mechanical power occurs. Renewable energy sources (RES), such as solar and wind power, are connected to the grid via electronic converters. RES connected through converters affect the system's inertia by decreasing it and making it time-varying. This new setting challenges the ability of current control schemes to maintain frequency stability. Proposing adequate controllers for this new paradigm is key for the performance and stability of future power grids. The contribution of this paper is a framework to learn sparse time-invariant frequency controllers in a power system network with a time-varying evolution of rotational inertia. We model power dynamics using a Switched-Affine hybrid system to consider different modes corresponding to different inertia coefficients. We design a controller that uses as features, i.e. input, the systems states. In other words, we design a control proportional to the angles and frequencies. We include virtual inertia in the controllers to ensure stability. One of our findings is that it is possible to restrict communication between the nodes by reducing the number of features in the controller (from 22 to 10 in our case study) without disrupting performance and stability. Furthermore, once communication between nodes has reached a threshold, increasing it beyond this threshold does not improve performance or stability. We find a correlation between optimal feature selection in sparse controllers and the topology of the network.more » « less
-
null (Ed.)We consider the problem of collective exploration of a known n- node edge-weighted graph by k mobile agents that have limited energy but are capable of energy transfers. The agents are initially placed at an arbitrary subset of nodes in the graph, and each agent has an initial, possibly different, amount of energy. The goal of the exploration problem is for every edge in the graph to be traversed by at least one agent. The amount of energy used by an agent to travel distance x is proportional to x. In our model, the agents can share energy when co-located: when two agents meet, one can transfer part of its energy to the other. For an n-node path, we give an O(n+k) time algorithm that either nds an exploration strategy, or reports that one does not exist. For an n-node tree with l leaves, we give an O(n+lk^2) algorithm that finds an exploration strategy if one exists. Finally, for the general graph case, we show that the problem of deciding if exploration is possible by energy-sharing agents is NP-hard, even for 3-regular graphs. In addition, we show that it is always possible to find an exploration strategy if the total energy of the agents is at least twice the total weight of the edges; moreover, this is asymptotically optimal.more » « less
-
Systems engineering processes coordinate the efforts of many individuals to design a complex system. However, the goals of the involved individuals do not necessarily align with the system-level goals. Everyone, including managers, systems engineers, subsystem engineers, component designers, and contractors, is self-interested. It is not currently understood how this discrepancy between organizational and personal goals affects the outcome of complex systems engineering processes. To answer this question, we need a systems engineering theory that accounts for human behavior. Such a theory can be ideally expressed as a dynamic hierarchical network game of incomplete information. The nodes of this network represent individual agents and the edges the transfer of information and incentives. All agents decide independently on how much effort they should devote to a delegated task by maximizing their expected utility; the expectation is over their beliefs about the actions of all other individuals and the moves of nature. An essential component of such a model is the quality function, defined as the map between an agent’s effort and the quality of their job outcome. In the economics literature, the quality function is assumed to be a linear function of effort with additive Gaussian noise. This simplistic assumption ignores two critical factors relevant to systems engineering: (1) the complexity of the design task, and (2) the problem-solving skills of the agent. Systems engineers establish their beliefs about these two factors through years of job experience. In this paper, we encode these beliefs in clear mathematical statements about the form of the quality function. Our approach proceeds in two steps: (1) we construct a generative stochastic model of the delegated task, and (2) we develop a reduced order representation suitable for use in a more extensive game-theoretic model of a systems engineering process. Focusing on the early design stages of a systems engineering process, we model the design task as a function maximization problem and, thus, we associate the systems engineer’s beliefs about the complexity of the task with their beliefs about the complexity of the function being maximized. Furthermore, we associate an agent’s problem solving-skills with the strategy they use to solve the underlying function maximization problem. We identify two agent types: “naïve” (follows a random search strategy) and “skillful” (follows a Bayesian global optimization strategy). Through an extensive simulation study, we show that the assumption of the linear quality function is only valid for small effort levels. In general, the quality function is an increasing, concave function with derivative and curvature that depend on the problem complexity and agent’s skills.more » « less
-
more » « less
Agent-based crawlers are commonly used in network maintenance and information gathering. In order not to disturb the main functionality of the system, whether acting at nodes or being in transit, they need to operate online, perform a single operation fast and use small memory. They should also be preferably deterministic, as crawling agents have limited capabilities of generating a large number of truly random bits. We consider a system in which an agent receives an update, typically an insertion or deletion, of some information upon visiting a node. On request, the agent needs to output hot information, i.e., with the net occurrence above certain frequency threshold. A desired time and memory complexity of such agent should be poly-logarithmic in the number of visited nodes and inversely proportional to the frequency threshold. Ours is the first such agent with rigorous analysis and a complementary almost-matching lower bound.
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
