Roie Zivan

AAMAS Conference 2026 Conference Paper

Agentic LLMs and Distributed Constraint Reasoning: A Symbiotic Perspective for Neurosymbolic Multi-Agent Systems

• Gauthier Picard
• William Yeoh
• Roie Zivan

Distributed Constraint Reasoning (DCR) has long provided a principled framework for modeling and solving multi-agent coordination and optimization problems. However, its practical adoption in realworld, human-centric domains has been hindered by the challenge of translating human intentions, preferences, and constraints into formal symbolic models. At thesame time, recentadvances in LLMs have enabled powerful agentic capabilities, including natural language understanding, flexible reasoning, and interactive problem solving, but these systems lack the formal rigor and guarantees needed for scalable multi-agent coordination. In this paper, we arguethattheconvergenceofthesetwoparadigmsoffersatimelyand transformative opportunity. We articulate several synergistic research directions: leveraging LLMs for translating natural language into DCR specifications, eliciting and refining user preferences, and enhancing inter-agent communication; and conversely, applying DCR models and algorithms to improve coordination, structured reasoning, resource allocation, and communication sensitivity in Agentic LLM systems. Together, these threads point toward hybrid neurosymbolic systems that combine the adaptability of LLMs with the mathematical rigor of DCR.

AAAI Conference 2026 Conference Paper

Truth, Justice, and Secrecy: Cake Cutting Under Privacy Constraints

• Yaron Salman
• Tamir Tassa
• Omer Lev
• Roie Zivan

Cake-cutting algorithms, which aim to fairly allocate a continuous resource based on individual agent preferences, have seen significant progress over the past two decades. Much of the research has concentrated on fairness, with comparatively less attention given to other important aspects. In 2010, Chen et al. introduced an algorithm that, in addition to ensuring fairness, was strategyproof---meaning agents had no incentive to misreport their valuations. However, even in the absence of strategic incentives to misreport, agents may still hesitate to reveal their true preferences due to privacy concerns (e.g., when allocating advertising time between firms, revealing preferences could inadvertently expose planned marketing strategies or product launch timelines). In this work, we extend the strategyproof algorithm of Chen et al. by introducing a privacy-preserving dimension. To the best of our knowledge, we present the first private cake-cutting protocol, and, in addition, this protocol is also envy-free and strategyproof. Our approach replaces the algorithm’s centralized computation with a novel adaptation of cryptographic techniques, enabling privacy without compromising fairness or strategyproofness. Thus, our protocol encourages agents to report their true preferences not only because they are not incentivized to lie, but also because they are protected from having their preferences exposed.

AAMAS Conference 2025 Conference Paper

Enhancing Lifelong Multi-Agent Path-finding by Using Artificial Potential Fields

• Arseniy Pertzovsky
• Roni Stern
• Ariel Felner
• Roie Zivan

We explore the use of Artificial Potential Fields (APFs) to solve Lifelong Multi-Agent Path Finding (LMAPF) problems. In LMAPF, a team of agents must move to their goal locations without collisions, and new goals are generated upon arrival. We propose methods for incorporating APFs in a range of LMAPF algorithms, including Prioritized Planning and MAPF-LNS2. Experimental results show that using APF yields up to a 7-fold increase in overall system throughput for LMAPF.

AAMAS Conference 2025 Conference Paper

Insights Regarding the Success of Damping in Improving Belief Propagation

• Uriel Zaed
• Omer Lev
• Roie Zivan

A common approach for solving distributed constraint optimization problems (DCOPs) is to represent them with a graphical model and to solve them with a message passing algorithm. Belief propagation is a popular and well studied such incomplete inference algorithm. Min-sum (often referred to as Max-sum) is the belief propagation version that is used for solving minimization DCOPs. Belief propagation is performed on a factor graph representation of the problem, in which the graph nodes take an active role in the algorithm, i. e. , they perform calculations and exchange messages with their neighbors. Unfortunately, the standard version of Min-sum fails to converge in many cases, and produces low quality solutions. Previous studies proposed methods to encourage its convergence and improve solution quality. Recently, empirical evidence indicated that the performance of Min-sum can be immensely improved by enhancing it with damping of beliefs (constraint costs) that are exchanged by the graph nodes. However, while this was empirically validated, a theoretical understanding of this phenomenon has not yet been established. In this research, we present a number of theoretical and empirical results that achieve important mile-stones in understanding damping’s success in improving Min-sum. These include adapting theoretical tools that were suggested for analyzing Min-sum to work with Damped Min-sum (DMS) and analyzing the effect of damping on graphs with special structures. We show that when belief propagation instantly converges, damping is redundant, and thus, the main contribution of damping is in reducing the exponential growth of the inconsistent beliefs that are propagated in the first steps of the algorithm’s run.

IJCAI Conference 2025 Conference Paper

Multi-Agent Corridor Generating Algorithm

• Arseni Pertzovskiy
• Roni Stern
• Roie Zivan
• Ariel Felner

In this paper, we propose the Multi-Agent Corridor Generating Algorithm (MACGA) for solving the Multi-agent Pathfinding (MAPF) problem, where a group of agents need to find non-colliding paths to their target locations. Existing approaches struggle to solve dense MAPF instances. In MACGA, the agents build corridors, which are sequences of connected vertices, from current locations towards agents' goals, and evacuate other agents out of the corridors to avoid collisions and deadlocks. We also present the MACGA+PIBT algorithm, which integrates the well-known rule-based PIBT algorithm into MACGA to improve runtime and solution quality. The proposed algorithms run in polynomial time and have a reachability property, i. e. , every agent is guaranteed to reach its goal location at some point. We demonstrate experimentally that MACGA and MACGA+PIBT outperform baseline algorithms in terms of success rate, runtime, and makespan across diverse MAPF benchmark grids.

AIJ Journal 2025 Journal Article

Separate but equal: Equality in belief propagation for single-cycle graphs

• Erel Cohen
• Ben Rachmut
• Omer Lev
• Roie Zivan

Belief propagation is a widely used, incomplete optimization algorithm whose main theoretical properties hold only under the assumption that beliefs are not equal. Nevertheless, there is substantial evidence to suggest that equality between beliefs does occur. A published method to overcome belief equality, which is based on the use of unary function-nodes, is commonly assumed to resolve the problem. In this study, we focus on min-sum, the version of belief propagation that is used to solve constraint optimization problems. We prove that for the case of a single-cycle graph, belief equality can only be avoided when the algorithm converges to the optimal solution. Under any other circumstances, the unary function method will not prevent equality, indicating that some of the existing results presented in the literature are in need of reassessment. We differentiate between belief equality, which refers to equal beliefs in a single message, and assignment equality, which prevents the coherent assignment of values to the variables, and we provide conditions for both.

IROS Conference 2024 Conference Paper

CGA: Corridor Generating Algorithm for Multi-Agent Environments

• Arseniy Pertzovsky
• Roni Stern
• Roie Zivan

In this work, we consider path planning for a team of mobile agents where one agent must reach a given target as soon as possible and the others must accommodate to avoid collisions. We call this practical problem the Single-Agent Corridor Generating (SACG) problem and explore several algorithms for solving it. We propose two baseline algorithms based on existing Multi-Agent Path Finding (MAPF) algorithms and outline their limitations. Then, we present the Corridor Generating Algorithm (CGA), a fast and complete algorithm for solving SACG. CGA performs well compared to the baseline approaches. In addition, we show how CGA can be generalized to address the lifelong version of MAPF, where new goals appear over time.

JAIR Journal 2024 Journal Article

Collision Avoiding Max-Sum for Mobile Sensor Teams

• Arseniy Pertzovsky
• Roie Zivan
• Noa Agmon

Recent advances in technology have large teams of robots with limited computation skills work together in order to achieve a common goal. Their personal actions need to contribute to the joint effort, however, they also must assure that they do not harm the efforts of the other members of the team, e.g., as a result of collisions. We focus on the distributed target coverage problem, in which the team must cooperate in order to maximize utility from sensed targets, while avoiding collisions with other agents. State of the art solutions focus on the distributed optimization of the coverage task in the team level, while neglecting to consider collision avoidance, which could have far reaching consequences on the overall performance. Therefore, we propose CAMS: a collision-avoiding version of the Max-sum algorithm, for solving problems including mobile sensors. In CAMS, a factor-graph that includes two types of constraints (represented by function-nodes) is being iteratively generated and solved. The first type represents the task-related requirements, and the second represents collision avoidance constraints. We prove that consistent beliefs are sent by target representing function-nodes during the run of the algorithm, and identify factor-graph structures on which CAMS is guaranteed to converge to an optimal (collision-free) solution. We present an experimental evaluation in extensive simulations, showing that CAMS produces high quality collision-free coverage also in large and complex scenarios. We further present evidence from experiments in a real multi-robot system that CAMS outperforms the state of the art in terms of convergence time.

AAMAS Conference 2023 Conference Paper

Ask and You Shall be Served: Representing & Solving Multi-agent Optimization Problems with Service Requesters and Providers

• Maya Lavie
• Tehila Caspi
• Omer Lev
• Roie Zivan

In scenarios with numerous emergencies that arise and require the assistance of various rescue units (e. g. , medical, fire, & police forces), the rescue units would ideally be allocated quickly and distributedly while aiming to minimize casualties. This is one of many examples of distributed settings with service providers (the rescue units) and service requesters (the emergencies) which we term service oriented settings. Allocating the service providers in a distributed manner while aiming for a global optimum is hard to model, let alone achieve, using the existing Distributed Constraint Optimization Problem (DCOP) framework. Hence, the need for a novel approach and corresponding algorithms. We present the Service Oriented Multi-Agent Optimization Problem (SOMAOP), a new framework to overcome DCOP’s shortcomings in service oriented settings. We evaluate the framework using algorithms based on auctions and matching (e. g. , Gale Shapely). We empirically show that algorithms based on repeated auctions converge to a high quality solution very fast, while repeated matching problems converge slower, but produce higher quality solutions. We demonstrate the advantages of our approach over standard incomplete DCOP algorithms and a greedy centralized algorithm.

IJCAI Conference 2023 Conference Paper

Asynchronous Communication Aware Multi-Agent Task Allocation

• Ben Rachmut
• Sofia Amador Nelke
• Roie Zivan

Multi-agent task allocation in physical environments with spatial and temporal constraints, are hard problems that are relevant in many realistic applications. A task allocation algorithm based on Fisher market clearing (FMC_TA), that can be performed either centrally or distributively, has been shown to produce high quality allocations in comparison to both centralized and distributed state of the art incomplete optimization algorithms. However, the algorithm is synchronous and therefore depends on perfect communication between agents. We propose FMC_ATA, an asynchronous version of FMC_TA, which is robust to message latency and message loss. In contrast to the former version of the algorithm, FMC_ATA allows agents to identify dynamic events and initiate the generation of an updated allocation. Thus, it is more compatible for dynamic environments. We further investigate the conditions in which the distributed version of the algorithm is preferred over the centralized version. Our results indicate that the proposed asynchronous distributed algorithm produces consistent results even when the communication level is extremely poor.

AAMAS Conference 2023 Conference Paper

Asynchronous Communication Aware Multi-Agent Task Allocation

• Ben Rachmut
• Sofia Amador Nelke
• Roie Zivan

Multi-agent task allocation in physical environments with spatial and temporal constraints are hard problems relevant to many realistic applications. A task allocation algorithm based on Fisher market clearing (FMC_TA), which can be performed centrally or distributively, has been shown to produce high quality allocations compared to the centralized and distributed state of the art incomplete optimization algorithms. However, the algorithm is synchronous and thus depends on perfect communication between agents. We propose FMC_ATA, an asynchronous version of FMC_TA, which is robust to message latency and message loss. In contrast to the former version of the algorithm, FMC_ATA allows agents to identify events and initiate the generation of an updated allocation. Thus, it is more compatible with dynamic environments.

AAMAS Conference 2023 Conference Paper

CAMS: Collision Avoiding Max-Sum for Mobile Sensor Teams

• Arseni Pertzovskiy
• Roie Zivan
• Noa Agmon

Recent advances in technology have large teams of robots with limited computation and communication skills work together in order to achieve a common goal. Their personal actions need to contribute to the joint effort, however, they also must assure that they do not harm the efforts of the other members of the team, e. g. , as a result of collisions. We focus on the distributed target coverage problem, in which the team must cooperate in order to maximize utility from sensed targets, while avoiding collisions with other agents. State of the art solutions focus on the distributed optimization of the coverage task in the team level, while neglecting to consider collision avoidance, which could have far reaching consequences on the overall performance. Therefore, we propose CAMS: a collision-avoiding version of the Max-sum algorithm, for solving problems including mobile sensors. In CAMS, a factor-graph that includes two types of constraints (represented by functionnodes) is being iteratively generated and solved. The first type represents the task-related requirements, and the second represents collision avoidance constraints. We prove that consistent beliefs are sent by target representing function-nodes during the run of the algorithm, and identify factor-graph structures on which CAMS is guaranteed to converge to an optimal (collision-free) solution. We present an empirical evaluation in extensive simulations, showing that CAMS produces high quality collision-free coverage also in large and complex scenarios. We further present evidence from experiments in a real multi-robot system that CAMS outperforms the state of the art in terms of convergence time.

JAAMAS Journal 2023 Journal Article

Effect of asynchronous execution and imperfect communication on max-sum belief propagation

• Roie Zivan
• Ben Rachmut
• William Yeoh

Abstract Max-sum is a version of belief propagation that was adapted for solving distributed constraint optimization problems. It has been studied theoretically and empirically, extended to versions that improve solution quality and converge rapidly, and is applicable to multiple distributed applications. The algorithm was presented both as synchronous and asynchronous algorithms. However, neither the differences in the performance of the two execution versions nor the implications of imperfect communication (i. e. , massage delay and message loss) on the two versions have been investigated to the best of our knowledge. We contribute to the body of knowledge on Max-sum by: (1) Establishing the theoretical differences between the two execution versions of the algorithm, focusing on the construction of beliefs; (2) Empirically evaluating the differences between the solutions generated by the two versions of the algorithm, with and without message delay or loss; and (3) Establishing both theoretically and empirically the positive effect of damping on reducing the differences between the two versions. Our results indicate that, in contrast to recent published results indicating that message latency has a drastic (positive) effect on the performance of distributed local search algorithms, the effect of imperfect communication on Damped Max-sum (DMS) is minor. The version of Max-sum that includes both damping and splitting of function nodes converges to high quality solutions very fast, even when a large percentage of the messages sent by agents do not arrive at their destinations. Moreover, the quality of solutions in the different versions of DMS is dependent of the number of messages that were received by the agents, regardless of the amount of time they were delayed or if these messages are only a portion of the total number of messages that was sent by the agents.

EAAI Journal 2023 Journal Article

Scheduling operations in a large hospital by multiple agents

• Noam Gaon
• Yuval Gabai Schlosberg
• Roie Zivan

The scheduling of operations in a large hospital is performed jointly by several groups of people, each with its own objective and constraints. It is a two-phase process, starting with the allocation of operating rooms to wards, and followed by the scheduling of operations in each operating room of the hospital on each day. The final schedule must satisfy all inter-ward hard constraints, such as the allocation of anesthetists, nurses, and equipment to operations that are taking place in parallel, and ideally, it should also address soft constraints such as taking the urgency and complexity of operations into consideration. This study contributes to the ongoing effort of adapting multi-agent optimization models and algorithms to real-world applications by modeling the problems in both phases as distributed constraint optimization problems (DCOPs), with different properties. The first phase includes partially cooperative ward-representing agents, allocating operating rooms for daily usage among themselves. In the second phase, ward-representing agents interact with agents representing constraining elements, in order to generate daily operation schedules for each operating room, thus forming a unique bipartite constraint graph. On one side are the ward representatives, while on the other are the agents representing the constraining resources. Each agent has a non-trivial local problem to solve, and its solution serves as the proposed assignment in the distributed algorithm. The study begins by discussing the properties required of the algorithms needed to solve the two phases. It then proposes adjustments to existing distributed partially cooperative algorithms and local search algorithms to solve these problems, and compares the results of different variants of these algorithms. The results obtained for both phases emphasize that successful collaboration is predicated on two requirements: that agents hold consistent information regarding their peers’ states and that the degree of exploration undertaken by the algorithm is restricted in order to produce high-quality solutions.

AAAI Conference 2023 Conference Paper

Separate but Equal: Equality in Belief Propagation for Single Cycle Graphs

• Erel Cohen
• Omer Lev
• Roie Zivan

Belief propagation is a widely used incomplete optimization algorithm, whose main theoretical properties hold only under the assumptions that beliefs are not equal. Nevertheless, there is much evidence that equality between beliefs does occur. A method to overcome belief equality by using unary function-nodes is assumed to resolve the problem. We focus on Min-sum, the belief propagation version for solving constraint optimization problems. We prove that on a single cycle graph, belief equality can be avoided only when the algorithm converges to the optimal solution. In any other case, the unary function methods will not prevent equality, rendering some existing results in need of reassessment. We differentiate between belief equality, which includes equal beliefs in a single message, and assignment equality, that prevents a coherent selection of assignments to variables. We show the necessary and satisfying conditions for both.

JAIR Journal 2022 Journal Article

Communication-Aware Local Search for Distributed Constraint Optimization

• Ben Rachmut
• Roie Zivan
• William Yeoh

Most studies investigating models and algorithms for distributed constraint optimization problems (DCOPs) assume that messages arrive instantaneously and are never lost. Specifically, distributed local search DCOP algorithms, have been designed as synchronous algorithms (i.e., they perform in synchronous iterations in which each agent exchanges messages with all its neighbors), despite running in asynchronous environments. This is true also for an anytime mechanism that reports the best solution explored during the run of synchronous distributed local search algorithms. Thus, when the assumption of perfect communication is relaxed, the properties that were established for the state-of-the-art local search algorithms and the anytime mechanism may not necessarily apply. In this work, we address this limitation by: (1) Proposing a Communication-Aware DCOP model (CA-DCOP) that can represent scenarios with different communication disturbances; (2) Investigating the performance of existing local search DCOP algorithms, specifically Distributed Stochastic Algorithm (DSA) and Maximum Gain Messages (MGM), in the presence of message latency and message loss; (3) Proposing a latency-aware monotonic distributed local search DCOP algorithm; and (4) Proposing an asynchronous anytime framework for reporting the best solution explored by non-monotonic asynchronous local search DCOP algorithms. Our empirical results demonstrate that imperfect communication has a positive effect on distributed local search algorithms due to increased exploration. Furthermore, the asynchronous anytime framework we proposed allows one to benefit from algorithms with inherent explorative heuristics.

JAIR Journal 2022 Journal Article

Proactive Dynamic Distributed Constraint Optimization Problems

• Khoi D. Hoang
• Ferdinando Fioretto
• Ping Hou
• William Yeoh
• Makoto Yokoo
• Roie Zivan

The Distributed Constraint Optimization Problem (DCOP) formulation is a powerful tool for modeling multi-agent coordination problems. To solve DCOPs in a dynamic environment, Dynamic DCOPs (D-DCOPs) have been proposed to model the inherent dynamism present in many coordination problems. D-DCOPs solve a sequence of static problems by reacting to changes in the environment as the agents observe them. Such reactive approaches ignore knowledge about future changes of the problem. To overcome this limitation, we introduce Proactive Dynamic DCOPs (PD-DCOPs), a novel formalism to model D-DCOPs in the presence of exogenous uncertainty. In contrast to reactive approaches, PD-DCOPs are able to explicitly model possible changes of the problem and take such information into account when solving the dynamically changing problem in a proactive manner. The additional expressivity of this formalism allows it to model a wider variety of distributed optimization problems. Our work presents both theoretical and practical contributions that advance current dynamic DCOP models: (i) We introduce Proactive Dynamic DCOPs (PD-DCOPs), which explicitly model how the DCOP will change over time; (ii) We develop exact and heuristic algorithms to solve PD-DCOPs in a proactive manner; (iii) We provide theoretical results about the complexity of this new class of DCOPs; and (iv) We empirically evaluate both proactive and reactive algorithms to determine the trade-offs between the two classes. The final contribution is important as our results are the first that identify the characteristics of the problems that the two classes of algorithms excel in.

AAMAS Conference 2021 Conference Paper

Branch-and-Bound Heuristics for Incomplete DCOPs

• Atena M. Tabakhi
• Yuanming Xiao
• William Yeoh
• Roie Zivan

The Incomplete Distributed Constraint Optimization Problem (I- DCOP) extends the distributed constraint optimization problem, where constraint costs are allowed to be unspeci�ed. A distributed variant of the Synchronous Branch-and-Bound (SyncBB) search algorithm has been proposed to solve I-DCOPs, where unspeci�ed constraint costs are elicited during its execution. In this paper, we propose two heuristics that can be used in conjunction with SyncBB to solve I-DCOPs. Our proposed heuristics speed up the algorithm by pruning those parts of the search space whose solution quality is sub-optimal. Thus, our model and heuristics extend the state of the art in distributed constraint reasoning to better model and solve distributed agent-based applications with user preferences.

AAMAS Conference 2021 Conference Paper

Latency-Aware Local Search for Distributed Constraint Optimization

• Ben Rachmut
• Roie Zivan
• William Yeoh

Most studies investigating models and algorithms for distributed constraint optimization problems (DCOPs) assume messages arrive instantaneously or within a (short) bounded delay. Specifically, distributed local search DCOP algorithms have been designed as synchronous algorithms, performing in an asynchronous environment, i. e. , algorithms that perform in synchronous iterations in which each agent exchanges messages with all its neighbors. This is true also for an anytime mechanism that reports the best solution explored during the run of synchronous distributed local search algorithms. Thus, when the assumptions on instantaneous message arrival are relaxed, the state of the art local search algorithms and mechanism do not apply. In this work, we address this limitation by: (1) Investigating the performance of existing local search DCOP algorithms in the presence of message latency; (2) Proposing an asynchronous monotonic distributed local search DCOP algorithm; and (3) Proposing an asynchronous anytime framework for reporting the best solution explored by non-monotonic asynchronous local search DCOP algorithms. Our empirical results demonstrate that, up to some extent, message delays have a positive effect on distributed local search algorithms due to increased exploration. The asynchronous anytime framework proposed, allows a maximal benefit from such latency based explorative heuristics.

AAMAS Conference 2021 Conference Paper

Partially Cooperative Multi-Agent Periodic Indivisible Resource Allocation

• Yuval Gabai Schlosberg
• Roie Zivan

Asymmetric distributed constraint optimization problems (AD- COPs) in which agents are partially cooperative, is a model for representing multi-agent optimization problems in which agents, are willing to cooperate in order to achieve a global goal, as long as some minimal threshold on their personal utility is satisfied. We contribute by: 1) extending the ADCOP model to represent resource allocation problems in which indivisible resources are periodically allocated, e. g. , meeting rooms, operating rooms, etc. 2) adjusting partially cooperative local search algorithms to solve problems represented by the extended model. 3) presenting an implementation of a realistic problem that is represented by the proposed model, and empirical evidence of the compatibility of partially cooperative algorithms for this scenario.

JAAMAS Journal 2020 Journal Article

Applying Max-sum to asymmetric distributed constraint optimization problems

• Roie Zivan
• Tomer Parash
• Yarden Naveh

Abstract We study the adjustment and use of the Max-sum algorithm for solving Asymmetric Distributed Constraint Optimization Problems (ADCOPs). First, we formalize asymmetric factor-graphs and apply the different versions of Max-sum to them. Apparently, in contrast to local search algorithms, most Max-sum versions perform similarly when solving symmetric and asymmetric problems and some even perform better on asymmetric problems. Second, we prove that the convergence properties of Max-sum_ADVP (an algorithm that was previously found to outperform standard Max-sum and Bounded Max-sum) and the quality of the solutions it produces, are dependent on the order between nodes involved in each constraint, i. e. , the inner constraint order (ICO). A standard ICO allows to reproduce the properties achieved for symmetric problems. Third, we demonstrate that a non-standard ICO can be used to balance exploration and exploitation. Our results indicate that Max-sum_ADVP with non-standard ICO and Damped Max-sum, when solving asymmetric problems, both outperform other versions of Max-sum, as well as local search algorithms specifically designed for solving ADCOPs.

AAAI Conference 2020 Conference Paper

Beyond Trees: Analysis and Convergence of Belief Propagation in Graphs with Multiple Cycles

• Roie Zivan
• Omer Lev
• Rotem Galiki

Belief propagation, an algorithm for solving problems represented by graphical models, has long been known to converge to the optimal solution when the graph is a tree. When the graph representing the problem includes a single cycle, the algorithm either converges to the optimal solution or performs periodic oscillations. While the conditions that trigger these two behaviors have been established, the question regarding the convergence and divergence of the algorithm on graphs that include more than one cycle is still open. Focusing on Max-sum, the version of belief propagation for solving distributed constraint optimization problems (DCOPs), we extend the theory on the behavior of belief propagation in general – and Max-sum specifically – when solving problems represented by graphs with multiple cycles. This includes: 1) Generalizing the results obtained for graphs with a single cycle to graphs with multiple cycles, by using backtrack cost trees (BCT). 2) Proving that when the algorithm is applied to adjacent symmetric cycles, the use of a large enough damping factor guarantees convergence to the optimal solution.

AIJ Journal 2020 Journal Article

Governing convergence of Max-sum on DCOPs through damping and splitting

• Liel Cohen
• Rotem Galiki
• Roie Zivan

Max-sum is a version of Belief Propagation, used for solving DCOPs. In tree-structured problems, Max-sum converges to the optimal solution in linear time. Unfortunately, when the constraint graph representing the problem includes multiple cycles (as in many standard DCOP benchmarks), Max-sum does not converge and explores low quality solutions. Recent attempts to address this limitation proposed versions of Max-sum that guarantee convergence, while ignoring some of the problem's constraints. Damping is a method that is often used for increasing the chances that Belief Propagation will converge. That being said, it has not been suggested for inclusion in the algorithms that propose Max-sum for solving DCOPs. In this paper we advance the research on incomplete-inference DCOP algorithms by: 1) investigating the effect of damping on Max-sum. We prove that, while damping slows down the propagation of information among agents, on tree-structured graphs, Max-sum with damping is guaranteed to converge to the optimal solution in weakly polynomial time; and 2) proposing a novel method for adjusting the level of asymmetry in the factor graph, in order to achieve a balance between exploitation and exploration, when using Max-sum for solving DCOPs. By converting a standard factor graph to an equivalent split constraint factor graph (SCFG), in which each function-node is split into two function-nodes, we can control the level of asymmetry for each constraint. Our empirical results demonstrate a drastic improvement in the performance of Max-sum when using damping (referred to herein as Damped Max-sum, DMS). However, in contrast to the common assumption that Max-sum performs best when converging, we demonstrate that non converging versions perform efficient exploration, and produce high quality results, when implemented within an anytime framework. On most standard benchmarks, the best results were achieved using versions with a high damping factor, which outperformed existing incomplete DCOP algorithms. In addition, our results imply that by applying DMS to SCFGs with a minor level of asymmetry, we can find high quality solutions within a small number of iterations, even without using an anytime framework. We prove that for a factor graph with a single constraint, if this constraint is split symmetrically, Max-sum applied to the resulting cycle is guaranteed to converge to the optimal solution. We further demonstrate that for an asymmetric split, convergence is not guaranteed.

TIST Journal 2020 Journal Article

Market Clearing–based Dynamic Multi-agent Task Allocation

• Sofia Amador Nelke
• Steven Okamoto
• Roie Zivan

Realistic multi-agent team applications often feature dynamic environments with soft deadlines that penalize late execution of tasks. This puts a premium on quickly allocating tasks to agents. However, when such problems include temporal and spatial constraints that require tasks to be executed sequentially by agents, they are NP-hard, and thus are commonly solved using general and specifically designed incomplete heuristic algorithms. We propose FMC_TA, a novel such incomplete task allocation algorithm that allows tasks to be easily sequenced to yield high-quality solutions. FMC_TA first finds allocations that are fair (envy-free), balancing the load and sharing important tasks among agents, and efficient (Pareto optimal) in a simplified version of the problem. It computes such allocations in polynomial or pseudo-polynomial time (centrally or distributedly, respectively) using a Fisher market with agents as buyers and tasks as goods. It then heuristically schedules the allocations, taking into account inter-agent constraints on shared tasks. We empirically compare our algorithm to state-of-the-art incomplete methods, both centralized and distributed, on law enforcement problems inspired by real police logs. We present a novel formalization of the law enforcement problem, which we use to perform our empirical study. The results show a clear advantage for FMC_TA in total utility and in measures in which law enforcement authorities measure their own performance. Besides problems with realistic properties, the algorithms were compared on synthetic problems in which we increased the size of different elements of the problem to investigate the algorithm’s behavior when the problem scales. The domination of the proposed algorithm was found to be consistent.

JAIR Journal 2019 Journal Article

Distributed Gibbs: A Linear-Space Sampling-Based DCOP Algorithm

• Duc Thien Nguyen
• William Yeoh
• Hoong Chuin Lau
• Roie Zivan

Researchers have used distributed constraint optimization problems (DCOPs) to model various multi-agent coordination and resource allocation problems. Very recently, Ottens et al. proposed a promising new approach to solve DCOPs that is based on confidence bounds via their Distributed UCT (DUCT) sampling-based algorithm. Unfortunately, its memory requirement per agent is exponential in the number of agents in the problem, which prohibits it from scaling up to large problems. Thus, in this article, we introduce two new sampling-based DCOP algorithms called Sequential Distributed Gibbs (SD-Gibbs) and Parallel Distributed Gibbs (PD-Gibbs). Both algorithms have memory requirements per agent that is linear in the number of agents in the problem. Our empirical results show that our algorithms can find solutions that are better than DUCT, run faster than DUCT, and solve some large problems that DUCT failed to solve due to memory limitations.

AIJ Journal 2019 Journal Article

Privacy preserving region optimal algorithms for symmetric and asymmetric DCOPs

• Tal Grinshpoun
• Tamir Tassa
• Vadim Levit
• Roie Zivan

Region-optimal algorithms are local search algorithms for solving Distributed Constraint Optimization Problems (DCOPs). In each iteration of the search in such algorithms, every agent selects a group of agents that comply with some selection criteria (each algorithm specifies different criteria). Then, the agent who selected the group, called the mediator, collects assignment information from the group and neighboring agents outside the group, in order to find an optimal set of assignments for its group's agents. A contest between mediators of adjacent groups determines which groups will replace their assignments in that iteration to the found optimal ones. In this work we present a framework called RODA (Region Optimal DCOP Algorithm) that encompasses the algorithms in the region optimality family, and in particular any method for selecting groups. We devise a secure implementation of RODA, called P-RODA, which preserves constraint privacy and partial decision privacy. Our discussion covers both symmetric and asymmetric DCOPs. The two main cryptographic means that enable this privacy preservation are secret sharing and homomorphic encryption. We estimate the computational overhead of P-RODA with respect to RODA and give an upper bound that depends on the group and domain sizes and on the graph topology, but not on the number of agents. The estimations are substantiated with experimental results, including experiments on a simulator, that compare the performance of P-RODA to that of its competing algorithm, P-Max-Sum.

EAAI Journal 2018 Journal Article

Applying max-sum to teams of mobile sensing agents

• Harel Yedidsion
• Roie Zivan
• Alessandro Farinelli

Multi-agent applications that include teams of mobile sensing agents are challenging since they are inherently dynamic and a single movement of a mobile sensor can change the problem that the entire team is facing. A variation of the Distributed Constraint Optimization model for Mobile Sensor Teams (DCOP_MST) was previously adjusted to represent such problems along with local search algorithms that were enhanced with exploration methods. This paper considers the use of the Max-sum algorithm for solving problems of deploying a mobile sensor team in an unknown environment to track and monitor points of interest (targets), represented by the DCOP_MST model. The DCOP_MST model allows the representation of different functions for aggregating the joint coverage of targets by multiple sensors. The use of different functions has a dramatic effect on the complexity of the Max-sum algorithm. When using cardinality functions, Max-sum can be performed efficiently regardless of the arity of constraints. When Max-sum is used to solve applications that require other (more complex) aggregation functions, its complexity is exponential in the arity of the constraints and thus, its usefulness is limited. In this paper we investigate the performance of the Max-sum algorithm on two implementations of the DCOP_MST model. Each implementation considers a different joint credibility function for determining the coverage for each target, with respect to the locations and the credibility of agents. In the first, the coverage is calculated according to the number of agents that are located within sensing range from the target. This function can be calculated efficiently. The second takes the angle between the lines of sight of different agents to a target into consideration. The larger the difference in the angle between the lines of sight, the higher the coverage efficiency. We analyze the challenges in adjusting the Max-sum algorithm in both scenarios and propose enhancements of the algorithm that make it more efficient. We provide empirical evidence of the advantages resulting from these enhancements in comparison to the naive algorithm.

IJCAI Conference 2018 Conference Paper

Socially Motivated Partial Cooperation in Multi-agent Local Search

• Tal Ze'evi
• Roie Zivan
• Omer Lev

Partial Cooperation is a paradigm and a corresponding model, proposed to represent multi-agent systems in which agents are willing to cooperate to achieve a global goal, as long as some minimal threshold on their personal utility is satisfied. Distributed local search algorithms were proposed in order to solve asymmetric distributed constraint optimization problems (ADCOPs) in which agents are partially cooperative. We contribute by: 1) extending the partial cooperative model to allow it to represent dynamic cooperation intentions, affected by changes in agents’ wealth, in accordance with social studies literature. 2) proposing a novel local search algorithm in which agents receive indications of others’ preferences on their actions and thus, can perform actions that are socially beneficial. Our empirical study reveals the advantage of the proposed algorithm in multiple benchmarks. Specifically, on realistic meeting scheduling problems it overcomes limitations of standard local search algorithms.

AAMAS Conference 2018 Conference Paper

Socially Motivated Partial Cooperation in Multi-agent Local Search

• Tal Ze'evi
• Roie Zivan
• Omer Lev

Partial Cooperation is a paradigm and a corresponding model for representing multi-agent systems in which agents are willing to cooperate in order to achieve a global goal, as long as some minimal threshold on their personal utility is satisfied. Distributed local search algorithms were proposed in order to solve asymmetric distributed constraint optimization problems (ADCOPs) in which agents are partially cooperative. We contribute by: 1) extending the partial cooperative model to allow it to represent dynamic cooperation intentions, affected by changes in agents’ wealth, in accordance with social studies literature. 2) proposing a novel local search algorithm in which agents receive indications of others’ preferences on their actions and thus, can perform actions that are socially beneficial. Our empirical study reveals the advantage of the proposed algorithm in multiple benchmarks. Specifically, on realistic meeting scheduling problems it overcomes limitations of standard local search algorithms.

JAAMAS Journal 2017 Journal Article

Balancing exploration and exploitation in incomplete Min/Max-sum inference for distributed constraint optimization

• Roie Zivan
• Tomer Parash
• Steven Okamoto

Abstract Distributed Constraint Optimization Problems (DCOPs) are NP-hard and therefore the number of studies that consider incomplete algorithms for solving them is growing. Specifically, the Max-sum algorithm has drawn attention in recent years and has been applied to a number of realistic applications. Unfortunately, in many cases Max-sum does not produce high-quality solutions. More specifically, Max-sum does not converge and explores solutions of low quality when run on problems whose constraint graph representation contains multiple cycles of different sizes. In this paper we advance the state-of-the-art in incomplete algorithms for DCOPs by: (1) proposing a version of the Max-sum algorithm that operates on an alternating directed acyclic graph (Max-sum_AD), which guarantees convergence in linear time; (2) solving a major weakness of Max-sum and Max-sum_AD that causes inconsistent costs/utilities to be propagated and affect the assignment selection, by introducing value propagation to Max-sum_AD (Max-sum_ADVP); and (3) proposing exploration heuristic methods that evidently improve the algorithms performance further. We prove that Max-sum_ADVP converges to monotonically improving states after each change of direction, and that it is guaranteed to converge in pseudo-polynomial time to a stable solution that does not change with further changes of direction. Our empirical study reveals a large improvement in the quality of the solutions produced by Max-sum_ADVP on various benchmarks, compared to the solutions produced by the standard Max-sum algorithm, Bounded Max-sum and Max-sum_AD with no value propagation. It is found to be the best guaranteed convergence inference algorithm for DCOPs. The exploration methods we propose for Max-sum_ADVP improve its performance further. However, anytime results demonstrate that their exploration level is not as efficient as a version of Max-sum, which uses Damping.

AAMAS Conference 2017 Conference Paper

Incentivizing Cooperation between Heterogeneous Agents in Dynamic Task Allocation

• Sofia Amador Nelke
• Roie Zivan

Market Clearing is an economic concept that features attractive properties when used for resource and task allocation, e. g. , Pareto optimality and Envy Freeness. Recently, an algorithm based on Market Clearing, FMC_TA, has been shown to be most effective for realistic dynamic multi agent task allocation, outperforming general optimization methods, e. g. , Simulated annealing, and dedicated algorithms, specifically designed for task allocation. That been said, FMC_TA was applied to a homogeneous team of agents and used linear personal utility functions for representing agents’ preferences. These properties limited the settings on which the algorithm could be applied. In this paper we advance the research on task allocation methods based on market clearing by enhancing the FMC_TA algorithm such that it: 1) can use concave personal utility functions as its input and 2) can apply to applications which require the collaboration of heterogeneous agents, i. e. agents with different capabilities. We demonstrate that the use of concave functions indeed encourages collaboration among agents. Our results on both homogeneous and heterogeneous scenarios indicate that the use of personal utility functions with small concavity is enough to achieve the desired incentivized cooperation result, and on the other hand, in contrast to functions with increased concavity, does not cause a severe delay in the execution of tasks.

AAMAS Conference 2017 Conference Paper

Infinite-Horizon Proactive Dynamic DCOPs

• Khoi D. Hoang
• Ping Hou
• Ferdinando Fioretto
• William Yeoh
• Roie Zivan
• Makoto Yokoo

The Distributed Constraint Optimization Problem (DCOP) formulation is a powerful tool for modeling multi-agent coordination problems. Researchers have recently extended this model to Proactive Dynamic DCOPs (PD-DCOPs) to capture the inherent dynamism present in many coordination problems. The PD-DCOP formulation is a finite-horizon model that assumes a finite horizon is known a priori. It ignores changes to the problem after the horizon and is thus not guaranteed to find optimal solutions for infinite-horizon problems, which often occur in the real world. Therefore, we (i) propose the Infinite-Horizon PD-DCOP (IPD- DCOP) model, which extends PD-DCOPs to handle infinite horizons; (ii) exploit the convergence properties of Markov chains to determine the optimal solution to the problem after it has converged; (iii) propose three distributed greedy algorithms to solve IPD-DCOPs; (iv) provide theoretical quality guarantees on the new model; and (v) empirically evaluate both proactive and reactive algorithms to determine the tradeoffs between the two classes. The final contribution is important as, thus far, researchers have exclusively evaluated the two classes of algorithms in isolation. As a result, it is difficult to identify the characteristics of problems that they excel in. Our results are the first in this important direction.

AAMAS Conference 2017 Conference Paper

Max-sum Revisited; The Real Power of Damping

• Liel Cohen
• Roie Zivan

JAIR Journal 2017 Journal Article

Privacy Preserving Implementation of the Max-Sum Algorithm and its Variants

• Tamir Tassa
• Tal Grinshpoun
• Roie Zivan

One of the basic motivations for solving DCOPs is maintaining agents' privacy. Thus, researchers have evaluated the privacy loss of DCOP algorithms and defined corresponding notions of privacy preservation for secured DCOP algorithms. However, no secured protocol was proposed for Max-Sum, which is among the most studied DCOP algorithms. As part of the ongoing effort of designing secure DCOP algorithms, we propose P-Max-Sum, the first private algorithm that is based on Max-Sum. The proposed algorithm has multiple agents preforming the role of each node in the factor graph, on which the Max-Sum algorithm operates. P-Max-Sum preserves three types of privacy: topology privacy, constraint privacy, and assignment/decision privacy. By allowing a single call to a trusted coordinator, P-Max-Sum also preserves agent privacy. The two main cryptographic means that enable this privacy preservation are secret sharing and homomorphic encryption. In addition, we design privacy-preserving implementations of four variants of Max-Sum. We conclude by analyzing the price of privacy in terns of runtime overhead, both theoretically and by extensive experimentation.

AAMAS Conference 2016 Conference Paper

Applying DCOP_MST to a Team of Mobile Robots with Directional Sensing Abilities (Extended Abstract)

• Harel Yedidsion
• Roie Zivan

IJCAI Conference 2016 Conference Paper

Distributed Breakout: Beyond Satisfaction

• Steven Okamoto
• Roie Zivan
• Aviv Nahon

The Distributed Breakout Algorithm (DBA) is a local search algorithm that was originally designed to solve DisCSPs and DisMaxCSPs. Extending it to general-valued DCOPs requires three design choices: manner of modifying base costs (multiplicative weights or additive penalties); definition of constraint violation (non-zero cost, non-minimum cost, and maximum cost); and scope of modifying cost tables during breakout (entry, row, column, or table). We propose Generalized DBA (GDBA) to span the 24 combinations in the three dimensions. In our theoretical analysis we prove that some variants of GDBA are equivalent for certain problems, and prove that other variants may find suboptimal solutions even on tree topologies where DBA is complete. Our extensive empirical evaluation on various benchmarks shows that in practice, GDBA is capable of finding solutions of equal or significantly lower cost than alternative heuristic approaches (including DSA).

IJCAI Conference 2016 Conference Paper

Preserving Privacy in Region Optimal DCOP Algorithms

• Tamir Tassa
• Roie Zivan
• Tal Grinshpoun

Region-optimal algorithms are local search algorithms for the solution of Distributed ConstraintOptimization Problems (DCOPs). In each iteration of the search in such algorithms, every agent selects a group of agents that comply with some selection criteria (each algorithm specifies different criteria). Then, the agent who selected the group, called the mediator, collects assignment information from the group and neighboring agents outside the group, in order to find an optimal set of assignments for its group's agents. A contest between mediators of adjacent groups determines which groups will replace their assignments in that iteration to the found optimal ones. In this work we present a framework called RODA (Region-Optimal DCOP Algorithm) that encompasses the algorithms in the region-optimality family, and in particular any method for selecting groups. We devise a secure implementation of RODA, called PRODA, which preserves constraint privacy and partial decision privacy. The two main cryptographic means that enable this privacy preservation are secret sharing and homomorphic encryption. We estimate the computational overhead of P-RODA with respect to RODA and give an upper bound that depends on the group and domain sizes and the graph topology but not on the number of agents. The estimations are backed with experimental results.

AAMAS Conference 2016 Conference Paper

Proactive Dynamic Distributed Constraint Optimization

• Khoi D. Hoang
• Ferdinando Fioretto
• Ping Hou
• Makoto Yokoo
• William Yeoh
• Roie Zivan

Current approaches that model dynamism in DCOPs solve a sequence of static problems, reacting to changes in the environment as the agents observe them. Such approaches thus ignore possible predictions on future changes. To overcome this limitation, we introduce Proactive Dynamic DCOPs (PD-DCOPs), a novel formalism to model dynamic DCOPs in the presence of exogenous uncertainty. In contrast to reactive approaches, PD-DCOPs are able to explicitly model the possible changes to the problem, and take such information into account proactively, when solving the dynamically changing problem. The additional expressivity of this formalism allows it to model a wider variety of distributed optimization problems. Our work presents both theoretical and practical contributions that advance current dynamic DCOP models: (i) we introduce the PD-DCOP model, which explicitly captures dynamic changes of the DCOP over time; (ii) we discuss the complexity of this new class of DCOPs; and (iii) we develop both exact and approximation algorithms with quality guarantees to solve PD- DCOPs proactively.

IJCAI Conference 2015 Conference Paper

Applying Max-Sum to Asymmetric Distributed Constraint Optimization

• Roie Zivan
• Tomer Parash
• Yarden Naveh

We study the adjustment and use of the Max-sum algorithm for solving Asymmetric Distributed Constraint Optimization Problems (ADCOPs). First, we formalize asymmetric factor-graphs and apply the different versions of Max-sum to them. Apparently, in contrast to local search algorithms, most Max-sum versions perform similarly when solving symmetric and asymmetric problems and some even perform better on asymmetric problems. Second, we prove that the convergence properties of Max-sum ADVP (an algorithm that was previously found to outperform other Max-sum versions) and the quality of the solutions it produces are dependent on the order between nodes involved in each constraint, i. e. , the inner constraint order (ICO). A standard ICO allows to reproduce the properties achieved for symmetric problems, and outperform previously proposed local search ADCOP algorithms. Third, we demonstrate that a non-standard ICO can be used to balance exploration and exploitation, resulting in the best performing Maxsum version on both symmetric and asymmetric standard benchmarks.

JAAMAS Journal 2015 Journal Article

Distributed envy minimization for resource allocation

• Arnon Netzer
• Amnon Meisels
• Roie Zivan

Abstract Minimizing envy in distributed discrete resource or task allocation, is an unusual distributed optimization challenge, since the quality of the allocation for each of the agents is dependent, not only on its own allocation, but on the allocation of others as well. Thus, in order to perform distributed search for allocations with minimal envy there is a need to design innovative algorithms that can cope with the challenging constraint structure of an envy minimization problem. Distributed methods for minimizing envy among agents in indivisible resource allocation problems are presented. First, Distributed Envy Minimization Problems (DEMP) are formulated as Distributed Constraint Reasoning problems. When the DEMPs are large, and cannot be solved by a complete search an incomplete local search algorithm is presented. Each transfer of a good from one agent to another involves the change of state of more than one agent. Thus, a minimizing envy local search algorithm must build upon actions (transfers) that include multiple agents. Since DEMPs are particularly susceptible to local minima during local search, the paper proposes an algorithm that alternates between two different hill climbing search phases. The first phase uses one-transfer steps while the other exploits envy cycle elimination steps. An algorithm that minimizes envy while preserving efficiency, is proposed. The proposed algorithm finds a Pareto optimal allocation with low envy. In the context of resource allocation problems, a Pareto optimal solution is particularly desirable since it presents a stable solution. The proposed algorithm first finds a divisible Pareto optimal envy-free allocation using a Fisher market equilibrium. This allocation is transferred into an indivisible allocation of goods while maintaining the Pareto optimal characteristic of the allocation and a low envy level among agents.

IJCAI Conference 2015 Conference Paper

Max-Sum Goes Private

• Tamir Tassa
• Roie Zivan
• Tal Grinshpoun

As part of the ongoing effort of designing secure DCOP algorithms, we propose P-MAX-SUM, the first private algorithm that is based on MAX-SUM. The proposed algorithm has multiple agents preforming the role of each node in the factor graph, on which the MAX-SUM algorithm operates. P-MAX- SUM preserves three types of privacy: topology privacy, constraint privacy, and assignment/decision privacy. By allowing a single call to a trusted coordinator, P-MAX-SUM also preserves agent privacy. The two main cryptographic means that enable this privacy preservation are secret sharing and homomorphic encryption. Our experiments on structured and realistic problems show that the overhead of privacy preservation in terms of runtime is reasonable.

JAAMAS Journal 2014 Journal Article

Distributed constraint optimization for teams of mobile sensing agents

• Roie Zivan
• Harel Yedidsion
• Katia Sycara

Abstract Coordinating a mobile sensor team (MST) to cover targets is a challenging problem in many multiagent applications. Such applications are inherently dynamic due to changes in the environment, technology failures, and incomplete knowledge of the agents. Agents must adaptively respond by changing their locations to continually optimize the coverage of targets. We propose distributed constraint optimization problems (DCOP)_MST, a new model for representing MST problems that is based on DCOP. In DCOP_MST, agents maintain variables for their physical positions, while each target is represented by a constraint that reflects the quality of coverage of that target. In contrast to conventional, static DCOPs, DCOP_MST not only permits dynamism but exploits it by restricting variable domains to nearby locations; consequently, variable domains and constraints change as the agents move through the environment. DCOP_MST confers three major advantages. It directly represents the multiple forms of dynamism inherent in MSTs. It also provides a compact representation that can be solved efficiently with local search algorithms, with information and communication locality based on physical locality as typically occurs in MST applications. Finally, DCOP_MST facilitates organization of the team into multiple sub-teams that can specialize in different roles and coordinate their activity through dynamic events. We demonstrate how a search-and-detection team responsible for finding new targets and a surveillance sub-team tasked with coverage of known targets can effectively work together to improve performance while using the DCOP_MST framework to coordinate. We propose different algorithms to meet the specific needs of each sub-team and several methods for cooperation between sub-teams. For the search-and-detection team, we develop an algorithm based on the DSA that forces intensive exploration for new targets. For the surveillance sub-team, we adapt several incomplete DCOP algorithms, including MGM, DSA, DBA, and Max-sum, which requires us to develop an efficient method for agents to find the value assignment in their local environment that is optimal in minimizing the maximum unmet coverage requirement over all targets. The disadvantage of dynamic domains based on physical locality is that adaptations of standard local search algorithms tend to become trapped in local optima where targets beyond the immediate range of the agents go uncovered. To address this shortcoming we develop exploration methods to be used with the local search algorithms. Our algorithms are extensively evaluated in a simulation environment. We use a reputation model to determine the individual credibility of agents and consider both additive and submodular joint credibility functions for determining coverage of targets by multiple agents. The performance is measured on two objectives: minimizing the maximum remaining coverage requirement, and minimizing the sum of remaining coverage requirements. Our results show that DSA and MGM with the exploration heuristics outperform the other incomplete algorithms across a wide range of settings. Furthermore, organizing the team into two sub-teams leads to significant gains in performance, and performance continues to improve with greater cooperation between the sub-teams.

AAAI Conference 2014 Conference Paper

Dynamic Multi-Agent Task Allocation with Spatial and Temporal Constraints

• Sofia Amador
• Steven Okamoto
• Roie Zivan

Realistic multi-agent team applications often feature dynamic environments with soft deadlines that penalize late execution of tasks. This puts a premium on quickly allocating tasks to agents, but finding the optimal allocation is NP-hard due to temporal and spatial constraints that require tasks to be executed sequentially by agents. We propose FMC TA, a novel task allocation algorithm that allows tasks to be easily sequenced to yield high-quality solutions. FMC TA first finds allocations that are fair (envyfree), balancing the load and sharing important tasks between agents, and efficient (Pareto optimal) in a simplified version of the problem. It computes such allocations in polynomial or pseudo-polynomial time (centrally or distributedly, respectively) using a Fisher market with agents as buyers and tasks as goods. It then heuristically schedules the allocations, taking into account inter-agent constraints on shared tasks. We empirically compare our algorithm to state-of-the-art incomplete methods, both centralized and distributed, on law enforcement problems inspired by real police logs. The results show a clear advantage for FMC TA both in total utility and in other measures commonly used by law enforcement authorities.

AIJ Journal 2014 Journal Article

Explorative anytime local search for distributed constraint optimization

• Roie Zivan
• Steven Okamoto
• Hilla Peled

Distributed Constraint Optimization Problems (DCOPs) are an elegant model for representing and solving many realistic combinatorial problems that are distributed by nature. DCOPs are NP-hard and therefore many recent studies consider incomplete algorithms for solving them. Distributed local search algorithms, in which agents in the system hold value assignments to their variables and iteratively make decisions on whether to replace them, can be used for solving DCOPs. 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 that is explored by the algorithm. Previous attempts to use local search algorithms for solving DCOPs reported the state held by the system at the termination of the algorithm, which was not necessarily the (global) best state explored. A general framework that enhances distributed local search algorithms for DCOPs with the anytime property is proposed. The proposed framework makes use of a BFS-tree in order to accumulate the costs of the system's state during the algorithm's iterative performance and to propagate the detection of a new best state when it is found. 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). We further propose a set of increased exploration heuristics that exploit the proposed anytime framework. These exploration methods implement different approaches towards exploration. Our empirical study considers various scenarios including random, realistic, and structured problems. It reveals the advantage of the use of the proposed heuristics in the anytime framework over state-of-the-art local search algorithms.

SoCS Conference 2013 Conference Paper

Multi-Agent Path Finding for Self Interested Agents

• Zahy Bnaya
• Roni Stern
• Ariel Felner
• Roie Zivan
• Steven Okamoto

Multi-agent pathfinding (MAPF) deals with planning paths for individual agents such that a global cost function (e. g. , the sum of costs) is minimized while avoiding collisions between agents. Previous work proposed centralized or fully cooperative decentralized algorithms assuming that agents will follow paths assigned to them. When agents are {\em self-interested}, however, they are expected to follow a path only if they consider that path to be their most beneficial option. In this paper we propose the use of a taxation scheme to implicitly coordinate self-interested agents in MAPF. We propose several taxation schemes and compare them experimentally. We show that intelligent taxation schemes can result in a lower total cost than the non coordinated scheme even if we take into consideration both travel cost and the taxes paid by agents.

AAMAS Conference 2012 Conference Paper

Max/Min-sum Distributed Constraint Optimization through Value Propagation on an Alternating DAG

• Roie Zivan
• Hilla Peled

Distributed Constraint Optimization Problems (DCOPs) are NP-hard and therefore the number of studies that consider incomplete algorithms for solving them is growing. Specifically, the Max-sum algorithm has drawn attention in recent years and has been applied to a number of realistic applications. Unfortunately, in many cases Max-sum does not produce high quality solutions. More specifically, when problems include cycles of various sizes in the factor graph upon which Max-sum performs, the algorithm does not converge and the states that it visits are of low quality. In this paper we advance the research on incomplete algorithms for DCOPs by: (1) Proposing a version of the Max-sum algorithm that operates on an alternating directed acyclic graph (Max-sum\_AD), which guarantees convergence in linear time. (2) Identifying major weaknesses of Max-sum and Max-sum\_AD that cause inconsistent costs/utilities to be propagated and affect the assignment selection. (3) Solving the identified problems by introducing value propagation to Max-sum\_AD. Our empirical study reveals a large improvement in the quality of the solutions produced by Max-sum\_AD with value propagation (VP), when solving problems which include cycles, compared with the solutions produced by the standard Max-sum algorithm, Bounded Max-sum and Max-sum\_AD with no value propagation.

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.

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.

AAMAS Conference 2011 Conference Paper

Can Trust Increase the Efficiency of Cake Cutting Algorithms?

• Roie Zivan

Fair division methods offer guarantees to agents of the proportional size or quality of their share in a division of a resource (cake). These guarantees come with a price. Standard fair division methods (or "cake cutting" algorithms) do not find efficient allocations (not Pareto optimal). The lack of efficiency of these methods makes them less attractive for solving multi-agent resource and task allocation. Previous attempts to increase the efficiency of cake cutting algorithms for two agents resulted in asymmetric methods that were limited in their ability to find allocations in which both agents receive more than their proportional share. Trust can be the foundation on which agents exchange information and enable the exploration of allocations that are beneficial for both sides. On the other hand, the willingness of agents to put themselves in a vulnerable position due to their trust in others, results in loss of the fairness guarantees that motivate the design of fair division methods. In this work we extend the study on fair and efficient cake cutting algorithms by proposing a new notion of trust-based efficiency, which formulates a relation between the level of trust between agents and the efficiency of the allocation. Furthermore, we propose a method for finding trust-based efficiency. The proposed method offers a balance between the guarantees that fair division methods offer to agents and the efficiency that can be achieved by exposing themselves to the actions of other agents. When the level of trust is the highest, the allocation produced by the method is globally optimal (social welfare).

AAMAS Conference 2011 Conference Paper

Maximizing Revenue in Symmetric Resource Allocation Systems When User Utilities Exhibit Diminishing Returns

• Roie Zivan
• Miroslav Dud
• iacute; k
• Praveen Paruchuri
• Katia Sycara

Consumers of resources in realistic applications (e. g. , web, multimedia) typically derive diminishing-return utilities from the amount of resource they receive. A resource provider who is deriving an equal amount of revenue from each satisfied user (e. g. , by online advertising), can maximize the number of users by identifying a satisfaction threshold for each user, i. e. , the minimal amount of resource the user requires in order to use the service (rather than drop out). A straightforward approach is to ask users to submit their minimal demands (direct revelation). Unfortunately, self-interested users may try to manipulate the system by submitting untruthful requirements. We propose an incentive-compatible mechanism for maximizing revenue in a resource allocation system where users are ex-ante symmetric (same amount of revenue for any satisfied user) and have diminishing-return utility functions. Users are encouraged by the mechanism to submit their true requirements and the system aims to satisfy as many users as possible. Unlike previous solutions, our mechanism does not require monetary payments from users or downgrading of service. Our mechanism satisfies the number of users within a constant factor of the optimum. Our empirical evaluation demonstrates that in practice, our mechanism can be significantly closer to the optimum than implied by the worst-case analysis. Our mechanism can be generalized to settings when revenue from each user can differ. Also, under some assumptions and adjustments, our mechanism can be used to allocate resource periodically over time.

AAMAS Conference 2010 Conference Paper

Deception in Networks of Mobile Sensing Agents

• Viliam Lis
• yacute;
• Roie Zivan
• Katia Sycara
• Michal Péchouček

Recent studies have investigated how a team of mobile sensors can cope withreal world constraints, such as uncertainty in the reward functions, dynamically appearing and disappearing targets, technology failures endchanges in the environment conditions. In this study we consider an additional element, deception by an adversary, which is relevant in many (military) applications. The adversary isexpected to use deception to prevent the sensor team from performing itstasks. We employ a game theoretic model to analyze the expected strategy ofthe adversary and find the best response. More specifically we considerthat the adversary deceptively changes the importance that agents give totargets in the area. The opponent is expected to use camouflage in order to create confusionamong the sensors regarding the importance of targets, and reduce the team'sefficiency in target coverage. We represent a Mobile Sensor Team problem using the Distributed ConstraintOptimization Problem (DCOP) framework. We propose an optimal method for theselection of a position of a single agent facing a deceptive adversary. Thismethod serves as a heuristic for agents to select their position in a fullscale problem with multiple agents in a large area. Our empirical study demonstrates the success of our model as compared withexisting models in the presence of deceptions.

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.

AAMAS Conference 2008 Conference Paper

Anytime Local Search for Distributed Constraint Optimization

• Roie Zivan

AAAI Conference 2008 Conference Paper

Anytime Local Search for Distributed Constraint Optimization

• Roie Zivan

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 Dis- COP algorithms which make use of a pseudo-tree (ADOPT, DPOP).

IJCAI Conference 2007 Conference Paper

• Roie Zivan
• Amnon Meisels

Max-CSPs are Constraint Optimization Problems that are commonly solved using a Branch and Bound algorithm. The B\B algorithm was enhanced by consistency maintenance procedures. All these algorithms traverse the search space in a chronological order and gain their efficiency from the quality of the consistency maintenance procedure. The present study introduces Conflict-directed Backjumping (CBJ) for Branch and Bound algorithms. The proposed algorithm maintains Conflict Sets which include only assignments whose replacement can lead to a better solution. The algorithm backtracks according to these sets. CBJ can be added to all classes of the Branch and Bound algorithm, in particular to versions of Branch and Bound that use advanced maintenance procedures of local consistency levels, NC*, AC* and FDAC. The experimental evaluation of B&B CBJ on random Max-CSPs shows that the performance of all algorithms is improved both in the number of assignments and in the time for completion.

ECAI Conference 2006 Conference Paper

Asynchronous Forward-Bounding for Distributed Constraints Optimization

• Amir Gershman
• Amnon Meisels
• Roie Zivan

A new search algorithm for solving distributed constraint optimization problems (DisCOPs) is presented. Agents assign variables sequentially and propagate their assignments asynchronously. The asynchronous forward-bounding algorithm (AFB) is a distributed optimization search algorithm that keeps one consistent partial assignment at all times. Forward bounding propagates the bounds on the cost of solutions by sending copies of the partial assignment to all unassigned agents concurrently. The algorithm is described in detail and its correctness proven. Experimental evaluation of AFB on random Max-DisCSPs reveals a phase transition as the tightness of the problem increases. This effect is analogous to the phase transition of Max-CSP when local consistency maintenance is applied [3]. AFB outperforms Synchronous Branch & Bound (SBB) as well as the asynchronous state-of-the-art ADOPT algorithm, for the harder problem instances. Both asynchronous algorithms outperform SBB by a large factor.

AIJ Journal 2006 Journal Article

Concurrent search for distributed CSPs

• Roie Zivan
• Amnon Meisels

A distributed concurrent search algorithm for distributed constraint satisfaction problems (DisCSPs) is presented. Concurrent search algorithms are composed of multiple search processes (SPs) that operate concurrently and scan non-intersecting parts of the global search space. Each SP is represented by a unique data structure, containing a current partial assignment (CPA), that is circulated among the different agents. Search processes are generated dynamically, started by the initializing agent, and by any number of agents during search. In the proposed, ConcDB, algorithm, all search processes perform dynamic backtracking. As a consequence of backjumping, a search space can be found unsolvable by a different search process. This enhances the efficiency of the ConcDB algorithm. Concurrent Dynamic Backtracking is an asynchronous distributed algorithm and is shown to be faster than former algorithms for solving DisCSPs. Experimental evaluation of ConcDB, on randomly generated DisCSPs demonstrates that the network load of ConcDB is similar to the network load of synchronous backtracking and is much lower than that of asynchronous backtracking. The advantage of Concurrent Search is more pronounced in the presence of imperfect communication, when messages are randomly delayed.