The research topic that is central to my group on constraints processing is that of distributed constraints. A large group of former and current graduate students are active in this research area.  Roie Zivan, Amir Gershman, Moshe Zazon, Tal Grinshpoun, Alon Grubstein, Arnon Netzer, Or Perry, Benny Lutati, Vadim Levitt, Zohar Komarovsky and Omer Litov are continuing a long trip of investigation of distributed constraints processing.  These include  distributed constraint satisfaction problems (DCSPs) and distributed constraints optimization problems (DCOPs) and in the last 7 years mainly distributed search for self-interested agents. The unique aspect of DCSPs & DCOPs is that they combine search algorithms with concurrency. Both topics have proven of great interest for our basic research. Constraint satisfaction problems have served for two decades as a cristal clear laboratory for search algorithms, due to the unique clarity of the problem definition - Vriables; Domains; (well-defined) Constraints. My group's work in the last decade has built on the clarity of CSPs and added to it the emphasize on all aspects of concurrency - concurrent algorithms; concurrent measures of performance; concurrent heuristics. A first summary of the work on Distributed Search by Constrained Agents came out in my book, published by Springer Verlag in 2008.
A short history of our research on Distributed Constraints Reasoning:
2002/3
•    A first search algorithm that uses dynamic ordering - Dynamically Ordered Distributed Forward Checking (DODFC).  
•    A parallel backtrack search algorithm on DCSPs that performed better than the classical asynchronous backtracking (ABT) algorithm of Yokoo
•    A concurrent performance measure for run time of search algorithms on DisCSPs. A distributed algorithm for counting non-concurrent constraints checks (NCCCs).  

2003/4
•    A new search algorithm that performs forward checking asynchronously while searching the  search space sequentially. The new algorithm is called Asynchronous Forward Checking (AFC).
•    The concurrent BT algorithm has been improved to include dynamic splitting of the search space - Concurrent Backtracking (ConcBT).

2004/5
•    The concurrent search algorithm has been improved to include dynamic backtracking and became ConcDB.
•    Once one learns how to measure concurrent performance of search algorithms on DCSPs one can model delays in message delivery. The behavior of three families of algorithms under random message delays has been studied. Algorithms that use a single search process are affected quite badly by random message delays and the effect grows with average delay size. This applies to asynchronous single search algorithms, such as ABT, as well as to synchronous single search algorithms. In contrast, concurrent search that uses multiple search processes concurrently experiences a relatively small effect of random message delay and as the size of delays grows its performance stays almost constant (Msg_Delay).


2005/6
•    A first search algorithm for DCOPs (Distributed Constraint Optimization Problems), that uses Asynchronous Forward Bounding (AFB). It turns out that similarly to asynchronous forward-checking, for DCOPs a coordinated search algorithm that uses asynchronous forward bounding improves the performance of asynchronous optimization search by a large margin. The main result, showing the advantage of AFB over ADOPT was presented at ECAI in July 2006.
•    A most profound result, establishing a deep understanding of constrained search, is that the standard (by now classical) Asynchronous Backtracking - ABT - algorithm of Yokoo, can be modified to include dynamic variable ordering. Enabling ABT to include dynamic variable ordering is a notable result and has won us the best paper award of CP-05.  The award establishes the acceptance of research on distributed constraints, by the constraints satisfaction community.

2006/7
•    A study of privacy aspects of DCSP search has produced a search algorithm for Asymmetric DCSPs, which keeps the privacy of constraints (i.e. asymmetric). This is an extension of an algorithm for asymmetric DCSPs that was proposed by Meseguer and Brito in 2003.
•    Backjumping was added to the successful AFB algorithm, to make it the best performing DisCOP algorithm. The paper that was presented at IJCAI-07 in Hyderabad (AFB-BJ) reported an extensive experimental evaluation against all DCOP algorithms.
•    A first version of Min-domain ordering for ABT_DO was presented at CP-07, establishing superior performance on randomly generated DCSPs the final paper is in Constraints 2009).

2007/8
•    The APO algorithm was proven incorrect and a correct version was published in JAIR Comp_APO. Its performance was compared to several DCOP algorithms.
•    A first multi search algorithm for DCSPs was presented at the annual workshop DCR-08 (Multi-CBJ). It's performance was found to be better than all other DCSP algorithms.
•    A complete treatment of search on DCSPs with Asymmetric constraints was published in Constraints. The paper includes the best algorithm for asymmetric DCSPs and an extensive evaluation of its privacy loss.
•    A preliminary study of self-interested agents within DCOP search was based on a concrete example problem – The Meetings Scheduling Problem (MSP). The study proposed several methods that can deal partly with self-interested participants and still arrive at a good enough solution. Presented at the conference on Automated Timetabling (PATAT-08).

2008/9
•    A general representation for self-interested agents, within the DCOP paradigm, is Asymmetric DCOPs. The new representation is presented, together with specific complete algorithms for search on ADCOPs. The initial evaluation results show that the new specific algorithms for ADCOPs outperform standard DCOP algorithms that are adapted for asymmetric DCOPs (ADCOPs). 

•    First results about the use of game theoretic methods to study self interested agents demonstrated that for the simplified meeting scheduling game there exists a "cooperative" solution. In other words, that there can be an initiative for agents to cooperate in search for a solution that offers higher gains for the participants, than what they are guaranteed in a Nash Equilibrium (IDC-2009).
 

2009/10
•    Local search for Asymmetric DCOPs was published in AAMAS-2010 - "Local Search for Distributed Asymmetric Optimization". The full paper is now being submitted to the AI Journal (2011).
•    A new algorithm for DCOPs that uses concurrent search processes forms the first chapter in Arnon Netzer's PhD thesis and appears in the proceedings of the DCR workshop in AAMAS-2010 - "Concurrent Forward Bounding for DCOPs".

2010/11
•    A complete treatment of search on DCSPs with Asymmetric constraints was published in the Constraints journal. The paper includes the best algorithm for asymmetric DCSPs and an extensive evaluation of its privacy loss.
•    A preliminary study of self-interested agents within DCOP search was based on a concrete example problem – The Meetings Scheduling Problem (MSP). The study proposed several methods that can deal partly with self-interested participants and still arrive at a good enough solution. Presented at the conference on Automated Timetabling (PATAT-08). 

2011/2012

  • Arnon Netzer's (best performing) concurrent search algorithm for DCOPs, ConcFB, was published in JAIR. 
  • Arnon Netzer's paper on Social DCOPs, DCOP search algorithms for socially oriented global goals was presented at DCR 2011 (his 2nd chapter of the PhD thesis, on Self-interested and socially aware agents in DCOPs)
  • Alon Grubshtein's paper on a graphical game that enables cooperation by self-interested agents was presented at IDC-2011.
  • Alon Grubshtein's ABT algorithm for finding a Nash Equilibrium in a graphical game (e.g., an ADCOP) was presented in ECAI-2012.

2012/2013

  • Finally, all search algorithms developed by Alon, Tal, Arnon for Asymmetric DCOPs (ADCOPs) have appeared in JAIR 2013.
  • Vadim's first characterization of Boolean games that have a pure Nash equlibrium with and without taxation was presented in AAMAS-2013.
  • Two papers on complete search and on local search for Envy-minimization on DCOPs were presented at ICAART-2013 and IAT-2013.
  • Or Perry's study on the impact of classes of synchronization of DCOP algorithms on their performance in asynchronous environment was presented in ICAART-2013.

2013/2014

  • Vadim, Benny & Tal presented a model of iterative Boolean games with environment variables for charging electric vehicles (EVs) on the smart grid, in IAT-2013.
  • Vadim, Benny & Tal presented our state-of-the-art model of charging congestion games for electric vehicles (EVs) on the smart grid, in AAAI-2014.

 The above results establish three major directions of investigating Graphical games using all techniques of distributed algorithms for DCSPs and DCOPs. Thus, my group's main research direction is established to be distributed search (both complete and stochastic) for finding solutions to several families of Graphical games. 

2014/2015

  • Zohar, Vadim & Tal presented a paper on characterization of Boolean games where a PNE can be enforced by side-payments, in IJCAI-2015. (Buenos Eires)
  • Arnon's paper (with Roie) on complete and local search for envy-minimization of ADCOPs has appeared in JAIR 2015.

2015/2016

 

  • Zohar, Vadim & Tal presented a paper on local search for the Public Goods game (PGG), where a PNE of higher social welfare can be enforced by side-payments, in IAT-2016. 
  • Arnon's paper (with Roie) on complete and local search for envy-minimization of ADCOPs has appeared in JAIR 2015.

 

Distributed Search by
Constrained Agents
Algorithms, Performance, Communication