Roni Stern

AAAI Conference 2026 Conference Paper

Multi-Agent Path Finding with Unassigned Agents (MAPFUA)

• Ariel Felner
• Roni Stern

In the Multi-Agent Path Finding (MAPF) problem, the aim is to find collision free paths for multiple agents. MAPF has many practical applications and has spawned massive research interest in the past two decades. Most MAPF research assumed that every agent is assigned a target it must reach. This assumption often does not hold in several key applications such as automated warehouses and parking lots, where some agents are assigned targets to reach, and others, denoted as unassigned agents, can either stay idle or move to clear the way for the assigned agents. In this paper we introduce this important problem, explain its uniqueness and encourage the entire community to work on it.

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.

AAAI Conference 2025 Conference Paper

A Domain-Independent Agent Architecture for Adaptive Operation in Evolving Open Worlds

• Shiwali Mohan
• Wiktor Piotrowski
• Roni Stern
• Sachin Grover
• Sookyung Kim
• Jacob Le
• Johan de Kleer
• Yoni Sher

Model-based reasoning agents are ill-equipped to act in novel situations in which their model of the environment no longer sufficiently represents the world. We propose HYDRA, a framework for designing model-based agents operating in mixed discrete-continuous worlds that can autonomously detect when the environment has evolved from its canonical setup, understand how it has evolved, and adapt the agents' models to perform effectively. HYDRA is based upon PDDL+, a rich modeling language for planning in mixed, discrete-continuous environments. It augments the planning module with visual reasoning, task selection, and action execution modules for closed-loop interaction with complex environments. HYDRA implements a novel meta-reasoning process that enables the agent to monitor its own behavior from a variety of aspects. The process employs a diverse set of computational methods to maintain expectations about the agent's own behavior in an environment. Divergences from those expectations are useful in detecting when the environment has evolved and identifying opportunities to adapt the underlying models. HYDRA builds upon ideas from diagnosis and repair and uses a heuristics-guided search over model changes such that they become competent in novel conditions. The HYDRA framework has been used to implement novelty-aware agents for three diverse domains - CartPole++ (a higher dimension variant of a classic control problem), Science Birds (an IJCAI competition problem), and PogoStick (a specific problem domain in Minecraft). We report empirical observations from these domains to demonstrate the efficacy of various components in the novelty meta-reasoning process.

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.

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.

JAIR Journal 2025 Journal Article

Prioritised Planning: Completeness, Optimality, and Complexity

• Jonathan Morag
• Yue Zhang
• Daniel Koyfman
• Zhe Chen
• Ariel Felner
• Daniel Harabor
• Roni Stern

Prioritised Planning (PP) is a popular approach for multi-agent and multi-robot navigation. In PP, collision-free paths are computed for one agent at a time, following a total order over the agents, called a priority ordering. Many MAPF algorithms follow this approach or use it in some way, including several state-of-the-art MAPF algorithms, although it is known that PP is neither complete nor optimal. In this work, we characterise the space of problems a PP algorithm can solve, and define the search problem of identifying whether a given MAPF problem is in that space. We call this search problem Prioritised MAPF (P-MAPF) and investigate its computational complexity, showing that it is generally NP-hard. Then, we develop a novel efficient search algorithm called Path and Priority Search (PaPS), which solves P-MAPF, providing guarantees of completeness and optimality. We next observe that PP algorithms operate with two primary degrees of freedom – the choice of priority ordering, and the choice of individual paths for agents. Accordingly, we further divide P-MAPF into two planning problems corresponding to the two degrees of freedom. We call them Priority-Function Constrained MAPF (PFC-MAPF), where the path choice is fixed while the priority ordering is not, and Priority Constrained MAPF (PC-MAPF), where the priority ordering is fixed while the path choice is not. We analyse these problems as well, and show how PaPS can be easily adapted to create algorithms that solve these problems optimally. We experiment with our algorithms in a range of settings, including comparisons with existing PP baselines. Our results show how the different degrees of freedom of PP-based algorithms affect their behaviour, and provide the first-known results for solution-quality optimality for PP-based algorithms on a popular MAPF benchmark set. The latter can be used as a lower bound for any PP algorithm.

AIJ Journal 2024 Journal Article

A domain-independent agent architecture for adaptive operation in evolving open worlds

• Shiwali Mohan
• Wiktor Piotrowski
• Roni Stern
• Sachin Grover
• Sookyung Kim
• Jacob Le
• Yoni Sher
• Johan de Kleer

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.

SoCS Conference 2024 Conference Paper

Crafting a Pogo Stick in Minecraft with Heuristic Search (Extended Abstract)

• Yarin Benyamin
• Argaman Mordoch
• Shahaf S. Shperberg
• Wiktor Piotrowski
• Roni Stern

Minecraft is a widely popular video game renowned for its intricate environment. The game

AAAI Conference 2024 Conference Paper

Learning Safe Action Models with Partial Observability

• Hai S. Le
• Brendan Juba
• Roni Stern

A common approach for solving planning problems is to model them in a formal language such as the Planning Domain Definition Language (PDDL), and then use an appropriate PDDL planner. Several algorithms for learning PDDL models from observations have been proposed but plans created with these learned models may not be sound. We propose two algorithms for learning PDDL models that are guaranteed to be safe to use even when given observations that include partially observable states. We analyze these algorithms theoretically, characterizing the sample complexity each algorithm requires to guarantee probabilistic completeness. We also show experimentally that our algorithms are often better than FAMA, a state-of-the-art PDDL learning algorithm.

ECAI Conference 2024 Conference Paper

Novelty Accommodating Multi-Agent Planning in High Fidelity Simulated Open World

• James Chao
• Wiktor Piotrowski
• Roni Stern
• Héctor J. Ortiz-Peña
• Mitch Manzanares
• Shiwali Mohan
• Douglas S. Lange

Autonomous agents operating within real-world environments often rely on automated planners to ascertain optimal actions towards desired goals or the optimization of a specified objective function. Integral to these agents are common architectural components such as schedulers, tasked with determining the timing for executing planned actions, and execution engines, responsible for carrying out these scheduled actions while monitoring their outcomes. We address the significant challenge that arises when unexpected phenomena, termed novelties, emerge within the environment, altering its fundamental characteristics, composition, and dynamics. This challenge is inherent in all deployed real-world applications and may manifest suddenly and without prior notice or explanation. The introduction of novelties into the environment can lead to inaccuracies within the planner’s internal model, rendering previously generated plans obsolete. Recent research introduced agent design aimed at detecting and adapting to such novelties. However, these designs lack consideration for action scheduling in continuous time-space, coordination of concurrent actions by multiple agents, or memory-based novelty accommodation. Additionally, the application has been primarily demonstrated in lower fidelity environments. In our study, we propose a general purpose AI agent framework designed to detect, characterize, and adapt to novelties in highly noisy, complex, and stochastic environments that support concurrent actions and external scheduling. We showcase the efficacy of our agent through experimentation within a high-fidelity simulator for realistic military scenarios.

IROS Conference 2024 Conference Paper

Online Planning for Multi Agent Path Finding in Inaccurate Maps

• Nir Malka
• Guy Shani
• Roni Stern

In multi-agent path finding (MAPF), agents navigate to their target positions without conflict within an environment, typically represented as a graph. Traditionally, the input graph is assumed to be accurate. We investigate MAPF scenarios where the input graph may be inaccurate, containing non-existent edges or missing edges present in the environment. Agents can verify the existence or non-existence of an edge only by moving close to it. To navigate such maps, we propose an online approach where planning and execution are interleaved. As agents gather new information about the environment over time, they replan accordingly. To minimize replanning efforts, we developed methods to identify and replan only for agents affected by observed changes. To scale to larger problems, we defer conflicts resolution expected only in the distant future and adapt single-agent path-finding algorithms to account for map inaccuracies. Experimental results show impressive scalability, solving problems involving over 1000 agents in under 3 minutes.

IROS Conference 2024 Conference Paper

Optimal and Bounded Suboptimal Any-Angle Multi-agent Pathfinding

• Konstantin S. Yakovlev
• Anton Andreychuk
• Roni Stern

Multi-agent pathfinding (MAPF) is the problem of finding a set of conflict-free paths for a set of agents. Typically, the agents' moves are limited to a pre-defined graph of possible locations and allowed transitions between them, e. g. a 4-neighborhood grid. We explore how to solve MAPF problems when each agent can move between any pair of possible locations as long as traversing the line segment connecting them does not lead to a collision with the obstacles. This is known as any-angle pathfinding. We present the first optimal any-angle multi-agent pathfinding algorithm. Our planner is based on the Continuous Conflict-based Search (CCBS) algorithm and an optimal any-angle variant of the Safe Interval Path Planning (TO-AA-SIPP). The straightforward combination of those, however, scales poorly since any-angle path finding induces search trees with a very large branching factor. To mitigate this, we adapt two techniques from classical MAPF to the any-angle setting, namely Disjoint Splitting and Multi-Constraints. Experimental results on different combinations of these techniques show they enable solving over 30% more problems than the vanilla combination of CCBS and TO-AA-SIPP. In addition, we present a bounded-suboptimal variant of our algorithm, that enables trading runtime for solution cost in a controlled manner.

SoCS Conference 2024 Conference Paper

Optimal and Bounded Suboptimal Any-Angle Multi-agent Pathfinding (Extended Abstract)

• Konstantin S. Yakovlev
• Anton Andreychuk
• Roni Stern

Multi-agent pathfinding (MAPF) is the problem of finding a set of conflict-free paths for a set of agents. We explore how to solve MAPF problems when each agent can move between any pair of possible locations as long as traversing the line segment connecting them does not lead to a collision with the obstacles. This is known as any-angle pathfinding. We present the first optimal any-angle multi-agent pathfinding algorithm. Our planner is based on the Continuous Conflict-based Search (CCBS) algorithm and an optimal any-angle variant of the Safe Interval Path Planning (TO-AA-SIPP). The straightforward combination of those, however, scales poorly. To mitigate this, we adapt two techniques from classical MAPF to the any-angle setting, namely Disjoint Splitting and Multi-Constraints. Experimental results on different combinations of these techniques show they enable solving over 30% more problems than the vanilla combination of CCBS and TO-AA-SIPP. In addition, we present a bounded-suboptimal variant of our algorithm, that enables trading runtime for solution cost in a controlled manner.

SoCS Conference 2024 Conference Paper

Prioritised Planning with Guarantees

• Jonathan Morag
• Yue Zhang 0048
• Daniel Koyfman
• Zhe Chen 0016
• Ariel Felner
• Daniel Harabor
• Roni Stern

Prioritised Planning (PP) is a family of incomplete and sub-optimal algorithms for multi-agent and multi-robot navigation. In PP, agents compute collision-free paths in a fixed order, one at a time. Although fast and usually effective, PP can still fail, leaving users without explanation or recourse. In this work, we give a theoretical and empirical basis for better understanding the underlying problem solved by PP, which we call Priority Constrained MAPF (PC-MAPF). We first investigate the complexity of PC-MAPF and show that the decision problem is NP-hard. We then develop Priority Constrained Search (PCS), a new algorithm that is both complete and optimal with respect to a fixed priority ordering. We experiment with PCS in a range of settings, including comparisons with existing PP baselines, and we give first-known results for optimal PC-MAPF on a popular benchmark set.

ICAPS Conference 2024 Conference Paper

Safe Learning of PDDL Domains with Conditional Effects

• Argaman Mordoch
• Enrico Scala
• Roni Stern
• Brendan Juba

Powerful domain-independent planners have been developed to solve various types of planning problems. These planners often require a model of the acting agent

PRL Workshop 2024 Workshop Paper

Solving Minecraft Tasks via Model Learning

• Yarin Benyamin
• Argaman Mordoch
• Shahaf S. Shperberg
• Roni Stern

Minecraft is a sandbox game that offers a rich and complex environment for AI research. Its design allows for defining diverse tasks and challenges for AI agents, such as gathering resources and crafting items. Previous works have applied both Reinforcement Learning (RL) and Automated Planning methods to accomplish different tasks in Minecraft. RL methods usually require a large number of interactions with the environment, while planning methods require a model of the domain to be available. Creating planning domain models for Minecraft tasks is arduous. Algorithms for learning a planning domain model from observations exist, yet they have mostly been used on planning benchmarks. In this work, we explore the use of such algorithms for solving Minecraft tasks. We propose an agent that learns domain models from observations—either generated by an expert or collected online—and uses them with an off-theshelf domain-independent planner. As a case study, we explore how such an agent can be used for the task of crafting a wooden pogo stick. Experimental results demonstrate the benefit of domain model learning and planning over standard RL-based methods.

SoCS Conference 2023 Conference Paper

Adapting to Planning Failures in Lifelong Multi-Agent Path Finding

• Jonathan Morag
• Roni Stern
• Ariel Felner

Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths for multiple agents operating in the same environment. In Lifelong MAPF (LMAPF), these agents continuously receive new destinations, and the task is to constantly update their paths while optimizing for a high throughput over time. Therefore, many MAPF sub-problems must be solved over time in order to solve a single LMAPF problem. LMAPF problems manifest in real-world applications, such as automated warehouses, where strict responsiveness requirements limit the amount of time allocated to planning. MAPF algorithms occasionally fail to produce a plan within the allotted time. We propose a system design for LMAPF that is robust to such planning failures. Then, we explore different approaches to avoid planning failures, reduce their severity, and handle them when they occur. In particular, we describe and analyze different Fail Policies that are applied when planning failures occur and ensure collisions and unnecessary degradation of throughput are avoided. To our knowledge, while such Fail Policies are used in practice in the industry, they have yet to be researched academically.

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.

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.

SoCS Conference 2023 Conference Paper

Greedy Priority-Based Search for Suboptimal Multi-Agent Path Finding

• Shao-Hung Chan
• Roni Stern
• Ariel Felner
• Sven Koenig

Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths, one for each agent, in a shared environment, while minimizing their sum of travel times. Since solving MAPF optimally is NP-hard, researchers have explored algorithms that solve MAPF suboptimally but efficiently. Priority-Based Search (PBS) is the leading algorithm for this purpose. It finds paths for individual agents, one at a time, and resolves collisions by assigning priorities to the colliding agents and replanning their paths during its search. However, PBS becomes ineffective for MAPF instances with high densities of agents and obstacles. Therefore, we introduce Greedy PBS (GPBS), which uses greedy strategies to speed up PBS by minimizing the number of collisions between agents. We then propose techniques that speed up GPBS further, namely partial expansions, target reasoning, induced constraints, and soft restarts. We show that GPBS with all these improvements has a higher success rate than the state-of-the-art suboptimal algorithm for a 1-minute runtime limit, especially for MAPF instances with small maps and dense obstacles.

ICAPS Conference 2023 Conference Paper

Heuristic Search for Physics-Based Problems: Angry Birds in PDDL+

• Wiktor Piotrowski
• Yoni Sher
• Sachin Grover
• Roni Stern
• Shiwali Mohan

This paper studies how a domain-independent planner and combinatorial search can be employed to play AngryBirds, a well established AI challenge problem. To model the game, we use PDDL+, a planning language for mixed discrete/continuous domains that supports durative processes and exogenous events. The paper describes the PDDL+ model and identifies key design decisions that reduce the problem complexity. In addition, we propose several domain-specific enhancements including heuristics and a search technique similar to preferred operators. Together, they alleviate the complexity of combinatorial search. We evaluate our approach by comparing its performance with dedicated domain-specific solvers on a range of Angry Birds levels. The results show that our performance is on par with these domain-specific approaches in most levels, even without using our domain-specific search enhancements.

SoCS Conference 2023 Conference Paper

Heuristic Search for Physics-Based Problems: Angry Birds in PDDL+ [Extended Abstract]

• Wiktor Piotrowski
• Yoni Sher
• Sachin Grover
• Roni Stern
• Shiwali Mohan

Angry Birds is a very popular game that requires reasoning about sequential actions in a continuous world with discrete exogenous events. Different versions of the game are hard computationally, and the reigning world champion is still a human despite a long-running yearly competition in IJCAI conferences. In this work, we present the Hydra, the first successful game-playing agent for Angry Birds that uses a domain-independent planner and combinatorial search techniques. Hydra models the game using PDDL+, a rich planning language designed for mixed discrete/continuous domains. To reason about continuous aspects of the domain, Hydra employs time discretization techniques that raise a combinatorial search challenge. To meet this challenge, we propose domain-specific heuristics and a novel "preferred states" mechanism similar to the preferred operators mechanism from classical planning. We compared Hydra with state-of-the-art Angry Birds agents. The results show Hydra can solve a greater diversity of Angry Birds levels compared to other agents and highlight its current limitations.

AAAI Conference 2023 Conference Paper

Learning Safe Numeric Action Models

• Argaman Mordoch
• Brendan Juba
• Roni Stern

Powerful domain-independent planners have been developed to solve various types of planning problems. These planners often require a model of the acting agent's actions, given in some planning domain description language. Yet obtaining such an action model is a notoriously hard task. This task is even more challenging in mission-critical domains, where a trial-and-error approach to learning how to act is not an option. In such domains, the action model used to generate plans must be safe, in the sense that plans generated with it must be applicable and achieve their goals. Learning safe action models for planning has been recently explored for domains in which states are sufficiently described with Boolean variables. In this work, we go beyond this limitation and propose the NSAM algorithm. NSAM runs in time that is polynomial in the number of observations and, under certain conditions, is guaranteed to return safe action models. We analyze its worst-case sample complexity, which may be intractable for some domains. Empirically, however, NSAM can quickly learn a safe action model that can solve most problems in the domain.

AAMAS Conference 2023 Conference Paper

Learning to Operate in Open Worlds by Adapting Planning Models

• Wiktor Piotrowski
• Roni Stern
• Yoni Sher
• Jacob Le
• Matthew Klenk
• Johan DeKleer
• Shiwali Mohan

Planning agents are ill-equipped to act in novel situations in which their domain model no longer accurately represents the world. We introduce an approach for such agents operating in open worlds that detects the presence of novelties and effectively adapts their domain models and consequent action selection. It uses observations of action execution and measures their divergence from what is expected, according to the environment model, to infer existence of a novelty. Then, it revises the model through a heuristics-guided search over model changes. We report empirical evaluations on the CartPole problem, a standard Reinforcement Learning (RL) benchmark. The results show that our approach can deal with a class of novelties very quickly and in an interpretable fashion.

PRL Workshop 2023 Workshop Paper

Model Learning to Solve Minecraft Tasks

• Yarin Benyamin
• Argaman Mordoch
• Shahaf S. Shperberg
• Roni Stern

Minecraft is a sandbox game that offers a rich and complex environment for AI research. Its design allows defining diverse tasks and challenges for AI agents, such as gathering resources and crafting items. Previous works have applied both Reinforcement Learning (RL) and Automated Planning methods to accomplish different tasks in Minecraft. RL methods usually require a large number of interactions with the environment, while planning methods requires a model of the domain to be available. Creating planning domain models for Minecraft tasks is arduous. Algorithms for learning a domain model from observations exist, yet have mostly been used on planning benchmarks. In this work, we explore the use of such algorithms for solving Minecraft tasks. We focus on the task of crafting a wooden pogo stick and explore different ways to represent states in this domain. Then, propose an agent that learns domain models from observations --- either generated by an expert or collected online --- and uses them with an off-the-shelf domain-independent planner.

ICAPS Conference 2023 Conference Paper

Multi Agent Path Finding under Obstacle Uncertainty

• Bar Shofer
• Guy Shani
• Roni Stern

In multi-agent path finding (MAPF), several agents must move from their current positions to their target positions without colliding. Prior work on MAPF commonly assumed perfect knowledge of the environment. We consider a MAPF setting where this is not the case, and the planner does not know a-priori whether some positions are blocked or not. To sense whether such a position is traversable, an agent must move close to it and adapt its behavior accordingly. In this work we focus on solving this type of MAPF problem, for cases where planning is centralized but cannot be done during execution. In this setting, a solution can be formulated as a plan tree for each agent, branching on the observations. We propose algorithms for finding such plans trees for two modes of executions: centralized, where the agents share information concerning observed obstacles during execution, a decentralized, where such communication is not allowed. The proposed algorithms are complete and can be configured to optimize solution cost, measured for either the best case or the worst case. We implemented these algorithms and provide experimental results demonstrating how our approach scales with respect to the number of agents and the number of positions we are uncertain about. The results show that our algorithms can solve non-trivial problems, but also highlight that this type of MAPF problems is significantly harder than classical MAPF.

SoCS Conference 2022 Conference Paper

An Online Approach for Multi-Agent Path Finding Under Movement Uncertainty (Extended Abstract)

• Elad Levy
• Guy Shani
• Roni Stern

In this work, we address the problem of finding paths for multiple agents while avoiding collisions between them, where agents

AAAI Conference 2022 Conference Paper

Learning Probably Approximately Complete and Safe Action Models for Stochastic Worlds

• Brendan Juba
• Roni Stern

We consider the problem of learning action models for planning in unknown stochastic environments that can be defined using the Probabilistic Planning Domain Description Language (PPDDL). As input, we are given a set of previously executed trajectories, and the main challenge is to learn an action model that has a similar goal achievement probability to the policies used to create these trajectories. To this end, we introduce a variant of PPDDL in which there is uncertainty about the transition probabilities, specified by an interval for each factor that contains the respective true transition probabilities. Then, we present SAM+, an algorithm that learns such an imprecise-PPDDL environment model. SAM+ has a polynomial time and sample complexity, and guarantees that with high probability, the true environment is indeed captured by the defined intervals. We prove that the action model SAM+ outputs has a goal achievement probability that is almost as good or better than that of the policies used to produced the training trajectories. Then, we show how to produce a PPDDL model based on this imprecise-PPDDL model that has similar properties.

JAIR Journal 2022 Journal Article

Migrating Techniques from Search-based Multi-Agent Path Finding Solvers to SAT-based Approach

• Pavel Surynek
• Roni Stern
• Eli Boyarski
• Ariel Felner

In the multi-agent path finding problem (MAPF) we are given a set of agents each with respective start and goal positions. The task is to find paths for all agents while avoiding collisions, aiming to minimize a given objective function. Many MAPF solvers were introduced in the past decade for optimizing two specific objective functions: sum-of-costs and makespan. Two prominent categories of solvers can be distinguished: search-based solvers and compilation-based solvers. Search-based solvers were developed and tested for the sum-of-costs objective, while the most prominent compilation-based solvers that are built around Boolean satisfiability (SAT) were designed for the makespan objective. Very little is known on the performance and relevance of solvers from the compilation-based approach on the sum-of-costs objective. In this paper, we start to close the gap between these cost functions in the compilation-based approach. Our main contribution is a new SAT-based MAPF solver called MDD-SAT, that is directly aimed to optimally solve the MAPF problem under the sum-of-costs objective function. Using both a lower bound on the sum-of-costs and an upper bound on the makespan, MDD-SAT is able to generate a reasonable number of Boolean variables in our SAT encoding. We then further improve the encoding by borrowing ideas from ICTS, a search-based solver. In addition, we show that concepts applicable in search-based solvers like ICTS and ICBS are applicable in the SAT-based approach as well. Specifically, we integrate independence detection, a generic technique for decomposing an MAPF instance into independent subproblems, into our SAT-based approach, and we design a relaxation of our optimal SAT-based solver that results in a bounded suboptimal SAT-based solver. Experimental evaluation on several domains shows that there are many scenarios where our SAT-based methods outperform state-of-the-art sum-of-costs search-based solvers, such as variants of the ICTS and ICBS algorithms.

AIJ Journal 2022 Journal Article

Multi-agent pathfinding with continuous time

• Anton Andreychuk
• Konstantin Yakovlev
• Pavel Surynek
• Dor Atzmon
• Roni Stern

SoCS Conference 2022 Conference Paper

Online Multi-Agent Path Finding: New Results

• Jonathan Morag
• Ariel Felner
• Roni Stern
• Dor Atzmon
• Eli Boyarski

Online MAPF extends the classical Multi-Agent Path Finding problem (MAPF) by considering a more realistic problem in which new agents may appear over time. As online solvers are not aware of which agents will join in the future, the notion of snapshot-optimal was defined, where only current knowledge is considered. In this paper, we perform an extensive comparison between oracle-optimal solutions (where the solver is preinformed of future agents), snapshot-optimal solutions, and suboptimal solutions obtained by prioritised planning.

JAAMAS Journal 2022 Journal Article

Privacy preserving planning in multi-agent stochastic environments

• Tommy Hefner
• Guy Shani
• Roni Stern

Abstract Collaborative privacy preserving planning ( cppp ) gained much attention in the past decade. cppp aims to create solutions for multi agent planning problems where cooperation is required to achieve an efficient solution, without exposing information that the agent considers private in the process. To date, cppp has focused on domains with deterministic action effects. However, in real-world problems action effects are often non-deterministic, and actions can have multiple possible effects with varying probabilities. In this paper, we introduce Stochastic cppp ( scppp ), which is an extension of cppp to domains with stochastic action effects. We show how scppp can be modeled as a Markov decision process ( mdp ) and how the value-iteration algorithm can be adapted to solve it. This adaptation requires extending value-iteration to support multiple agents and privacy. Then, we present two adaptions of the real-time dynamic programming ( rtdp ) algorithm, a popular algorithm for solving mdp s, designed to solve scppp problems. The first rtdp adaptation, called distributed rtdp ( drtdp ), yields identical behavior to applying rtdp in a centralized manner on the joint problem. To preserve privacy, drtdp uses a message passing mechanism adopted from the mafs algorithm. The second rtdp adaptation is an approximation of drtdp called public synchronization rtdp ( ps - rtdp ). ps - rtdp differs from drtdp mainly in its message passing mechanism, where ps - rtdp sends significantly fewer messages than drtdp. We experimented on domains adapted from the deterministic cppp literature by adding different stochastic effects to different actions. The results show that ps - rtdp can reduce the amount of messages compared to drtdp by orders of magnitude thus improving run-time, while producing policies with similar expected costs.

JAAMAS Journal 2022 Journal Article

Reducing disclosed dependencies in privacy preserving planning

• Rotem Lev Lehman
• Guy Shani
• Roni Stern

Abstract In collaborative privacy preserving planning ( cppp ), a group of agents jointly creates a plan to achieve a set of goals while preserving each others’ privacy. In state of the art cppp algorithms, the agents avoid explicitly sharing the value of private state variables. However, they may implicitly reveal dependencies between actions, that is, which action facilitates achieving the preconditions of another action. Previous work in cppp did not limit the disclosure of such dependencies. In this paper, we explicitly limit the amount of disclosed dependencies, allowing agents to publish only some of the dependencies between their actions. We investigate different strategies for deciding which dependencies to publish, and how they affect the ability to find solutions. We evaluate the ability of two solvers — distribute forward search and centralized planning based on a single-agent projection — to produce plans under this constraint. Experiments over standard cppp domains show that the proposed dependency-sharing strategies enable generating plans while sharing only a small fraction of all dependencies.

SoCS Conference 2021 Conference Paper

Experimental Evaluation of Classical Multi Agent Path Finding Algorithms

• Omri Kaduri
• Eli Boyarski
• Roni Stern

Modern optimal multi-agent path finding (MAPF) algorithms can scale to solve problems with hundreds of agents. To facilitate comparison between these algorithms, a benchmark of MAPF problems was recently proposed. We report a comprehensive evaluation of a diverse set of state-of-the-art optimal MAPF algorithms over the entire benchmark. The results show that in terms of coverage, the recently proposed LazyCBS algorithm outperforms all others significantly, but it is usually not the fastest algorithm. This suggests algorithm selection methods can be beneficial. Then, we characterize different setups for algorithm selection in MAPF, and evaluate simple baselines for each setup. Finally, we propose an extension of the existing MAPF benchmark in the form of different ways to distribute the agents’ source and target locations.

SoCS Conference 2021 Conference Paper

Improving Continuous-time Conflict Based Search

• Anton Andreychuk
• Konstantin S. Yakovlev
• Eli Boyarski
• Roni Stern

Multi-Agent Pathfinding (MAPF) is the problem of finding paths for n agents in a graph such that each agent reaches its goal vertex and the agents do not collide with each other while moving along these paths. While different problem statements of MAPF exist, we are focused on MAPFr (Walker, Sturtevant, and Felner 2018), in which actions’ durations can be non-uniform, agents have geometric shapes, and time is continuous. Continuous-time conflict-based search (CCBS) (Andreychuk et al. 2019) is a recently proposed algorithm for finding optimal solutions to MAPFr problems. In this work, we propose several improvements to CCBS based on known improvements to the Conflictbased search (CBS) algorithm (Sharon et al. 2015) for classical MAPF, namely Disjoint Splitting (DS), Prioritizing Conflicts (PC), and high-level heuristics. We evaluate the impact of these improvements experimentally on both roadmaps and grids. Our results show that CCBS with these improvements is able to solve significantly more problems.

AAAI Conference 2021 Conference Paper

Improving Continuous-time Conflict Based Search

• Anton Andreychuk
• Konstantin Yakovlev
• Eli Boyarski
• Roni Stern

Conflict-Based Search (CBS) is a powerful algorithmic framework for optimally solving classical multi-agent path finding (MAPF) problems, where time is discretized into the time steps. Continuous-time CBS (CCBS) is a recently proposed version of CBS that guarantees optimal solutions without the need to discretize time. However, the scalability of CCBS is limited because it does not include any known improvements of CBS. In this paper, we begin to close this gap and explore how to adapt successful CBS improvements, namely, prioritizing conflicts (PC), disjoint splitting (DS), and high-level heuristics, to the continuous time setting of CCBS. These adaptions are not trivial, and require careful handling of different types of constraints, applying a generalized version of the Safe interval path planning (SIPP) algorithm, and extending the notion of cardinal conflicts. We evaluate the effect of the suggested enhancements by running experiments both on general graphs and 2k -neighborhood grids. CCBS with these improvements significantly outperforms vanilla CCBS, solving problems with almost twice as many agents in some cases and pushing the limits of multiagent path finding in continuous-time domains.

AAMAS Conference 2021 Conference Paper

Partial Disclosure of Private Dependencies in Privacy Preserving Planning

• Rotem Lev Lehman
• Guy Shani
• Roni Stern

KR Conference 2021 Conference Paper

Safe Learning of Lifted Action Models

• Brendan Juba
• Hai S. Le
• Roni Stern

Creating a domain model, even for classical, domain-independent planning, is a notoriously hard knowledge-engineering task. A natural approach to solve this problem is to learn a domain model from observations. However, model learning approaches frequently do not provide safety guarantees: the learned model may assume actions are applicable when they are not, and may incorrectly capture actions' effects. This may result in generating plans that will fail when executed. In some domains such failures are not acceptable, due to the cost of failure or inability to replan online after failure. In such settings, all learning must be done offline, based on some observations collected, e. g. , by some other agents or a human. Through this learning, the task is to generate a plan that is guaranteed to be successful. This is called the model-free planning problem. Prior work proposed an algorithm for solving the model-free planning problem in classical planning. However, they were limited to learning grounded domains, and thus they could not scale. We generalize this prior work and propose the first safe model-free planning algorithm for lifted domains. We prove the correctness of our approach, and provide a statistical analysis showing that the number of trajectories needed to solve future problems with high probability is linear in the potential size of the domain model. We also present experiments on twelve IPC domains showing that our approach is able to learn the real action model in all cases with at most two trajectories.

JAIR Journal 2021 Journal Article

Safe Multi-Agent Pathfinding with Time Uncertainty

• Tomer Shahar
• Shashank Shekhar
• Dor Atzmon
• Abdallah Saffidine
• Brendan Juba
• Roni Stern

In many real-world scenarios, the time it takes for a mobile agent, e.g., a robot, to move from one location to another may vary due to exogenous events and be difficult to predict accurately. Planning in such scenarios is challenging, especially in the context of Multi-Agent Pathfinding (MAPF), where the goal is to find paths to multiple agents and temporal coordination is necessary to avoid collisions. In this work, we consider a MAPF problem with this form of time uncertainty, where we are only given upper and lower bounds on the time it takes each agent to move. The objective is to find a safe solution, which is a solution that can be executed by all agents and is guaranteed to avoid collisions. We propose two complete and optimal algorithms for finding safe solutions based on well-known MAPF algorithms, namely, A* with Operator Decomposition (A* + OD) and Conflict-Based Search (CBS). Experimentally, we observe that on several standard MAPF grids the CBS-based algorithm performs better. We also explore the option of online replanning in this context, i.e., modifying the agents' plans during execution, to reduce the overall execution cost. We consider two online settings: (a) when an agent can sense the current time and its current location, and (b) when the agents can also communicate seamlessly during execution. For each setting, we propose a replanning algorithm and analyze its behavior theoretically and empirically. Our experimental evaluation confirms that indeed online replanning in both settings can significantly reduce solution cost.

SoCS Conference 2021 Conference Paper

Studying Online Multi-Agent Path Finding

• Jonathan Morag
• Roni Stern
• Ariel Felner
• Dor Atzmon
• Eli Boyarski

Multi-agent path finding (MAPF) is the problem of planning a set of non-conflicting plans on a graph, for a set of agents. Online MAPF extends MAPF by considering a more realistic problem in which new agents may appear over time. While planning, an online solver does not know whether and which agents will join in the future. Therefore, in online problems the notion of snapshot-optimal was defined, where only current knowledge is considered. The quality of such a solution may be weaker than the quality of a solution to an equivalent offline MAPF problem (offline-optimality), where the solver is preinformed of all the agents that will appear in the future. In this paper we explore, theoretically and empirically, the quality of snapshot-optimal solutions compared to offline-optimal solutions.

AAAI Conference 2021 Conference Paper

Towards a Unifying Framework for Formal Theories of Novelty

• Terrance Boult
• Przemyslaw Grabowicz
• Derek Prijatelj
• Roni Stern
• Lawrence Holder
• Joshua Alspector
• Mohsen M. Jafarzadeh
• Toqueer Ahmad

Managing inputs that are novel, unknown, or out-ofdistribution is critical as an agent moves from the lab to the open world. Novelty-related problems include being tolerant to novel perturbations of the normal input, detecting when the input includes novel items, and adapting to novel inputs. While significant research has been undertaken in these areas, a noticeable gap exists in the lack of a formalized definition of novelty that transcends problem domains. As a team of researchers spanning multiple research groups and different domains, we have seen, first hand, the difficulties that arise from ill-specified novelty problems, as well as inconsistent definitions and terminology. Therefore, we present the first unified framework for formal theories of novelty and use the framework to formally define a family of novelty types. Our framework can be applied across a wide range of domains, from symbolic AI to reinforcement learning, and beyond to open world image recognition. Thus, it can be used to help kick-start new research efforts and accelerate ongoing work on these important novelty-related problems.

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.

ICAPS Conference 2020 Conference Paper

Algorithm Selection for Optimal Multi-Agent Pathfinding

• Omri Kaduri
• Eli Boyarski
• Roni Stern

The challenge of finding an optimal solution to a multi-agent path finding (MAPF) problem has attracted significant academic and industrial interest in recent years. While the problem is NP-Hard, modern optimal MAPF algorithms can scale to solve problems with hundreds of agents. Nevertheless, no single optimal MAPF algorithm dominates all benchmarks problems, and there are no clear, provable, guidelines for when each algorithm should be used. To address this, we present the first successful Algorithm Selection (AS) model for optimal MAPF. We propose two approaches for learning an AS model. The first approach uses a standard supervised learning algorithm with a set of handcrafted MAPF-specific features. The second approach, casts a MAPF problem to an image and applies a deep Convolutional Neural Network to classify it. We evaluate both approaches over a large dataset and show that using an AS model to select which algorithm to use for each instance results in solving more problems and in a shorter runtime compared to the state of the art.

AIJ Journal 2020 Journal Article

Batch repair actions for automated troubleshooting

• Hilla Shinitzky
• Roni Stern

ECAI Conference 2020 Conference Paper

Bidding in Spades

• Gal Cohensius
• Reshef Meir
• Nadav Oved
• Roni Stern

We present a Spades bidding algorithm that is superior to recreational human players and to publicly available bots. Like in Bridge, the game of Spades is composed of two independent phases, bidding and playing. This paper focuses on the bidding algorithm, since this phase holds a precise challenge: based on the input, choose the bid that maximizes the agent’s winning probability. Our Bidding-in-Spades (BIS) algorithm heuristically determines the bidding strategy by comparing the expected utility of each possible bid. A major challenge is how to estimate these expected utilities. To this end, we propose a set of domain-specific heuristics, and then correct them via machine learning using data from real-world players. The BIS algorithm we present can be attached to any playing algorithm. It beats rule-based bidding bots when all use the same playing component. When combined with a rule-based playing algorithm, it is superior to the average recreational human.

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.

ICAPS Conference 2020 Conference Paper

Privacy Preserving Planning in Stochastic Environments

• Guy Shani
• Roni Stern
• Tommy Hefner

Collaborative privacy preserving planning (cppp) has gained much attention in the past decade. To date, cppp has focused on domains with deterministic action effects. In this paper, we extend cppp to domains with stochastic action effects. We show how such environments can be modeled as an mdp. We then focus on the popular Real-Time Dynamic Programming (RTDP) algorithm for computing value functions for mdps, extending it to the stochastic cppp setting. We provide two versions of RTDP: a complete version identical to executing centralized RTDP, and an approximate version that sends significantly fewer messages and computes competitive policies in practice. We experiment on domains adapted from the deterministic cppp literature.

ICAPS Conference 2020 Conference Paper

Probabilistic Robust Multi-Agent Path Finding

• Dor Atzmon
• Roni Stern
• Ariel Felner
• Nathan R. Sturtevant
• Sven Koenig

In a multi-agent path finding (MAPF) problem, the task is to move a set of agents to their goal locations without conflicts. In the real world, unexpected events may delay some of the agents. In this paper, we therefore study the problem of finding a p-robust solution to a given MAPF problem, which is a solution that succeeds with probability at least p, even though unexpected delays may occur. We propose two methods for verifying that given solutions are p-robust. We also introduce an optimal CBS-based algorithm, called pR-CBS, and a fast suboptimal algorithm, called pR-GCBS, for finding such solutions. Our experiments show that a p-robust solution reduces the number of conflicts compared to optimal, non-robust solutions.

ICAPS Conference 2020 Conference Paper

Revisiting Bounded-Suboptimal Safe Interval Path Planning

• Konstantin S. Yakovlev
• Anton Andreychuk
• Roni Stern

Safe-interval path planning (SIPP) is a powerful algorithm for finding a path in the presence of dynamic obstacles. SIPP returns provably optimal solutions. However, in many practical applications of SIPP such as path planning for robots, one would like to trade-off optimality for shorter planning time. In this paper we explore different ways to build a bounded-suboptimal SIPP and discuss their pros and cons. We compare the different bounded-suboptimal versions of SIPP experimentally. While there is no universal winner, the results provide insights into when each method should be used.

JAIR Journal 2020 Journal Article

Robust Multi-Agent Path Finding and Executing

• Dor Atzmon
• Roni Stern
• Ariel Felner
• Glenn Wagner
• Roman Barták
• Neng-Fa Zhou

Multi-agent path-finding (MAPF) is the problem of finding a plan for moving a set of agents from their initial locations to their goals without collisions. Following this plan, however, may not be possible due to unexpected events that delay some of the agents. In this work, we propose a holistic solution for MAPF that is robust to such unexpected delays. First, we introduce the notion of a k-robust MAPF plan, which is a plan that can be executed even if a limited number (k) of delays occur. We propose sufficient and required conditions for finding a k-robust plan, and show how to convert several MAPF solvers to find such plans. Then, we propose several robust execution policies. An execution policy is a policy for agents executing a MAPF plan. An execution policy is robust if following it guarantees that the agents reach their goals even if they encounter unexpected delays. Several classes of such robust execution policies are proposed and evaluated experimentally. Finally, we present robust execution policies for cases where communication between the agents may also be delayed. We performed an extensive experimental evaluation in which we compared different algorithms for finding robust MAPF plans, compared different ro- bust execution policies, and studied the interplay between having a robust plan and the performance when using a robust execution policy.

PRL Workshop 2020 Workshop Paper

Safe Learning of Lifted Action Models

• Brendan Juba
• Hai Le
• Roni Stern

Creating a domain model, even for classical, domainindependent planning, is a notoriously hard knowledgeengineering task. A natural approach to solve this problem is to use learning, but learning approaches frequently do not provide guarantees of safety: variously, actions may fail or may not lead to the desired outcome. In some domains such failures are not acceptable, due to the cost of failure or inability to replan online after failure. In such settings, all learning must be done offline, based on some observations collected, e. g. , by some other agents or a human. Through this learning, the task is to generate a plan that is guaranteed to be successful. This is called the model-free planning problem. Prior work proposed an algorithm for solving the model-free planning problem in classical planning. However, they were limited to learning grounded domains, and thus they could not scale. We generalize this prior work and propose the first safe model-free planning algorithm for lifted domains. We prove the correctness of our approach, and provide a statistical analysis showing that the number of trajectories needed to solve future problems with high probability is linear in the potential size of the domain model. We also present experiments demonstrating that our approach scales favorably in practice.

ICAPS Conference 2020 Conference Paper

Solving the Longest Simple Path Problem with Heuristic Search

• Yossi Cohen
• Roni Stern
• Ariel Felner

Prior approaches for finding the longest simple path (LSP) in a graph used constraints solvers and genetic algorithms. In this work, we solve the LSP problem with heuristic search. We first introduce several methods for pruning dominated path prefixes. Then, we propose several admissible heuristic functions for this problem. Experimental results demonstrate the large impact of the proposed heuristics and pruning rules.

SoCS Conference 2019 Conference Paper

Assigning Suppliers to Meet a Deadline

• Liat Cohen
• Tal Grinshpoun
• Roni Stern

Most real-world project have a deadline and consist of completing tasks. In our setting, each task needs to be executed by a single supplier, chosen from a subset of suppliers that have the required proficiency to handle that task. The suppliers differ in their execution times, which are stochastically taken from known distributions. The Supplier Assignment for Meeting a Deadline (SAMD) problem is the problem of assigning a supplier to each task in a manner that maximizes the chance to meet the overall project deadline. We propose an A*-based approach, along with an efficient admissible heuristic function, that guarantees an optimal solution for this problem. Experimentally, we compare our A*-based approach to an exhaustive brute-force approach and several heuristic methods. The results show that our A*-based approach compares favorably with the heuristic methods, and is orders of magnitude faster than the exhaustive alternative.

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

IJCAI Conference 2019 Conference Paper

Domain-Dependent and Domain-Independent Problem Solving Techniques

• Roni Stern

Heuristic search is a general problem-solving method. Some heuristic search algorithms, like the well-known A* algorithm, are domain-independent, in the sense that their knowledge of the problem at-hand is limited to the (1) initial state, (2) state transition operators and their costs, (3) goal-test function, and (4) black-box heuristic function that estimates the value of a state. Prominent examples are A* and Weighted A*. Other heuristic search algorithms are domain-dependent, that is, customized to solve problems from a specific domain. A well-known example is conflict-directed A*, which is specifically designed to solve model-based diagnosis problems. In this paper, we review our recent advancements in both domain-independent and domain-dependent heuristic search, and outline several challenging open questions.

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.

SoCS Conference 2019 Conference Paper

Measuring the Vulnerability of a Multi-Agent Pathfinding Solution

• Rotem Yoeli
• Roni Stern
• Dor Atzmon

Multi-agent pathfinding is the problem of finding a non-interfering paths for a set of agents, such that if the agents follow these paths then each agent will reach its desired destination. Recent years have shown tremendous advances in this field, with optimal and suboptimal algorithms that are able to plan paths for over 100 agents in reasonable time. However, autonomous mobile agents are prime targets for cyber-security attacks, where an adversary may take control over an agent to disrupt the agents execution of their plan. This threat raises two questions. The first question is how much damage can an agent do if it does not follow its plan. The second question is how can one plan a-priori to be as robust as possible to such cyber-attacks. In this work, We provide an answer to both questions. To compute the maximal amount of damage that an adversary agent can do, we define a corresponding graph search problem and solve this problem with A*. Then, we provide a very simple method to choose a solution that is robust to such damages. We demonstrate both algorithms in simulation over standard multi-agent pathfinding domains.

IJCAI Conference 2019 Conference Paper

Multi-Agent Pathfinding with Continuous Time

• Anton Andreychuk
• Konstantin Yakovlev
• Dor Atzmon
• Roni Stern

Multi-Agent Pathfinding (MAPF) is the problem of finding paths for multiple agents such that every agent reaches its goal and the agents do not collide. Most prior work on MAPF were on grids, assumed agents' actions have uniform duration, and that time is discretized into timesteps. In this work, we propose a MAPF algorithm that do not assume any of these assumptions, is complete, and provides provably optimal solutions. This algorithm is based on a novel combination of Safe Interval Path Planning (SIPP), a continuous time single agent planning algorithms, and Conflict-Based Search (CBS). We analyze this algorithm, discuss its pros and cons, and evaluate it experimentally on several standard benchmarks.

SoCS Conference 2019 Conference Paper

Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks

• Roni Stern
• Nathan R. Sturtevant
• Ariel Felner
• Sven Koenig
• Hang Ma 0001
• Thayne T. Walker
• Jiaoyang Li 0001
• Dor Atzmon

The multi-agent pathfinding problem (MAPF) is the fundamental problem of planning paths for multiple agents, where the key constraint is that the agents will be able to follow these paths concurrently without colliding with each other. Applications of MAPF include automated warehouses, autonomous vehicles, and robotics. Research on MAPF has been flourishing in the past couple of years. Different MAPF research papers assume different sets of assumptions, e. g. , whether agents can traverse the same road at the same time, and have different objective functions, e. g. , minimize makespan or sum of agents

AAAI Conference 2019 Conference Paper

Online Multi-Agent Pathfinding

• Jiří Švancara
• Marek Vlk
• Roni Stern
• Dor Atzmon
• Roman Barták

Multi-agent pathfinding (MAPF) is the problem of moving a group of agents to a set of target destinations while avoiding collisions. In this work, we study the online version of MAPF where new agents appear over time. Several variants of online MAPF are defined and analyzed theoretically, showing that it is not possible to create an optimal online MAPF solver. Nevertheless, we propose effective online MAPF algorithms that balance solution quality, runtime, and the number of plan changes an agent makes during execution.

SoCS Conference 2019 Conference Paper

Probabilistic Robust Multi-Agent Path Finding

• Dor Atzmon
• Ariel Felner
• Roni Stern

In a multi-agent path-finding (MAPF) problem, the task is to find a plan for moving a set of agents from their initial locations to their goals without collisions. Following this plan, however, may not be possible due to unexpected events that delay some of the agents. Guaranteeing that collisions will never occur may be impossible. An important task is to find a plan that is very likely to succeed, even though unexpected delays may occur. We propose an algorithm for finding a plan in which the probability that no collisions will occur is at least a given parameter p (p-robust plan). We show that finding an optimal p-robust plan is significantly more difficult than finding an optimal standard plan. As a practical solution, we propose a greedy algorithm based on the Conflict-Based Search framework. Our experiments show that it finds p-robust plans with cost that is relatively close to the optimal cost of the standard, non-robust plans.

AIJ Journal 2019 Journal Article

Probably bounded suboptimal heuristic search

• Roni Stern
• Gal Dreiman
• Richard Valenzano

AAAI Conference 2019 Conference Paper

Safe Partial Diagnosis from Normal Observations

• Roni Stern
• Brendan Juba

Model-based diagnosis (MBD) is difficult to use in practice because it requires a model of the diagnosed system, which is often very hard to obtain. We explore theoretically how observing the system when it is in a normal state can provide information about the system that is sufficient to learn a partial system model that allows automated diagnosis. We analyze the number of observations needed to learn a model capable of finding faulty components in most cases. Then, we explore how knowing the system topology can help us to learn a useful model from the normal observations for settings in which many of the internal system variables cannot be observed. Unlike other data-driven methods, our learned model is safe, in the sense that subsystems identified as faulty are guaranteed to truly be faulty.

JAAMAS Journal 2018 Journal Article

Action dependencies in privacy-preserving multi-agent planning

• Shlomi Maliah
• Guy Shani
• Roni Stern

Abstract Collaborative privacy-preserving planning (CPPP) is a multi-agent planning task in which agents need to achieve a common set of goals without revealing certain private information. In many CPPP algorithms, the individual agents reason about a projection of the multi-agent problem onto a single-agent classical planning problem. For example, an agent can plan as if it controls the public actions of other agents, ignoring any private preconditions and effects theses actions may have, and use the cost of this plan as a heuristic estimate of the cost of the full, multi-agent plan. Using such a projection, however, ignores some dependencies between agents’ public actions. In particular, it does not contain dependencies between public actions of other agents caused by their private facts. We propose a projection in which these private dependencies are maintained. The benefit of our dependency-preserving projection is demonstrated by using it to produce high-level plans in a new privacy-preserving planner, and as a heuristic for guiding forward search privacy-preserving algorithms. Both are able to solve more benchmark problems than any other state-of-the-art privacy-preserving planner. This more informed projection does not explicitly expose any private fact, action, or precondition. In addition, we show that even if an adversary agent knows that an agent has some private objects of a given type (e. g. , trucks), it cannot infer the number of such private objects that the agent controls. This introduces a novel form of strong privacy, which we call object-cardinality privacy, that is motivated by real-world requirements.

EAAI Journal 2018 Journal Article

An Artificial Intelligence paradigm for troubleshooting software bugs

• Amir Elmishali
• Roni Stern
• Meir Kalech

SoCS Conference 2018 Conference Paper

Bounded Suboptimal Game Tree Search

• Dor Atzmon
• Roni Stern
• Abdallah Saffidine

Finding the minimax value of a game is an important problem in a variety of fields, including game theory, decision theory, statistics, philosophy, economics, robotics, and security. Classical algorithms such as the Minimax algorithm can be used to find the minimax value, but require iterating over the entire game tree, which is in many cases too large. Alpha-Beta pruning identifies portions of the game tree that are not necessary for finding the minimax value, but in many cases the remaining part of the game tree is still too large to search in reasonable time. For such cases, we propose a class of algorithms that accepts a parameter e and returns a value that is guaranteed to be at most e away from the true minimax value. We lay the theoretical foundation for building such algorithms and present one such algorithm based on Alpha-Beta. Experimentally, we show that our algorithm allows controlling this runtime/solution quality tradeoff effectively.

SoCS Conference 2018 Conference Paper

Focused SANA: Speeding Up Network Alignment

• Ilia Leybovich
• Rami Puzis
• Roni Stern
• Maor Reuben

Network Alignment (NA) is a generalization of the graph isomorphism problem for non-isomorphic graphs, where the goal is to find a node mapping as close as possible to isomorphism. Recent successful NA algorithms follow a search-based approach, such as simulated annealing. We propose to speed up search-based NA algorithms by pruning the search-space based on heuristic rules derived from the topological features of the aligned nodes. We define several desirable properties of such pruning rules, analyze them theoretically, and propose a pruning rule based on nodes

SoCS Conference 2018 Conference Paper

Robust Multi-Agent Path Finding

• Dor Atzmon
• Roni Stern
• Ariel Felner
• Glenn Wagner
• Roman Barták
• Neng-Fa Zhou

In the multi-agent path-finding (MAPF) problem, the task is to find a plan for moving a set of agents from their initial locations to their goals without collisions. Following this plan, however, may not be possible due to unexpected events that delay some of the agents. We explore the notion of k-robust MAPF, where the task is to find a plan that can be followed even if a limited number of such delays occur. k-robust MAPF is especially suitable for agents with a control mechanism that guarantees that each agent is within a limited number of steps away from its pre-defined plan. We propose sufficient and required conditions for finding a k-robust plan, and show how to convert several MAPF solvers to find such plans. Then, we show the benefit of using a k-robust plan during execution, and for finding plans that are likely to succeed.

AAMAS Conference 2018 Conference Paper

Robust Multi-Agent Path Finding

• Dor Atzmon
• Roni Stern
• Ariel Felner
• Glenn Wagner
• Roman Bart�k
• Neng-Fa Zhou

AIJ Journal 2018 Journal Article

Sequential plan recognition: An iterative approach to disambiguating between hypotheses

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

SoCS Conference 2018 Conference Paper

Sub-Optimal SAT-Based Approach to Multi-Agent Path-Finding Problem

• Pavel Surynek
• Ariel Felner
• Roni Stern
• Eli Boyarski

In multi-agent path finding (MAPF) the task is to find nonconflicting paths for multiple agents. In this paper we focus on finding suboptimal solutions for MAPF for the sum-of-costs variant. Recently, a SAT-based approached was developed to solve this problem and proved beneficial in many cases when compared to other search-based solvers. In this paper, we present SAT-based unbounded- and bounded-suboptimal algorithms and compare them to relevant algorithms. Experimental results show that in many case the SAT-based solver significantly outperforms the search-based solvers.

SoCS Conference 2017 Conference Paper

Dynamic Potential Search on Weighted Graphs

• Daniel Gilon
• Ariel Felner
• Roni Stern

Dynamic Potential Search (DPS) is a recently introduced search algorithm that returns a bounded-suboptimal cost solution. DPS orders nodes in the open-list based on their potential which is a combination of both the g- and h-values of a node. In this paper we study the behavior of DPS on weighted graphs. In particular, we develop a new variant of DPS, called DPSU which calculates the potential by counting one for each edge regardless of its costs. We develop an eager version and a restrained version of DPSU. We then compare all these algorithms on a number of weighted graphs and study the pros and cons of each of them.

IJCAI Conference 2017 Conference Paper

Efficient, Safe, and Probably Approximately Complete Learning of Action Models

• Roni Stern
• Brendan Juba

In this paper we explore the theoretical boundaries of planning in a setting where no model of the agent's actions is given. Instead of an action model, a set of successfully executed plans are given and the task is to generate a plan that is safe, i. e. , guaranteed to achieve the goal without failing. To this end, we show how to learn a conservative model of the world in which actions are guaranteed to be applicable. This conservative model is then given to an off-the-shelf classical planner, resulting in a plan that is guaranteed to achieve the goal. However, this reduction from a model-free planning to a model-based planning is not complete: in some cases a plan will not be found even when such exists. We analyze the relation between the number of observed plans and the likelihood that our conservative approach will indeed fail to solve a solvable problem. Our analysis show that the number of trajectories needed scales gracefully.

AIJ Journal 2017 Journal Article

How many diagnoses do we need?

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

SoCS Conference 2017 Conference Paper

k-Robust Multi-Agent Path Finding

• Dor Atzmon
• Ariel Felner
• Roni Stern
• Glenn Wagner
• Roman Barták
• Neng-Fa Zhou

In the multi-agent path-finding (MAPF) problem a plan is needed to move a set of agents from their initial location to their goals without collisions. In this paper we introduce and study the k-robust MAPF problem, where we seek a plan that is robust to k unexpected delays per agent.

SoCS Conference 2017 Conference Paper

Modifying Optimal SAT-Based Approach to Multi-Agent Path-Finding Problem to Suboptimal Variants

• Pavel Surynek
• Ariel Felner
• Roni Stern
• Eli Boyarski

In multi-agent path finding (MAPF) the task is to find non-conflicting paths for multiple agents. Recently, a SAT-based approach was developed to solve this problem and proved beneficial in many cases when compared to other search-based solvers. In this paper, we introduce SAT-based unbounded- and bounded-suboptimal algorithms and compare them to relevant search-based algorithms.

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.

SoCS Conference 2017 Conference Paper

Search-Based Optimal Solvers for the Multi-Agent Pathfinding Problem: Summary and Challenges

• Ariel Felner
• Roni Stern
• Solomon Eyal Shimony
• Eli Boyarski
• Meir Goldenberg
• Guni Sharon
• Nathan R. Sturtevant
• Glenn Wagner

Multi-agent pathfinding (MAPF) is an area of expanding research interest. At the core of this research area, numerous diverse search-based techniques were developed in the past 6 years for optimally solving MAPF under the sum-of-costs objective function. In this paper we survey these techniques, while placing them into the wider context of the MAPF field of research. Finally, we provide analytical and experimental comparisons that show that no algorithm dominates all others in all circumstances. We conclude by listing important future research directions.

SoCS Conference 2017 Conference Paper

Shortest Path for K Goals

• Roni Stern
• Meir Goldenberg
• Ariel Felner

In this paper we study the k goal search problem (kGS), which is the problem of solving k shortest path problems that share the same start state. Two fundamental heuristic search approaches are analyzed: searching for the k goals one at a time, or searching for all k goals together in a single pass. Key theoretical properties are established and a preliminary experimental evaluation is performed.

SoCS Conference 2016 Conference Paper

An Empirical Comparison of the Hardness of Multi-Agent Path Finding under the Makespan and the Sum of Costs Objectives

• Pavel Surynek
• Ariel Felner
• Roni Stern
• Eli Boyarski

In the multi-agent path finding (MAPF) the task is to find non-conflicting paths for multiple agents. Recently, existing makespan optimal SAT-based solvers for MAPF have been modified for the sum-of-costs objective. In this paper, we empirically compare the hardness of solving MAPF with SAT-based and search-based solvers under the makespan and the sum-of-costs objectives in a number of domains. The experimental evaluation shows that MAPF under the makespan objective is easier across all the tested solvers and domains.

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

AAMAS Conference 2016 Conference Paper

Boolean Satisfiability Approach to Optimal Multi-agent Path Finding Under the Sum of Costs Objective (Extended Abstract)

• Pavel Surynek
• Ariel Felner
• Roni Stern
• Eli Boyarski

This paper focuses on finding optimal solutions to the multiagent path finding (MAPF) problem over undirected graphs where the task is to find non-colliding paths for multiple agents, each with a different start and goal position. An encoding of MAPF to Boolean satisfiability (SAT) is already known to the makespan optimal variant of the problem. In this paper we present the first SAT-solver for minimizing the sum of costs enabled by introducing cardinality constraints into the SAT encoding. An experimental evaluation on grid graphs indicate promising performance of the new SAT-based method in comparison with the best variants of previous sum-of-costs search solvers.

JAAMAS Journal 2016 Journal Article

Collaborative privacy preserving multi-agent planning

• Shlomi Maliah
• Guy Shani
• Roni Stern

Abstract In many cases several entities, such as commercial companies, need to work together towards the achievement of joint goals, while hiding certain private information. To collaborate effectively, some sort of plan is needed to coordinate the different entities. We address the problem of automatically generating such a coordination plan while preserving the agents’ privacy. Maintaining privacy is challenging when planning for multiple agents, especially when tight collaboration is needed and a global high-level view of the plan is required. In this work we present the Greedy Privacy-Preserving Planner (GPPP), a privacy preserving planning algorithm in which the agents collaboratively generate an abstract and approximate global coordination plan and then individually extend the global plan to executable plans. To guide GPPP, we propose two domain independent privacy preserving heuristics based on landmarks and pattern databases, which are classical heuristics for single agent search. These heuristics, called privacy-preserving landmarks and privacy preserving PDBs, are agnostic to the planning algorithm and can be used by other privacy-preserving planning algorithms. Empirically, we demonstrate on benchmark domains the benefits of using these heuristics and the advantage of GPPP over existing privacy preserving planners for the multi-agent STRIPS formalism.

SoCS Conference 2016 Conference Paper

Dynamic Potential Search - A New Bounded Suboptimal Search

• Daniel Gilon
• Ariel Felner
• Roni Stern

Potential Search (PS) is an algorithm that is designed to solve bounded cost search problems. In this paper, we modify PS to work within the framework of bounded suboptimal search and introduce Dynamic Potential Search (DPS). DPS uses the idea of PS but modifies the bound to be the product of the minimal f-value in OPEN and the required suboptimal bound. We study DPS and its attributes. We then experimentally compare DPS to WA* and to EES on a variety of domains and study parameters that affect the behavior of these algorithms. In general we show that in domains with unit edge costs (e. g. , many standard benchmarks) DPS significantly outperforms WA* and EES but there are exceptions.

ECAI Conference 2016 Conference Paper

Efficient SAT Approach to Multi-Agent Path Finding Under the Sum of Costs Objective

• Pavel Surynek
• Ariel Felner
• Roni Stern
• Eli Boyarski

In the multi-agent path finding (MAPF) the task is to find non-conflicting paths for multiple agents. In this paper we present the first SAT-solver for the sum-of-costs variant of MAPF which was previously only solved by search-based methods. Using both a lower bound on the sum-of-costs and an upper bound on the makespan, we are able to have a reasonable number of variables in our SAT encoding. We then further improve the encoding by borrowing ideas from ICTS, a search-based solver. Experimental evaluation on several domains showed that there are many scenarios where the new SAT-based method outperforms the best variants of previous sum-of-costs search solvers - the ICTS and ICBS 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.

AIJ Journal 2016 Journal Article

Predicting optimal solution costs with bidirectional stratified sampling in regular search spaces

• Levi H.S. Lelis
• Roni Stern
• Shahab Jabbari Arfaee
• Sandra Zilles
• Ariel Felner
• Robert C. Holte

SoCS Conference 2016 Conference Paper

Repair Policies for Not Reopening Nodes in Different Search Settings

• Vitali Sepetnitsky
• Ariel Felner
• Roni Stern

We examine two policies for reopening of nodes: never reopen (NR) and always reopen (AR). While there are circumstances where each policy isbeneficial, we observed empirically that NR is usually faster. However, NR may fail to return a solution of the desired quality in two scenarios: (1) in a bounded suboptimal search when inconsistent heuristics are usedand (2) in a bounded cost setting. To remedy this we provide two repair policies for NR when the desired quality was not obtained. The firstpolicy is to restart AR. The second policy is to repeatedly place the nodesthat were not reopened back in OPEN and continue with NR. Experimentalresults show that both repair polices outperform the AR policy.

SoCS Conference 2016 Conference Paper

Searching with a Corrupted Heuristic

• Levi H. S. Lelis
• Richard Valenzano
• Gabriel L. Nazar
• Roni Stern

Memory-based heuristics are a popular and effective class of admissible heuristic functions. However, corruptions to memory they use may cause these heuristics to become inadmissible. Corruption can be caused by the physical environment due to radiation and network errors, or it can be introduced voluntarily in order to decrease energy consumption. We introduce memory error correction schemes that do not require additional memory and exploit knowledge about the behavior of consistent heuristics. This is in contrast with error correcting code approaches which can limit the amount of corruption but at the cost of additional energy and memory consumption. Search algorithms using our methods are guaranteed to find a solution if one exists and its suboptimality is bounded. Moreover, our methods are resilient to any number of memory errors that may occur. An experimental evaluation is also provided to demonstrate the applicability of our approach.

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.

ICAPS Conference 2016 Conference Paper

Stronger Privacy Preserving Projections for Multi-Agent Planning

• Shlomi Maliah
• Guy Shani
• Roni Stern

Collaborative privacy-preserving planning (CPPP) is a multi-agent planning task in which agents need to achieve a common set of goals without revealing certain private information. In many CPPP algorithms the individual agents reason about a projection of the multiagent problem onto a single-agent classical planning problem. For example, an agent can plan as if it controls the public actions of other agents, ignoring their unknown private preconditions and effects, and use the cost of this plan as a heuristic for the cost of the full, multi-agent plan. Using such a projection, however, ignores some dependencies between agents’ public actions. In particular, it does not contain dependencies between actions of other agents caused by their private facts. We propose a projection in which these private dependencies are maintained. The benefit of our dependency-preserving projection is demonstrated by using it to produce high level plans in a new privacy preserving planner that is able to solve more benchmark problems than any other state-of-the-art privacy preserving planner. This more informed projection does not explicitly share private information. In addition, we show that even if an adversary agent knows that an agent has some private objects of a given type (e. g. , trucks), it cannot infer how many such private objects the agent controls. This introduces a novel strong form of privacy that is motivated by real-world requirements.

AAAI Conference 2016 Conference Paper

What’s Hot in Heuristic Search

• Roni Stern
• Levi Lelis

Search in general, and heuristic search in particular, is at the heart of many Artificial Intelligence algorithms and applications. There is now a growing and active community devoted to the empirical and theoretical study of heuristic search algorithms, thanks to the successful application of search-based algorithms to areas such as robotics, domain-independent planning, optimization, and computer games. In this extended abstract we highlight recent efforts in understanding suboptimal search algorithms, as well as ensembles of heuristics and algorithms. The result of these efforts are meta-reasoning methods which are applied to orchestrate the different components of modern search algorithms. Finally, we mention recent innovative applications of search that demonstrate the relevance of the field to general AI.

AIJ Journal 2015 Journal Article

Conflict-based search for optimal multi-agent pathfinding

• Guni Sharon
• Roni Stern
• Ariel Felner
• Nathan R. Sturtevant

ICAPS Conference 2015 Conference Paper

Don't Split, Try To Work It Out: Bypassing Conflicts in Multi-Agent Pathfinding

• Eli Boyarski
• Ariel Felner
• Guni Sharon
• Roni Stern

Conflict-Based Search (CBS) is a recently introduced algorithm for Multi-AgentPath Finding (MAPF) whose runtime is exponential in the number of conflictsfound between the agents' paths. We present an improved version of CBS thatbypasses conflicts thereby reducing the CBS search tree. Experimental resultsshow that this improvement reduces the runtime by an order of magnitude in manycases.

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

ICBS: Improved Conflict-Based Search Algorithm for Multi-Agent Pathfinding

• Eli Boyarski
• Ariel Felner
• Roni Stern
• Guni Sharon
• David Tolpin
• Oded Betzalel
• Eyal Shimony

Conflict-Based Search (CBS) and its enhancements, Meta-Agent CBS and bypassing conflicts are amongst the strongest newly introduced algorithms for Multi-Agent Path Finding. This paper introduces two new improvements to CBS and incorporates them into a coherent, improved version of CBS, namely ICBS. Experimental results show that each of these improvements further reduces the runtime over the existing CBS-based approaches. When all improvements are combined, an even larger improvement is achieved, producing state-of-the art results for a number of domains.

SoCS Conference 2015 Conference Paper

ICBS: The Improved Conflict-Based Search Algorithm for Multi-Agent Pathfinding

• Eli Boyarski
• Ariel Felner
• Roni Stern
• Guni Sharon
• Oded Betzalel
• David Tolpin
• Solomon Eyal Shimony

Conflict-Based Search (CBS) and its generalization, Meta-Agent CBS are amongst the strongest newly introduced algorithms for Multi-Agent Path Finding. This paper introduces ICBS, an improved version of CBS. ICBS incorporates three orthogonal improvements to CBS which are systematically described and studied. Experimental results show that each of these improvements reduces the runtime over basic CBS by up to 20x in many cases. When all three improvements are combined, an even larger improvement is achieved, producing state-ofthe art results for a number of domains.

IJCAI Conference 2015 Conference Paper

Max Is More than Min: Solving Maximization Problems with Heuristic Search

• Roni Stern
• Scott Kiesel
• Rami Puzis
• Ariel Felner
• Wheeler Ruml

Most work in heuristic search considers problems where a low cost solution is preferred (MIN problems). In this paper, we investigate the complementary setting where a solution of high reward is preferred (MAX problems). Example MAX problems include finding a longest simple path in a graph, maximal coverage, and various constraint optimization problems. We examine several popular search algorithms for MIN problems and discover the curious ways in which they misbehave on MAX problems. We propose modifications that preserve the original intentions behind the algorithms but allow them to solve MAX problems, and compare them theoretically and empirically. Interesting results include the failure of bidirectional search and close relationships between Dijkstra’s algorithm, weighted A*, and depth-first search.

AAAI Conference 2015 Conference Paper

Multi-Agent Pathfinding as a Combinatorial Auction

• Ofra Amir
• Guni Sharon
• Roni Stern

This paper proposes a mapping between multi-agent pathfinding (MAPF) and combinatorial auctions (CAs). In MAPF, agents need to reach their goal destinations without colliding. Algorithms for solving MAPF aim at assigning agents non-conflicting paths that minimize agents’ travel costs. In CA problems, agents bid over bundles of items they desire. Auction mechanisms aim at finding an allocation of bundles that maximizes social welfare. In the proposed mapping of MAPF to CAs, agents bid on paths to their goals and the auction allocates non-colliding paths to the agents. Using this formulation, auction mechanisms can be naturally used to solve a range of MAPF problem variants. In particular, auction mechanisms can be applied to non-cooperative settings with self-interested agents while providing optimality guarantees and robustness to manipulations by agents. The paper further shows how to efficiently implement an auction mechanism for MAPF, utilizing methods and representations from both the MAPF and CA literatures.

SoCS Conference 2015 Conference Paper

Search Problems in the Domain of Multiplication: Case Study on Anomaly Detection Using Markov Chains

• Yisroel Mirsky
• Aviad Cohen 0002
• Roni Stern
• Ariel Felner
• Lior Rokach
• Yuval Elovici
• Bracha Shapira

Most work in heuristic search focused on path finding problems in which the cost of a path in the state space is the sum of its edges

SoCS Conference 2015 Conference Paper

Solving the Snake in the Box Problem with Heuristic Search: First Results

• Alon Palombo
• Roni Stern
• Rami Puzis
• Ariel Felner
• Scott Kiesel
• Wheeler Ruml

Snake in the Box (SIB) is the problem of finding the longest simple path along the edges of an n-dimensional cube, subject to certain constraints. SIB has important applications in coding theory and communications. State of the art algorithms for solving SIB apply uninformed search with symmetry breaking techniques. We formalize this problem as a search problem and propose several admissible heuristics to solve it. Using the proposed heuristics is shown to have a huge impact on the number of nodes expanded and, in some configurations, on runtime. These results encourage further research in using heuristic search to solve SIB, and to solve maximization problems more generally.

SoCS Conference 2014 Conference Paper

A* with Lookahead Re-Evaluated

• Zhaoxing Bu
• Roni Stern
• Ariel Felner
• Robert C. Holte

A* with lookahead (AL*) is a variant of A* that performs a cost-bounded DFS lookahead from a node when it is generated. We show that the original version of AL* (AL*0) can, in some circumstances, fail to return an optimal solution because of the move pruning it does. We present two new versions, AL*1 and ELH, that we prove to always be correct and give conditions in which AL*0 is guaranteed to be correct. In our experiments with unit costs, AL*0 was usually the fastest AL* version, but its advantage was usually small. In our experiments with non-unit costs, AL*0 substantially outperforms both A* and IDA*. We also evaluate the idea of immediately expanding a generated node if it has the same f-value as its parent. We find that doing so causes AL* to require more memory and sometimes slows AL* down.

SoCS Conference 2014 Conference Paper

Estimating Search Tree Size with Duplicate Detection

• Levi H. S. Lelis
• Roni Stern
• Nathan R. Sturtevant

In this paper we introduce Stratified Sampling with Duplicate Detection (SSDD), an algorithm for estimating the number of state expansions performed by heuristic search algorithms seeking solutions in state spaces represented by undirected graphs. SSDD is general and can be applied to estimate other state-space properties. We test SSDD on two tasks: (i) prediction of the number of A* expansions in a given f-layer when using a consistent heuristic function, and (ii) prediction of the state-space radius. SSDD has the asymptotic guarantee of producing perfect estimates in both tasks. Our empirical results show that in task (i) SSDD produces good estimates in all four domains tested, being in most cases orders of magnitude more accurate than a competing scheme, and in task (ii) SSDD quickly produces accurate estimates of the radii of the 4x4 Sliding-Tile Puzzle and the 3x3x3 Rubik

SoCS Conference 2014 Conference Paper

Extended Framework for Target Oriented Network Intelligence Collection

• Liron Samama-Kachko
• Rami Puzis
• Roni Stern
• Ariel Felner

The Target Oriented Network Intelligence Collection (TONIC) problem is the problem of finding profiles in a social network that contain publicly available information about a given target profile via automated crawling. Such profiles are called leads. Leads can be found by crawling the network using the profiles

SoCS Conference 2014 Conference Paper

Max is More than Min: Solving Maximization Problems with Heuristic Search

• Roni Stern
• Scott Kiesel
• Rami Puzis
• Ariel Felner
• Wheeler Ruml

Most work in heuristic search considers problems where a low cost solution is preferred (MIN problems). In this paper, we investigate the complementary setting where a solution of high reward is preferred (MAX problems). Example MAX problems include finding the longest simple path in a graph, maximal coverage, and various constraint optimization problems. We examine several popular search algorithms for MIN problems — optimal, suboptimal, and bounded suboptimal - and discover the curious ways in which they misbehave on MAX problems. We propose modifications that preserve the original intentions behind the algorithms but allow them to solve MAX problems, and compare them theoretically and empirically. Interesting results include the failure of bidirectional search and a discovered close relationships between Dijkstra

AIJ Journal 2014 Journal Article

Potential-based bounded-cost search and Anytime Non-Parametric A ⁎

• Roni Stern
• Ariel Felner
• Jur van den Berg
• Rami Puzis
• Rajat Shah
• Ken Goldberg

ECAI Conference 2014 Conference Paper

Privacy Preserving Landmark Detection

• Shlomi Maliah
• Guy Shani
• Roni Stern

In many cases several entities, such as commercial companies, need to work together towards the achievement of joint goals, while hiding certain private information. Multi-agent STRIPS (MA-STRIPS) is a new and attractive model for describing collaborative multi-agent privacy preserving planning, which is appropriate for such problems. In single agent classical planning, landmarks are key to constructing strong heuristics for state space search. In this paper we propose a method for identifying landmarks in MA-STRIPS in a privacy preserving distributed setting. The agents collaborate to find sound landmarks without revealing their private actions or goals. In addition, we also propose a novel MA-STRIPS planner that uses these landmarks. We empirically show that our detected landmarks improve the performance of previous approaches, and that our new planner is faster than all existing planners for multi-agent problems.

SoCS Conference 2014 Conference Paper

Solving the Target-Value Search Problem

• Carlos Linares López
• Roni Stern
• Ariel Felner

This paper addresses the Target-Value Search (TVS) problem, which is the problem of finding a path between two nodes in a graph whose cost is as close as possible to a given target value, T. This problem has been previously addressed: first, for directed acyclic graphs; second, for general graphs under the assumption that nodes can be revisited given that the same edge can not be traversed twice. In this work we focus on a more restrictive variant of the same problem where nodes can not be revisited. We prove that this variant is NP-complete and discuss novel theoretical properties and provide empirical results to solve this problem optimally.

SoCS Conference 2014 Conference Paper

Suboptimal Variants of the Conflict-Based Search Algorithm for the Multi-Agent Pathfinding Problem

• Max Barer
• Guni Sharon
• Roni Stern
• Ariel Felner

The task in the multi-agent path finding problem (MAPF) is to find paths for multiple agents, each with a different start and goal position, such that agents do not collide. A successful optimal MAPF solver is the conflict-based search (CBS) algorithm. CBS is a two level algorithm where special conditions ensure it returns the optimal solution. Solving MAPF optimally is proven to be NP-hard, hence CBS and all other optimal solvers do not scale up. We propose several ways to relax the optimality conditions of CBS trading solution quality for runtime as well as bounded-suboptimal variants, where the returned solution is guaranteed to be within a constant factor from optimal solution cost. Experimental results show the benefits of our new approach; a massive reduction in running time is presented while sacrificing a minor loss in solution quality. Our new algorithms outperform other existing algorithms in most of the cases.

ECAI Conference 2014 Conference Paper

Suboptimal Variants of the Conflict-Based Search Algorithm for the Multi-Agent Pathfinding Problem

• Max Barer
• Guni Sharon
• Roni Stern
• Ariel Felner

AAAI Conference 2014 Conference Paper

To Share or Not to Share? The Single Agent in a Team Decision Problem

• Ofra Amir
• Barbara Grosz
• Roni Stern

This paper defines the “Single Agent in a Team Decision” (SATD) problem. SATD differs from prior multi-agent communication problems in the assumptions it makes about teammates’ knowledge of each other’s plans and possible observations. The paper proposes a novel integrated logical-decisiontheoretic approach to solving SATD problems, called MDP- PRT. Evaluation of MDP-PRT shows that it outperforms a previously proposed communication mechanism that did not consider the timing of communication and compares favorably with a coordinated Dec-POMDP solution that uses knowledge about all possible observations.

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.

SoCS Conference 2013 Conference Paper

Bounded Suboptimal Heuristic Search in Linear Space

• Matthew Hatem
• Roni Stern
• Wheeler Ruml

It is commonly appreciated that solving search problems optimally can overrun time and memory constraints. Bounded suboptimal search algorithms trade increased solution cost for reduced solving time and memory consumption. However, even suboptimal search can overrun memory on large problems. The conventional approach to this problem is to combine a weighted admissible heuristic with an optimal linear space algorithm, resulting in algorithms such as Weighted IDA* (wIDA*). However, wIDA* does not exploit distance-to-go estimates or inadmissible heuristics, which have recently been shown to be helpful for suboptimal search. In this paper, we present a linear space analogue of Explicit Estimation Search (EES), a recent algorithm specifically designed for bounded suboptimal search. We call our method Iterative Deepening EES (IDEES). In an empirical evaluation, we show that IDEES dramatically outperforms wIDA* on domains with non-uniform edge costs and can scale to problems that are out of reach for the original EES.

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.

IJCAI Conference 2013 Conference Paper

Target-Value Search Revisited

• Carlos Linares López
• Roni Stern
• Ariel Felner

This paper addresses the Target-Value Search (TVS) problem, which is the problem of finding a path between two nodes in a graph whose cost is as close as possible to a given target value, T. This problem has been previously addressed only for directed acyclic graphs. In this work we develop the theory required to solve this problem optimally for any type of graphs. We modify traditional heuristic search algorithms for this setting, and propose a novel bidirectional search algorithm that is specifically suited for TVS. The benefits of this bidirectional search algorithm are discussed both theoretically and experimentally on several domains.

SoCS Conference 2013 Conference Paper

Target-Value Search Revisited (Extended Abstract)

• Carlos Linares López
• Roni Stern
• Ariel Felner

This paper addresses the Target-Value Search (TVS) problem, which is the problem of finding a path between two nodes in a graph whose cost is as close as possible to a given target value T. This problem has been previously addressed only for directed acyclic graphs. In this work we develop the theory required to solve this problem optimally for any type of graphs. We modify traditional heuristic search algorithms for this setting, and propose a novel bidirectional search algorithm that is specifically suited for TVS. The benefits of this bidirectional search algorithm are discussed both theoretically and experimentally on several domains. A longer version of this work was accepted to IJCAI-2013 (Linares Lopez et al. 2013)

AIJ Journal 2013 Journal Article

The increasing cost tree search for optimal multi-agent pathfinding

• Guni Sharon
• Roni Stern
• Meir Goldenberg
• Ariel Felner

AAAI Conference 2013 Conference Paper

TONIC: Target Oriented Network Intelligence Collection for the Social Web

• Roni Stern
• Liron Samama
• Rami Puzis
• Tal Beja
• Zahy Bnaya
• Ariel Felner

In this paper we introduce the Target Oriented Network Intelligence Collection (TONIC) problem, which is the problem of finding profiles in a social network that contain information about a given target via automated crawling. We formalize TONIC as a search problem and a best-first approach is proposed for solving it. Several heuristics are presented to guide this search. These heuristics are based on the topology of the currently known part of the social network. The efficiency of the proposed heuristics and the effect of the graph topology on their performance is experimentally evaluated on the Google+ social network.

ICAPS Conference 2013 Conference Paper

Using Alternative Suboptimality Bounds in Heuristic Search

• Richard Valenzano
• Shahab Jabbari Arfaee
• Jordan Tyler Thayer
• Roni Stern
• Nathan R. Sturtevant

Most bounded suboptimal algorithms in the search literature have been developed so as to be epsilon-admissible. This means that the solutions found by these algorithms are guaranteed to be no more than a factor of (1 + ε) greater than optimal. However, this is not the only possible form of suboptimality bounding. For example, another possible suboptimality guarantee is that of additive bounding, which requires that the cost of the solution found is no more than the cost of the optimal solution plus a constant gamma. In this work, we consider the problem of developing algorithms so as to satisfy a given, and arbitrary, suboptimality requirement. To do so, we develop a theoretical framework which can be used to construct algorithms for a large class of possible suboptimality paradigms. We then use the framework to develop additively bounded algorithms, and show that in practice these new algorithms effectively trade-off additive solution suboptimality for runtime.

SoCS Conference 2012 Conference Paper

A* Variants for Optimal Multi-Agent Pathfinding

• Meir Goldenberg
• Ariel Felner
• Roni Stern
• Jonathan Schaeffer 0001

Several variants of A* have been recently proposed for find-ing optimal solutions for the multi-agent pathfinding (MAPF)problem. We describe the application of the new enhancedpartial-expansion technique to MAPF, show how patterndatabases can be applied on top of this technique and com-pare the different A* variants experimentally.

SoCS Conference 2012 Conference Paper

Alternative Forms of Bounded Suboptimal Search

• Richard Valenzano
• Shahab Jabbari Arfaee
• Jordan Tyler Thayer
• Roni Stern

Previous research into bounded suboptimal search has focused on the development of epsilon-admissible algorithms which are guaranteed to return solutions that are no more than a factor larger than optimal. In this paper, we consider the problem of how to construct search algorithms that satisfy alternative types of guarantees such as an additive bound. This bounding paradigm requires that the cost of any solution found is no more than the optimal cost plus gamma, which is a user-defined constant. To this end, we provide theorems that define sufficient conditions for developing algorithms for arbitrary bounding paradigms when using best-first search, iterative deepening, or focal list-based search. We then show by experimentation that these theorems can be used to construct effective additively bounded algorithms.

SoCS Conference 2012 Conference Paper

Are We There Yet? - Estimating Search Progress

• Jordan Tyler Thayer
• Roni Stern
• Levi H. S. Lelis

Heuristic search is a general problem solving technique. While most evaluations of heuristic search focus on the speed of search, there are relatively few techniques for predicting when search will end. This paper provides a study of progress estimating techniques for optimal, suboptimal, and bounded suboptimal heuristic search algorithms. We examine two previously proposed techniques, search velocity and search vacillation, as well as two new approaches, path-based estimation and distribution-based estimation. We find that both new approaches are better at estimating the remaining amount of search effort than previous work in all three varieties of search, occasionally erring by less than 5%.

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

Conflict-Based Search For Optimal Multi-Agent Path Finding

• Guni Sharon
• Roni Stern
• Ariel Felner
• Nathan Sturtevant

In the multi agent path finding problem (MAPF) paths should be found for several agents, each with a different start and goal position such that agents do not collide. Previous optimal solvers applied global A*-based searches. We present a new search algorithm called Conflict Based Search (CBS). CBS is a two-level algorithm. At the high level, a search is performed on a tree based on conflicts between agents. At the low level, a search is performed only for a single agent at a time. In many cases this reformulation enables CBS to examine fewer states than A* while still maintaining optimality. We analyze CBS and show its benefits and drawbacks. Experimental results on various problems shows a speedup of up to a full order of magnitude over previous approaches.

SoCS Conference 2012 Conference Paper

Conflict-Based Search for Optimal Multi-Agent Path Finding

• Guni Sharon
• Roni Stern
• Ariel Felner
• Nathan R. Sturtevant

We present a new two-level search algorithm for optimal multi-agent path finding called Conflict Based Search (CBS). At the high level, a search is performed on a tree based on conflicts between agents. At the low level, a search is performed only for a single agent at a time. Experimental results on various problems shows a speedup of up to a full order of magnitude over previous approaches.

AAAI Conference 2012 Conference Paper

Exploring the Duality in Conflict-Directed Model-Based Diagnosis

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

ICAPS Conference 2012 Conference Paper

Faster Bounded-Cost Search Using Inadmissible Estimates

• Jordan Tyler Thayer
• Roni Stern
• Ariel Felner
• Wheeler Ruml

Many important problems are too difficult to solve optimally. A traditional approach to such problems is bounded suboptimal search, which guarantees solution costs within a user-specified factor of optimal. Recently, a complementary approach has been proposed: bounded-cost search, where solution cost is required to be below a user-specified absolute bound. In this paper, we show how bounded-cost search can incorporate inadmissible estimates of solution cost and solution length. This information has previously been shown to improve bounded suboptimal search and, in an empirical evaluation over five benchmark domains, we find that our new algorithms surpass the state-of-the-art in bounded-cost search as well, particularly for domains where action costs differ.

SoCS Conference 2012 Conference Paper

Meta-Agent Conflict-Based Search For Optimal Multi-Agent Path Finding

• Guni Sharon
• Roni Stern
• Ariel Felner
• Nathan R. Sturtevant

The task in the multi-agent path finding problem (MAPF) isto find paths for multiple agents, each with a different startand goal position, such that agents do not collide. It is possibleto solve this problem optimally with algorithms that arebased on the A* algorithm. Recently, we proposed an alternativealgorithm called Conflict-Based Search (CBS) (Sharonet al. 2012), which was shown to outperform the A*-basedalgorithms in some cases. CBS is a two-level algorithm. Atthe high level, a search is performed on a tree based on conflictsbetween agents. At the low level, a search is performedonly for a single agent at a time. While in some cases CBSis very efficient, in other cases it is worse than A*-based algorithms. This paper focuses on the latter case by generalizingCBS to Meta-Agent CBS (MA-CBS). The main idea isto couple groups of agents into meta-agents if the number ofinternal conflicts between them exceeds a given bound. MACBSacts as a framework that can run on top of any completeMAPF solver. We analyze our new approach and provideexperimental results demonstrating that it outperforms basicCBS and other A*-based optimal solvers in many cases.

SoCS Conference 2012 Conference Paper

Partial-Expansion A* with Selective Node Generation

• Ariel Felner
• Meir Goldenberg
• Guni Sharon
• Roni Stern
• Tal Beja
• Nathan R. Sturtevant
• Robert C. Holte
• Jonathan Schaeffer 0001

A* is often described as being 'optimal, ' in that it expands the minimum number of unique nodes. But, A* may generate many extra nodes which are never expanded. This is a performance loss, especially when the branching factor is large. Partial Expansion A* (PEA*) addresses this problem when expanding a node, n, by generating all the children of n but only storing children with the same f-cost as n. We introduce an enhanced version of PEA* (EPEA*). Given a priori domain knowledge, EPEA* only generates the children with the same f-cost as the parent. State-of-the-art results were obtained for a number of domains. Drawbacks of EPEA* are also discussed. A full version of this paper appears in the proceedings of AAAI-2012

AAAI Conference 2012 Conference Paper

Partial-Expansion A* with Selective Node Generation

• Ariel Felner
• Meir Goldenberg
• Guni Sharon
• Roni Stern
• Tal Beja
• Nathan Sturtevant
• Jonathan Schaeffer
• Robert Holte

A* is often described as being ‘optimal’, in that it expands the minimum number of unique nodes. But, A* may generate many extra nodes which are never expanded. This is a performance loss, especially when the branching factor is large. Partial Expansion A* (PEA*) (Yoshizumi, Miura, and Ishida 2000) addresses this problem when expanding a node, n, by generating all the children of n but only storing children with the same f-cost as n. n is re-inserted into the OPEN list, but with the f-cost of the next best child. This paper introduces an enhanced version of PEA* (EPEA*). Given a priori domain knowledge, EPEA* generates only the children with the same f-cost as the parent. EPEA* is generalized to its iterative-deepening variant, EPE-IDA*. For some domains, these algorithms yield substantial performance improvements. State-of-the-art results were obtained for the pancake puzzle and for some multi-agent pathfinding instances. Drawbacks of EPEA* are also discussed.

ICAPS Conference 2012 Conference Paper

Predicting Optimal Solution Cost with Bidirectional Stratified Sampling

• Levi H. S. Lelis
• Roni Stern
• Ariel Felner
• Sandra Zilles
• Robert C. Holte

Optimal planning and heuristic search systems solve state-space searchproblems by finding a least-cost path from start to goal. As a byproduct of having an optimal path they also determine the optimal solution cost. In this paper we focus on the problem of determining the optimal solution cost for a state-space search problem directly, i. e. without actually finding a solution path of that cost. We present an efficient algorithm, BiSS, based on ideas of bidirectional search and stratified sampling that produces accurate estimates of the optimal solution cost. Our method is guaranteed to return the optimal solution cost in the limit as the sample size goes to infinity. We show empirically that our method makes accurate predictions in several domains. In addition, we show that our method scales to state spaces much larger than can be solved optimally. In particular, we estimate the average solution cost for the 6x6, 7x7, and 8x8 Sliding-Tile Puzzle and provide indirect evidence that these estimates are accurate.

SoCS Conference 2012 Conference Paper

Predicting Optimal Solution Cost with Bidirectional Stratified Sampling (Abstract)

• Levi H. S. Lelis
• Roni Stern
• Ariel Felner
• Sandra Zilles
• Robert C. Holte

Optimal planning and heuristic search systems solve state-space searchproblems by finding a least-cost path from start to goal. As a byproduct of having an optimal path they also determine the optimal solution cost. In this paper we focus on the problem of determining the optimal solution cost for a state-space search problem directly, i. e. , without actually finding a solution path of that cost. We present an efficient algorithm, BiSS, based on ideas of bidirectional search and stratified sampling that produces accurate estimates of the optimal solution cost. Our method is guaranteed to return the optimal solution cost in the limit as the sample size goes to infinity.

SoCS Conference 2012 Conference Paper

Search-Aware Conditions for Probably Approximately Correct Heuristic Search

• Roni Stern
• Ariel Felner
• Robert C. Holte

The notion of finding a solution that is approximately optimal with high probability was recently introduced to the field of heuristic search, formalized as Probably Approximately Correct Heuristic Search, or PAC search in short. A big challenge when constructing a PAC search algorithm is to identify when a given solution achieves the desired sub-optimality with the required confidence, allowing the search to halt and return the incumbent solution. In this paper we propose two novel methods for identifying when a PAC search can halt. Unlike previous work, the new methods provided in this paper become more knowledgeable as the search progresses. This can speedup the search, since the search can halt earlier with the proposed methods and still keeping the desired PAC solution quality guarantees. Experimental results indeed show a substantial speedup of the search in comparison to the previous approach for PAC search.

ICAPS Conference 2011 Conference Paper

Potential Search: A Bounded-Cost Search Algorithm

• Roni Stern
• Rami Puzis
• Ariel Felner

In this paper we address the following search task: find a goal with cost smaller than or equal to a given fixed constant. This task is relevant in scenarios where a fixed budget is available to execute a plan and we would like to find such a plan with minimum search effort. We introduce an algorithm called Potential search (PTS) which is specifically designed to solve this problem. PTS is a best-first search that expands nodes according to the probability that they will be part of a plan whose cost is less than or equal to the given budget. We show that it is possible to implement PTS even without explicitly calculating these probabilities, when a heuristic function and knowledge about the error of this heuristic function are given. In addition, we also show that PTS can be modified to an anytime search algorithm. Experimental results show that PTS outperforms other relevant algorithms in most cases, and is more robust.

SoCS Conference 2011 Conference Paper

Predicting Solution Cost with Conditional Probabilities

• Levi H. S. Lelis
• Roni Stern
• Shahab Jabbari Arfaee

Classical heuristic search algorithms find the solution cost of a problem while finding the path from the start state to a goal state. However, there are applications in which finding the path is not needed. In this paper we propose an algorithm that accurately and efficiently predicts the solution cost of a problem without finding the actual solution. We show empirically that our predictor makes more accurate predictions when compared to the bootstrapped heuristic, which is known to be a very accurate inadmissible heuristic. In addition, we show how our prediction algorithm can be used to enhance heuristic search algorithms. Namely, we use our predictor to calculate a bound for a bounded best-first search algorithm and to tune the w-value of Weighted IDA*. In both cases major search speedups were observed.

SoCS Conference 2011 Conference Paper

Probably Approximately Correct Heuristic Search

• Roni Stern
• Ariel Felner
• Robert C. Holte

A* is a best-first search algorithm that returns an optimal solution. w-admissible algorithms guarantee that the returned solution is no larger than w times the optimal solution. In this paper we introduce a generalization of the w-admissibility concept that we call PAC search, which is inspired by the PAC learning framework in Machine Learning. The task of a PAC search algorithm is to find a solution that is w-admissible with high probability. In this paper we formally define PAC search, and present a framework for PAC search algorithms that can work on top of any search algorithm that produces a sequence of solutions. Experimental results on the 15-puzzle demonstrate that our framework activated on top of Anytime Weighted A* (AWA*) expands significantly less nodes than regular AWA* while returning solutions that have almost the same quality.

SoCS Conference 2011 Conference Paper

Pruning Techniques for the Increasing Cost Tree Search for Optimal Multi-agent Pathfinding

• Guni Sharon
• Roni Stern
• Meir Goldenberg
• Ariel Felner

We address the problem of optimal path finding for multiple agents where agents must not collide and their total travel cost should be minimized. Previous work used traditional single-agent search variants of the A* algorithm. In Sharon et. al. (2011), we introduced a novel two-level search algorithm framework for this problem. The high-level searches a novel search tree called increasing cost tree (ICT). The low-level performs a goal test on each ICT node. The new framework, called ICT search (ICTS), showed to run faster than the previous state-of-the-art A* approach by up to three orders of magnitude in many cases. In this paper we focus on the low-level of ICTS which performs the goal test. We introduce a number of optional pruning techniques that can significantly speed up the goal test. We discuss these pruning techniques and provide supporting experimental results.

IJCAI Conference 2011 Conference Paper

The Increasing Cost Tree Search for Optimal Multi-Agent Pathfinding

• Guni Sharon
• Roni Stern
• Meir Goldenberg
• Ariel Felner

We address the problem of optimal path finding for multiple agents where agents must not collide and their total travel cost should be minimized. Previous work used traditional single-agent search variants of the A* algorithm. We present a novel formalization for this problem which includes a search tree called the increasing cost tree (ICT) and a corresponding search algorithm that finds optimal solutions. We analyze this new formalization and compare it to the previous state-of-the-art A*-based approach. Experimental results on various domains show the benefits and drawbacks of this approach. A speedup of up to 3 orders of magnitude was obtained in a number of cases.

SoCS Conference 2010 Conference Paper

Potential Search: A New Greedy Anytime Heuristic Search

• Roni Stern
• Rami Puzis
• Ariel Felner

In this paper we explore a novel approach for anytime heuristic search, in which the node that is most probable to improve the incumbent solution is expanded first. This is especially suited for the "anytime aspect" of anytime algorithms - the possibility that the algorithm will be be halted anytime throughout the search. The potential of a node to improve the incumbent solution is estimated by a custom cost function, resulting in Potential Search, an anytime best-first search. Experimental results on the 15-puzzle and on the key player problem in communication networks (KPP-COM) show that this approach is competitive with state-of-the-art anytime heuristic search algorithms, and is more robust.

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.

AAAI Conference 2010 Conference Paper

Using Lookaheads with Optimal Best-First Search

• Roni Stern
• Tamar Kulberis
• Ariel Felner
• Robert Holte

We present an algorithm that exploits the complimentary benefits of best-first search (BFS) and depth-first search (DFS) by performing limited DFS lookaheads from the frontier of BFS. We show that this continuum requires significantly less memory than BFS. In addition, a time speedup is also achieved when choosing the lookahead depth correctly. We demonstrate this idea for breadth-first search and for A*. Additionally, we show that when using inconsistent heuristics, Bidirectional Pathmax (BPMX), can be implemented very easily on top of the lookahead phase. Experimental results on several domains demonstrate the benefits of all our ideas.

JAAMAS Journal 2007 Journal Article

Searching for close alternative plans

• Ariel Felner
• Roni Stern
• Alex Pomeransky

JAAMAS Journal 2006 Journal Article

Searching for close alternative plans

• Ariel Felner
• Roni Stern
• Alex Pomeransky

Abstract Consider the situation where an intelligent agent accepts as input a complete plan, i. e. , a sequence of states (or operators) that should be followed in order to achieve a goal. For some reason, the given plan cannot be implemented by the agent, who then goes about trying to find an alternative plan that is as close as possible to the original. To achieve this, a search algorithm that will find similar alternative plans is required, as well as some sort of comparison function that will determine which alternative plan is closest to the original. In this paper, we define a number of distance metrics between plans, and characterize these functions and their respective attributes and advantages. We then develop a general algorithm based on best-first search that helps an agent efficiently find the most suitable alternative plan. We also propose a number of heuristics for the cost function of this best-first search algorithm. To explore the generality of our idea, we provide three different problem domains where our approach is applicable: physical roadmap path finding, the blocks world, and task scheduling. Experimental results on these various domains support the efficiency of our algorithm for finding close alternative plans.

AAMAS Conference 2002 Conference Paper

Finding Optimal Path in Unknown Physical Environments

• Ariel Felner
• Roni Stern
• Sarit Kraus