Meir Goldenberg

SoCS Conference 2018 Conference Paper

Extended Abstract: The Heuristic Search Research Framework

• Meir Goldenberg

This paper is an extended abstract of the recently published journal article (M. Goldenberg, The Heuristic Search Research Framework. Knowledge-Based Systems 129: 1–3. 2017). The Heuristic Search Research Framework is a software framework for implementing heuristic search algorithms and exploring their properties. The framework uses policy-based design to enable efficient, flexible and well-organized implementations. In addition, the framework provides effective tools for exploring the properties of the implemented algorithms. The extensive online documentation includes a video demo.

SoCS Conference 2017 Conference Paper

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

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

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

SoCS Conference 2017 Conference Paper

Shortest Path for K Goals

• Roni Stern
• Meir Goldenberg
• Ariel Felner

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

SoCS Conference 2013 Conference Paper

Optimal-Generation Variants of EPEA

• Meir Goldenberg
• Ariel Felner
• Nathan R. Sturtevant
• Robert C. Holte
• Jonathan Schaeffer 0001

It is known that A* is optimal with respect to the expanded nodes (Dechter and Pearl 1985) (D&P). The exact meaning of this optimality varies depending on the class of algorithms and instances over which A* is claimed to be optimal. A* does not provide any optimality guarantees with respect to the generated nodes. However, such guarantees may be critical for optimally solving instances of domains with a large branching factor. In this paper, we introduce two new variants of the recently introduced Enhanced Partial Expansion A* algorithm (EPEA*) (Felner et al. 2012). We leverage the results of D&P to show that these variants possess optimality with respect to the generated nodes in much the same sense as A* possesses optimality with respect to the expanded nodes. The results in this paper are theoretical. A study of the practical performance of the new variants is beyond the scope of this paper.

AIJ Journal 2013 Journal Article

The increasing cost tree search for optimal multi-agent pathfinding

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

SoCS Conference 2012 Conference Paper

A* Variants for Optimal Multi-Agent Pathfinding

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

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

SoCS Conference 2012 Conference Paper

Partial-Expansion A* with Selective Node Generation

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

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

AAAI Conference 2012 Conference Paper

Partial-Expansion A* with Selective Node Generation

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

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

SoCS Conference 2011 Conference Paper

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

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

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

AAAI Conference 2011 Conference Paper

The Compressed Differential Heuristic

• Meir Goldenberg
• Nathan Sturtevant
• Ariel Felner
• Jonathan Schaeffer

The differential heuristic (DH) is an effective memory-based heuristic for explicit state spaces. In this paper we aim to improve its performance and memory usage. We introduce a compression method for DHs which stores only a portion of the original uncompressed DH, while preserving enough information to enable efficient search. Compressed DHs (CDH) are flexible and can be tuned to fit any size of memory, even smaller than the size of the state space. Furthermore, CDHs can be built without the need to create and store the entire uncompressed DH. Experimental results across different domains show that, for a given amount of memory, a CDH significantly outperforms an uncompressed DH.

SoCS Conference 2011 Conference Paper

The Compressed Differential Heuristic

• Meir Goldenberg
• Nathan R. Sturtevant
• Ariel Felner
• Jonathan Schaeffer 0001

The differential heuristic (DH) is an effective memory-based heuristic for explicit state spaces. In this paper, we aim to improve its performance and memory usage. We introduce a compression method for DHs which stores only a portion of the original uncompressed DH, while preserving enough information to enable efficient search. Compressed DHs (CDH) can be tuned to fit any size of memory, even smaller than the size of the state space. Experimental results across different domains show that, for a given amount of memory, a CDH significantly outperforms an uncompress

IJCAI Conference 2011 Conference Paper

The Increasing Cost Tree Search for Optimal Multi-Agent Pathfinding

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

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

SoCS Conference 2010 Conference Paper

Portal-Based True-Distance Heuristics for Path Finding

• Meir Goldenberg
• Ariel Felner
• Nathan R. Sturtevant
• Jonathan Schaeffer 0001

True distance memory-based heuristics (TDHs) were recently introduced as a way to obtain admissible heuristics for explicit state spaces. In this paper, we introduce a new TDH, the portal-based heuristic. The domain is partitioned into regions and portals between regions are identified. True distances between all pairs of portals are stored and used to obtain admissible heuristics throughout the search. We introduce an A*-based algorithm that takes advantage of the special properties of the new heuristic. We study the advantages and limitations of the new heuristic. Our experimental results show large performance improvements over previously-reported TDHs for commonly used classes of maps.