There are three important notions that have been taking shape in recent planning research. One is the notion of bounded width, a characteristic of many planning domains when goals are atomic, that allows for polynomial search algorithms and extensions, as found in state-of-the-art planners like Dual-BFWS. Second, the notion of serializations; namely, the idea that planning problems can often be solved by solving a sequence of subproblems. And third, the notion of general policies: policies that solve not just one domain instance but a whole collection of them. In this talk, I'll present recent work that ties these notions together. An interesting side-effect of the analysis is a new powerful language for specifying and using problem decompositions in the form of sketches, that provides a convenient alternative to HTNs and decomposition methods based on goal or landmark counters.

This is joint work with Blai Bonet.

Short Bio: Hector Geffner is an ICREA Research Professor at the Universitat Pompeu Fabra (UPF) in Barcelona, Spain, and a Wallenberg Guest Professor at Linköping University. He grew up in Buenos Aires and obtained a PhD in Computer Science at UCLA in 1989 under the supervision of Judea Pearl. He worked then at the IBM T.J. Watson Research Center in NY, USA, and at the Universidad Simon Bolivar, in Caracas. Hector is a Fellow of AAAI and EurAI, and teaches logic, AI, and a course on social and technological change. He is currently doing research on learning representations for planning, as part of an ERC funded project.

Balanced separation is a basic building block in many search algorithms and data structures. In graphs, the balanced separator number is an important parameter that was shown to be useful for upper bounding search space sizes of route planning techniques. In this talk, we discuss related graph parameters and prove that those can be instrumented to lower bound search space sizes. This allows us to develop the first approximation algorithm for the average search space size in customizable contraction hierarchies, one of the most prominent preprocessing-based route planning techniques on road networks. As balanced separator computation in graphs poses an NP-hard problem, we propose theoretical and practical algorithmic ideas to still be able to leverage the concept. Finally, we consider the convex separation paradigm and discuss how it can be transferred from computational geometry to graph algorithms.

Short Bio: Sabine Storandt is a professor for Algorithmics at the University of Konstanz, Germany.

A major drawback of stochastic local search algorithms is the cycling phenomenon, i.e., revisiting some parts of the search area. In this talk, I will present a generic local search strategy namely Configuration Checking (CC) for addressing this issue. The CC strategy has been successfully used in various NP hard combinatorial search problems and pushed the state of the art in many of them, including Boolean Satisfiability, Maximum Clique, Vertex Cover, Set Cover, Dominating Set, among others. I will introduce the idea via some examples in the context of different problems.

Short Bio: Shaowei Cai is currently a professor of computer science in Chinese Academy of Sciences. His interests include heuristic search, combinatorial optimization and Electronic design automation (EDA), and he has published more than 80 papers in top journals and conferences such as Artificial Intelligence, IEEE Trans. on Computers, ACM Trans. on Computational Logic, IJCAI, AAAI, etc. His work has been recognized at several important international competitions, including 10+ gold and silver medals in SAT Competitions and wins 21 out of 44 categories in recent 7 MaxSAT Evaluations, and Second Place Award in EDA Challenge 2021, and won the Best Paper Award of SAT 2021 conference. His algorithms and their implementations have been prominently used in important real-world applications, including projects at MIT, US Federal Communication Commission (FCC), Tencent electronic map, Azure cloud platform at Microsoft, and he serves as program chair of the IJCAI workshop "Heuristic Search in Industries" and SPC for IJCAI and AAAI regularly.

Deep Learning and Tree Search are complementary. It is especially the case for games. An example of this combination is Monte Carlo Tree Search and residual networks used in Alpha Zero and Polygames. Another example is Minimax and value networks used in Descent which won 5 gold medals at the last computer olympiad. We will also describe the AlphaMu search algorithm for the game of Bridge and Monte Carlo Search algorithms for optimization problems.

Short Bio: Tristan Cazenave is professor of Artificial Intelligence at LAMSADE, University Paris-Dauphine, PSL, CNRS. He is the head of the master IASD and holds a PRAIRIE chair. He works on Artificial Intelligence for games and optimization problems, more specifically on Monte Carlo Search and Deep Reinforcement Learning. He is editor-in-chief of the ICGA journal, the journal of the computer games community. He has published more than 200 scientific papers.

Exploiting multiple processing cores in parallel best-first search can be tricky. In many cases, the parallel version can be slower than the sequential version!
In the first part of the talk, I will cover parallel admissible search, where the focus will be on load balancing, synchronization, and communication overheads in parallel A*.
The second part of the talk will be about non-admissible parallel best-first search. Unlike parallel A*, where the states to be explored by parallel A* must be closely related to the states explored by sequential A*, parallelization of non-admissible algorithms such as greedy best-first search poses a significant challenge in that it is not even clear which states should be explored by the parallel algorithm -- in fact, parallel GBFS can perform arbitrarily worse than sequential GBFS. I will summarize recent work on a framework which allows us to define a parallel GBFS variant which offers some guarantees on the behavior relative to sequential GBFS.

Short Bio: Alex Fukunaga is a Professor in the Graduate School of Arts and Sciences at the University of Tokyo, Japan. His research interests are in combinatorial search, domain-independent planning, and metaheuristics. He received his Ph.D. in Computer Science at UCLA, and has previously held research positions at the Tokyo Institute of Technology and the NASA/Caltech Jet Propulsion Laboratory. He was co-chair of SoCS 2017, and currently serves on the editorial board of the Artificial Intelligence Journal.

Pattern database heuristics and their additive combination are two ideas that have originally been proposed 15-20 years ago in the combinatorial search community. Since then these ideas have also been investigated and expanded in the area of domain-independent planning. We concisely present different types of abstraction heuristics and cost partitioning that originated from this line of research in automated planning.

Short Bio: Gabriele Röger is lecturer and research associate at the AI group of the University of Basel. She received her doctoral degree (Dr. rer. nat) from the University of Freiburg (Germany) in June 2014. Her research is mostly on classical planning and heuristic search.
Gabriele is a co-developer of the Fast Downward and Temporal Fast Downward planning systems and obtained six awards at the International Planning Competitions 2008-2018. She received the ICAPS 2016 best dissertation award and was co-author of three best (student) papers at ICAPS and two best papers at AAAI.
She is in the program or senior program committees of all major traditional AI and planning conferences (IJCAI, AAAI, ICAPS, ECAI), was area chair at AAAI 2019 and is a member of the JAIR editorial board. Gabriele was a conference co-chair of SoCS 2013, program co-chair of ICAPS 2018 and associate program co-chair of AAAI 2021. Currently she is a member of the ICAPS executive council.

Short Bio: Silvan Sievers is a post-doctoral researcher at the AI group at the University of Basel, where he previously completed his PhD (Dr. phil.) under the supervision of Malte Helmert in October 2017. Silvan's main research interest lies in the area of classical domain-independent planning, where he focuses on heuristic search algorithms for solving planning tasks optimally. He is specifically interested in the merge-and-shrink framework and other abstraction heuristics such as pattern databases.
Silvan is a regular contributor to the Fast Downward planning system and won several awards in International Planning Competitions (learning track 2014, unsolvability competition 2016, classical optimal track 2018). Two of Silvan's papers received awards at AAAI 2014 and SoCS 2020. He is a regular (senior) program committee member of AAAI, IJCAI, ICAPS and SoCS.

Deploying multi-robot systems in the real world poses major challenges to the already highly combinatorial problems of planning and coordination. In this talk, I will show how some of the most compelling research questions in search are brought about by real-world requirements. We will explore the problem of combining planning, coordination, and control, and outline both general and application-specific ways to realize such combinations. The talk will include results achieved in basic and applied research projects involving major industrial partners and spanning a variety of application areas (warehouse automation, mining automation, and coordination of autonomous vehicles). I will also discuss how engagement and cooperation with the industry can help to discover novel research questions and to maximize both academic impact and industrial uptake.

Short Bio: Federico Pecora is Associate Professor in Computer Science at Örebro University, Sweden, where he leads the Multi-Robot Planning and Control Laboratory. His research interests include the intersection of Artificial Intelligence and Robotics, focusing specifically on constraint-based reasoning, automated planning, and search techniques for hybrid reasoning. Most of his recent work deals with the use of these methods for plan-based robot control, multi-robot planning and coordination, and the integration of these with robot motion planning and control. Federico has active collaborations with the industry (including Epiroc, Scania, Volvo, and Bosch) on topics related to the automation of industrial vehicles and robots.

I will talk about how to pick a good research topic and, once you have found one, what you can do to ensure that your research has impact, both on other researchers and beyond. Of course, there are many ways how to do that and none of them is surefire, so I will talk a bit about my own research experience. I will start by talking about research in general and will then try to provide some ideas in the context of research on heuristic and combinatorial search.

Short Bio: Sven Koenig is a professor of computer science at the University of Southern California. Most of his research centers around techniques for decision making (planning and learning) that enable single situated agents (such as robots or decision-support systems) and teams of agents to act intelligently in their environments and exhibit goal-directed behavior in real-time, even if they have only incomplete knowledge of their environment, imperfect abilities to manipulate it, limited or noisy perception or insufficient reasoning speed. Sven is a fellow of the Association for the Advancement of Artificial Intelligence (AAAI), the Association for Computing Machinery (ACM), the Institute of Electrical and Electronics Engineers (IEEE), and the American Association for the Advancement of Science (AAAS). Additional information about Sven can be found on his webpages: idm-lab.org.