Master Classes

Decoupled Search: A New Form of State-Space Exploration

Álvaro Torralba

Aalborg University

Abstract: Decoupled search is a recent technique for state-space exploration that aims to leverage the structure of the problem in a unique way. By automatically decomposing the problem into factors that are conditionally independent of each other, it refactors the state space in which the search is conducted. This can potentially reduce the state space dramatically, often by several orders of magnitude. Thus, decoupled search is a promising approach for state-space exploration and has already been applied into Automated Planning and model checking with good and promising results.In this tutorial, we will start with the basics, introducing what decoupled search is, how can it decompose planning tasks, and how search is conducted afterwards. We will also draw connections to other related forms of factoring tasks, such as the ones used in multi-agent path finding. And we will conclude with some recent advances on how to efficiently compute heuristics for this form of search.
Bio: Álvaro Torralba is Associate Professor at the University of Aalborg, Denmark. His research interests are on algorithmic approaches for general problem solving, such as heuristic search, and their application into Automated Planning and optimization. His research has been focused on new methods for efficiently performing search, such as symbolic search with BDDs, decoupled search, or other forms of guidance such as heuristic and dominance analysis functions.

On Clashing Wavefronts in Pareto Search

Sabine Storandt

Universität Konstanz

Abstract: In multi-objective optimization problems, the goal is usually to compute the set of Pareto-optimal solutions. To solve problem instances of considerable size, solution approaches often rely on efficient combination and filtering of partial solutions. In particular, non-dominance filtering of unions or Minkowski sums of intermediate Pareto sets occurs as a frequent subtask, e.g., in dynamic programming methods for multi-objective knapsacks or in planning algorithms for multi-objective shortest paths. Given two Pareto sets A and B, the Minkowski sum M is defined as the set of elements resulting from the pairwise addition of the elements in A and B. When the input sets are n large, the size of the Minkowski sum is quadratic in n. However, the subset of non-dominated points in M is usually much smaller, so computing all of M and then performing dominance filtering takes an unnecessary amount of time and space. We present several output-sensitive algorithms that compute the non-dominated subset of M without computing and storing all of M. We also discuss connections to geometric search problems, where the goal is to efficiently report pairs of input objects with certain properties without computing and checking all pairs explicitly.
Bio: Sabine Storandt has been a professor at the University of Konstanz since 2018 and leads the group on Algorithmics. Her research focuses on graph algorithms, algorithm engineering, and discrete optimization.

Programmatic Policies for Game Playing

Levi Lelis

University of Alberta

Abstract: In this tutorial, you will learn how to implement systems for synthesizing computer programs that encode policies for solving Markov decision processes (MDPs) in the context of games. Programmatic policies offer advantages such as interpretability compared to neural policies. However, a major drawback of programmatic policies is the need to search through vast and often discontinuous program spaces to synthesize them. In this tutorial, we will explore recent advances in combinatorial search algorithms for synthesizing such policies in the context of game playing.
Bio: Levi Lelis’ research goal is to develop intelligent systems that are able to augment people through teaching and collaboration. Currently, his group is working on algorithms to generate human-interpretable knowledge, such as programmatic policies for solving sequential decision-making problems. They seek to use machine-generated knowledge to teach humans how to solve problems. For example, these machine-created interpretable policies can be used to compile human-readable manuals for teaching people game strategies. Levi is also interested in investigating the use of interpretable machine-generated knowledge in human-machine collaborative tasks, where algorithms help humans solve problems. Levi is currently an Assistant Professor in the Department of Computing Science at the University of Alberta.

Towards massively parallelized search-based planning in robotics

Maxim Likhachev

Carnegie Mellon University

Abstract: Planning in physical robots is often severely time limited. At the same time, the requirements on the fidelity of the planning models and their ability to account for more and more relevant factors keep on growing. Unfortunately, CPUs have hit the plateau in their clock speed, making it hard for single-threaded planning algorithms to support these evergrowing requirements while also respecting time limits. On the contrary, the number of CPU cores has grown significantly, a trend that is likely to continue. This calls for the development of planning algorithms that exploit parallelization. I will talk about some of the work that my group has done towards the development of massively parallelized search-based planning algorithms with robotics being a target domain. In particular, a key feature in planning for robotics is that the major chunk of computational effort during planning is spent on computing the outcome of an action and the cost of the resulting edge rather than searching the graph itself. The algorithms I describe exploit this property to harness the multi-threading capability of modern processors. I will present some of these algorithms, describe their theoretical properties, show some of the experimental analysis on planning for mobile manipulation, and discuss future directions.
Bio: Maxim Likhachev is a Professor of Robotics at Carnegie Mellon University, directing Search-based Planning Laboratory (SBPL). His group at CMU researches heuristic search, decision-making and planning algorithms, all with applications to the control of robotic systems including unmanned ground and aerial vehicles, mobile manipulation platforms, humanoids, and multi-robot systems. Maxim obtained his Ph.D. in Computer Science from Carnegie Mellon University with a thesis called “Search-based Planning for Large Dynamic Environments.” He has over 150 publications in top journals and conferences on AI and Robotics and numerous paper awards. His work on Anytime D* algorithm, an anytime planning algorithm for dynamic environments, has been awarded the title of Influential 10-year Paper at International Conference on Automated Planning and Scheduling (ICAPS) 2017, the top venue for research on planning and scheduling. Some of the other awards include selection for 2010 DARPA Computer Science Study Panel that recognizes promising faculty in Computer Science and being on a team that won 2007 DARPA Urban Challenge and on a team that won the Gold Edison award in 2013. Maxim founded RobotWits, a company devoted to developing advanced planning and decision-making technologies for self-driving vehicles and recently acquired by Waymo, and co-founded TravelWits, an online travel tech company that brings AI to make travel logistics easier. Finally, Maxim is an executive co-producer of regional Emmy-nominated The Robot Doctor TV series aimed at showing the use of mathematics in Robotics and inspiring high-school students to pursue careers in science and technology.

Page updated

Google Sites

Report abuse