SoCS 2020: The 13th Annual Symposium on Combinatorial Search

Master Class

The SoCS Master Class is a one-day event to disseminate cutting-edge research of combinatorial search and optimisation in the broader field of AI and applications.

We are pleased to have the following speakers for the Master Class:

Roman Bartak

Charles University

Master Class Title: Compilation-based approaches to planning and scheduling

Planning and scheduling are closely related areas with one significant difference - in planning we do not know the actions in the final plan. The tutorial describes how to solve planning and scheduling problems by compilation to another formalism, such as CSP, MIP, or SAT. We specifically highlight the similarities and differences among the models. While scheduling models are based strongly on global resource constraints, the planning models require some form of layered approach with iterative construction of models. Optional activities, that attempt to bridge both areas, will also be mentioned.

Marco Maratea

University of Genova, DIBRIS

Master Class Title: Answer Set Programming: Modeling, Solving and Applications

Answer Set Programming (ASP) is a powerful logic programming formalism that extends the database language Datalog with, e.g. unrestricted usage of negation in the body of rules, disjunction in the head of rules, aggregate atoms, hard and weak constraints, and optimization statements. Computational problems, even of high complexity, can be solved in ASP in a declarative way, by first specifying a logic program as a set of rules, such that its solutions (answer sets) correspond to the solutions of the problem, and then using an answer set solver to find such solutions.
In this Master Class I will overview the ASP-Core2 language, in which problems can be specified, the ASP programming methodology, and the ideas behind the algorithms implemented in the main ASP solvers. I will then outline some ASP applications, with focus on those in real-world scenarios.

Abdallah Saffidine

University of New South Wales

Master Class Title: Solving algorithms for two-player games from the ground up

From Connect Four to Chess, via Checkers and Backgammon, two-player games have long been used as benchmark and target domains for adversarial search algorithms. While solving a two-player game shares some characteristics with solving a single-agent puzzle such as Rubik's Cube, this task comes with new challenges of its own. In the first half of this talk, I will examine three of the main foundational approaches to this task, namely Alpha-Beta, Monte Carlo Tree Search, and Proof Number Search. Casting these paradigms in a unified algorithmic framework shed lights on their similarities and differences. In the second half of the talk, I will focus on a few elegant selected heuristic improvements that have seen some success in practice.

Roni Stern

Ben Gurion University

Master Class Title: Domain-dependent and domain-independent suboptimal heuristic search

Heuristic search is a general problem-solving method. The theory for using heuristic search to find optimal solutions is well-understood, with fundamental algorithms such as A* and IDA* and theory about their effectiveness. However, many real-world problems are just too difficult to be solved optimality. In this talk I will cover a range of heuristic search algorithms that trade-off optimality for runtime in different ways. This includes suboptimal algorithms such as Greedy Best-First Search; bounded-suboptimal search algorithms such as Weighted A*, A*epsilon, Explicit Estimation Search, and Dynamic Potential Search; anytime search algorithms such as Anytime Weighted A* and Anytime Repairing A*; and bounded-cost search algorithms. Finally, I will show several examples where domain-dependent information, beyond the heuristic function, can be used to create better suboptimal search algorithms.

Nathan Sturtevant

University of Alberta

Master Class Title: Heuristic Search: You have hear it said, but I tell you...

You may have heard that A* and IDA* are optimal effective. But, the effectiveness of these algorithms is highly dependent on the assumptions made when analyzing them. In this talk we will present foundational algorithms 35-50 years old in the field of heuristic search and the assumptions made with their analysis. Then, we will show how these assumptions may not be valid for current and future work in the field. Given this, we will also present new algorithms that have been developed to broaden the applicability of these approaches. In particular, we will look at A* vs bidirectional search, A* vs inconsistent heuristics, IDA* vs non-unit edge costs, and Weighted A* vs node re-openings.