1,721,073 research outputs found
Generalized Assignment for Multirobot Systems via Distributed Branch-and-Price
Full text linkIn this article, we consider a network of agents that has to self-assign a set of tasks while respecting resource constraints. One possible formulation is the generalized assignment problem, where the goal is to find a maximum payoff while satisfying capability constraints. We propose a purely distributed branch-and-price algorithm to solve this problem in a cooperative fashion. Inspired by classical (centralized) branch-and-price schemes, in the proposed algorithm, each agent locally solves small linear programs, generates columns by solving simple knapsack problems, and communicates to its neighbors a fixed number of basic columns. We prove finite-time convergence of the algorithm to an optimal solution of the problem. Then, we apply the proposed scheme to a generalized assignment scenario, in which a team of robots has to serve a set of tasks. We implement the proposed algorithm in a Robot Operating System testbed and provide experiments for a team of heterogeneous robots solving the assignment problem
A Distributed Mixed-Integer Framework to Stochastic Optimal Microgrid Control
Full text linkThis article deals with distributed control of microgrids composed of storages, generators, renewable energy sources, and critical and controllable loads. We consider a stochastic formulation of the optimal control problem associated with the microgrid that appropriately takes into account the unpredictable nature of the power generated by renewables. The resulting problem is a mixed-integer linear program and is NP-hard and nonconvex. Moreover, the peculiarity of the considered framework is that no central unit can be used to perform the optimization, but rather the units must cooperate with each other by means of neighboring communication. To solve the problem, we resort to a distributed methodology based on a primal decomposition approach. The resulting algorithm is able to compute high-quality feasible solutions to a two-stage stochastic optimization problem, for which we also provide a theoretical upper bound on the constraint violation. Finally, a Monte Carlo numerical computation on a scenario with a large number of devices shows the efficacy of the proposed distributed control approach. The numerical experiments are performed on realistic scenarios obtained from Generative Adversarial Networks (GANs) trained an open-source historical dataset of the EU
A Learning-based Distributed Algorithm for Personalized Aggregative Optimization
No full textThis paper addresses distributed aggregative optimization, i.e., a recently emerged framework in which agents in a network want to minimize the sum of local objective functions depending both on a local decision variable and on an aggregated version of all the variables (e.g., the mean). We consider a "personalized"set-up in which each local function is given by the sum of a known term and an unknown one capturing the user's dissatisfaction. We propose a novel data-driven distributed algorithm taking advantage of users' noisy feedback to learn the parameters of the unknown function concurrently with the optimization steps. We prove an upper bound for the dynamic regret related to (i) the initial conditions, (ii) the temporal variations of the objective functions, and (iii) the learning errors. Moreover, by considering the average dynamic regret, we prove that both initial conditions and learning errors do not affect the asymptotic performance of the algorithm. Finally, a numerical simulation in the context of opinion dynamics validates our findings
Constraint-Coupled Distributed Optimization: A Relaxation and Duality Approach
Full text linkIn this paper, we consider a general challenging distributed optimization setup arising in several important network control applications. Agents of a network want to minimize the sum of local cost functions, each one depending on a local variable, subject to local and coupling constraints, with the latter involving all the decision variables. We propose a novel fully distributed algorithm based on a relaxation of the primal problem and an elegant exploration of duality theory. Despite its complex derivation, based on several duality steps, the distributed algorithm has a very simple and intuitive structure. That is, each node finds a primal-dual optimal solution pair of a local relaxed version of the original problem and then updates suitable auxiliary local variables. We prove that agents asymptotically compute their portion of an optimal (feasible) solution of the original problem. This primal recovery property is obtained without any averaging mechanism typically used in dual decomposition methods. To corroborate the theoretical results, we show how the methodology applies to an instance of a distributed model-predictive control scheme in a microgrid control scenario
Nonconvex Distributed Optimization via Lasalle and Singular Perturbations
Full text linkIn this letter we address nonconvex distributed consensus optimization, a popular framework for distributed big-data analytics and learning. We consider the Gradient Tracking algorithm and, by resorting to an elegant system theoretical analysis, we show that agent estimates asymptotically reach consensus to a stationary point. We take advantage of suitable coordinates to write the Gradient Tracking as the interconnection of a fast dynamics and a slow one. To use a singular perturbation analysis, we separately study two auxiliary subsystems called boundary layer and reduced systems, respectively. We provide a Lyapunov function for the boundary layer system and use Lasalle-based arguments to show that trajectories of the reduced system converge to the set of stationary points. Finally, a customized version of a Lasalle's Invariance Principle for singularly perturbed systems is proved to show the convergence properties of the Gradient Tracking
Timescale Separation for Discrete-Time Nonlinear Stochastic Systems
No full textIn this letter, we present a timescale separation result for discrete-time stochastic systems. We consider the feedback interconnection of two stochastic subsystems, referred to as fast and slow dynamics, and analyze them by combining timescale separation theory and stochastic LaSalle and Lyapunov theorems. Specifically, we separately focus on two auxiliary dynamics, named the boundary layer system (related to the fast part) and the reduced system (related to the slow part). For each of these auxiliary schemes, we identify a stochastic LaSalle testing condition and guarantee that satisfying both conditions is sufficient to prove almost sure LaSalle-type convergence of the original stochastic interconnection. Finally, we focus on stochastic optimization and exploit this new tool to prove almost sure convergence of the popular Stochastic Averaged Gradient and SAGA algorithms in a general nonconvex framework
Interaction-Based Distributed Learning in Cyber-Physical and Social Networks
Full text linkIn this paper, we consider a network scenario in which agents can evaluate each other according to a score graph that models some physical or social interaction. The goal is to design a distributed protocol, run by the agents, allowing them to learn their unknown state among a finite set of possible values. We propose a Bayesian framework in which scores and states are associated to probabilistic events with unknown parameters and hyperparameters, respectively. We prove that each agent can learn its state by combining a local Bayesian classifier with a (centralized) Maximum Likelihood (ML) estimator of the parameter-hyperparameter. To overcome the intractability of the ML problem, we provide two relaxed probabilistic models that lead to distributed estimation schemes with affordable complexity. In order to highlight the appropriateness of the proposed relaxations, we demonstrate the distributed estimators on a machine-to-machine testing setup for anomaly detection and on a social interaction setup for user profiling
Distributed Mixed-Integer Linear Programming via Cut Generation and Constraint Exchange
Full text linkMany problems of interest for cyber-physical network systems can be formulated as mixed-integer linear programs in which the constraints are distributed among the agents. In this paper, we propose a distributed algorithmic framework to solve this class of optimization problems in a peer-to-peer network with no coordinator and with limited computation and communication capabilities. At each communication round, agents locally solve a small linear program, generate suitable cutting planes, and communicate a fixed number of active constraints. Within the distributed framework, we first propose an algorithm that, under the assumption of integer-valued optimal cost, guarantees finite-time convergence to an optimal solution. Second, we propose an algorithm for general problems that provides a suboptimal solution up to a given tolerance in a finite number of communication rounds. Both algorithms work under asynchronous, directed, unreliable networks. Finally, through numerical computations, we analyze the algorithm scalability in terms of the network size. Moreover, for a multi-agent multi-task assignment problem, we show, consistently with the theory, its robustness to packet loss
ChoiRbot: A ROS 2 Toolbox for Cooperative Robotics
Full text linkIn this letter, we introduce ChoiRbot, a toolbox for distributed cooperative robotics based on the novel Robot Operating System (ROS) 2. ChoiRbot provides a fully-functional toolset to execute complex distributed multi-robot tasks, either in simulation or experimentally, with a particular focus on networks of heterogeneous robots without a central coordinator. Thanks to its modular structure, ChoiRbot allows for a highly straight implementation of optimization-based distributed control schemes, such as distributed optimal control, model predictive control, task assignment, in which local computation and communication with neighboring robots are alternated. To this end, the toolbox provides functionalities for the solution of distributed optimization problems. The package can be also used to implement distributed feedback laws that do not need optimization features but do require the exchange of information among robots. The potential of the toolbox is illustrated with simulations and experiments on distributed robotics scenarios with mobile ground robots. The ChoiRbot toolbox is available at https://github.com/OPT4SMART/choirbot
Structured-policy Q-learning: an LMI-based Design Strategy for Distributed Reinforcement Learning
No full textIn this paper, we consider a Linear Quadratic optimal control problem with the assumptions that the system dynamics is unknown and that the designed feedback control has to comply with a desired sparsity pattern. An important application where this set-up arises is distributed control of network systems, where the aim is to find an optimal sparse controller matching the communication graph. To tackle the problem, we propose a Reinforcement Learning framework based on a Q-learning scheme preserving a desired policy structure. At each time step the performance of the current candidate feedback is first evaluated through the computation of its Q-function, and then a new sparse feedback matrix, improving on the previous one, is computed. We prove that the scheme produces at each iteration a stabilizing feedback control with the desired sparsity and with non-increasing cost, which in turns indicates that every limit point of the computed feedback matrices is sparse and stabilizing. The algorithm is numerically tested on a distributed control scenario with randomly generated graph and unstable dynamics
- …
