Arrow Research search

Author name cluster

Hermann Kaindl

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.

13 papers
2 author rows

Possible papers

13

IJCAI Conference 1999 Conference Paper

Switching from Bidirectional to Unidirectional Search

  • Hermann Kaindl
  • Gerhard Kainz
  • Roland Steiner
  • Andreas Auer
  • Klaus Radda

Recently, we showed that for traditional bidirectional search with "front-to-end" evaluations, it is not the meeting of search fronts but the cost of proving the optimality of a solution that is problematic. Using our improved understanding of the problem, we developed a new approach to improving this kind of search: switching to unidirectional search after the search frontiers meet for the first time (with the first solution found). This new approach shows improvements over previous bidirectional search approaches and (partly) also over the corresponding unidirectional search approaches in different domains. Together with a special-purpose improvement for the TSP, this approach showed better results than the standard search algorithms using the same knowledge.

PDF

AIJ Journal 1998 Journal Article

Benefits of using multivalued functions for minimaxing

  • Anton Scheucher
  • Hermann Kaindl

Minimaxing has been very successful in game-playing practice, although a complete explanation of why it has been that successful has not yet been given. In particular, it has not been shown why it should be useful—as it is in practice—to use multivalued evaluation functions. Such functions have many distinct values as their result and can discriminate between positions according to the heuristic knowledge represented in these values. In this paper, we modify a basic pathological model by adding two assumptions regarding multivalued evaluation functions. These assumptions, non-uniformity of error distribution and dependency of heuristic values, directly relate to the properties of multivalued evaluation functions as used in practice. Simulation studies of our multivalued model have exhibited sharp error reductions for deeper searches using minimaxing. This behavior corresponds to observations in practice. The error reductions are primarily due to the improved evaluation quality as search depth increases. This phenomenon of lower probability of static evaluation errors with increasing search depth is revealed through our model, although the same evaluation function is used at all levels of the tree, and although its general error probability is independent of the depth. Essentially, with increasing search depth, the evaluation function is more frequently used on such positions which can be more reliably evaluated by a multivalued function with the assumed properties. This effect together with the ability to discriminate between positions of different “goodness” leads to the benefits of using multivalued evaluation functions (of appropriate granularity) for minimaxing.

Details DOI

AAAI Conference 1994 Conference Paper

Memory-Bounded Bidirectional Search

  • Hermann Kaindl

Previous approaches to bidirectional search require exponential space, and they are either less efficient than unidirectional search for finding optimal solutions, or they cannot even find such solutions for difficult problems. Based on a memory-bounded unidirectional algorithm for trees (SMA*), we developed a graph search extension, and we used it to construct a very efficient memory-bounded bidirectional algorithm. This bidirectional algorithm can be run for difficult problems with bounded memory. In addition, it is much more efficient than the corresponding unidirectional search algorithm also for finding optimal solutions to difficult problems. In summary, bidirectional search appears to be the best approach to solving difficult problems, and this indicates the extreme usefulness of a paradigm that was neglected for long. Notation s, t l-1 (4 ra (4 d d’ d(n) hf (4 il$f h44 F$) c* c L min TREES TREES OPEN; CLOSED~ PC(4 Start node and goal node, respectively. Successors of node n in the problem graph. Parents of node n in the problem graph. Current search direction index; when search is in the forward direction d = 1, and when in the backward direction d = 2. 3 - d; it is the index of the direction opposite to the current search direction. Cost of an optimal path from s to n if i = 1, or from t to n if i = 2. Cost of an optimal path from n to t if i = 1, or from n to s if i = 2. Estimates of g: (n) and hf (n), respectively. Static evaluation function. Revised evaluation after pathmax or backup. Cost of an optimal path from s to t. Cost of a solution path from s to t found. Cost of the best (least costly) complete path found so far from s to t. The forward search tree. The backward search tree. The set of open nodes in TREES. The set of closed nodes in TREE; . Parent of node n in TREES.

PDF Details
v2026.09.13