Distributed Problem Solving

Distributed problem solving is a subfield of Multi-agent Systems (MAS). the focus of this research area is to find protocols to allow agents to solve problems when their local decision making is in some way impacted by the decision of the other agents. In the cooperative form, the agents work together to create a globally acceptable solution. In the competitive form, the agents work to solve the problem, whether it is a shared problem or not, from their own perspective.

In the CNAS lab, we develop protocols that are both cooperative and competitive to solve a myriad of distributed problems including

  • Distributed resource allocation - sensor networks
  • Distibuted constraint satisfaction - 3-satisfiability and graph coloring
  • Distributed constraint optimization - MaxSat and valued graph coloring
  • Dynamic, distributed constraint satisfaction

From this work, we have developed a number of best-of-the-breed algorithms for solving these problems. These algorithms fall into two primary classes: hill-climbing algorithms and cooperative mediation-based algorithms

Hill Climbing Algorithms

This class of algorithms uses the simple priniple of having agents change the value to their solution whenever it will improve its solution. This causes the overall solution quality to climb to a better state.
  • Improved Version of the Distributed Stochastic Algorithm
  • Distributed Probabilistic Protocol (DPP)
  • Dynamic Distributed Breakout Algorithm (DynDBA)

Cooperative Mediation-Based Algorithms

Cooperative mediation works by selecting agents to mediate of regional problems and then propose a solution to all of the agents involved. This for of dynamic, partial centralization causes the overall solution to quickly climb to a better state and if done properly can be used to create algorithm with the provable properties such as soundness, completeness, and optimality.