"Extending Heuristic Search" Speaker: Roni Stern, Ben-Gurion University Date: Wednesday, 12 January 2011 Time: 12noon Place: Ross 201 Abstract: In the first part of my talk I will 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. This continuum requires significantly less memory than BFS, and a time speedup is also achieved when choosing the lookahead depth correctly. This idea is demonstrated for breadth-first search and for A*, and can be efficiently integrated with Bidirectional Pathmax (BPMX) when using inconsistent heuristics. This is a joint work with Tamar Kulberis, Ariel Felner and Robert Holte. In the second part of my talk I will address a novel yet very realistic search task: finding a path to a goal state with cost lower than a given constant. This corresponds to scenarios in which there is a given budget to execute a plan, and we would like to find that plan with minimum search effort. For this problem, which we call the bounded-cost search problem, we developed a novel algorithm: Potential search, which is a best-first search that expands nodes according to the probability that they will be part of a plan of cost no more than the given budget. Fortunately, it is possible to implement Potential search even without explicitly calculating these probabilities, given a heuristic function and knowledge about the error of this heuristic function. Finally, we also show that Potential search can be used to construct an efficient anytime search algorithm, that is competitive with the state-of-the-art. This is a joint work with Rami Puzis and Ariel Felner. Time permitting, I will also present how concepts from the probably approximately correct (PAC) learning theory can be applied in heuristic search.