Anytime local search for distributed constraint optimization

ABSTRACT

Most former studies of Distributed Constraint Optimization Problems (DisCOPs) search considered only complete search algorithms, which are practical only for relatively small problems. Distributed local search algorithms can be used for solving DisCOPs. However, because of the differences between the global evaluation of a system's state and the private evaluation of states by agents, agents are unaware of the global best state which is explored by the algorithm. Previous attempts to use local search algorithms for solving DisCOPs reported the state held by the system at the termination of the algorithm, which was not necessarily the best state explored.

A general framework for implementing distributed local search algorithms for DisCOPs is proposed. The proposed framework makes use of a BFS-tree in order to accumulate the costs of the system's state in its different steps and to propagate the detection of a new best step when it is found. The resulting framework enhances local search algorithms for DisCOPs with the anytime property. The proposed framework does not require additional network load. Agents are required to hold a small (linear) additional space (beside the requirements of the algorithm in use). The proposed framework preserves privacy at a higher level than complete DisCOP algorithms which make use of a pseudo-tree (ADOPT, DPOP).

REFERENCES

• 1: A. Gershman, A. Meisels, and R. Zivan. Asynchronous forward-bounding for distributed constraints optimization. In Proc. ECAI-06, pages 103--107, August 2006.
• 2: R. Greenstadt, B. J. Grosz, and M. D. Smith. Ssdpop: Improving the privacy of dcop with secret sharing, distributed constraint reasoning workshop (der), providence, rhode island, september 2007. In Distributed Constraint Reasoning Workshop (DCR), CP-07, Providence, RI, USA, September 2006.
• 3: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 4: Roger Mailler , Victor Lesser, Solving Distributed Constraint Optimization Problems Using Cooperative Mediation, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.438-445, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.249]
• 5: Pragnesh Jay Modi , Wei-Min Shen , Milind Tambe , Makoto Yokoo, Adopt: asynchronous distributed constraint optimization with quality guarantees, Artificial Intelligence, v.161 n.1-2, p.149-180, January 2005 [doi>10.1016/j.artint.2004.09.003]
• 6: A. Petcu and B. Faltings. A scalable method for multiagent constraint optimization. In IJCAI, pages 266--271, 2005.
• 7: A. Schaerf. Local search techniques for large high-school timetabling problems. IEEE Transactions on Systems, Man, and Cybernetics---Part A: Systems and Humans, 29(4):368--377, 1999.
• 8: Weixiong Zhang , Guandong Wang , Zhao Xing , Lars Wittenburg, Distributed stochastic search and distributed breakout: properties, comparison and applications to constraint optimization problems in sensor networks, Artificial Intelligence, v.161 n.1-2, p.55-87, January 2005 [doi>10.1016/j.artint.2004.10.004]
• 9: S. Zilberstein. Using anytime algorithms in intelligent systems. AI Magazine, 17(3):73--83, 1996.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Constrained optimization
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Intelligent agents

General Terms:
Algorithms, Design, Theory