We provide a unifying framework for distributed convex optimization over time-varying networks, in the presence of constraints and uncertainty, features that are typically treated separately in the literature. We adopt a proximal minimization perspective and show that this set-up allows us to bypass the difficulties of existing algorithms while simplifying the underlying mathematical analysis. We develop an iterative algorithm and show the convergence of the resulting scheme to some optimizer of the centralized problem. To deal with the case where the agents' constraint sets are affected by a possibly common uncertainty vector, we follow a scenario-based methodology and offer probabilistic guarantees regarding the feasibility properties of the resulting solution. To this end, we provide a distributed implementation of the scenario approach, allowing agents to use a different set of uncertainty scenarios in their local optimization programs. The efficacy of our algorithm is demonstrated by means of a numerical example related to a regression problem subject to regularization.
We deal with decision making in a large-scale multi-agent system, where each agent aims at minimizing a local cost function subject to local constraints, and the local decision variables of all agents are coupled through a global constraint. We consider a cooperative framework where the multi-agent decision problem is formulated as a constrained optimization program with the sum of the local costs as global cost to be minimized with respect to the local decision variables of all agents, subject to both local and global constraints. We focus on a non-convex linear set-up where all costs and constraints are linear but local decision variables are discrete or include a discrete component, and propose a distributed iterative scheme based on dual decomposition and consensus to solve the resulting Mixed Integer Linear Program (MILP). Our approach extends recent results in the literature to a distributed set-up with a time-varying communication network and allows to: reduce the computational and communication effort, achieve resilience to communication failures, and also preserve privacy of local information. The approach is demonstrated on a numerical example of optimal charging of plug-in electric vehicles.
1 November 2019 in Nonlinear Analysis: Hybrid Systems
This article addresses the design of a fully automated photovoltaic (PV) power plant inspection process by a fleet of unmanned aerial and ground vehicles (UAVs/UGVs). More specifically, we consider the problem of assigning a set of target points to be inspected to a fleet of UAVs/UGVs so as to minimize the overall energy consumption while accounting for the battery degradation and the vehicle deterioration. In order to cope with the combinatorial complexity of the problem, we propose a suboptimal resolution strategy that integrates a graph-theoretic approach for local path planning at the robot level into a market-based approach for task assignment at the fleet level. The resulting coordination scheme is scalable and plug and play, and requires a minimal amount of information exchange between the robots and a central auctioneer, thus allowing the interoperability of different robotic platforms. Extensive numerical analysis via a multiagent simulation software shows the effectiveness of the proposed approach.
This paper introduces a new heuristic function that can be incorporated in any kinodynamic planner using motion primitives, to the purpose of increasing its convergence rate. The heuristic function is proven to be admissible and, hence, the optimality properties of the planning algorithm are preserved. Notably, it can be applied to planning problems with generic agent motion models and cost criteria, since it depends only on the database of motion primitives. The proposed heuristic has been integrated into a randomized sampling-based and a deterministic kinodynamic planner, and its effectiveness has been shown in numerical examples with different agent motion models and cost criteria.