SoCS 2020
Invited Speakers

Colocated Conference

Past SoCS Conferences
2019 Napa, CA
2018 Stockholm, Sweden
2017 Pittsburgh, PA
2016 Tarrytown, NY
2015 Ein Gedi, Israel
2014 Prague, Czechia
2013 Leavenworth, WA
2012 Niagara Falls, Canada
2011 Barcelona, Spain
2010 Atlanta, GA
2009 Lake Arrowhead, CA
2008 Chicago, IL

SoCS 2020: The 13th Annual Symposium on Combinatorial Search

Invited Speakers

We are pleased to have the following invited speakers at SoCS 2020:

Rina Dechter

University of California at Irvine

Talk Title: Probabilistic Reasoning Meets Heuristic Search


Graphical models, including constraint networks, Bayesian networks, Markov random fields and influence diagrams, have become a central paradigm for knowledge representation and reasoning in Artificial Intelligence, and provide powerful tools for solving problems in a variety of application domains, including coding and information theory, signal and image processing, data mining, learning, computational biology, and computer vision. Although past decades have seen considerable progress in algorithms in graphical models, many real-world problems are of such size and complexity that they remain out of reach. Advances in exact and approximate inference methods are thus crucial to address these important problems with potential impact across many computational disciplines. Exact inference is typically NP-hard, motivating the development of approximate and anytime techniques.

After summarizing the main principles behind the AND/OR search guided by heuristics based on variational inference (e.g., weighted mini-bucket and cost-shifting schemes) for solving graphical models queries, I will focus on recent work for solving the marginal map task, a query that combines, and generalizes optimization and summations queries and is far harder than both. These type of queries appear in sequential decision making and in particular in planning under uncertainty. The emerging solvers aim for anytime behavior that generates not only an approximation that improves with time, but also upper and lower bounds, which become tighter with more time.

About the Speaker:

Rina Dechter's research centers on computational aspects of automated reasoning and knowledge representation including search, constraint processing, and probabilistic reasoning. She is a Chancellor's Professor of Computer Science at University of California, Irvine. She holds a Ph.D. from UCLA, an M.S. degree in applied mathematics from the Weizmann Institute, and a B.S. in mathematics and statistics from the Hebrew University in Jerusalem. She is the author of Constraint Processing published by Morgan Kaufmann (2003), and of Reasoning with Probabilistic and Deterministic Graphical Models: Exact Algorithms published by Morgan and Claypool Publishers (2013, second ed. 2019).
She has co-authored close to 200 research papers and has served on the editorial boards of: Artificial Intelligence, the Constraint Journal, Journal of Artificial Intelligence Research (JAIR), and Journal of Machine Learning Research (JMLR). She is a Fellow of the American Association of Artificial Intelligence since 1994, was a Radcliffe Fellow during 2005-2006, received the 2007 Association of Constraint Programming (ACP) Research Excellence Award, and became an ACM Fellow in 2013. She served as a Co-Editor-in-Chief of Artificial Intelligence from 2011 to 2018 and is the conference chair-elect of IJCAI-2022.

Peter Stuckey

Monash University
Joint SoCS/CPAIOR talk

Talk Title: Combinatorial Optimisation for Multi-Agent Path Finding


Multi-Agent Path Finding (MAPF) is a problem that requires one to compute a set of collision-free paths for a team of moving agents. The problem appears in variety of practical applications including warehouse logistics, traffic management, aircraft towing and computer games. The general version of the problem (minimizing makespan or sum of path costs, on graphs with parallel actions and rotations) is known to be NP-hard. One of the leading methods for solving MAPF optimally, employs a strategy known as Conflict-based Search (CBS). The central idea is to plan paths for each agent independently and resolve collisions by branching the current plan. Each branch is a new candidate plan wherein one agent or the other is forced to find a new path that avoids the selected collision. When we examine CBS from an optimisation perspective, it is clearly a form of (Logic-based) Benders Decomposition. This begs the question: can we use combinatorial optimisation techniques to tackle the MAPF problem efficiently? In this talk I will show two approaches: the first uses core-guided search together with a nogood learning Constraint Programming solver; the second uses Branch-and-Cut-and-Price together with a MIP solver. Both methods prove to be highly competitive to previous CBS approaches.

About the Speaker:

Peter J. Stuckey is a Professor in Faculty of Information Technology at Monash University and Fellow of the Association for the Advancement of Artificial Intelligence. He is a pioneer in the field of constraint programming: He is an author of CLP(R), one of the first three constraint programming systems ever devised; he helped define the theoretical underpinnings of the field with a paper describing the formal semantics, and co-wrote the first textbook in the field. He has driven the development of MiniZinc the most widely used constraint programming modelling language. And devised the "lazy clause generation" (LCG) approach to discrete optimization which defines the state-of-the-art for very many discrete optimization problems. This work was awarded the Google Australia Eureka Prize for Innovation in Computer Science and the Woodward Medal.

Copyright © 2020 Symposium on Combinatorial Search