Location
Freie Universität Berlin and Zuse Institute Berlin
Takustr. 7
14195 Berlin
Lecture Hall (R 2005) and Seminar Room (R 2006), ground floor, round part of ZIB building
Hints for visitors
Invited Speaker
Ariel Felner, Professor at the Faculty of Engineering Sciences, Ben-Gurion University, Israel
Synopsis
Large-scale search is at the core of Artificial Intelligence and it provides the foundations for many different
approaches in problem-solving. It builds and explores large state space graphs which typically exceed the main memory
of standard computers. Thus novel approaches for the efficient organization of state space graphs are sought.
Pattern databases are lower bound estimate tables that are used as guidance for the search process. They are generated in a complete traversal of abstract state spaces. They tend to be large, and there are different options for their combination. Such form of abstraction is used in the algorithm community for shortest path search, in the model checking community to validate soft- and hardware, and in Artificial Intelligence to explore large state spaces.
System architecture of cluster- and high-performance computers is getting more complex due to the many cores per processor, highly parallel execution units (SIMD), and deeper cache- and memory hierarchies. The increased memory capacity of new memory technology makes it possible to hold larger pattern databases and larger search frontiers. However, their optimal placement in the memory hierarchy is an increasingly challenging task in the design of efficient search algorithms.
Lifting the combination of common algorithms like A*, IDA*, and their parallel variants to table-oriented pattern database search on high-performance computers is necessary for problem-solving in various applications. In bio-informatics, for example, according to Gusfield the optimal multiple sequence alignment stands out as the "holy grail". Dynamic programming is known to suffer from large state spaces (exponentially growing in the number of sequences) and the according memory consumption, so that refined lower bounds and A* algorithms like iterative-deepening dynamic programming have been used. Quite often the heuristics that are applied to the multiple sequence alignment problem are generated by fully exploring problems of less sequences, which in table form is a pattern database.
News
Pattern databases and large-scale symbolic search dominated the International Planning Competition 2018. Within
the Top 6 planning systems, we find 5 systems, all based on these technologies. The only exception - and winner
of the competition by a margin of 2 of 200 planning tasks - is a portfolio. In several domains, it applied the
above techniques, and where it performed best, it ran the symbolic search winner of the last competition.
Organizers
- Stefan Edelkamp, Professor in AI Planning, King's College London (KCL)
- Alexander Reinefeld, Professor at Humboldt Universität zu Berlin, Scientific Director in Parallel and Distributed Computing, Zuse Institute Berlin
- Knut Reinert, Professor in Computational Biology, Freie Universität Berlin, Team Leader in Max-Planck-Institute for Molecular Genetics
Funded by
Joint Research Workshops Program of King's College London and Freie Universität Berlin, and Zuse Institute Berlin
