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.

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.

Domain-independent planning algorithms require as input an action model that specifies the preconditions and effects of each action. Constructing such models is often challenging for domain experts, particularly in domains where actions involve both Boolean and numeric state variables. We address the problem of learning such hybrid action models from observations of successful action executions. A central challenge is that observing only successful executions provides no explicit evidence about which conditions are necessary for an action to be applicable. This difficulty is especially pronounced for learning numeric preconditions, for which there exist negative theoretical results concerning efficient learnability. To mitigate this limitation, we propose SAM-SVM, a novel numeric action model learning algorithm that learns numeric preconditions by heuristically simulating negative observations, i.e., possible states where actions are inapplicable. We also implemented NSAM+SVM, a hybrid algorithm that integrates SAM-SVM and NSAM, an existing conservative action model learning algorithm. Empirical evaluation demonstrates that SAM-SVM can learn more accurate action models and achieves improved planning performance compared to existing methods on standard numeric planning benchmarks, and NSAM+SVM provides the most robust behavior across most domains.

Background: Multi-Agent Planning (MAP) involves coordinating the actions of multiple autonomous agents to achieve shared objectives. A prevalent formalism for MAP is the Multi-Agent Planning Domain Definition Language (MA-PDDL). While effective, existing MA-PDDL solvers typically require complete access to agents’ action models—specifically their preconditions and effects. However, manually creating these models is often intractable, requiring exhaustive domain expertise. Objectives: This work explores an alternative approach: automatically learning agents’ action models from observed transitions. Since learned models may be inaccurate, planning with them can yield invalid or non-executable sequences. To mitigate this, we formalize a requirement for safety, ensuring that plans generated via the learned model remain sound with respect to the real unknown action model. Methods: Previous research introduced the Safe Action Model Learning (SAM) algorithm for single-agent domains. However, SAM is not suitable for MA-PDDL environments where observations include concurrently executed actions, since it cannot naturally disambiguate the individual contributions of the agents to the observed effects. To address this, we introduce Multi-Agent Safe Action Model Learning (MA-SAM), a safe action model learning algorithm designed to handle concurrent multi-agent observations. For scenarios where individual action effects remain ambiguous, we further propose MA-SAM+ , which learns the preconditions and effects of macro-actions representing concurrent execution of subsets of actions. We evaluate both algorithms on domains from the Competition of Distributed and Multi-Agent Planners (CoDMAP) benchmarks and a novel MAP domain inspired by the game Overcooked. Results: We establish a theoretical lower bound on the sample complexity for learning safe action models in multi-agent settings. We prove that MA-SAM does not achieve this lower bound in all cases, identifying specific conditions under which its sample complexity may become unbounded. Empirically, both MA-SAM and MA-SAM+ significantly outperform SAM-based baselines in coverage and applicability rates. While their performance is comparable in many settings, MA-SAM+ highly outperforms MA-SAM in some of the evaluated domains. Conclusions: We present the first algorithms capable of learning safe MA-PDDL action models from concurrently executed actions, providing both theoretical foundations and empirical validation across diverse planning benchmarks

• Demonstrate the feasibility of software fault diagnosis with partial traces and highlight the advantages of probabilistic reconstruction for fault localization when full execution traces are unavailable. • Propose algorithms, called Rec-Min, Rec-Max, and Rec-Weighted, that build on Spectrum-based Fault Localization (SFL), augmented by a trace reconstruction process that fills the missing parts of the program trace via static code analysis. • Evaluate the algorithms on 109 versions of 10 projects from the Defects4J dataset, showing significant fault localization improvements compared to a baseline approach. • Show that the Rec-Weighted algorithm achieves the best trade-off, reducing wasted effort by 34.4 %. Finding the root cause of observed software bugs, also referred to as software fault diagnosis, is a challenging problem that often must be solved in order to maintain software reliability. Spectrum-Based Fault Localization (SFL) is a powerful technique for automated software fault diagnosis that leverages execution traces. However, having the exact trace of every executed function is not common in real-world software projects, since tracing incurs significant overhead. Instead, many projects maintain log files to track execution, from which only partial execution traces may be extracted. This raises a key challenge: how can we diagnose fault faults (bugs) correctly given only partial execution traces? One way to do so is to run SFL using only the available partial traces. This approach is very limited, as it ignores all components that are not in the partial trace, which may even include the buggy components we are looking for. To overcome this limitation, we propose to use trace reconstruction techniques to synthetically add components to the given partial traces. These techniques analyze possible execution paths, which are extracted via static code analysis. In this work, we consider three trace reconstruction techniques: Rec-Min, Rec-Max, and Rec-Weighted. Rec-Min adds to the partial traces components present in all possible execution paths. Rec-Max adds to the partial trace components that exists in at least one execution path. Rec-Weighted applies a more refined approach. It assigns likelihood scores to the missing components based on the number of execution paths that pass through them. Then, it adapts SFL to intelligently consider these likelihood scores. Empirical evaluation on 109 faulty versions of 10 projects from the Defects4J dataset demonstrates that using our trace reconstruction techniques significantly enhances fault localization compared to the baseline SFL that only uses the partial traces. In some cases, using Rec-Weighted enabled reducing the wasted effort by 34.4 %.

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.

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.

Multi-Agent Path Finding (MAPF) deals with finding conflict-free paths for a set of agents from an initial configuration to a given target configuration. The Lifelong MAPF (LMAPF) problem is a well-studied online version of MAPF in which an agent receives a new target when it reaches its current target. The common approach for solving LMAPF is to treat it as a sequence of MAPF problems, periodically replanning from the agents’ current configurations to their current targets. A significant drawback of this approach is that in MAPF the agents must reach a configuration in which all agents are at their targets simultaneously. Coordinating the agents’ paths such that they occupy their targets at the same time is needlessly restrictive for LMAPF. Techniques have been proposed to indirectly mitigate this drawback. In this position paper, we describe cases where these mitigation techniques fail. As an alternative, we propose to solve LMAPF problems by solving a sequence of modified MAPF problems, in which the objective is for each agent to eventually visit its target, but not necessarily for all agents to do so simultaneously. We refer to this MAPF variant as MAPF for Lifelong (MAPF4L) and propose how to solve it by modifying several existing MAPF algorithms. A limited experimental evaluation identifies some cases where using a MAPF4L algorithm can improve the system throughput significantly.

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.

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.

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.

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. Manually designing such an action model is a notoriously challenging task. An alternative is to automatically learn action models from observation. Such an action model is called safe if every plan created with it is consistent with the real, unknown action model. Algorithms for learning such safe action models exist, yet they cannot handle domains with conditional or universal effects, which are common constructs in many planning problems. We prove that learning non-trivial safe action models with conditional effects may require an exponential number of samples. Then, we identify reasonable assumptions under which such learning is tractable and propose Conditional-SAM, the first algorithm capable of doing so. We analyze Conditional-SAM theoretically and evaluate it experimentally. Our results show that the action models learned by Conditional-SAM can be used to solve perfectly most of the test set problems in most of the experimented domains.

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.

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.

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.

Minecraft is a widely popular video game renowned for its intricate environment. The game's open-ended design allows the creation of unique tasks and challenges for the agents, providing a broad spectrum for researchers to experiment with different AI techniques and applications. Indeed, various Minecraft tasks have been posed as an AI challenge. Most AI research on Minecraft focused on either applying Reinforcement Learning (RL) to solve the problem, learning an action model for planning, or modeling the problem for a domain-independent planner. In this work, we focus on the combinatorial search aspect of solving the Craft Wooden Pogo task within the Polycraft World AI Lab (PAL) Minecraft environment. PAL is an interface to Minecraft that provides an API for AI agents to interact with Minecraft's environment and send commands to the main character. PAL supports symbolic observations of the current state, making it ideal for planning algorithms, which require a symbolic model of the environment for problem-solving. Other Minecraft research frameworks such as MineRL, provide a visual, pixel-based representation of the game.

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.

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.

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.

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.

In multi-agent systems, multi-agent planning and diagnosis are two key subfields – multi-agent planning approaches identify plans for the agents to execute in order to reach their goals, and multi-agent diagnosis approaches identify root causes for faults when they occur, typically by using information from the multi-agent planning model as well as the resulting multi-agent plan. However, when a plan fails during execution, the cause can often be related to some commonsense information that is neither explicitly encoded in the planning nor diagnosis problems. As such existing diagnosis approaches fail to accurately identify the root causes in such situations.

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.

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.

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.

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.

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.

In this work, we address the problem of finding paths for multiple agents while avoiding collisions between them, where agents' actions have stochastic outcomes. The objective is to create a joint policy for all agents that minimize the expected sum of costs of getting all agents to their goals, while guaranteeing that collisions never occur. Unlike previous work on multi-agent pathfinding (MAPF), the stochastic outcomes are not limited to delays, and thus the set of locations each agent may end up at can be very large. Consequently, offline planning is prohibitively expensive since collisions between agents may occur in many locations and time steps, while avoiding them is a hard constraint. Instead, we propose a suboptimal online approach in which each agent follows its individually-optimal policy until it detected potential collisions in the future. Then, the potentially conflicting agents create a joint policy for resolving the potential collision. We evaluated this policy experimentally on existing an MAPF benchmark, modified to include stochasticity. The results show that we are able to find high quality solutions for non-trivial grids with up to 12 agents, significantly surpassing several baseline approaches.

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.

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.

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.

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 2^k-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 multi-agent path finding in continuous-time domains.

Managing inputs that are novel, unknown, or out-of-distribution 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.

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.

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.

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.

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.

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.

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.

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.

In this paper, we present the DeBGUer tool, a web-based tool for prediction and isolation of software bugs. DeBGUer is a partial implementation of the Learn, Diagnose, and Plan (LDP) paradigm, which is a recently introduced paradigm for integrating Artificial Intelligence (AI) in the software bug detection and correction process. In LDP, a diagnosis (DX) algorithm is used to suggest possible explanations – diagnoses – for an observed bug. If needed, a test planning algorithm is subsequently used to suggest further testing. Both diagnosis and test planning algorithms consider a fault prediction model, which associates each software component (e.g., class or method) with the likelihood that it contains a bug. DeBGUer implements the first two components of LDP, bug prediction (Learn) and bug diagnosis (Diagnose). It provides an easy-to-use web interface, and has been successfully tested on 12 projects.

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.

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.

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.

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.

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.

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' actions costs. These assumptions and objectives are sometimes implicitly assumed or described informally. This makes it difficult for establishing appropriate baselines for comparison in research papers, as well as making it difficult for practitioners to find the papers relevant to their concrete application. This paper aims to fill this gap and facilitate future research and practitioners by providing a unifying terminology for describing the common MAPF assumptions and objectives. In addition, we also provide pointers to two MAPF benchmarks. In particular, we introduce a new grid-based benchmark for MAPF, and demonstrate experimentally that it poses a challenge to contemporary MAPF algorithms.

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.

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.

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.

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.

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' degrees. Experimental results show that using the proposed rule yields significant speedup and higher alignment quality compared to the state of the art. In addition, we redefine common NA objective functions in terms of established statistical analysis metrics, opening a wide range of possible objective functions.

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.

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.

The multi-agent pathfinding (MAPF) problem has attracted considerable attention because of its relation to practical applications. In this paper, we present a constraint-based declarative model for MAPF, together with its implementation in Picat, a logic-based programming language. We show experimentally that our Picat-based implementation is highly competitive and sometimes outperforms previous approaches. Importantly, the proposed Picat implementation is very versatile. We demonstrate this by showing how it can be easily adapted to optimize different MAPF objectives, such as minimizing makespan or minimizing the sum of costs, and for a range of MAPF variants. Moreover, a Picat-based model can be automatically compiled to several general-purpose solvers such as SAT solvers and Mixed Integer Programming solvers (MIP). This is particularly important for MAPF because some MAPF variants are solved more efficiently when compiled to SAT while other variants are solved more efficiently when compiled to MIP. We analyze these differences and the impact of different declarative models and encodings on empirical performance.

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.

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.

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.

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.

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.

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.

Software fault prediction algorithms predict which software components is likely to contain faults using machine learning techniques. Software diagnosis algorithm identify the faulty software components that caused a failure using model-based or spectrum based approaches. We show how software fault prediction algorithms can be used to improve software diagnosis. The resulting data-augmented diagnosis algorithm overcomes key problems in software diagnosis algorithms: ranking diagnoses and distinguishing between diagnoses with high probability and low probability. We demonstrate the efficiency of the proposed approach empirically on three open sources domains, showing significant increase in accuracy of diagnosis and efficiency of troubleshooting. These encouraging results suggests broader use of data-driven methods to complement and improve existing model-based methods.

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.

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.

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.

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.

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.

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.

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

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.

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.

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.

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.

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' weights. This paper addresses a different class of path finding problems in which the cost of a path is the product of its weights. We present reductions from different classes of multiplicative path finding problems to suitable classes of additive path finding problems. As a case study, we consider the problem of finding least and most probable paths in a Markov Chain, where path cost corresponds to the probability of traversing it. The importance of this problem is demonstrated in an anomaly detection application for cyberspace security. Three novel anomaly detection metrics for Markov Chains are presented, where computing these metrics require finding least and most probable paths. The underlying Markov Chain is dynamically changing, and so fast methods for computing least and most probable paths are needed. We propose such methods based on the proposed reductions and using heuristic search algorithms.

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.

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-decision-theoretic 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.

We propose a combination of AI techniques to improve softwaretesting. 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 planningalgorithm is used to suggest further tests to identify thecorrect diagnosis. A tester preforms these tests and reportstheir outcome back to the MBD algorithm, which uses thisinformation to prune incorrect diagnoses. This iterative processcontinues until the correct diagnosis is returned. We callthis testing paradigm Test, Diagnose and Plan (TDP). Severaltest planning algorithms are proposed to minimize the numberof TDP iterations, and consequently the number of testsrequired until the correct diagnosis is found. Experimentalresults show the benefits of using an MDP-based planning algorithmsover greedy test planning in three benchmarks.

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.

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.

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.

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.

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's Cube.

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.

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' friend lists (immediate neighborhood) in order to decide which profile will be crawled next. Assuming that leads tend to cluster together, prior work limited the search for new leads only to immediate neighbors of the leads previously found. In this paper we relax this limitation, and extend the scope of the search to a wider neighborhood, including the possibility of crawling to non-leads, i.e., profiles that have no publicly available information about the target. We propose a set of heuristics that guide this search. Experimental results show that with the new setting more leads can be found and leads are found faster. In addition, we perform a cost benefit analysis of the search, weighing the reward of finding leads with the costs of the search.

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's algorithm, weighted A*, and depth-first search. This work demonstrates that MAX problems demand their own heuristic search algorithms, which are worthy objects of study in their own right.

When solving instances of problem domains that feature a large branching factor, A* may generate a large number of nodes whose cost is greater than the cost of the optimal solution. We designate such nodes as surplus. Generating surplus nodes and adding them to the OPEN list may dominate both time and memory of the search. A recently introduced variant of A* called Partial Expansion A* (PEA*) deals with the memory aspect of this problem. When expanding a node n, PEA* generates all of its children and puts into OPEN only the children with f = f (n). n is re-inserted in the OPEN list with the f -cost of the best discarded child. This guarantees that surplus nodes are not inserted into OPEN. In this paper, we present a novel variant of A* called Enhanced Partial Expansion A* (EPEA*) that advances the idea of PEA* to address the time aspect. Given a priori domain- and heuristic- specific knowledge, EPEA* generates only the nodes with f = f(n). Although EPEA* is not always applicable or practical, we study several variants of EPEA*, which make it applicable to a large number of domains and heuristics. In particular, the ideas of EPEA* are applicable to IDA* and to the domains where pattern databases are traditionally used. Experimental studies show significant improvements in run-time and memory performance for several standard benchmark applications. We provide several theoretical studies to facilitate an understanding of the new algorithm.

This paper introduces a novel 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 the application of a SAT compiler which optimizes the encoding to provide more succinct CNF representations than obtained with previous works. 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 and 74XXX benchmarks. Our results open the way to improve the state-of-the-art on a range of similar MBD problems.

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.

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.

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.

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)

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* 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.

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-of-the-art on a range of similar MBD problems.

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.

A model-based diagnosis problem occurs when an observation is inconsistent with the assumption that the diagnosed system is not faulty. The task of a diagnosis engine is to compute diagnoses, which are assumptions on the health of components in the diagnosed system that explain the observation. In this paper, we extend Reiter's well-known theory of diagnosis by exploiting the duality of the relation between conflicts and diagnoses. This duality means that a diagnosis is a hitting set of conflicts, but a conflict is also a hitting set of diagnoses. We use this property to interleave the search for diagnoses and conflicts: a set of conflicts can guide the search for diagnosis, and the computed diagnoses can guide the search for more conflicts. We provide the formal basis for this dual conflict-diagnosis relation, and propose a novel diagnosis algorithm that exploits this duality. Experimental results show that the new algorithm is able to find a minimal cardinality diagnosis faster than the well-known Conflict-Directed A*.

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

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.

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.

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.

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.

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.

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%.

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.

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.

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.

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.

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.

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.

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.

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.

We address the problem of finding the shortest path between two points in an unknown real physical environment, where a traveling agent must move around in the environment to explore unknown territory. We introduce the Physical-A* algorithm (PHA*) for solving this problem. PHA* expands all the mandatory nodes that A* would expand and returns the shortest path between the two points. However, due to the physical nature of the problem, the complexity of the algorithm is measured by the traveling effort of the moving agent and not by the number of generated nodes, as in standard A*. PHA* is presented as a two-level algorithm, such that its high level, A*, chooses the next node to be expanded and its low level directs the agent to that node in order to explore it. We present a number of variations for both the high-level and low-level procedures and evaluate their performance theoretically and experimentally. We show that the travel cost of our best variation is fairly close to the optimal travel cost, assuming that the mandatory nodes of A* are known in advance. We then generalize our algorithm to the multi-agent case, where a number of cooperative agents are designed to solve the problem. Specifically, we provide an experimental implementation for such a system. It should be noted that the problem addressed here is not a navigation problem, but rather a problem of finding the shortest path between two points for future usage.