Call for Abstracts & Participation: International Workshop on Pattern Databases and Large-Scale Search

[Stefan Edelkamp]

----------------------------------------------------------------

CALL FOR ABSTRACTS AND PARTICIPATION

----------------------------------------------------------------

First International Workshop on Pattern Databases and Large-Scale Search

Berlin, 4th-5th of October, 2018

-------------------------------

Invited Speaker

Ariel Felner, Professor at Faculty of Engineering Sciences, Ben-Gurion University, Israel

--

Location

Freie Universität Berlin
Zuse Institut Berlin
Takustr. 7, Room 2006
14195 Berlin

News

Pattern Databases and Large-Scale Symbolic Search dominated the International
Planning Competition 2018. Within the Top 6 planners, we find 5 systems using

these technologies. The only exception and winner of the competition (by a small

margin of 2 of 200 solved planning tasks) is a portfolio. In several domains,

it applied the above techniques, and when it performed overall best, it ran the

symbolic search winner of the last competition.   

Chairs

Stefan Edelkamp, Professor in AI Planning, King's College London (KCL)

Knut Reinert, Professor in Computational Biology, Freie Universität Berlin (FUB), Team Leader in Max-Planck-Institute for Molecular Genetics.

Alexander Reinefeld, Scientific Director in Parallel and Distributed Computing, Zuse Institut Berlin (ZIB), Professor at Humboldt University Berlin.

--

Synopsis

Large-scale search engineers state space graph exploration algorithms to exploit computational power. It includes aspects such as many-core CPUs and GPUs as well as larger amounts of main memory and disk space. There is the duality of latency and locality of the search and one might say that disk is the new RAM and RAM is the new disk. Pattern databases are lower bound estimate tables that are used as guidance for the overall search. They are generated in a complete traversal of abstract state spaces. They tend to be larger, 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. Traditional computers have typically three levels of caches and the main memory. The main memory is usually large and slow. The three levels of caches decrease in performance and increase in size with the distance to the processor. In the near future, this hierarchy is going to be deeper and more complicated. Future servers can have much more memory than current systems. At the same time, the memory hierarchy will be more complicated. More memory can be used for larger pattern databases and larger search frontiers. The efficient placement of the different data structures onto the different memory types will be challenging. On the API side, standardisation just begins. Lifting the combination of known algorithms like A, IDA* and MapReduce to table-oriented pattern database search on HPC and multi-core CPU systems is also needed in the applications. In Bio-Informatics, according to Gusfield the optimal multiple sequence alignment problem 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* and IDA* 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.

Link of the Organizers to the Topic

In the area of optimal action planning the state-of-the-art tools apply pattern databases together with a meta search on top to establish an optimal selection of them. In his influential paper, Stefan Edelkamp has introduced pattern databases for AI planning, and they still dominate the international planning competitions. For large-scale search data structures like binary decision diagrams are used for a better time-space trade-off. He also published results on memory-limited, external-memory, and randomized algorithms for the multiple sequence alignment problem. In the area of combinatorial search all goes back to solving the sliding puzzle. The 8 and the 15-puzzle are completely solved. However, the 24-puzzle is not solved yet and it is highly unlikely that it will be completely solved in the near future. Korf showed how to solve 50 random instances. However, it turned out that his instances are not particularly difficult to solve. This is attributed to the Gaussian distribution with a majority of instances having a medium-length solution path and only few of them requiring far more moves to be solved (long tail). Alexander Reinefeld used large additive pattern databases and created one instance for which he could show only a lower bound of 140 and an upper bound of 142 for the length of the shortest path. For comparison, the longest shortest path in Korf's random set is only 113. Magnitude more nodes had to be expanded to find only the bounds on the shortest path than to solve Korf's hardest instance. For the area of bio-informatics, in his early career Knut Reinert has published on variants of the A* algorithms to solve the multiple sequence alignment and related problems. One problem with optimal sequencing is that the (possible affine) cost function provided in form of similarity matrices is rooted in experiments. Nowadays, in his group(s) sequencing is still is a major concern, but the interest has shifted from solving sequence alignment problems optimally to analysing larger amounts of biomedical data, mostly for next generation from sequencing data. 

If you want to participate in this event you can send the title and an abstract of your talk to

one the organizers for a light-weight review. The workshop is funded by Freie Universitaet

Berlin and King's College London. See you there.

--

Professor Stefan Edelkamp

Department of Informatics
King's College London
Strand Campus, Bush House
30 Aldwych, London WC2B 4BG