Decentralized online planning, such as decentralized Monte Carlo tree search (MCTS), is an attractive paradigm for cooperative multi-agent systems in information-gathering tasks. However, current MCTS algorithms implicitly assume that agents are always available and actively contributing throughout the mission. In realistic, dynamic, and volatile environments, agent attrition is common and can severely degrade performance. In this paper, we demonstrate that agent attrition can cause current decentralized MCTS methods to perform arbitrarily worse than the optimum, particularly in applications with submodular reward functions. To address this issue, we propose Attritable Monte Carlo Tree Search (A-MCTS), a decentralized MCTS algorithm that adapts quickly and efficiently to reductions in the set of active agents. Our key idea is to have each agent build its search tree using the global utility function while coordinating with teammates through a regret-matching algorithm. Our theoretical analysis and extensive simulations show that A-MCTS maintains effective coordination among agents, even in high-attrition environments. We evaluate our approach in different information-gathering problems by modeling realistic reference scenarios. Results highlight that A-MCTS substantially improves over the main competing methods regarding global utility, scalability, and robustness.

Decentralized planning is a key element of cooperative multi-agent systems for information gathering tasks. However, despite the high frequency of agent failures in realistic large deployment scenarios, current approaches perform poorly in the presence of failures, by not converging at all, and/or by making very inefficient use of resources (e.g. energy). In this work, we propose Attritable MCTS (A-MCTS), a decentralized MCTS algorithm capable of timely and efficient adaptation to changes in the set of active agents. It is based on the use of a global reward function for the estimation of each agent’s local contribution, and regret matching for coordination. We evaluate its effectiveness in realistic data-harvesting problems under different scenarios. We show both theoretically and experimentally that A-MCTS enables efficient adaptation even under high failure rates. Results suggest that, in the presence of frequent failures, our solution improves substantially over the best existing approaches in terms of global utility and scalability.

Coordinated multi-robot systems are an effective way to harvest data from sensor networks and implement active perception strategies. However, achieving efficient coordination in a way that guarantees a target QoS while adapting dynamically to changes (in the environment and/or in the system) is a key open issue. In this paper, we propose a novel decentralized Monte Carlo Tree Search (MCTS) algorithm for dynamic environments that allows agents to optimize their own actions while achieving some form of coordination. Its main underlying idea is to balance adaptively the exploration-exploitation trade-off to deal effectively with changes in the environment while filtering out outdated and irrelevant samples via a sliding window mechanism. We show both theoretically and through simulations that in dynamic environments our algorithm provides a log-factor (in terms of time steps) smaller regret than state-of-the-art decentralized multi-agent planning methods. We instantiate our approach to the problem of underwater data collection, showing in a variety of different settings that our approach greatly outperforms the best-competing approaches, both in terms of convergence speed and global utility.

Coordinated multi-robot systems are an effective way to harvest data from sensor networks and to implement active perception strategies. However, achieving efficient coordination in a way which guarantees a target QoS while adapting dynamically to changes (in the environment, due to sensors’ mobility, and/or in the value of harvested data) is to date a key open issue. In this paper, we propose a novel decentralized Monte Carlo Tree Search algorithm (MCTS) which allows agents to optimize their own actions while achieving some form of coordination, in a changing environment. Its key underlying idea is to balance in an adaptive manner the exploration-exploitation trade-off to deal effectively with abrupt changes caused by the environment and random changes caused by other agents’ actions. Critically, outdated and irrelevant samples - an inherent and prevalent feature in all multi-agent MCTS-based algorithms - are filtered out by means of a sliding window mechanism. We show both theoretically and through simulations that our algorithm provides a log-factor (in terms of time steps) smaller regret than state-of-the-art decentralized multi-agent planning methods. We instantiate our approach on the problem of underwater data collection, showing on a set of different models for changes that our approach greatly outperforms the best available algorithms for that setting, both in terms of convergence speed and of global utility.

Superresolution reconstruction produces a high-resolution image from a set of low-resolution images. Previous iterative methods for superresolution had not adequately addressed the computational and numerical issues for this ill-conditioned and typically underdetermined large scale problem. We propose efficient block circulant preconditioners for solving the Tikhonov-regularized superresolution problem by the conjugate gradient method. We also extend to underdetermined systems the derivation of the generalized cross-validation method for automatic calculation of regularization parameters. The effectiveness of our preconditioners and regularization techniques is demonstrated with superresolution results for a simulated sequence and a forward looking infrared (FLIR) camera image sequence.

In many image restoration/resolution enhancement applications, the blurring process, i.e., point spread function (PSF) of the imaging system, is not known or is known only to within a set of parameters. We estimate these PSF parameters for this ill-posed class of inverse problem from raw data, along with the regularization parameters required to stabilize the solution, using the generalized cross-validation method (GCV). We propose efficient approximation techniques based on the Lanczos algorithm and Gauss quadrature theory, reducing the computational complexity of the GCV. Data-driven PSF and regularization parameter estimation experiments with synthetic and real image sequences are presented to demonstrate the effectiveness and robustness of our method.

Superresolution produces high quality, high resolution images from a set of degraded, low resolution frames. We present a new and efficient wavelet-based algorithm for image superresolution. The algorithm is a combination of interpolation and restoration processes. Unlike previous work, our method exploits the interlaced sampling structure in the low resolution data. Numerical experiments and analysis demonstrate the effectiveness of our approach and illustrate why the computational complexity only doubles for 2-D superresolution versus 1-D case.

Superresolution reconstruction produces a high resolution image from a set of low resolution images. Previous work on superresolution had not adequately addressed the computational issues for this problem. In this paper, we propose efficient block circulant preconditioners for solving the regularized superresolution problem by conjugate gradients. The effectiveness of the preconditioners is demonstrated with superresolution results for a simulated image sequence and a FLIR image sequence.