Author name cluster

Shahaf Shperberg

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers

1 author row

AIJ Journal 2026 Journal Article

Is DIBBS a DXBB algorithm?

Nathan R. Sturtevant
Shahaf Shperberg
Ariel Felner

The recently-introduced Dynamically Improved Bounds Bidirectional Search (DIBBS) algorithm attributes its success to the fact that it is not a deterministic expansion-based black box algorithm (DXBB). After communication with the authors, there is agreement that this characterization is incorrect. The goal of this research note is to provide correction in the literature regarding the claims around DIBBS, to make it clearer why DIBBS is a DXBB algorithm, and to explain why its performance is bounded by bidirectional search theory.

Details DOI

IJCAI Conference 2025 Conference Paper

Concurrent Planning and Execution Using Dispatch-Dependent Values

Andrew Coles
Erez Karpas
Eyal Shimony
Shahaf Shperberg
Wheeler Ruml

Agents operating in the real world must cope with the fact that time passes while they plan. In some cases, such as under tight deadlines, the only way for such an agent to achieve its goal is to execute an action before a complete plan has been found. This problem is called Concurrent Planning and Execution (CoPE). Previous work on CoPE relied on a value function that assumes search will finish before actions are executed, causing the agent to be overly pessimistic in many situations. In this paper, we define a new value function that takes into account the agent's ability to dispatch actions incrementally. This allows us to devise a much simpler algorithm for concurrent planning and execution. An experimental evaluation on problems with time pressure shows that the new method significantly outperforms the previous state-of-the-art.

PDF Details DOI

IJCAI Conference 2024 Conference Paper

Theoretical Study on Multi-objective Heuristic Search

Shawn Skyler
Shahaf Shperberg
Dor Atzmon
Ariel Felner
Oren Salzman
Shao-Hung Chan
Han Zhang
Sven Koenig

This paper provides a theoretical study on Multi-Objective Heuristic Search. We first classify states in the state space into must-expand, maybe-expand, and never-expand states and then transfer these definitions to nodes in the search tree. We then formalize a framework that generalizes A* to Multi-Objective Search. We study different ways to order nodes under this framework and their relation to traditional tie-breaking policies and provide theoretical findings. Finally, we study and empirically compare different ordering functions.

PDF Details DOI

AIJ Journal 2023 Journal Article

Conflict-tolerant and conflict-free multi-agent meeting

Dor Atzmon
Ariel Felner
Jiaoyang Li
Shahaf Shperberg
Nathan Sturtevant
Sven Koenig

In the Multi-Agent Meeting problem (MAM), the task is to find the optimal meeting location for multiple agents, as well as a path for each agent to that location. Among all possible meeting locations, the optimal meeting location has the minimum cost according to a given cost function. Two cost functions are considered in this research: (1) the sum of all agents paths' costs to the meeting location (SOC) and (2) the cost of the longest path among them (MKSP). MAM has many real-life applications, such as choosing a gathering point for multiple traveling agents (humans, cars, or robots). In this paper, we divide MAM into two variants. In its basic version, MAM allows multiple agents to occupy the same location, i. e. , it is conflict tolerant. For MAM, we introduce MM*, a Multi-Directional Heuristic Search algorithm, that finds the optimal meeting location under different cost functions. MM* generalizes the Meet in the Middle (MM) bidirectional search algorithm to the case of finding an optimal meeting location for multiple agents. Several admissible heuristics are proposed for MM*, and experiments demonstrate the benefits of MM*. As agents may be embodied in the world, a solution to MAM may contain conflicting paths, where more than one agent occupies the same location at the same time. The second variant of the MAM problem is called Conflict-Free Multi-Agent Meeting (CF-MAM), where the task is to find the optimal meeting location for multiple agents (as in MAM) as well as conflict-free paths (in the same manner as the prominent Multi-Agent Path Finding problem (MAPF)) to that location. For optimally solving CF-MAM, we introduce two novel algorithms, which combine MAM and MAPF solvers. We prove the optimality of both algorithms and compare them experimentally, showing the pros and cons of each algorithm. 1

Details DOI

IJCAI Conference 2023 Conference Paper

Front-to-End Bidirectional Heuristic Search with Consistent Heuristics: Enumerating and Evaluating Algorithms and Bounds

Lior Siag
Shahaf Shperberg
Ariel Felner
Nathan Sturtevant

Recent research on bidirectional heuristic search (BiHS) is based on the must-expand pairs theory (MEP theory), which describes which pairs of nodes must be expanded during the search to guarantee the optimality of solutions. A separate line of research in BiHS has proposed algorithms that use lower bounds that are derived from consistent heuristics during search. This paper links these two directions, providing a comprehensive unifying view and showing that both existing and novel algorithms can be derived from the MEP theory. An extended set of bounds is formulated, encompassing both previously discovered bounds and new ones. Finally, the bounds are empirically evaluated by their contribution to the efficiency of the search

PDF Details DOI

IJCAI Conference 2020 Conference Paper

Bidirectional Heuristic Search: Expanding Nodes by a Lower Bound

Shahaf Shperberg
Ariel Felner
Nathan Sturtevant
Eyal Shimony
Avi Hayoun

Recent work on bidirectional search defined a lower bound on costs of paths between pairs of nodes, and introduced a new algorithm, NBS, which is based on this bound. Building on these results, we introduce DVCBS, a new algorithm that aims to to further reduce the number of expansions. Generalizing beyond specific algorithms, we then propose a method for enhancing heuristics by propagating such lower bounds (lb-propagation) between frontiers. This lb-propagation can be used in existing algorithms, often improving their performance, as well as making them "well behaved".

PDF Details DOI

IJCAI Conference 2020 Conference Paper

Multi-Directional Heuristic Search

Dor Atzmon
Jiaoyang Li
Ariel Felner
Eliran Nachmani
Shahaf Shperberg
Nathan Sturtevant
Sven Koenig

In the Multi-Agent Meeting problem (MAM), the task is to find a meeting location for multiple agents, as well as a path for each agent to that location. In this paper, we introduce MM*, a Multi-Directional Heuristic Search algorithm that finds the optimal meeting location under different cost functions. MM* generalizes the Meet in the Middle (MM) bidirectional search algorithm to the case of finding an optimal meeting location for multiple agents. Several admissible heuristics are proposed, and experiments demonstrate the benefits of MM*.

PDF Details DOI

IJCAI Conference 2020 Conference Paper

Trading Plan Cost for Timeliness in Situated Temporal Planning

Shahaf Shperberg
Andrew Coles
Erez Karpas
Eyal Shimony
Wheeler Ruml

If a planning agent is considering taking a bus, for example, the time that passes during its planning can affect the feasibility of its plans, as the bus may depart before the agent has found a complete plan. Previous work on this situated temporal planning setting proposed an abstract deliberation scheduling scheme for maximizing the probability of finding a plan that is still feasible at the time it is found. In this paper, we extend the deliberation scheduling approach to address problems in which plans can differ in their cost. Like the planning deadlines, these costs can be uncertain until a complete plan has been found. We show that finding a deliberation policy that minimizes expected cost is PSPACE-hard and that even for known costs and deadlines the optimal solution is a contingent, rather than sequential, schedule. We then analyze special cases of the problem and use these results to propose a greedy scheme that considers both the uncertain deadlines and costs. Our empirical evaluation shows that the greedy scheme performs well in practice on a variety of problems, including some generated from planner search trees.

PDF Details DOI