SYMay 22, 2018
A Distributed Version of the Hungarian Method for Multi-Robot AssignmentSmriti Chopra, Giuseppe Notarstefano, Matthew Rice et al.
In this paper, we propose a distributed version of the Hungarian Method to solve the well known assignment problem. In the context of multi-robot applications, all robots cooperatively compute a common assignment that optimizes a given global criterion (e.g. the total distance traveled) within a finite set of local computations and communications over a peer-to-peer network. As a motivating application, we consider a class of multi-robot routing problems with "spatio-temporal" constraints, i.e. spatial targets that require servicing at particular time instants. As a means of demonstrating the theory developed in this paper, the robots cooperatively find online, suboptimal routes by applying an iterative version of the proposed algorithm, in a distributed and dynamic setting. As a concrete experimental test-bed, we provide an interactive "multi-robot orchestral" framework in which a team of robots cooperatively plays a piece of music on a so-called orchestral floor.
SYMar 25, 2013
A Polyhedral Approximation Framework for Convex and Robust Distributed OptimizationMathias Bürger, Giuseppe Notarstefano, Frank Allgöwer
In this paper we consider a general problem set-up for a wide class of convex and robust distributed optimization problems in peer-to-peer networks. In this set-up convex constraint sets are distributed to the network processors who have to compute the optimizer of a linear cost function subject to the constraints. We propose a novel fully distributed algorithm, named cutting-plane consensus, to solve the problem, based on an outer polyhedral approximation of the constraint sets. Processors running the algorithm compute and exchange linear approximations of their locally feasible sets. Independently of the number of processors in the network, each processor stores only a small number of linear constraints, making the algorithm scalable to large networks. The cutting-plane consensus algorithm is presented and analyzed for the general framework. Specifically, we prove that all processors running the algorithm agree on an optimizer of the global problem, and that the algorithm is tolerant to node and link failures as long as network connectivity is preserved. Then, the cutting plane consensus algorithm is specified to three different classes of distributed optimization problems, namely (i) inequality constrained problems, (ii) robust optimization problems, and (iii) almost separable optimization problems with separable objective functions and coupling constraints. For each one of these problem classes we solve a concrete problem that can be expressed in that framework and present computational results. That is, we show how to solve: position estimation in wireless sensor networks, a distributed robust linear program and, a distributed microgrid control problem.
OCSep 16, 2011
On the reachability and observability of path and cycle graphsGianfranco Parlangeli, Giuseppe Notarstefano
In this paper we investigate the reachability and observability properties of a network system, running a Laplacian based average consensus algorithm, when the communication graph is a path or a cycle. More in detail, we provide necessary and sufficient conditions, based on simple algebraic rules from number theory, to characterize all and only the nodes from which the network system is reachable (respectively observable). Interesting immediate corollaries of our results are: (i) a path graph is reachable (observable) from any single node if and only if the number of nodes of the graph is a power of two, $n=2^i, i\in \natural$, and (ii) a cycle is reachable (observable) from any pair of nodes if and only if $n$ is a prime number. For any set of control (observation) nodes, we provide a closed form expression for the (unreachable) unobservable eigenvalues and for the eigenvectors of the (unreachable) unobservable subsystem.
SYJun 14, 2018
Constraint Coupled Distributed Optimization: a Relaxation and Duality ApproachIvano Notarnicola, Giuseppe Notarstefano
In this paper we consider a general, challenging distributed optimization set-up 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.
DCMay 2, 2018
Distributed Big-Data Optimization via Block-Iterative Convexification and AveragingIvano Notarnicola, Ying Sun, Gesualdo Scutari et al.
In this paper, we study distributed big-data nonconvex optimization in multi-agent networks. We consider the (constrained) minimization of the sum of a smooth (possibly) nonconvex function, i.e., the agents' sum-utility, plus a convex (possibly) nonsmooth regularizer. Our interest is in big-data problems wherein there is a large number of variables to optimize. If treated by means of standard distributed optimization algorithms, these large-scale problems may be intractable, due to the prohibitive local computation and communication burden at each node. We propose a novel distributed solution method whereby at each iteration agents optimize and then communicate (in an uncoordinated fashion) only a subset of their decision variables. To deal with non-convexity of the cost function, the novel scheme hinges on Successive Convex Approximation (SCA) techniques coupled with i) a tracking mechanism instrumental to locally estimate gradient averages; and ii) a novel block-wise consensus-based protocol to perform local block-averaging operations and gradient tacking. Asymptotic convergence to stationary solutions of the nonconvex problem is established. Finally, numerical results show the effectiveness of the proposed algorithm and highlight how the block dimension impacts on the communication overhead and practical convergence speed.
DCMay 27, 2018
Distributed Big-Data Optimization via Block CommunicationsIvano Notarnicola, Ying Sun, Gesualdo Scutari et al.
We study distributed multi-agent large-scale optimization problems, wherein the cost function is composed of a smooth possibly nonconvex sum-utility plus a DC (Difference-of-Convex) regularizer. We consider the scenario where the dimension of the optimization variables is so large that optimizing and/or transmitting the entire set of variables could cause unaffordable computation and communication overhead. To address this issue, we propose the first distributed algorithm whereby agents optimize and communicate only a portion of their local variables. The scheme hinges on successive convex approximation (SCA) to handle the nonconvexity of the objective function, coupled with a novel block-signal tracking scheme, aiming at locally estimating the average of the agents' gradients. Asymptotic convergence to stationary solutions of the nonconvex problem is established. Numerical results on a sparse regression problem show the effectiveness of the proposed algorithm and the impact of the block size on its practical convergence speed and communication cost.
SYMay 22, 2018
Distributed Partitioned Big-Data Optimization via Asynchronous Dual DecompositionIvano Notarnicola, Ruggero Carli, Giuseppe Notarstefano
In this paper we consider a novel partitioned framework for distributed optimization in peer-to-peer networks. In several important applications the agents of a network have to solve an optimization problem with two key features: (i) the dimension of the decision variable depends on the network size, and (ii) cost function and constraints have a sparsity structure related to the communication graph. For this class of problems a straightforward application of existing consensus methods would show two inefficiencies: poor scalability and redundancy of shared information. We propose an asynchronous distributed algorithm, based on dual decomposition and coordinate methods, to solve partitioned optimization problems. We show that, by exploiting the problem structure, the solution can be partitioned among the nodes, so that each node just stores a local copy of a portion of the decision variable (rather than a copy of the entire decision vector) and solves a small-scale local problem.
SYJun 24, 2016
Asynchronous Distributed Optimization via Randomized Dual Proximal GradientIvano Notarnicola, Giuseppe Notarstefano
In this paper we consider distributed optimization problems in which the cost function is separable, i.e., a sum of possibly non-smooth functions all sharing a common variable, and can be split into a strongly convex term and a convex one. The second term is typically used to encode constraints or to regularize the solution. We propose a class of distributed optimization algorithms based on proximal gradient methods applied to the dual problem. We show that, by choosing suitable primal variable copies, the dual problem is itself separable when written in terms of conjugate functions, and the dual variables can be stacked into non-overlapping blocks associated to the computing nodes. We first show that a weighted proximal gradient on the dual function leads to a synchronous distributed algorithm with local dual proximal gradient updates at each node. Then, as main paper contribution, we develop asynchronous versions of the algorithm in which the node updates are triggered by local timers without any global iteration counter. The algorithms are shown to be proper randomized block-coordinate proximal gradient updates on the dual function.
SYMar 24, 2017
Final-State Constrained Optimal Control via a Projection Operator ApproachIvano Notarnicola, Florian A. Bayer, Giuseppe Notarstefano et al.
In this paper we develop a numerical method to solve nonlinear optimal control problems with final-state constraints. Specifically, we extend the PRojection Operator based Netwon's method for Trajectory Optimization (PRONTO), which was proposed by Hauser for unconstrained optimal control problems. While in the standard method final-state constraints can be only approximately handled by means of a terminal penalty, in this work we propose a methodology to meet the constraints exactly. Moreover, our method guarantees recursive feasibility of the final-state constraint. This is an appealing property especially in realtime applications in which one would like to be able to stop the computation even if the desired tolerance has not been reached, but still satisfy the constraints. Following the same conceptual idea of PRONTO, the proposed strategy is based on two main steps which (differently from the standard scheme) preserve the feasibility of the final-state constraints: (i) solve a quadratic approximation of the nonlinear problem to find a descent direction, and (ii) get a (feasible) trajectory by means of a feedback law (which turns out to be a nonlinear projection operator). To find the (feasible) descent direction we take advantage of final-state constrained Linear Quadratic optimal control methods, while the second step is performed by suitably designing a constrained version of the trajectory tracking projection operator. The effectiveness of the proposed strategy is tested on the optimal state transfer of an inverted pendulum.
SYNov 8, 2018
A Primal Decomposition Method with Suboptimality Bounds for Distributed Mixed-Integer Linear ProgrammingAndrea Camisa, Ivano Notarnicola, Giuseppe Notarstefano
In this paper we deal with a network of agents seeking to solve in a distributed way Mixed-Integer Linear Programs (MILPs) with a coupling constraint (modeling a limited shared resource) and local constraints. MILPs are NP-hard problems and several challenges arise in a distributed framework, so that looking for suboptimal solutions is of interest. To achieve this goal, the presence of a linear coupling calls for tailored decomposition approaches. We propose a fully distributed algorithm based on a primal decomposition approach and a suitable tightening of the coupling constraints. Agents repeatedly update local allocation vectors, which converge to an optimal resource allocation of an approximate version of the original problem. Based on such allocation vectors, agents are able to (locally) compute a mixed-integer solution, which is guaranteed to be feasible after a sufficiently large time. Asymptotic and finite-time suboptimality bounds are established for the computed solution. Numerical simulations highlight the efficacy of the proposed methodology.
DCMar 24, 2017
A duality-based approach for distributed min-max optimization with application to demand side managementIvano Notarnicola, Mauro Franceschelli, Giuseppe Notarstefano
In this paper we consider a distributed optimization scenario in which a set of processors aims at minimizing the maximum of a collection of "separable convex functions" subject to local constraints. This set-up is motivated by peak-demand minimization problems in smart grids. Here, the goal is to minimize the peak value over a finite horizon with: (i) the demand at each time instant being the sum of contributions from different devices, and (ii) the local states at different time instants being coupled through local dynamics. The min-max structure and the double coupling (through the devices and over the time horizon) makes this problem challenging in a distributed set-up (e.g., well-known distributed dual decomposition approaches cannot be applied). We propose a distributed algorithm based on the combination of duality methods and properties from min-max optimization. Specifically, we derive a series of equivalent problems by introducing ad-hoc slack variables and by going back and forth from primal and dual formulations. On the resulting problem we apply a dual subgradient method, which turns out to be a distributed algorithm. We prove the correctness of the proposed algorithm and show its effectiveness via numerical computations.
SYApr 24, 2018
A Duality-Based Approach for Distributed Optimization with Coupling ConstraintsIvano Notarnicola, Giuseppe Notarstefano
In this paper we consider a distributed optimization scenario in which a set of agents has to solve a convex optimization problem with separable cost function, local constraint sets and a coupling inequality constraint. We propose a novel 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 solves a local version of the original problem relaxation, and updates suitable dual variables. We prove the algorithm correctness and show its effectiveness via numerical computations.
DCMar 24, 2017
A randomized primal distributed algorithm for partitioned and big-data non-convex optimizationIvano Notarnicola, Giuseppe Notarstefano
In this paper we consider a distributed optimization scenario in which the aggregate objective function to minimize is partitioned, big-data and possibly non-convex. Specifically, we focus on a set-up in which the dimension of the decision variable depends on the network size as well as the number of local functions, but each local function handled by a node depends only on a (small) portion of the entire optimization variable. This problem set-up has been shown to appear in many interesting network application scenarios. As main paper contribution, we develop a simple, primal distributed algorithm to solve the optimization problem, based on a randomized descent approach, which works under asynchronous gossip communication. We prove that the proposed asynchronous algorithm is a proper, ad-hoc version of a coordinate descent method and thus converges to a stationary point. To show the effectiveness of the proposed algorithm, we also present numerical simulations on a non-convex quadratic program, which confirm the theoretical results.
OCFeb 16, 2017
A Bayesian framework for distributed estimation of arrival rates in asynchronous networksAngelo Coluccia, Giuseppe Notarstefano
In this paper we consider a network of agents monitoring a spatially distributed arrival process. Each node measures the number of arrivals seen at its monitoring point in a given time-interval with the objective of estimating the unknown local arrival rate. We propose an asynchronous distributed approach based on a Bayesian model with unknown hyperparameter, where each node computes the minimum mean square error (MMSE) estimator of its local arrival rate in a distributed way. As a result, the estimation at each node "optimally" fuses the information from the whole network through a distributed optimization algorithm. Moreover, we propose an ad-hoc distributed estimator, based on a consensus algorithm for time-varying and directed graphs, which exhibits reduced complexity and exponential convergence. We analyze the performance of the proposed distributed estimators, showing that they: (i) are reliable even in presence of limited local data, and (ii) improve the estimation accuracy compared to the purely decentralized setup. Finally, we provide a statistical characterization of the proposed estimators. In particular, for the ad-hoc estimator, we show that as the number of nodes goes to infinity its mean square error converges to the optimal one. Numerical Monte Carlo simulations confirm the theoretical characterization and highlight the appealing performances of the estimators.
SYMay 22, 2018
An Empirical Bayes Approach for Distributed Estimation of Spatial FieldsFrancesco Sasso, Angelo Coluccia, Giuseppe Notarstefano
In this paper we consider a network of spatially distributed sensors which collect measurement samples of a spatial field, and aim at estimating in a distributed way (without any central coordinator) the entire field by suitably fusing all network data. We propose a general probabilistic model that can handle both partial knowledge of the physics generating the spatial field as well as a purely data-driven inference. Specifically, we adopt an Empirical Bayes approach in which the spatial field is modeled as a Gaussian Process, whose mean function is described by means of parametrized equations. We characterize the Empirical Bayes estimator when nodes are heterogeneous, i.e., perform a different number of measurements. Moreover, by exploiting the sparsity of both the covariance and the (parametrized) mean function of the Gaussian Process, we are able to design a distributed spatial field estimator. We corroborate the theoretical results with two numerical simulations: a stationary temperature field estimation in which the field is described by a partial differential (heat) equation, and a data driven inference in which the mean is parametrized by a cubic spline.
SYDec 14, 2018
Distributed Submodular Minimization over Networks: a Greedy Column Generation ApproachAndrea Testa, Ivano Notarnicola, Giuseppe Notarstefano
Submodular optimization is a special class of combinatorial optimization arising in several machine learning problems, but also in cooperative control of complex systems. In this paper, we consider agents in an asynchronous, unreliable and time-varying directed network that aim at cooperatively solving submodular minimization problems in a fully distributed way. The challenge is that the (submodular) objective set-function is only partially known by agents, that is, each one is able to evaluate the function only for subsets including itself. We propose a distributed algorithm based on a proper linear programming reformulation of the combinatorial problem. Our algorithm builds on a column generation approach in which each agent maintains a local candidate basis and locally generates columns with a suitable greedy inner routine. A key interesting feature of the proposed algorithm is that the pricing problem, which involves an exponential number of constraints, is solved by the agents through a polynomial time greedy algorithm. We prove that the proposed distributed algorithm converges in finite time to an optimal solution of the submodular minimization problem and we corroborate the theoretical results by performing numerical computations on instances of the $s$--$t$ minimum graph cut problem.
OCFeb 15, 2017
A core-set approach for distributed quadratic programming in big-data classificationGiuseppe Notarstefano
A new challenge for learning algorithms in cyber-physical network systems is the distributed solution of big-data classification problems, i.e., problems in which both the number of training samples and their dimension is high. Motivated by several problem set-ups in Machine Learning, in this paper we consider a special class of quadratic optimization problems involving a "large" number of input data, whose dimension is "big". To solve these quadratic optimization problems over peer-to-peer networks, we propose an asynchronous, distributed algorithm that scales with both the number and the dimension of the input data (training samples in the classification problem). The proposed distributed optimization algorithm relies on the notion of "core-set" which is used in geometric optimization to approximate the value function associated to a given set of points with a smaller subset of points. By computing local core-sets on a smaller version of the global problem and exchanging them with neighbors, the nodes reach consensus on a set of active constraints representing an approximate solution for the global quadratic program.
31.0SYApr 10
Stability-Certified On-Policy Data-Driven LQR via Recursive Learning and Policy GradientLorenzo Sforni, Guido Carnevale, Ivano Notarnicola et al.
In this paper, we investigate a data-driven framework to solve Linear Quadratic Regulator (LQR) problems when the dynamics is unknown, with the additional challenge of providing stability certificates for the overall learning and control scheme. Specifically, in the proposed on-policy learning framework, the control input is applied to the actual (unknown) linear system while iteratively optimized. We propose a learning and control procedure, termed Relearn LQR, that combines a recursive least squares method with a direct policy search based on the gradient method. The resulting scheme is analyzed by modeling it as a feedback-interconnected nonlinear dynamical system. A Lyapunov-based approach, exploiting averaging and timescale separation theories for nonlinear systems, allows us to provide formal stability guarantees for the whole interconnected scheme. The effectiveness of the proposed strategy is corroborated by numerical simulations, where Relearn LQR is deployed on an aircraft control problem, with both static and drifting parameters.
82.5OCApr 2
Nonlinear MPC for Feedback-Interconnected Systems: a Suboptimal and Reduced-Order Model ApproachStefano Di Gregorio, Guido Carnevale, Giuseppe Notarstefano
In this paper, we propose a suboptimal and reduced-order Model Predictive Control (MPC) architecture for discrete-time feedback-interconnected systems. The numerical MPC solver: (i) acts suboptimally, performing only a finite number of optimization iterations at each sampling instant, and (ii) relies only on a reduced-order model that neglects part of the system dynamics, either due to unmodeled effects or the presence of a low-level compensator. We prove that the closed-loop system resulting from the interconnection of the suboptimal and reduced-order MPC optimizer with the full-order plant has a globally exponentially stable equilibrium point. Specifically, we employ timescale separation arguments to characterize the interaction between the components of the feedback-interconnected system. The analysis relies on an appropriately tuned timescale parameter accounting for how fast the system dynamics are sampled. The theoretical results are validated through numerical simulations on a mechatronic system consisting of a pendulum actuated by a DC motor.
ROOct 26, 2020Code
ChoiRbot: A ROS 2 Toolbox for Cooperative RoboticsAndrea Testa, Andrea Camisa, Giuseppe Notarstefano
In this paper, 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.
12.7OCApr 22
On Reward-Balancing Methods for Reinforcement LearningSimone Baroncini, Bahman Gharesifard, Giuseppe Notarstefano
This paper investigates the so-called reward-balancing methods, a novel class of algorithms for solving discounted-return reinforcement learning (RL) problems. These methods consist of iteratively adjusting the reward function to transform the RL problem into an equivalent one in which the optimal policies are greedy. For this procedure, referred to as normalization process, we provide a theoretical analysis of the involved transformations, emphasizing their algebraic structure. Then, we introduce a control-theoretic reformulation, recasting the reward-balancing procedure into an optimal control framework. The approach is further extended to address model uncertainty through stochastic model sampling, yielding normalization guarantees and probabilistic bounds on stochastic fluctuations. Using the proposed optimal control framework within a scenario model predictive control (MPC) setting, we demonstrate, through simulation studies, performance improvements over the current state-of-the-art.
70.6OCApr 2
Safe Control of Feedback-Interconnected Systems via Singular PerturbationsStefano Di Gregorio, Guido Carnevale, Giuseppe Notarstefano
Control Barrier Functions (CBFs) have emerged as a powerful tool in the design of safety-critical controllers for nonlinear systems. In modern applications, complex systems often involve the feedback interconnection of subsystems evolving at different timescales, e.g., two parts from different physical domains (e.g., the electrical and mechanical parts of robotic systems) or a physical plant and an (optimization or control) algorithm. In these scenarios, safety constraints often involve only a portion of the overall system. Inspired by singular perturbations for stability analysis, we develop a formal procedure to lift a safety certificate designed on a reduced-order model to the overall feedback-interconnected system. Specifically, we show that under a sufficient timescale separation between slow and fast dynamics, a composite CBF can be designed to certify the forward invariance of the safe set for the interconnected system. As a result, the online safety filter only needs to be solved for the lower-dimensional, reduced-order model. We numerically test the proposed approach on: (i) a robotic arm with joint motor dynamics, and (ii) a physical plant driven by an optimization algorithm.
ROApr 6, 2021
Multi-Robot Pickup and Delivery via Distributed Resource AllocationAndrea Camisa, Andrea Testa, Giuseppe Notarstefano
In this paper, we consider a large-scale instance of the classical Pickup-and-Delivery Vehicle Routing Problem (PDVRP) that must be solved by a network of mobile cooperating robots. Robots must self-coordinate and self-allocate a set of pickup/delivery tasks while minimizing a given cost figure. This results in a large, challenging Mixed-Integer Linear Problem that must be cooperatively solved % without a central coordinator. We propose a distributed algorithm based on a primal decomposition approach that provides a feasible solution to the problem in finite time. An interesting feature of the proposed scheme is that each robot computes only its own block of solution, thereby preserving privacy of sensible information. The algorithm also exhibits attractive scalability properties that guarantee solvability of the problem even in large networks. To the best of our knowledge, this is the first attempt to provide a scalable distributed solution to the problem. The algorithm is first tested through Gazebo simulations on a ROS~2 platform, highlighting the effectiveness of the proposed solution. Finally, experiments on a real testbed with a team of ground and aerial robots are provided.
OCSep 3, 2020
GTAdam: Gradient Tracking with Adaptive Momentum for Distributed Online OptimizationGuido Carnevale, Francesco Farina, Ivano Notarnicola et al.
This paper deals with a network of computing agents aiming to solve an online optimization problem in a distributed fashion, i.e., by means of local computation and communication, without any central coordinator. We propose the gradient tracking with adaptive momentum estimation (GTAdam) distributed algorithm, which combines a gradient tracking mechanism with first and second order momentum estimates of the gradient. The algorithm is analyzed in the online setting for strongly convex cost functions with Lipschitz continuous gradients. We provide an upper bound for the dynamic regret given by a term related to the initial conditions and another term related to the temporal variations of the objective functions. Moreover, a linear convergence rate is guaranteed in the static setup. The algorithm is tested on a time-varying classification problem, on a (moving) target localization problem, and in a stochastic optimization setup from image classification. In these numerical experiments from multi-agent learning, GTAdam outperforms state-of-the-art distributed optimization methods.
OCMay 31, 2019
Distributed Submodular Minimization via Block-Wise Updates and CommunicationsAndrea Testa, Francesco Farina, Giuseppe Notarstefano
In this paper we deal with a network of computing agents with local processing and neighboring communication capabilities that aim at solving (without any central unit) a submodular optimization problem. The cost function is the sum of many local submodular functions and each agent in the network has access to one function in the sum only. In this \emph{distributed} set-up, in order to preserve their own privacy, agents communicate with neighbors but do not share their local cost functions. We propose a distributed algorithm in which agents resort to the Lovàsz extension of their local submodular functions and perform local updates and communications in terms of single blocks of the entire optimization variable. Updates are performed by means of a greedy algorithm which is run only until the selected block is computed, thus resulting in a reduced computational burden. The proposed algorithm is shown to converge in expected value to the optimal cost of the problem, and an approximate solution to the submodular problem is retrieved by a thresholding operation. As an application, we consider a distributed image segmentation problem in which each agent has access only to a portion of the entire image. While agents cannot segment the entire image on their own, they correctly complete the task by cooperating through the proposed distributed algorithm.
SYJun 4, 2018
Distributed Learning from Interactions in Social NetworksFrancesco Sasso, Angelo Coluccia, Giuseppe Notarstefano
We consider a network scenario in which agents can evaluate each other according to a score graph that models some interactions. The goal is to design a distributed protocol, run by the agents, that allows 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 show that each agent can learn its state by means of a local Bayesian classifier and a (centralized) Maximum-Likelihood (ML) estimator of parameter-hyperparameter that combines plain ML and Empirical Bayes approaches. By using tools from graphical models, which allow us to gain insight on conditional dependencies of scores and states, we provide a relaxed probabilistic model that ultimately leads to a parameter-hyperparameter estimator amenable to distributed computation. To highlight the appropriateness of the proposed relaxation, we demonstrate the distributed estimators on a social interaction set-up for user profiling.
OCJun 13, 2017
Interaction-Based Distributed Learning in Cyber-Physical and Social NetworksFrancesco Sasso, Angelo Coluccia, Giuseppe Notarstefano
In 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 means of a local Bayesian classifier and a (centralized) Maximum-Likelihood (ML) estimator of the parameter-hyperparameter that combines plain ML and Empirical Bayes approaches. By using tools from graphical models, which allow us to gain insight on conditional dependences of scores and states, we provide two relaxed probabilistic models that ultimately lead to ML parameter-hyperparameter estimators amenable to distributed computation. In order to highlight the appropriateness of the proposed relaxations, we demonstrate the distributed estimators on a machine-to-machine testing set-up for anomaly detection and on a social interaction set-up for user profiling.
ROOct 5, 2016
From Tracking to Robust Maneuver Regulation: an Easy-to-Design Approach for VTOL Aerial RobotsSara Spedicato, Antonio Franchi, Giuseppe Notarstefano
In this paper we present a maneuver regulation scheme for Vertical Take-Off and Landing (VTOL) micro aerial vehicles (MAV). Differently from standard trajectory tracking, maneuver regulation has an intrinsic robustness due to the fact that the vehicle is not required to chase a virtual target, but just to stay on a (properly designed) desired path with a given velocity profile. In this paper we show how a robust maneuver regulation controller can be easily designed by converting an existing tracking scheme. The resulting maneuvering controller has three main appealing features, namely it: (i) inherits the robustness properties of the tracking controller, (ii) gains the appealing features of maneuver regulation, and (iii) does not need any additional tuning with respect to the tracking controller. We prove the correctness of the proposed scheme and show its effectiveness in experiments on a nano-quadrotor. In particular, we show on a nontrivial maneuver how external disturbances acting on the quadrotor cause instabilities in the standard tracking, while marginally affect the maneuver regulation scheme.