Multi-Agent Reinforcement Learning (MARL) is a widely used technique for optimization in decentralised control problems. However, most applications of MARL are in static environments, and are not suitable when agent behaviour and environment conditions are dynamic and uncertain. Addressing uncertainty in such environments remains a challenging problem for MARL-based systems. The dynamic nature of the environment causes previous knowledge of how agents interact to become outdated. Advanced knowledge of potential changes through prediction significantly supports agents converging to near-optimal control solutions. In this paper we propose P-MARL, a decentralised MARL algorithm enhanced by a prediction mechanism that provides accurate information regarding up-coming changes in the environment. This prediction is achieved by employing an Artificial Neural Network combined with a Self-Organising Map that detects and matches changes in the environment. The proposed algorithm is validated in a realistic smart-grid scenario, and provides a 92 Pareto efficient solution to an electric vehicle charging problem.
The problem faced is essentially a more complex version of the Distributed Constraint Optimization Problem (DCOP) @cite_12 @cite_10 . While optimal solutions exist for DCOP, these are NP-complete and are not suitable for large scale problems. More than that, a DCOP involving uncertainty , precisely due to the uncertainty involved in the environment's next state, which does not pertain a fully defined problem. This particular type of uncertain DCOP has also been defined as a Distributed Coordination of Exploration and Exploitation (DCEE) problem by @cite_15 , as DCOP under Stochastic Uncertainty (StochDCOP) by @cite_9 or simply dubbed DCOP with uncertainty @cite_14 . Since the environment is uncertain and non-stationary, agent rewards will continuously change, therefore a trade-off between exploration and exploitation is necessary in order to lead to a sufficiently good solution. As the environment's state is not known ahead of time, and is continuously undergoing change, the design of agent behaviour becomes infeasible.
@cite_14 @cite_9 @cite_15 @cite_10 @cite_12
2307562442 2141256287 2118826835 2951198288
In this paper, we introduce DCOPs with uncertainty (U-DCOPs), a novel generalisation of the canonical DCOP framework where the outcomes of local functions are represented by random variables, and the global objective is to maximise the expectation of an arbitrary utility function (that represents the agents' risk-profile) applied over the sum of these local functions. We then develop U-GDL, a novel decentralised algorithm derived from Generalised Distributive Law (GDL) that optimally solves U-DCOPs. A key property of U-GDL that we show is necessary for optimality is that it keeps track of multiple non-dominated alternatives, and only discards those that are dominated (i.e. local partial solutions that can never turn into an expected global maximum regardless of the realisation of the random variables). As a direct consequence, we show that applying a standard DCOP algorithm to U-DCOP can result in arbitrarily poor solutions. We empirically evaluate U-GDL to determine its computational overhead and bandwidth requirements compared to a standard DCOP algorithm. In many real-life optimization problems involving multiple agents, the rewards are not necessarily known exactly in advance, but rather depend on sources of exogenous uncertainty. For instance, delivery companies might have to coordinate to choose who should serve which foreseen customer, under uncertainty in the locations of the customers. The framework of Distributed Constraint Optimization under Stochastic Uncertainty was proposed to model such problems; in this paper, we generalize this formalism by introducing the concept of evaluation functions that model various optimization criteria. We take the example of three such evaluation functions, expectation, consensus, and robustness, and we adapt and generalize two previous algorithms accordingly. Our experimental results on a class of Vehicle Routing Problems show that incomplete algorithms are not only cheaper than complete ones (in terms of simulated time, Non-Concurrent Constraint Checks, and information exchange), but they are also often able to find the optimal solution. We also show that exchanging more information about the dependencies of their respective cost functions on the sources of uncertainty can help the agents discover higher-quality solutions. Increasing teamwork between agents typically increases the performance of a multi-agent system, at the cost of increased communication and higher computational complexity. This work examines joint actions in the context of a multi-agent optimization problem where agents must cooperate to balance exploration and exploitation. Surprisingly, results show that increased teamwork can hurt agent performance, even when communication and computation costs are ignored, which we term the team uncertainty penalty. This paper introduces the above phenomena, analyzes it, and presents algorithms to reduce the effect of the penalty in our problem setting. Many multi-agent coordination problems can be represented as DCOPs. Motivated by task allocation in disaster response, we extend standard DCOP models to consider uncertain task rewards where the outcome of completing a task depends on its current state, which is randomly drawn from unknown distributions. The goal of solving this problem is to find a solution for all agents that minimizes the overall worst-case loss. This is a challenging problem for centralized algorithms because the search space grows exponentially with the number of agents and is nontrivial for standard DCOP algorithms we have. To address this, we propose a novel decentralized algorithm that incorporates Max-Sum with iterative constraint generation to solve the problem by passing messages among agents. By so doing, our approach scales well and can solve instances of the task allocation problem with hundreds of agents and tasks.