| This thesis concerns multiagent coordination in hierarchical settings. These are distributed optimization problems showing the following characteristics: (1) the global problem is naturally decomposed into subproblems, (2) a sequence, defined a priori, exists in which the subproblems must be solved, (3) various agents are responsible for the subproblems, and (4) each subproblem is defined according to the solutions adopted for the preceding subproblems.The most commonly used coordination mechanisms can be described as heuristics. In contrast, some generic and complete distributed algorithms exist -- researchers in Distributed Artificial Intelligence (DAI) have proposed a generic framework called Distributed Constraint Optimization Problem (DCOP). However, there are certain difficulties in mapping the actual business context (which is highly hierarchical) into the DCOP framework. Thus, based on the strengths and weaknesses of both the complete and heuristic approaches, we propose new approaches.We first introduce a framework called HDCOP (for Hierarchical DCOP). It allows formal modeling of the global problem, agents' responsibilities, the solving sequence and the solution space accessible to the agents. Within HDCOP, the coordination space is modelled as a tree. This calls for the use of distributed tree search algorithm (e.g. SyncBB) as the coordination mechanism.However, the coordination space shows particular characteristics. It is a non-binary tree with a fixed depth, with a huge branching factor that varies from one node to another. Moreover, the tree is not fully defined a priori it is 'revealed' progressively during the search process. In such a context, even for huge computation times, algorithms applying depth-first search (like SyncBB) persist in exploring only minor variations of the first global solution (they differ only from the solution for the last subproblems).Organizational distributed decision making and Supply chain coordination are among the main application domains. The latter case is more thoroughly studied in this thesis. In this kind of problem, the cooperation of several facilities is needed to produce and deliver the products ordered by external customers. However, different alternatives are possible regarding the parts to use, the manufacturing processes to follow, the scheduling of operations and the choice of transportation. Therefore, supply chain partners must coordinate their local decisions (e.g. what to do, where and when), with the common objective of delivering the ordered products with the least possible delay.To overcome this issue, we have adapted centralized search strategies based on the computation of discrepancies (e.g. LDS) for their use in multi-agent contexts. These methods allow systematic searching of the solution space (thus look for the optimal solution) but aim at producing good solutions in a short period of time. We have proposed two distributed adaptations of this idea. The first algorithm (SyncLDS) is easier to implement, but allows the computation of only one agent at a time. The second (MacDS) allows agents to work concurrently so as to speed up the search process. It is also more robust, as it uses asynchronous communication and tolerates random message transmission delays.Finally, we have proposed 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. The strategy exploits the fact that the search tree is not binary. Based on the quality of previous solutions, the model seeks to extrapolate for which node it would be more profitable to visit alternative arcs first. This significantly speeds up the search process.These methods were evaluated using a real industrial supply chain problem in the forest products industry. In order to generalize results and study different properties of the algorithms, we also evaluated them for a wider range of problems using generated data. |
PDF Full Text Request