ADS: An adaptive search strategy for efficient distributed decision making
Jonathan Gaudreault, Gilles Pesant, Jean‐Marc Frayret, D'Amours, Sophie · PolyPublie (École Polytechnique de Montréal) · 2008
This paper concerns distributed decision-making in hierarchical settings. For this class of problems, the coordination space can be naturally modeled as a tree. A collective of agents can thus perform a distributed tree search in order to coordinate. Previous results have shown that search strategies based on discrepancies (e.g. LDS) can be adapted to a distributed context. They are more effective than chronological backtracking in such setting. In this paper we introduce ADS, an adaptive backtracking strategy based on the analysis of discrepancies. It enables the agents to collectively and dynamically learn which areas of the tree are most promising in order to visit them first. We evaluated the method using a real coordination problem in an industrial supply chain. This makes it possible for the team of agents to obtain high-quality solutions much more quickly than with previous methods.