Factored Planning: From Classical Planning to Dec-POMDPs
The idea of taking a problem and solving it by decomposing it to multiple smaller problems and then somehow combining them together has motivated algorithm design in many different area. I this talk I will review an evolving journey motivated by this idea that I’ve been taking with the help of many colleagues. Starting from an attempt to make classical planning more efficient, it evolves into distributed classical planning, privacy preserving multi-agent planning, multi-agent forward search, and eventually (for now?) planning in decentralized POMDPs. Common to most of these techniques is the idea of identifying the parts of the problem (variables/actions) involving multiple components/agents and those relevant to one component only. This then allows us to formulate an abstract problem whose solution forms a skeleton to the solution of the real problem. This skeleton then serves to partition the problem into multiple independent problems involving one component/agent only, that can be solved in parallel.
Short Bio: Ronen Brafman is the Scharf-Ullman Chair in Computer Science at Ben-Gurion University in Israel. He obtained his Ph.D. from Stanford University in 1996, was a Post-Doctoral Fellow at UBC, and was a research scientist at NASA AMES Research Center between 2004-2006. His work spans diverse aspects of decision making, including preference modeling and reinforcement learning, where he co-developed the CP-nets model and the R-max algorithm, but he is mostly interested in decision making under uncertainty, and more recently, planning for multi-agent systems where he co-introduced the MA-STRIPS model and privacy preserving planning. Ronen is also interested in applying planning to robotics, and improving the practice of software engineering for autonomous robots. He served as Program and Conference Chair for ICAPS, an Associate Editor for JAIR, AIJ, and JAAMAS, and is a AAAI and EurAI fellow.
Giuseppe De Giacomo
Giuseppe De Giacomo
Università degli Studi di Roma La Sapienza
Resilience in Planning and Synthesis
A central topic in AI is building autonomous agents that act intelligently. Program Synthesis, Planning in Nondeterministic Domains, and Reinforcement Learning are all about automatically synthesizing an agent strategy/plan/policy/behavior to accomplish desired tasks in a partially controllable (nondeterministic) world. Recently the importance of introducing forms of resilience has become apparent, including: considering more advanced forms of planning that are indeed tightly connected with program synthesis; focusing on plan/strategies with built-in tolerance capabilities; forms of best-effort synthesis; adopting multiple models of the world that incorporate increasingly exceptional world behaviors; focusing on maximally permissive strategies; and enforcing capabilities in addition to duties. In this talk, we discuss these issues using as representation formalisms Linear Temporal Logic on finite traces, a variant of one of the the most common temporal logics used in Formal Methods, which is particularly suitable for autonomous agents.
Short Bio: Giuseppe De Giacomo is full professor in Computer Science and Engineering at University of Roma La Sapienza. His research activity has concerned theoretical, methodological and practical aspects in different areas of AI and CS, most prominently Knowledge Representation, Reasoning about Actions, Generalized Planning, Autonomous Agents, Service Composition, Business Process Modeling, Data Management and Integration. He is AAAI Fellow, ACM Fellow, and EurAI Fellow. He has got an ERC Advanced Grant for the project WhiteMech: White-box Self Programming Mechanisms (2019-2024). He has been the Program Chair of ECAI 2020. He is in the Board of EurAI.
Recent Progress in Bidirectional Search
In bidirectional search a search forward from the start state and a search backward from the goal state are initiated aiming that the two frontiers will meet generating a solution path from the start state to the goal state. Bidirectional search is a fundamental technique that dates back to the very beginning of the research on heuristic search and many ideas and algorithms were developed over the years. Nevertheless, in the past few years there has been significant progress in this area with new understandings, new concepts and new algorithms involving several research groups. The talk will cover these new developments and put them in the context of previous work while focusing on the following theme: what is the work that must be done by a bidirectional search and whether/what algorithms can really do it. The talk will cover new terms such as a must-expand pair of nodes, GMX and its vertex-cover and more. Moreover, new algorithms such as MM, fractional MM, NBS, DVCBS, GBFHS, DiBBS, IDBiHS will be described while discussing their benefits and drawbacks.
Short Bio: Ariel Felner is a professor of computer science and currently serves as the chair of the Software and Information Systems Engineering Department at Ben-Gurion University, Israel. He is a fellow of EurAI. His research interests involve all aspects of heuristic search including theoretical foundations, new search algorithms, the study and development of heuristics and applying all these to different domains and settings.
University of California
The Elements of Search Algorithms
By analogy to the fact that the enormous number of molecules that exist in the world are all composed of combinations of a small number of elements, in this talk I will argue that search algorithms can similarly be viewed as combinations of a small number of more basic ideas. I will try to identify some of these more basic elements, and show how a number of different search algorithms can be viewed as combinations of these elements.
Short Bio: Richard Korf is a Professor of computer science at the University of California, Los Angeles. He received his B.S. from M.I.T. in 1977, and his M.S. and Ph.D. from Carnegie-Mellon University in 1980 and 1983, respectively, all in computer science. From 1983 to 1985, he served as Herbert M. Singer Assistant Professor of Computer Science at Columbia University. His research is in the areas of problem solving, planning, and heuristic search in artificial intelligence. Korf is the recipient of a 1985 IBM Faculty Development Award, a 1986 NSF Presidential Young Investigator Award, the first UCLA Computer Science Department Distinguished Teaching Award in 1989, the UCLA Engineering School First Annual Student's Choice Award for Excellence in Teaching in 1996, the Lockheed Martin Excellence in Teaching Award in 2005, the Artificial Intelligence Classic Paper Award in 2016, and a career award from SoCS in 2018. He was elected a Fellow of the American Association for Artificial Intelligence in 1994.
The University of Melbourne
Width-Based Planning: Searching for Novelty
Sequential decision problems, where an agent is trying to find a sequence of actions to maximise a utility function or to satisfy a goal condition, have been the focus of different research communities: Control, Reinforcement Learning and AI Planning. My talk originates from the AI planning community, and focuses on width-based planning algorithms. Width-based algorithms search for solutions through a general definition of state novelty. These algorithms have been shown to result in state-of-the-art performance in classical planning, and have been successfully applied to model-based and model-free settings where the dynamics of the problem are given through simulation engines. Width-based algorithms performance is understood theoretically through the notion of planning width, providing polynomial guarantees on their runtime and memory consumption. To facilitate synergies across research communities, I will summarize the area of width-based planning, and survey current and future research directions.
Short Bio: Nir Lipovetzky is a Senior Lecturer in the School of Computing and Information Systems at The University of Melbourne. His interests span across research areas in AI planning, search, and learning, with a special focus on how to introduce novel approaches to the problem of inference in sequential decision problems. He is involved in developing tools to assist technology transfer from research to industry and education. He maintains the Lightweight Automated Planning ToolKiT (LAPKT), aimed to make your life easier if your purpose is to create, use or extend basic to advanced Automated Planners; Planimation, aimed to visualise solutions using declarative programming; and contributes to extend the editor and online solver for planning.domains, specially used for teaching activities. His contributions were recognized through best-paper / dissertation / system-demonstration / best-planners awards from ICAPS and the International Planning Competitions (IPC), and the Early Career spotlight at IJCAI-2021.
University of New Hampshire
Suboptimal Heuristic Search
Most interesting problems are too hard to solve optimally. I'll talk about alternative problem settings in which optimality is sacrificed for lower search time, such as greedy search, bounded-suboptimal search, contract search, and real-time search. When planning under time pressure, additional sources of heuristic information beyond cost-to-go become relevant, so there is lots of room for creativity here. My perspective is that search algorithms should be seen as rational agents maintaining beliefs about the search space and selecting nodes to expand so as to best achieve their computational goals.
Short Bio: Wheeler Ruml is a Professor of Computer Science at the University of New Hampshire (UNH). He was a co-founder of the SoCS symposium series and a General Co-Chair of ICAPS-14. Before joining UNH, he led a team at Xerox's PARC lab that used AI planning and search techniques to build the world's fastest printer. He enjoys trying to decide which node to expand.
University of Basel
Heuristics for Being a Researcher
Being a researcher is a unique, wonderful and at times bewildering experience. There is no one "right way" to be a researcher, but this will not stop people like me from giving you unsolicited and highly subjective advice. Some of it you may agree with, some of it you may strongly disagree with, and hopefully some of it will make you think in new directions. This presentation is for you, so I hope I will be able to tailor it to your needs, and that we will have a lively discussion.
Short Bio: Malte has worked in AI planning and heuristic search since 1998 and has attended every edition of SoCS so far. He firmly believes that strong theory begets strong algorithms and vice versa, and in his research he tries to contribute to both aspects evenly. Malte's work on classical planning and heuristic search has been recognized with a total of 21 best paper awards and honourable mentions at major AI conferences, including two best paper awards and one best student paper award at SoCS, two best paper awards and one honourable mention at AAAI, five best paper awards and three best student paper awards at ICAPS, and two ICAPS influential paper awards. In 2011, he received the IJCAI Computers and Thought Award "for fundamental contributions to the theory and practice in automated planning and combinatorial search".