Invited Speakers
We are pleased to have the following invited speakers at SoCS 2020:
|
Rina DechterUniversity of California at IrvineTalk Title: Probabilistic Reasoning Meets Heuristic Search Abstract: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). |
Peter StuckeyMonash UniversityJoint SoCS/CPAIOR talk Talk Title: Combinatorial Optimisation for Multi-Agent Path Finding Abstract: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. |
|