Scaling dcop algorithms for cooperative multi-agent coordination

Resumen

This dissertation focuses on scaling up distributed constraint optimization problem (DCOP) solving algorithms to cope with larger-scale and dynamic applications. The DCOP framework represents a coordination problem as a distributed function to optimize by a group of agents. Although it has been employed to tackle numerous application domains (e.g., meeting scheduling, sensor networks), DCOPs are NP-hard, and thus solving them poses challenging scalability issues. Here we identify the Generalized Distributive Law (GDL) as a promising foundation to build complete and approximate DCOP algorithms. On optimal solving, GDL-based algorithms offer scale-up opportunities thanks to their exponential complexity on the treewidth instead of on the number of agents. Firstly, we scale up the GDL with function filtering algorithm, a state-of-the-art algorithm that employs upper and lower bounds to prune (filter) suboptimal solutions. We present novel techniques to improve the quality of these bounds, hence reducing the algorithm's computation and communication costs. Our experiments show that agents using our techniques can solve larger problems than the state-of-the-art. Thereafter, we introduce a novel scheme that allows agents to trade off computation and communication costs. Using this scheme, we propose novel, optimal GDL algorithms, including the best-in-class for communication-constrained and for computation-constrained applications. Secondly, we turn our attention to larger-scale, dynamic applications for which optimality is not an option. We introduce the Limited-range Online Routing Problem (LORP) as a benchmark for such applications, along with the MASPlanes toolkit to facilitate research on it. Then we present LORP solutions based on Max-Sum, the approximate version of GDL. Using Tractable Higher-Order Potentials (THOPs), we show that it is possible to reduce Max-Sum's complexity from exponential to polynomial. Empirically, our novel approach for the LORP achieves better results than current state-of-the-art methods. However, THOP models are harder to design than standard DCOP models. Therefore, we also introduce a methodology for developing such models for complex applications involving heterogeneous teams of agents. Finally, we validate our methodology by implementing an inter-team coordination model for the RoboCup Rescue simulation that empirically yields notable performance benefits. In summary, this thesis widens the range of applications that optimal and approximate GDL-based DCOP algorithms can successfully tackle.