Depth-First Memory-Limited Search in AND/OR Search Spaces

Because many problems can be split into subproblems such that either all (AND) or one (OR) of them must be solved, AND/OR search has been a fundamental topic in AI. In addition, developing efficient AND/OR search has recently become more important because of the applications discovered in several domains.
In this talk, I present my attempts to develop depth-first memory-limited AND/OR search algorithms which can operate with restricted memory, while inheriting advantages of best-first search. In particular, I introduce Recursive Best-First AND/OR Search with Overestimation (RBFAOO), which has been applied to the MAP inference task in Graphical Models and optimal domain-independent non-deterministic planning.

Biography

Akihiro Kishimoto is a research staff member at IBM Research, Ireland. For almost 20 years, his research interests have been AI and parallel computing. He has applied AI technologies to games, domain-independent planning and real-world business problems. In addition to receiving several best paper awards from premier international conferences including ICAPS and IJCAI, he was a coauthor of a commercial computer shogi (Japanese chess) program that won the World Computer Shogi Championships four times. He obtained his BSc degree from the University of Tokyo in Japan and his MSc and PhD degrees from the University of Alberta in Canada.