SoCS 2014

SoCS 2014: The Seventh Annual Symposium on Combinatorial Search

Invited Speakers

We are pleased to have the following invited speakers at SoCS 2014:

Talk Title: Past, present, parallel: heuristic search in a changing computer world

Abstract:

Since its invention in 1968 by Hart, Nilsson and Raphael, many variants of the A* heuristic search algorithm have been devised. They are today found in many applications of practical relevance. Unfortunately, there exists a large class of very complex problems that can neither be solved with heuristic best-first search (because of limited memory space) nor with iterative depth-first search (due to limited computing time). How can we push the limitations a little bit further so that some of the previously intractable problems can be solved?

The answer to this question lies – in our view – in the efficient utilization of parallelism. Three things need to be done: (1) The space complexity must be reduced so that the solution space fits into the available distributed memories, (2) the scalability must be improved so that more processors can be employed to solve the problem in parallel, and (3) the efficacy of the heuristic must be improved so that a solution is found earlier. But above all, care must be taken to utilize all available parallel computational resources in a balanced way: CPUs, memories, and the network. With the example of the sliding tile puzzle, we will show how previously intractable problem instances can be solved on large systems with thousands of CPUs and we will try to glimpse into the future of heuristic search on exascale computers with millions of processors.
[presentation]

About the Speaker:

Alexander Reinefeld is Head of Computer Science Department Zuse Institute Berlin in Berlin-Dahlem. He is also Professor for Parallel and Distributed Systems Humboldt-Universitaet zu Berlin. Alexander Reinefelds' MSc and PhD degrees both come for the University of Hamburg. He has been the Director of the Paderborn Center for Parallel Computing.

His current research interests include the following topics: massively-parallel heuristic search with MapReduce, scalable, transactional key/value stores, data management and file systems for cloud computing, erasure codes for distributed data storage, energy efficient computing on manycore, GPGPU and FPGA.

Sven Koenig

Talk Title: Research Directions for Path Planning with A*

Abstract:

In a couple of years, A* will celebrate its 50th birthday, yet research on it is still going strong. In this talk, I'll give an overview of various facets of research on path planning with A*. In particular, I will talk about approaches that my research group has contributed to, including versions of A* for agent-centered search (such as real-time search), incremental search, any-angle search and hierarchical search, focusing on recent developments and their connections to robotics and video games. For example, A* search with subgoal graphs speeds up path planning by utilizing a small amount information compiled from map information in a preprocessing phase. It finds shortest paths by first finding high-level paths through subgoals and then shortest low-level paths between consecutive subgoals on the high-level path. The main insight here is that a large number of subgoals are only needed to connect certain start and goal locations to the other subgoals and can thus be ignored during path planning, resulting in a sparse graph without having to give up optimality.
[presentation]

About the Speaker:

Sven Koenig is a professor in computer science at the University of Southern California. He received his Ph.D. degree in computer science from Carnegie Mellon University. He is a fellow of the Association for the Advancement of Artificial Intelligence (AAAI), a distinguished speaker of the Association for Computing Machinery (ACM) and the recipient of an ACM Recognition of Service Award. Sven was also a program director at the National Science Foundation (NSF) from 2010 to 2012.

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.