Author name cluster

Alon Grubshtein

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

2 author rows

AIJ Journal 2012 Journal Article

Concurrent forward bounding for distributed constraint optimization problems

Arnon Netzer
Alon Grubshtein
Amnon Meisels

A distributed search algorithm for solving Distributed Constraints Optimization Problems (DCOPs) is presented. The new algorithm scans the search space by using multiple search processes (SPs) that run on all agents concurrently. SPs search in non-intersecting parts of the global search space and perform Branch & Bound search. Each search process (SP) uses the mechanism of forward bounding (FB) to prune efficiently its part of the global search space. The Concurrent Forward-Bounding (ConcFB) algorithm enables all SPs to share their upper bound across all parts of the global search space. The number of concurrent SPs is controlled dynamically by the ConcFB algorithm, by performing dynamic splitting. Within each SP a dynamic variable ordering is employed in order to help control the balance of computational load among all agents and across different SPs. The ConcFB algorithm is evaluated experimentally and compared to all state of the art DCOP algorithms. The number of Non-Concurrent Logical Operations, Non-Concurrent Steps, the total number of messages sent and CPU time are used as performance metrics. The evaluation procedure considers different DCOP problem types with a varying number of agents and different constraint graphs. As problems become larger and denser, ConcFB is shown to outperform all other evaluated algorithms by 2–3 orders of magnitude in all performance measures. Further evaluations comparing different variants of ConcFB provide important insights into the working of the algorithm and reveals the contribution of its different components.

Details DOI

ECAI Conference 2012 Conference Paper

Partial Cooperation in Multi-agent Local Search

Alon Grubshtein
Roie Zivan
Amnon Meisels

Multi-agent systems usually address one of two forms of interaction. One has completely competitive agents that act selfishly, each maximizing its own gain from the interaction. Auctions and voting scenarios usually assume such agents and follow game theoretic results. The other form of interaction has multiple agents that cooperatively search for some global goal, such as an optimal time slot allocation for all landing aircrafts in an airport.

Details

AAMAS Conference 2012 Conference Paper

Partial Cooperation in Multi-agent Search

Roie Zivan
Alon Grubshtein
Michal Friedman
Amnon Meisels

Multi-agent systems usually address one of two pure scenarios, completely competitive agents that act selfishly, each agent maximizing its own gain from the interaction or multiple agents that operate cooperatively in order to achieve a common goal. The present paper proposes a paradigm for multiple agents to solve a distributed problem, acting partly cooperatively and keeping a limited form of their self-interest. The proposed framework has multiple agents solving an asymmetric distributed constraints optimization problem (ADCOP), where agents have different personal gains from any mutual assignment. Three modes of cooperation are proposed – Non-cooperative, Guaranteed personal gain, and λ-cooperation (where agents’ willingness to suffer relative loss is parametrized by λ). The modes of cooperation are described, as well as their realization in search algorithms.

PDF

AAMAS Conference 2010 Conference Paper

Local search for Distributed Asymmetric Optimization

Alon Grubshtein
Roie Zivan
Tal Grinshpoun
Amnon Meisels

Distributed Constraints Optimization (DCOP) is a powerful framework for representing and solving distributed combinatorial problems, where the variables of the problem are owned by different agents. DCOP algorithms search for the optimal solution, optimizing the total gain (or cost) that iscomposed of all gains of all agents. Local search (LS) DCOP algorithms search locally for an approximate such solution. Many multi-agent problems include constraints that produce different gains (or costs) for the participating agents. Asymmetric gains of constrained agents cannot be naturally represented by the standard DCOP model. The present paper proposes a general framework for Asymmetric DCOPs (ADCOPs). The new framework is described and its differences from former attempts are discussed. New local search algorithms for ADCOPs are introduced and their advantages over existing algorithms and over formerrepresentations are discussed in detail. The new proposed algorithms for the ADCOP framework are evaluated experimentally and their performance compared to existing algorithms. Two measures of performance are used: quality of solutions and loss of privacy. The results show that the new algorithms significantly outperform existing DCOP algorithms with respect to both measures.

PDF