Improving the Efficiency of the Distributed Stochastic Algorithm

The Distributed Stochastic Algorithm (DSA) is a distributedhill-climbing technique for solving large Distributed Constraint Optimization Problems (DCOPs) such as distributedscheduling, resource allocation, and distributed route planning. The best known version of DSA, DSA-B, works byhaving agents change their assignments with probability $p$when making that change will improve their solution (ahill-climbing move). To escape local minima, DSA-B performs a lateral escape move by switching to another equallygood value with the same probability $p$. It is unclear whyhill climbing and escape moves are chosen with the sameprobability. We investigate the performance effects of making these moves with different probabilities, $p_H$ and $p_L$. Through empirical evaluation, we discover that the efficiencyof DSA can not only be considerably improved, but canbe more specifically tuned to a particular domain or user'sneeds when these two move types are considered separately. Our work also shows that DSA can outperform both DBAand DPP when it is properly tuned.

Authors

• Melanie Smith
• Roger Mailler

Keywords

• Distributed algorithm
• Local Search
• DCOP
• DSA