Meir Kalech

AAMAS Conference 2026 Conference Paper

Diagnosing Faults in Deep Reinforcement Learning based Systems: Settings and Benchmarks

• Avraham Natan
• Roni Stern
• Meir Kalech

Deep Reinforcement Learning (DRL) is often used to generate control policies for autonomous agents. These policies are trained to controlagentswhentheyoperatenormally. Thus, unexpectedfaults may cause agents controlled using these policies to fail. When this occurs, it is important to understand and explain the root cause of such failures. In this paper, we define this diagnosis problem under different settings and assumptions. We also provide a benchmark suite for evaluating algorithms for solving this problem based on environments from AI Gym, a popular DRL framework.

AAAI Conference 2026 Conference Paper

Robust Multiagent Combinatorial Path Finding

• Yehonatan Kidushim
• Avraham Natan
• Roni Stern
• Meir Kalech

Consider a system of multiple physical agents tasked with collaboratively collecting a set of spatially distributed goals as quickly as possible while avoiding collisions with the environment and with each other. This type of problem, which involves Multi-Agent Path Finding (MAPF) and task allocation, is called Multi-Agent Combinatorial Path Finding (MCPF). Prior work on MCPF assumed each agent has a final goal it must reach, there are no orientation constraints on the agents' movements, and the agents will follow their planned actions as intended. These assumptions rarely hold in real physical robots, which limits the applicability of existing MCPF algorithms in practical applications. We propose the Robust CBSS framework, a robust planning approach that solves MCPF without the aforementioned simplifying assumptions, and provide two implementations: a baseline version (RCbssBase) and an efficient version (RCbssEff). RCbssEff generalizes the Conflict-Based Steiner Search (CBSS) algorithm, building on ideas from the p-Robust CBS algorithm and algorithms for solving the Equality Generalized Traveling Salesman Problem. We prove that RCbssEff is complete and can be configured to return optimal solutions. Experimental results on benchmark MCPF problems show that RCbssEff balances planning time, solution cost, and collision reduction compared to baselines.

ECAI Conference 2023 Conference Paper

Blame Attribution for Multi-Agent Path Finding Execution Failures

• Avraham Natan
• Roni Stern
• Meir Kalech

In Multi-Agent Systems (MAS), Multi-Agent Path Finding (MAPF) is the problem of finding a conflict-free plan for a group of agents from a set of starting points to a set of target points. Deviations from this plan are standard in real-world applications and may decrease overall system efficiency and even lead to accidents and deadlocks. In large MAS scenarios with physical robots, multiple faulty events occur over time, contributing to the overall degraded system performance. This raises the main problem we address in this work: how to attribute blame for a degraded MAS performance over a set of faulty events. We formally define this problem and propose using the Shapley values to solve it. Then, we propose an algorithm that efficiently approximates Shapley values by considering only some subsets of faulty events set. We analyze this algorithm theoretically and experimentally and demonstrate that it enables effectively trading off runtime for error.

AAMAS Conference 2023 Conference Paper

Blame Attribution for Multi-Agent Pathfinding Execution Failures

• Avraham Natan
• Roni Stern
• Meir Kalech

When executing large Multi-Agent Path Finding (MAPF) scenarios, faulty events can occur over time and contribute to the overall degraded system performance. This raises the problem of how to attribute blame over the set of faulty events. The first contribution of this paper is to define this problem and propose the well-known Shapley value for solving it. The second contribution is an efficient approach for approximating Shapley values that is inspired by diagnosis concepts.

KR Conference 2023 Conference Paper

Diagnosis for Post Concept Drift Decision Trees Repair

• Shaked Almog
• Meir Kalech

Decision trees are commonly used in machine learning since they are accurate and robust classifiers. After a decision tree is built, the data can change over time, causing the classification performance to decrease. This data distribution change is a known challenge in machine learning, referred to as concept drift. Once a concept drift has been detected, usually by experiencing a decrease in the model's performance, it can be handled by training a new model. However, this method does not explain the drift harming the performance but only handles the drift's effects. The main contribution of this paper presents a novel two-step approach called APPETITE, which applies diagnosis techniques to identify the feature that has drifted and then adjusts the model accordingly. For the diagnosis step, we present two algorithms. We experimented on 73 known datasets from the literature and semi-synthesized drifts in their features. Both algorithms are better at handling concept drift than training a new model based on the samples after the drift. Combining the two algorithms can provide an explanation of the drift and is a competitive model against a new model trained on the entire data from before and after the drift.

AIJ Journal 2023 Journal Article

Diagnosis of intermittent faults in Multi-Agent Systems: An SFL approach

• Avraham Natan
• Meir Kalech
• Roman Barták

Multi-Agent Systems (MAS) can be found in a wide variety of applications, including industrial systems, transportation, software systems and more. In such systems, agents may experience faults that affect the performance of the whole system. However, faulty agents might not consistently experience their fault, but rather in certain conditions. For example, a robot with a faulty rotating mechanism will appear healthy if it is tasked to only move in a straight line. Those faults are called Intermittent Faults. Such faults may cause the entire system to fail, but not always. Previous work proposed diagnosis algorithms for MAS, assuming faulty agents persistently behave abnormally. To the best of our knowledge, intermittent faults in MAS have not been concretely explored. In this paper we formally present a novel problem called Diagnosis of Intermittent Faults in Multi-Agent Systems (DIFMAS): a group of agents are observed across multiple runs. In each run, the success/failure of the agents and the system is observed, aiming to explain all the failed runs by diagnosing which agent(s) are faulty. The contributions of this paper are: (1) formalizing DIFMAS as a Model-Based Diagnosis problem, (2) solving it by presenting a Spectrum-Based Fault Localization (SFL) based method, called Multi-Run SFL-based Diagnosis Algorithm (MRSD). Experiments demonstrate that MRSD's outperforms competing SFL-based algorithms. Moreover, the algorithm's performance increases if planned interactions are considered.

AAAI Conference 2023 Conference Paper

Distributed Spectrum-Based Fault Localization

• Avraham Natan
• Roni Stern
• Meir Kalech

Spectrum-Based Fault Localization (SFL) is a popular approach for diagnosing faulty systems. SFL algorithms are inherently centralized, where observations are collected and analyzed by a single diagnoser. Applying SFL to diagnose distributed systems is challenging, especially when communication is costly and there are privacy concerns. We propose two SFL-based algorithms that are designed for distributed systems: one for diagnosing a single faulty component and one for diagnosing multiple faults. We analyze these algorithms theoretically and empirically. Our analysis shows that the distributed SFL algorithms we developed output identical diagnoses to centralized SFL while preserving privacy.

EAAI Journal 2022 Journal Article

Exploring Design smells for smell-based defect prediction

• Bruno Sotto-Mayor
• Amir Elmishali
• Meir Kalech
• Rui Abreu

Defect prediction is commonly used to reduce the effort from the testing phase of software development. A promising strategy is to use machine learning techniques to predict which software components may be defective. Features are key factors to the prediction’s success, and thus extracting significant features can improve the model’s accuracy. In particular, code smells are a category of those features that have been shown to improve the prediction performance significantly. However, Design code smells, a state-of-the-art collection of code smells based on the violations of the object-oriented programming principles, have not been studied in the context of defect prediction. In this paper, we study the performance of defect prediction models by training multiple classifiers for 97 real projects. We compare using Design code smells as features and using other Traditional smells from the literature and both. Moreover, we cluster and analyze the models’ performance based on the categories of Design code smells. We conclude that the models trained with both the Design code smells and the smells from the literature performed the best, with an improvement of 4. 1% for the AUC score, compared to models trained with only Traditional smells. Consequently, Design smells are a good addition to the smells commonly studied in the literature for defect prediction.

AAAI Conference 2022 Conference Paper

Model-Based Diagnosis of Multi-Agent Systems: A Survey

• Meir Kalech
• Avraham Natan

As systems involving multiple agents are increasingly deployed, there is a growing need to diagnose failures in such systems. Model-Based Diagnosis (MBD) is a well known AI technique to diagnose faults in systems. In this approach, a model of the diagnosed system is given, and the real system is observed. A failure is announced when the real system’s output contradicts the model’s expected output. The model then is used to deduce the defective components that explain the unexpected observation. MBD has been increasingly being deployed in distributed and multi-agent systems. In this survey, we summarize twenty years of research in the field of model-based diagnosis algorithms for MAS diagnosis. We depict three attributes that should be considered when examining MAS diagnosis: (1) The objective of the diagnosis. Either diagnosing faults in the MAS plans or diagnosing coordination faults. (2) Centralized vs. distributed. The diagnosis method could be applied either by a centralized agent or by the agents in a distributed manner. (3) Temporal vs. nontemporal. Temporal diagnosis is used to diagnose the MAS’s temporal behaviors, whereas non-temporal diagnosis is used to diagnose the conduct based on a single observation. We survey diverse studies in MBD of MAS based on these attributes, and provide novel research challenges in this field for the AI community.

SoCS Conference 2021 Conference Paper

Contingent Planning for Robust Multi-Agent Path Finding

• Michal Nekvinda
• Roman Barták
• Meir Kalech

A classical approach to Multi-agent Path Finding assumes an offline construction of collision-free paths that the agents blindly follow during execution. k-robust plans can be executed without collisions even if an agent is delayed for at most k steps. In the paper, we propose a novel concept of robustness that uses alternative paths to which the agents are diverted in case of delay. Such plans can be found with much higher chances than k-robust plans.

AAAI Conference 2020 Conference Paper

AI for Software Quality Assurance Blue Sky Ideas Talk

• Meir Kalech
• Roni Stern

Modern software systems are highly complex and often have multiple dependencies on external parts such as other processes or services. This poses new challenges and exacerbate existing challenges in different aspects of software Quality Assurance (QA) including testing, debugging and repair. The goal of this talk is to present a novel AI paradigm for software QA (AI4QA). A quality assessment AI agent uses machine-learning techniques to predict where coding errors are likely to occur. Then a test generation AI agent considers the error predictions to direct automated test generation. Then a test execution AI agent executes tests, that are passed to the root-cause analysis AI agent, which applies automatic debugging algorithms. The candidate root causes are passed to a code repair AI agent that tries to create a patch for correcting the isolated error.

IS Journal 2020 Journal Article

Diagnosing Software System Exploits

• Amir Elmishali
• Roni Stern
• Meir Kalech

Software vulnerabilities are bugs in a program that an attacker can exploit to make the program deviate from its specification. An attacker exploits a vulnerability by crafting input that causes the program to behave incorrectly. Such an input is called an exploit. This article deals with diagnosing exploits, i. e. , given an exploit, the task is to return the vulnerability that allowed it. We show that existing software diagnosis algorithms are ill-suited for this problem, and introduce two novel techniques for adapting them to this problem. This includes manipulating an automated testing tool to generate additional inputs that are similar to the given exploit, and tracing below the desired granularity level to improve diagnostic accuracy. Experimental evaluation on real exploits from four open-source projects shows that our algorithm significantly reduces diagnostic efforts.

AAAI Conference 2020 Conference Paper

Model-Based Diagnosis with Uncertain Observations

• Dean Cazes
• Meir Kalech

Classical model-based diagnosis uses a model of the system to infer diagnoses – explanations – of a given abnormal observation. In this work, we explore how to address the case where there is uncertainty over a given observation. This can happen, for example, when the observations are collected by noisy sensors, that are known to return incorrect observations with some probability. We formally define this common scenario for consistency-based and abductive models. In addition, we analyze the complexity of two complete algorithms we propose for finding all diagnoses and correctly ranking them. Finally, we propose a third algorithm that returns the most probable diagnosis without finding all possible diagnoses. Experimental evaluation shows that this third algorithm can be very effective in cases where the number of faults is small and the uncertainty over the observations is not large. If, however, all possible diagnoses are desired, then the choice between the first two algorithms depends on whether the domain’s diagnosis form is abductive or consistent.

AIJ Journal 2019 Journal Article

Corrigendum to “Sequential plan recognition: An iterative approach to disambiguating between hypotheses” [Artif. Intell. 260 (2018) 51–73]

• Reuth Mirsky
• Roni Stern
• Kobi Gal
• Meir Kalech

TIST Journal 2019 Journal Article

Goal and Plan Recognition Design for Plan Libraries

• Reuth Mirsky
• Kobi Gal
• Roni Stern
• Meir Kalech

This article provides new techniques for optimizing domain design for goal and plan recognition using plan libraries. We define two new problems: Goal Recognition Design for Plan Libraries (GRD-PL) and Plan Recognition Design (PRD). Solving the GRD-PL helps to infer which goal the agent is trying to achieve, while solving PRD can help to infer how the agent is going to achieve its goal. For each problem, we define a worst-case distinctiveness measure that is an upper bound on the number of observations that are necessary to unambiguously recognize the agent’s goal or plan. This article studies the relationship between these measures, showing that the worst-case distinctiveness of GRD-PL is a lower bound of the worst-case plan distinctiveness of PRD and that they are equal under certain conditions. We provide two complete algorithms for minimizing the worst-case distinctiveness of plan libraries without reducing the agent’s ability to complete its goals: One is a brute-force search over all possible plans and one is a constraint-based search that identifies plans that are most difficult to distinguish in the domain. These algorithms are evaluated in three hierarchical plan recognition settings from the literature. We were able to reduce the worst-case distinctiveness of the domains using our approach, in some cases reaching 100% improvement within a predesignated time window. Our iterative algorithm outperforms the brute-force approach by an order of magnitude in terms of runtime.

EAAI Journal 2018 Journal Article

An Artificial Intelligence paradigm for troubleshooting software bugs

• Amir Elmishali
• Roni Stern
• Meir Kalech

Software bugs are prevalent and fixing them is time consuming, and therefore troubleshooting is an important part of software engineering. This paper presents a novel paradigm for incorporating Artificial Intelligence (AI) in the modern software troubleshooting process that can drastically reduce troubleshooting costs. In this paradigm, which we call Learn, Diagnose, and Plan (LDP), we integrate three AI technologies: (1) machine learning: learning from source-code structure, revisions history and past failures, which software components are more likely to contain bugs, (2) automated diagnosis: identifying the software components that need to be modified in order to fix an observed bug, and (3) automated planning: planning additional tests when such are needed to improve diagnostic accuracy. Importantly, these AI technologies are integrated in LDP in a synergistic manner: the diagnosis algorithm is modified to consider the learned fault predictions and the planner is modified to consider the possible diagnoses outputted by the diagnosis algorithm. The overall solution is demonstrated on real faults observed in four open source software projects.

AIJ Journal 2018 Journal Article

Sequential plan recognition: An iterative approach to disambiguating between hypotheses

• Reuth Mirsky
• Roni Stern
• Kobi Gal
• Meir Kalech

Plan recognition algorithms output hypotheses about an agent's plans from its observed actions. Due to imperfect knowledge about the agent's behavior and the environment, it is often the case that there are multiple hypotheses about an agent's plans that are consistent with the observations, though only one of these hypotheses is correct. This paper addresses the problem of how to disambiguate between hypotheses during the recognition process, by querying the acting agent about whether a given plan is part of the correct hypothesis. The main contribution is a sound and complete process for reducing the set of possible hypotheses called Sequential Plan Recognition (SPR). SPR iteratively queries the user and revises the set of possible hypotheses according to the outcome of the query. Several policies are provided for choosing which plans to query the agent. These policies address the problem of how to reduce the number of hypotheses during the recognition process using a minimal number of queries. The proposed policies include policies that use maximum likelihood and information gain measures. The paper provides a complexity analysis of the SPR process and the proposed query policies. It demonstrate its efficiency on two known domains from the literature, describing how performance and runtime are affected by features in the domain. Our results can inform the design of future plan recognition systems that interleave the recognition process with intelligent interventions of their users.

AIJ Journal 2017 Journal Article

How many diagnoses do we need?

• Roni Stern
• Meir Kalech
• Shelly Rogov
• Alexander Feldman

A known limitation of many diagnosis algorithms is that the number of diagnoses they return can be very large. This is both time consuming and not very helpful from the perspective of a human operator: presenting hundreds of diagnoses to a human operator (charged with repairing the system) is meaningless. In various settings, including decision support for a human operator and automated troubleshooting processes, it is sufficient to be able to answer a basic diagnostic question: is a given component faulty? We propose a way to aggregate an arbitrarily large set of diagnoses to return an estimate of the likelihood of a given component to be faulty. The resulting mapping of components to their likelihood of being faulty is called the system's health state. We propose two metrics for evaluating the accuracy of a health state and show that an accurate health state can be found without finding all diagnoses. An empirical study explores the question of how many diagnoses are needed to obtain an accurate enough health state, and an online stopping criteria is proposed.

AAAI Conference 2017 Short Paper

Plan Recognition Design

• Reuth Mirsky
• Roni Stern
• Ya'akov Gal
• Meir Kalech

Goal Recognition Design (GRD) is the problem of designing a domain in a way that will allow easy identification of agents’ goals. This work extends the original GRD problem to the Plan Recognition Design (PRD) problem which is the task of designing a domain using plan libraries in order to facilitate fast identification of an agent’s plan. While GRD can help to explain faster which goal the agent is trying to achieve, PRD can help in faster understanding of how the agent is going to achieve its goal. we define a new measure that quantifies the worst-case distinctiveness of a given planning domain, propose a method to reduce it in a given domain and show the reduction of this new measure in three domains from the literature.

IJCAI Conference 2016 Conference Paper

Anticipatory Troubleshooting

• Netantel Hasidi
• Roni Stern
• Meir Kalech
• Shulamit Reches

Troubleshooting is the process of diagnosing and repairing a system that is behaving abnormally. Diagnostic and repair actions may incur costs, and traditional troubleshooting algorithms aim to minimize the costs incurred until the system is fixed. We propose an anticipatory troubleshooting algorithm, which is able to reason about both current and future failures. To reason about failures over time, we incorporate statistical tools from survival analysis that enable predicting when a failure is likely to occur. Incorporating this prognostic information in a troubleshooting algorithm enables (1) better fault isolation and (2) more intelligent decision making in which repair actions to employ to minimize troubleshooting costs over time.

SoCS Conference 2016 Conference Paper

Batch Repair with Heuristic Search

• Hilla Shinitzky
• Roni Stern
• Meir Kalech

Recent work has raised the challenge of efficient automated troubleshooting in domains where repairing a set of components in a single repair action is cheaper than repairing each of them separately. This corresponds to cases where there is a non-negligible overhead to initiating a repair action and to testing the system after a repair action. The problem can be formalized as a combinatorial search problem, propose a new objective function to optimize, and investigate several search frameworks to solve it. The resulting search space is not monotone, but we are able to devise an admissible heuristic for it that enables solving it optimally in some cases with A*. Empirical evaluation on standard model-based diagnosis benchmark systems compare the A*-based approach with other search algorithms

AAAI Conference 2016 Conference Paper

Implementing Troubleshooting with Batch Repair

• Roni Stern
• Meir Kalech
• Hilla Shinitzky

Recent work has raised the challenge of efficient automated troubleshooting in domains where repairing a set of components in a single repair action is cheaper than repairing each of them separately. This corresponds to cases where there is a non-negligible overhead to initiating a repair action and to testing the system after a repair action. In this work we propose several algorithms for choosing which batch of components to repair, so as to minimize the overall repair costs. Experimentally, we show the benefit of these algorithms over repairing components one at a time.

IJCAI Conference 2016 Conference Paper

Sequential Plan Recognition

• Reuth Mirsky
• Roni Stern
• Ya'akov (Kobi) Gal
• Meir Kalech

Plan recognition algorithms infer agents' plans from their observed actions. Due to imperfect knowledge about the agent's behavior and the environment, it is often the case that there are multiple hypotheses about an agent's plans that are consistent with the observations, though only one of these hypotheses is correct. This paper addresses the problem of how to disambiguate between hypotheses, by querying the acting agent about whether a candidate plan in one of the hypotheses matches its intentions. This process is performed sequentially and used to update the set of possible hypotheses during the recognition process. The paper defines the sequential plan recognition process (SPRP), which seeks to reduce the number of hypotheses using a minimal number of queries. We propose a number of policies for the SPRP which use maximum likelihood and information gain to choose which plan to query. We show this approach works well in practice on two domains from the literature, significantly reducing the number of hypotheses using fewer queries than a baseline approach. Our results can inform the design of future plan recognition systems that interleave the recognition process with intelligent interventions of their users.

AAMAS Conference 2016 Conference Paper

Sequential Plan Recognition (Extended Abstract)

• Reuth Mirsky
• Ya'akov (Kobi) Gal
• Roni Stern
• Meir Kalech

Plan recognition algorithms need to maintain all candidate hypotheses which are consistent with the observations, even though there is only a single hypothesis that is the correct one. Unfortunately, the number of possible hypotheses can be exponentially large in practice. This paper addresses the problem of how to disambiguate between many possible hypotheses that are all consistent with the actions of the observed agent. One way to reduce the number of hypotheses is to consult a domain expert or the acting agent directly about its intentions. This process can be performed sequentially, updating the set of hypotheses during the recognition process. The paper specifically addresses the problem of how to minimize the number of queries made that are required to find the correct hypothesis. It adapts a number of probing techniques for choosing which plan to query, such as maximal information gain and maximum likelihood. These approaches were evaluated on a domain from the literature using a well known plan recognition algorithm. The results showed that the information gain approach was able to find the correct plan using significantly fewer queries than the maximum likelihood approach as well as a baseline approach choosing random plans. Our technique can inform the design of future plan recognition systems that interleave the recognition process with intelligent interventions of their users.

JAIR Journal 2015 Journal Article

Decision Making with Dynamic Uncertain Events

• Meir Kalech
• Shulamit Reches

When to make a decision is a key question in decision making problems characterized by uncertainty. In this paper we deal with decision making in environments where information arrives dynamically. We address the tradeoff between waiting and stopping strategies. On the one hand, waiting to obtain more information reduces uncertainty, but it comes with a cost. Stopping and making a decision based on an expected utility reduces the cost of waiting, but the decision is based on uncertain information. We propose an optimal algorithm and two approximation algorithms. We prove that one approximation is optimistic - waits at least as long as the optimal algorithm, while the other is pessimistic - stops not later than the optimal algorithm. We evaluate our algorithms theoretically and empirically and show that the quality of the decision in both approximations is near-optimal and much faster than the optimal algorithm. Also, we can conclude from the experiments that the cost function is a key factor to chose the most effective algorithm.

AAAI Conference 2015 Conference Paper

How Many Diagnoses Do We Need?

• Roni Stern
• Meir Kalech
• Shelly Rogov
• Alexander Feldman

A known limitation of many diagnosis algorithms is that the number of diagnoses they return can be very large. This raises the question of how to use such a large set of diagnoses. For example, presenting hundreds of diagnoses to a human operator (charged with repairing the system) is meaningless. In various settings, including decision support for a human operator and automated troubleshooting processes, it is sufficient to be able to answer a basic diagnostic question: is a given component faulty? We propose a way to aggregate an arbitrarily large set of diagnoses to return an estimate of the likelihood of a given component to be faulty. The resulting mapping of components to their likelihood of being faulty is called the system’s health state. We propose two metrics for evaluating the accuracy of a health state and show that an accurate health state can be found without finding all diagnoses. An empirical study explores the question of how many diagnoses are needed to obtain an accurate enough health state, and a simple online stopping criterion is proposed.

IJCAI Conference 2015 Conference Paper

Lie on the Fly: Iterative Voting Center with Manipulative Voters

• Lihi Naamani-Dery
• Svetlana Obraztsova
• Zinovi Rabinovich
• Meir Kalech

Manipulation can be performed when intermediate voting results are known; voters might attempt to vote strategically and try and manipulate the results during an iterative voting process. When only partial voting preferences are available, preference elicitation is necessary. In this paper, we combine two approaches of iterative processes: iterative preference elicitation and iterative voting and study the outcome and performance of a setting where manipulative voters submit partial preferences. We provide practical algorithms for manipulation under the Borda voting rule and evaluate those using different voting centers: the Careful voting center that tries to avoid manipulation and the Naive voting center. We show that in practice, manipulation happens in a low percentage of the settings and has a low impact on the final outcome. The Careful voting center reduces manipulation even further.

TIST Journal 2014 Journal Article

A Framework for Effectively Choosing between Alternative Candidate Partners

• Shulamit Reches
• Meir Kalech
• Philip Hendrix

Many multi-agent settings require that agents identify appropriate partners or teammates with whom to work on tasks. When selecting potential partners, agents may benefit from obtaining information about the alternatives, for instance, through gossip (i.e., by consulting others) or reputation systems. When information is uncertain and associated with cost, deciding on the amount of information needed is a hard optimization problem. This article defines a statistical model, the Information-Acquisition Source Utility model (IASU), by which agents, operating in an uncertain world, can determine (1) which information sources they should request for information, and (2) the amount of information to collect about potential partners from each source. To maximize the expected gain from the choice, IASU computes the utility of choosing a partner by estimating the benefit of additional information. The article presents empirical studies through a simulation domain as well as a real-world domain of restaurants. We compare the IASU model to other relevant models and show that the use of the IASU model significantly increases agents' overall utility.

TIST Journal 2014 Journal Article

Choosing a Candidate Using Efficient Allocation of Biased Information

• Shulamit Reches
• Meir Kalech

This article deals with a decision-making problem concerning an agent who wants to choose a partner from multiple candidates for long-term collaboration. To choose the best partner, the agent can rely on prior information he knows about the candidates. However, to improve his decision, he can request additional information from information sources. Nonetheless, acquiring information from external information sources about candidates may be biased due to different personalities of the agent searching for a partner and the information source. In addition, information may be costly. Considering the bias and the cost of the information sources, the optimization problem addressed in this article is threefold: (1) determining the necessary amount of additional information, (2) selecting information sources from which to request the information, and (3) choosing the candidates on whom to request the additional information. We propose a heuristic to solve this optimization problem. The results of experiments on simulated and real-world domains demonstrate the efficiency of our algorithm.

AAAI Conference 2014 Conference Paper

Using Model-Based Diagnosis to Improve Software Testing

• Tom Zamir
• Roni Stern
• Meir Kalech

We propose a combination of AI techniques to improve software testing. When a test fails, a model-based diagnosis (MBD) algorithm is used to propose a set of possible explanations. We call these explanations diagnoses. Then, a planning algorithm is used to suggest further tests to identify the correct diagnosis. A tester preforms these tests and reports their outcome back to the MBD algorithm, which uses this information to prune incorrect diagnoses. This iterative process continues until the correct diagnosis is returned. We call this testing paradigm Test, Diagnose and Plan (TDP). Several test planning algorithms are proposed to minimize the number of TDP iterations, and consequently the number of tests required until the correct diagnosis is found. Experimental results show the benefits of using an MDP-based planning algorithms over greedy test planning in three benchmarks.

IJCAI Conference 2013 Conference Paper

Machine-Learning-Based Circuit Synthesis

• Lior Rokach
• Meir Kalech
• Gregory Provan
• Alexander Feldman

Multi-level logic synthesis is a problem of immense practical significance, and is a key to developing circuits that optimize a number of parameters, such as depth, energy dissipation, reliability, etc. The problem can be defined as the task of taking a collection of components from which one wants to synthesize a circuit that optimizes a particular objective function. This problem is computationally hard, and there are very few automated approaches for its solution. To solve this problem we propose an algorithm, called Circuit-Decomposition Engine (CDE), that is based on learning decision trees, and uses a greedy approach for function learning. We empirically demonstrate that CDE, when given a library of different component types, can learn the function of Disjunctive Normal Form (DNF) Boolean representations and synthesize circuit structure using the input library. We compare the structure of the synthesized circuits with that of well-known circuits using a range of circuit similarity metrics.

AAAI Conference 2012 Conference Paper

Compiling Model-Based Diagnosis to Boolean Satisfaction

• Amit Metodi
• Roni Stern
• Meir Kalech
• Mike Codish

This paper introduces an encoding of Model Based Diagnosis (MBD) to Boolean Satisfaction (SAT) focusing on minimal cardinality diagnosis. The encoding is based on a combination of sophisticated MBD preprocessing algorithms and SAT compilation techniques which together provide concise CNF formula. Experimental evidence indicates that our approach is superior to all published algorithms for minimal cardinality MBD. In particular, we can determine, for the first time, minimal cardinality diagnoses for the entire standard ISCAS-85 benchmark. Our results open the way to improve the state-ofthe-art on a range of similar MBD problems.

AAAI Conference 2012 Conference Paper

Exploring the Duality in Conflict-Directed Model-Based Diagnosis

• Roni Stern
• Meir Kalech
• Alexander Feldman
• Gregory Provan

AAMAS Conference 2011 Conference Paper

Online Anomaly Detection in Unmanned Vehicles

• Eliahu Khalastchi
• Gal A. Kaminka
• Meir Kalech
• Raz Lin

Autonomy requires robustness. The use of unmanned (autonomous) vehicles is appealing for tasks which are dangerous or dull. However, increased reliance on autonomous robots increases reliance on their robustness. Even with validated software, physical faults can cause the controlling software to perceive the environment incorrectly, and thus to make decisions that lead to task failure. We present an online anomaly detection method for robots, that is light-weight, and is able to take into account a large number of monitored sensors and internal measurements, with high precision. We demonstrate a specialization of the familiar Mahalanobis Distance for robot use, and also show how it can be used even with very large dimensions, by online selection of correlated measurements for its use. We empirically evaluate these contributions in different domains: commercial Unmanned Aerial Vehicles (UAVs), a vacuum-cleaning robot, and a high-fidelity flight simulator. We find that the online Mahalanobis distance technique, presented here, is superior to previous methods.

AAAI Conference 2011 Conference Paper

When to Stop? That Is the Question

• Shulamit Reches
• Meir Kalech
• Rami Stern

When to make a decision is a key question in decision making problems characterized by uncertainty. In this paper we deal with decision making in environments where the information arrives dynamically. We address the tradeoff between waiting and stopping strategies. On the one hand, waiting to obtain more information reduces the uncertainty, but it comes with a cost. On the other hand, stopping and making a decision based on an expected utility, decreases the cost of waiting, but the decision is made based on uncertain information. In this paper, we prove that computing the optimal time to make a decision that guarantees the optimal utility is NP-hard. We propose a pessimistic approximation that guarantees an optimal decision when the recommendation is to wait. We empirically evaluate our algorithm and show that the quality of the decision is near-optimal and much faster than the optimal algorithm.

AAMAS Conference 2010 Conference Paper

Ants Meeting Algorithms

• Asaf Shiloni
• Alon Levy
• Ariel Felner
• Meir Kalech

Ant robots have very low computational power and limited memory. Theycommunicate by leaving pheromones in the environment. In order to createa cooperative intelligent behavior, ants may need to get together; however, they may not know the locations of other ants. Hence, we focus on an antvariant of the rendezvous problem, in which two ants are to be brought tothe same location in finite time. We introduce two algorithms that solvethis problem for two ants by simulating a bidirectional search in differentenvironment settings. An algorithm for an environment with no obstaclesand a general algorithm that handles all types of obstacles. We providedetailed discussion on the different attributes, size of pheromone required, and the performance of these algorithms.

AAMAS Conference 2010 Conference Paper

Decision Making with Dynamically Arriving Information

• Meir Kalech
• Avi Pfeffer

Decision making is the ability to decide on the best alternative among a set of candidates based on their value. In many real-world domains the value depends on events that occur dynamically, so that the decision is based on dynamically changing uncertain information. When there is a cost to waiting for more information, the question is when to make the decision. Do you stop and make the best decision you can, given the information you have so far, or do you wait until more information arrives so you can make a better decision? We propose a model that characterizes the influence of dynamic information on the utility of the decision. Based on this model, we present an optimal algorithm that guarantees the best time to stop. Unfortunately, its complexity is exponential in the number of candidates. We present an alternative framework in which the different candidates are solved separately. We formally analyze the alternative framework, and show how it leads to a range of specific heuristic algorithms. We evaluate the optimal and the simplest heuristic algorithms through experiments, and show that the heuristic algorithm is much faster than the optimal algorithm, and the utility of the winner it finds is close to the optimum.

JAAMAS Journal 2010 Journal Article

Diagnosis of coordination failures: a matrix-based approach

• Meir Kalech

Abstract One of the key requirements in many multi-agent teams is that agents coordinate specific aspects of their joint task. Unfortunately, this coordination may fail due to intermittent faults in sensor readings, communication faults, etc. A key challenge in the model-based diagnosis (MBD) of coordination failures is to represent a model of the coordination among the agents in a way that allows efficient detection and diagnosis, based on observation of the agents involved. Previously developed mechanisms are useful only for small groups of agents, since they represent the coordination with binary constraints. This paper presents a MBD approach to coordination failures in which non-binary constraints are allowed. This model has two inherent advantages: (1) the model enables to address real problems, (2) the model enables to address large groups by gathering multiple coordinations in one constraint. To solve the diagnosis problem, we propose a matrix-based approach to represent the basic building blocks of the MBD formalization. Theoretical and empirical evaluations show that this representation is efficient for large-scale teams.

JAAMAS Journal 2010 Journal Article

Practical voting rules with partial information

• Meir Kalech
• Sarit Kraus
• Claudia V. Goldman

Abstract Voting is an essential mechanism that allows multiple agents to reach a joint decision. The joint decision, representing a function over the preferences of all agents, is the winner among all possible (candidate) decisions. To compute the winning candidate, previous work has typically assumed that voters send their complete set of preferences for computation, and in fact this has been shown to be required in the worst case. However, in practice, it may be infeasible for all agents to send a complete set of preferences due to communication limitations and willingness to keep as much information private as possible. The goal of this paper is to empirically evaluate algorithms to reduce communication on various sets of experiments. Accordingly, we propose an iterative algorithm that allows the agents to send only part of their preferences, incrementally. Experiments with simulated and real-world data show that this algorithm results in an average of 35% savings in communications, while guaranteeing that the actual winning candidate is revealed. A second algorithm applies a greedy heuristic to save up to 90% of communications. While this heuristic algorithm cannot guarantee that a true winning candidate is found, we show that in practice, close approximations are obtained.

AAMAS Conference 2010 Conference Paper

Searching for a k-Clique in Unknown Graphs

• Roni Stern
• Meir Kalech
• Ariel Felner

Agents that solve problems in unknown graphs are usuallyrequired to iteratively explore parts of the graph. In thispaper we research the problem of finding a $k$-clique in anunknown graph while minimizing the number of required exploration actions. Two novel heuristics ($KnownDegree$ and$Clique^*$) are proposed to reduce the required explorationcost by carefully choosing which part of the environmentto explore. We further investigate the problem by addingprobabilistic knowledge of the graph and propose an MDPand a Monte Carlo based heuristic ($RClique^*$ ) that usesknowledge of edges probabilities to reduce the required exploration cost. The efficiency of the proposed approaches isdemonstrated on simulated random and scale free graphs.

SoCS Conference 2010 Conference Paper

Searching for a k-Clique in Unknown Graphs

• Roni Stern
• Meir Kalech
• Ariel Felner

Agents that solve problems in unknown graphs are usually required to iteratively explore parts of the graph. In this paper we research the problem of finding a k-clique in an unknown graph while minimizing the number of required exploration actions. Two novel heuristics Known Degree and Clique* are proposed to reduce the required exploration cost by carefully choosing which part of the environment to explore. We further investigate the problem by adding probabilistic knowledge of the graph and propose an Markov Decision Process(MDP) and a Monte Carlo based heuristic (RClique*) that uses knowledge of edge probabilities to reduce the required exploration cost. We demonstrate the efficiency of the proposed approaches on simulated random and scale free graphs as well as on real online web crawls.

KER Journal 2009 Journal Article

Diagnosing Coordination Faults in Multi-Agent Systems

• Meir Kalech

AAMAS Conference 2007 Conference Paper

Matrix-Based Representation for Coordination Fault Detection: A Formal Approach

• Meir Kalech
• Michael Lindner
• Gal A. Kaminka

Teamwork requires that team members coordinate their actions. The representation of the coordination is a key requirement since it influences the complexity and flexibility of reasoning team–members. One aspect of this requirement is detecting coordination faults as a result of intermittent failures of sensors, communication failures, etc. Detection of such failures, based on observations of the behavior of agents, is of prime importance. Though different solutions have been presented thus far, none has presented a comprehensive and formal resolution to this problem. This paper presents a formal approach to representing multi-agent coordination, and multi-agent observations, using matrix structures. This representation facilitates easy representation of coordination requirements, modularity, flexibility and reuse of existing systems. Based on this representation we present a novel solution for fault-detection that is both generic and efficient for large-scale teams.

AIJ Journal 2007 Journal Article

On the design of coordination diagnosis algorithms for teams of situated agents

• Meir Kalech
• Gal A. Kaminka

Teamwork demands agreement among team-members in order to collaborate and coordinate effectively. When a disagreement between teammates occurs (due to failures), team-members should ideally diagnose its causes, to resolve the disagreement. Such diagnosis of social failures can be expensive in communication and computation, challenges which previous work has not addressed. We present a novel design space of diagnosis algorithms, distinguishing several phases in the diagnosis process, and providing alternative algorithms for each phase. We then combine these algorithms in different ways to empirically explore specific design choices in a complex domain, on thousands of failure cases. The results show that different phases of diagnosis affect communication and computation overhead. In particular, centralizing the diagnosis disambiguation process is a key factor in reducing communications, while runtime is affected mainly by the amount of reasoning about other agents. These results contrast with previous work in disagreement detection (without diagnosis), in which distributed algorithms reduce communications.

AAAI Conference 2006 Conference Paper

Diagnosis of Multi-Robot Coordination Failures Using Distributed CSP Algorithms

• Meir Kalech

With increasing deployment of systems involving multiple coordinating agents, there is a growing need for diagnosing coordination failures in such systems. Previous work presented centralized methods for coordination failure diagnosis; however, these are not always applicable, due to the significant computational and communication requirements, and the brittleness of a single point of failure. In this paper we propose a distributed approach to model-based coordination failure diagnosis. We model the coordination between the agents as a constraint graph, and adapt several algorithms from the distributed CSP area, to use as the basis for the diagnosis algorithms. We evaluate the algorithms in extensive experiments with simulated and real Sony Aibo robots and show that in general a trade-off exists between the computational requirements of the algorithms, and their diagnosis results. Surprisingly, in contrast to results in distributed CSPs, the asynchronous backtracking algorithm outperforms stochastic local search in terms of both quality and runtime.

AAAI Conference 2005 Conference Paper

Towards Model-Based Diagnosis of Coordination Failures

• Meir Kalech

With increasing deployment of multi-agent and distributed systems, there is an increasing need for failure diagnosis systems. While successfully tackling key challenges in multiagent settings, model-based diagnosis has left open the diagnosis of coordination failures, where failures often lie in the boundaries between agents, and thus the inputs to the model—with which the diagnoser simulates the system to detect discrepancies—are not known. However, it is possible to diagnose such failures using a model of the coordination between agents. This paper formalizes model-based coordination diagnosis, using two coordination primitives (concurrence and mutual exclusion). We define the consistencybased and abductive diagnosis problems within this formalization, and show that both are NP-Hard by mapping them to other known problems.

IJCAI Conference 2003 Conference Paper

On the Design of Social Diagnosis Algorithms for Multi-Agent Teams

• Meir Kalech
• Gal A. Kaminka

Teamwork demands agreement among teammembers to collaborate and coordinate effectively. When a disagreement between teammates occurs (due to failures), team-members should ideally diagnose its causes, to resolve the disagreement. Such diagnosis of social failures can be expensive in communication and computation overhead, which previous work did not address. We present a novel design space of diagnosis algorithms, distinguishing several phases in the diagnosis process, and providing alternative algorithms for each phase. We then combine these algorithms in different ways to empirically explore specific design choices in a complex domain, on thousands of failure cases. The results show that centralizing the diagnosis disambiguation process is a key factor in reducing communications, while run-time is affected mainly by the amount of reasoning about other agents. These results contrast sharply with previous work in disagreement detection, in which distributed algorithms reduce communications.