Author name cluster

Eshed Shaham

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.

3 papers

2 author rows

IJCAI Conference 2019 Conference Paper

Optimally Efficient Bidirectional Search

Eshed Shaham
Ariel Felner
Nathan R. Sturtevant
Jeffrey S. Rosenschein

A* is optimally efficient with regard to node expansions among unidirectional admissible algorithms — those that only assume that the heuristic used is admissible. This paper studies algorithms that are optimally efficient for bidirectional search algorithms. We present the Fractional MM algorithm and its sibling, the MT algorithm, which is simpler to analyze. We then develop variants of these algorithms that are optimally efficient, each under different assumptions on the information available to the algorithm.

PDF Details

SoCS Conference 2018 Conference Paper

Minimizing Node Expansions in Bidirectional Search with Consistent Heuristics

Eshed Shaham
Ariel Felner
Nathan R. Sturtevant
Jeffrey S. Rosenschein

A* is optimally effective with regard to node expansions among unidirectional admissible algorithms—those that only assume that the heuristic used is admissible. Among bidirectional algorithms the Fractional MM algorithm is optimally effective (given the correct parameters) among admissible algorithms. This paper generalizes the bidirectional result to more complex settings where more information on the problem domain can be exploited: (1) When the cost of the minimal edge is known. (2) When the algorithm knows that the heuristics are consistent. This characterization uses a novel algorithm called MT. MT is similar to Fractional MM and is also optimally effective, but simpler to analyze.

Details

SoCS Conference 2017 Conference Paper

The Minimal Set of States that Must Be Expanded in a Front-to-End Bidirectional Search

Eshed Shaham
Ariel Felner
Jingwei Chen
Nathan R. Sturtevant

A* is optimal among admissible unidirectional algorithms when searching with a consistent heuristic. Recently, similar optimality bounds have been established for bidirectional search, but no practical algorithm is guaranteed to always achieve this bound. In this paper we study the nature of the number of nodes that must be expanded in any front-to-end bidirectional search. We present an efficient algorithm for computing that number and show that a theoretical parameterized generalization of MM, with the correct parameter, is the optimal front-to-end bidirectional search. We then experimentally compare various algorithms and show how far they are from optimal.

Details