SoCS 2010
Main Page
About SoCS
Call For Participation
[txt pdf (A4) pdf (Letter)]

Accepted Papers
Official Proceedings
Submission Details
Submission Site
Program Committee

SoCS Schedule
Invited Speakers
Registration and Lodging
Transportation to SoCS

Related Conferences

Past SoCS Conferences
2009 Lake Arrowhead, CA
2008 Chicago, IL

SoCS 2010: The Third Annual Symposium on Combinatorial Search

Invited Speakers

Dr. Dorothea Wagner
Talk Title: Algorithm Engineering for Route Planning


Nowadays, route planning systems belong to the most frequently used information systems. The algorithmic core problem of such systems, i.e., the fast computation of shortest paths is a classical problem that can be solved by Dijkstra's shortest paths algorithm. However, algorithms for route planning in transportation networks have recently undergone a rapid development, leading to methods that are up to three million times faster than Dijkstra's algorithm. In particular, computing shortest paths in huge networks has become a showpiece of Algorithm Engineering demonstrating the engineering cycle that consists of design, analysis, implementation and experimental evaluation of practicable algorithms.

We will provide a condensed overview of the techniques enabling this development. The main part of the talk will focus on variants of the problem that occur in more realistic traffic scenarios.

About the Speaker:

Dorothea Wagner is a full professor for Informatics at the Karlsruhe Institute of Technology (KIT). Her research interests include design and analysis of algorithms and algorithm engineering, graph algorithms, computational geometry and discrete optimization, particularly applied to transportation systems, network analysis, data mining and visualization.

Among other activities she is vice president of the DFG (Deutsche Forschungsgemeinschaft - German Research Foundation) and speaker of the scientific advisory board of Dagstuhl - Leibniz Center for Informatics. She was coordinator of the DFG priority program on "Algorithmics of Large and Complex Networks", member of the DFG research training group on "Self-organizing Sensor-Actuator-Networks" and one of the initiators of the DFG priority program on "Algorithm Engineering", coordinator of the EU RTN AMORE and participant of the EU projects COSIN, DELIS, CREEN and ARRIVAL. She is Editor in Chief of JDA (Journal on Discrete Algorithms), member of the editorial board of JGAA (Journal of Graph Algorithms and Applications), of CGTA (Computational Geometry: Theory and Applications) and of "Leitfäden der Informatik", B. G. Teubner.

Dorothea Wagner obtained her diploma and Ph.D. degrees in mathematics from the RWTH Aachen in 1983 and 1986 respectively; and 1992 the Habilitation degree from the TU Berlin. 1994 - 2003 she was a full professor at the Universität Konstanz.

Dr. Sven Koenig
Talk Title: Look Before you Leap or Leap Before you Look? Speeding up Search in Nondeterministic Domains


Autonomous agents must be able to make good decisions in complex situations that involve a substantial degree of uncertainty, yet find solutions in a timely manner despite a large number of potential contingencies. Search in non-deterministic domains is typically time-consuming due to the large number of contingencies. Thus, one needs to develop search techniques that speed up search by sacrificing the optimality of the resulting plans. Greedy on-line planning methods interleave search and action execution to allow agents to gather information early and then use the acquired information right away for replanning, which reduces the amount of search performed for unencountered situations and thus allows agents to plan efficiently and be reactive to their current situation. In this talk, I will give an overview of greedy on-line planning, including some of the theoretical guarantees provided by it.

About the Speaker:

Sven Koenig is an associate professor in 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. He is the recipient of an NSF CAREER award, an IBM Faculty Partnership Award, a Charles Lee Powell Foundation Award, a Raytheon Faculty Fellowship Award, an ACM Recognition of Service Award and a Mellon Mentoring Award, among others. He co-founded Robotics: Science and Systems (a highly selective robotics conference), was conference co-chair of the 2002 Symposium on Abstraction, Reformulation, and Approximation, conference co-chair of the 2004 International Conference on Automated Planning and Scheduling, symposium co-chair of the International Symposium on Combinatorial Search (SoCS), program co-chair of the 2005 International Joint Conference on Autonomous Agents and Multi-Agent Systems and program co-chair of the 2007 and 2008 AAAI Nectar programs.

Invited Panelists: Specific or General Planning

Richard Korf

About the Panelist:

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, heuristic search, and planning in artificial intelligence. He is the author of "Learning to Solve Problems by Searching for Macro-Operators" (Pitman, 1985). He serves on the editorial boards of Artificial Intelligence, and the Journal of Applied Intelligence. Dr. 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 first UCLA School of Engineering Student's Choice Award for Excellence in Teaching in 1996, and the Lockheed Martin Excellence in Teaching Award in 2005. He is a Fellow of the American Association for Artificial Intelligence.

Stefan Edelkamp

About the Panelist:

Stefan Edelkamp is with the Center for Computing and Communication Technology (TZI) at the Universität Bremen since 2008. He has been leading young research groups in Freiburg and Dortmund. He is on the editorial board of JAIR and steering committee member of MOCHART and SPIN. He organizes AAAI-10's Students Abstract and Poster Session and a Workshop on Security and AI. He is general co-chair of the International Conference on Automated Planning and Scheduling Systems (ICAPS-11) in Freiburg. He is in the lead of projects on directed, parallel, and external model checking, on general game playing, and on integrating AI methods for improved intrusion detection in computer networks. Last, but not least, he is an eager programmer. Besides being acting world champion in cost-optimal deterministic and non-deterministic AI planning, he has implemented fast sequential sorting algorithms and priority queues.

Malte Helmert

About the Panelist:

Malte Helmert is a lecturer at Albert-Ludwigs-Universität Freiburg, where he graduated with a diploma in computer science in 2001 and a Ph.D. in computer science in 2006. His main research area is classical domain-independent planning, with occasional forays into other areas where combinatorial search techniques can be applied, such as model checking. He is conference co-chair of the International Conference on Automated Planning and Scheduling (ICAPS 2011) in Freiburg and has served on the conference committee of the ICAPS conference series in various functions, including tutorial chair in 2009 and organizer of the international planning competition in 2008. He is an associate editor of JAIR. He is the main author of seven publications that have been awarded with best paper awards or honorable mentions at various venues, including ECP, ICAPS, AAAI, and an honorable mention for the IJCAII-JAIR best paper prize.