Author name cluster

Ben Rachmut

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.

6 papers

1 author row

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.

Details DOI

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.

PDF Details DOI

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.

PDF

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.

Details DOI

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.

PDF Details DOI

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.

PDF