AAAI-24 Tutorial on Recent Advances in Multi-Objective Search
4:15 pm-6:00 pm Wednesday, February 21
Embedded Files
Deterministic search and planning typically operate on graphs where each edge has a given cost, aiming to find a path of minimal cost. Heuristic search has developed tools for solving this path-finding problem, including the A* algorithm. However, the objective of search and planning is often much more complex in real life, for example, because one needs to trade-off between different costs. Multi-objective search and planning operate on graphs where each edge has two or more given costs, aiming to find paths that trade-off between the different costs in the form of a Pareto frontier of paths.
For example, transporting hazardous material requires trading off different costs for each street, such as its length and the number of residents that would be exposed to the hazardous material in case of an accident. Other examples include route planning for vehicles and robots (which involves trading off energy consumption and travel time), planning power transmission lines (which involves trading off power-generation cost and power loss), and scheduling satellites and routing packets in computer networks (which involves trading off profit and fairness).
This tutorial will provide an overview of the multi-objective search problem and summarize recent progress in this fast-moving research area. We will cover theoretical foundations, practical algorithms, and challenges that commonly arise in practice in a way that is accessible to all AI researchers and students. Our target audience is anyone interested in search and planning who wants to learn about this fascinating emerging field.
Prerequisites
Prerequisites
We assume that participants have knowledge equivalent to what is taught in a basic AI class. Especially we assume that participants have previous knowledge of the A* algorithm and heuristic search.
Organizers
Organizers
Ariel Felner is a professor of computer science at Ben-Gurion University, Israel. He is interested in all aspects of heuristic search, namely algorithms, heuristics, and applications. Multi-objective search has been the focus of his research for the past few years. Additional information on him can be found at https://felner.wixsite.com/home.
Oren Salzman is an assistant professor at The Henry and Marylin Taub Faculty of Computer Science at the Technion, Israel. His research focuses on revisiting classical computer science algorithms, tools, and paradigms to address the computational challenges that arise when planning motions for robots. Combining techniques from diverse domains such as computational geometry, graph theory, and machine learning, he strives to provide efficient algorithms with rigorous analyses for robot systems with many degrees of freedom moving in tight quarters. Additional information on him can be found at https://orensalzman.com/index.html.
Carlos Hernández is a full professor of computer science at Universidad San Sebastian, Chile. He is interested in all aspects of heuristic search and planning, namely algorithms, heuristics, and applications. Multi-objective search has been the focus of his research since he led an artificial intelligence group for freight transport applications in 2019. Additional information on him can be found in his Google Scholar profile at https://scholar.google.com/citations?user=dNsBXU8AAAAJ&hl=es.
Sven Koenig is a Dean’s professor of computer science at the University of Southern California, USA. Most of his research centers around techniques for decision-making that enable agents (such as robots and decision-support systems) and teams of agents to act intelligently in their environments and exhibit goal-directed behavior in real-time. Additional information about him can be found at idm-lab.org.
Han Zhang is a Ph.D. student at the University of Southern California. He is interested in path planning and heuristic search techniques and their applications to real-world planning problems. He has been working on multi-objective search since 2019. Additional information about his work can be found in his Google Scholar profile.
Page updated
Report abuse