webmaster: Sven Koenig

International Symposium on Combinatorial Search (SoCS)

SoCS 2008

Search is one of the few areas of artificial intelligence (and beyond) that lack their own conference. The First International Symposium on Search (SoCS 2008), organized as a AAAI-08 workshop, therefore brought together researchers interested in this topic to share their ideas and disseminate their latest research results. We expect this symposium to be a recurrent event. The first symposium focused on finding common ground between search techniques used in artificial intelligence and robotics.

Heuristic search and related algorithms are currently very active areas of research. For example, researchers investigate how to search in real-time, how to search with limited (possibly external) memory, how to search in parallel on several processors, how to solve sequences of similar search problems faster than with isolated searches, how to improve the runtime of the searches via randomization or learning techniques, how to discretize continuous state spaces, how to trade-off between the runtime and memory consumption of the search and the resulting solution quality, how to select between different search strategies, and how to focus the searches with sophisticated heuristics such as pattern databases. Their results are published in different conferences such as IJCAI, AAAI, ICAPS, NIPS, ICRA, and IROS. The First International Symposium on Search brought these researchers together to exchange their ideas, cross-fertilize the field and combine various search techniques that originated in different research communities.

The two-day symposium had more than 35 attendees, in part thanks to generous support from NSF for student participation. It featured an overview that highlighted the similarities and differences of search in artificial intelligence and robotics and 3 invited talks (by Oliver Brock, Malte Helmert and Maxim Likachev) on "Solving Hard Planning Problems in Robotics with Simple A*-like Searches", "Automatically Deriving Abstraction Heuristics" and "Search in Embodied Artificial Intelligence and Computational Biology."

The 15 oral presentations and more than 12 posters in a lively poster session displayed the diversity of research on search and its applications, covering topics such as abstraction, inconsistent heuristics, bounded sub-optimality, performance prediction, learning, symmetry, real-time search, moving-target search, connections to probabilistic reasoning and applications to robotics, machine learning, and diagnosis. One of the highlights of the symposium were presentations on the use of heuristic search in the first- and second-place vehicles participating in the DARPA Urban Challenge.


  • David Furcy, University of Wisconsin at Oshkosh
  • Sven Koenig, University of Southern California
  • Wheeler Ruml, University of New Hampshire
  • Rong Zhou, Palo Alto Research Center

Program Committee

  • Chris Beck, University of Toronto
  • Blai Bonet, Universidad Simón Bolívar
  • Stefan Edelkamp, University of Dortmund
  • Susan Epstein, Hunter College
  • Ariel Felner, Ben-Gurion University
  • David Furcy, University of Wisconsin at Oshkosh
  • David Ferguson, Carnegie Mellon University
  • Hector Geffner, Universitat Pompeu Fabra
  • Youssef Hamadi, Microsoft
  • Eric Hansen, Mississippi State University
  • Patrik Haslum, NICTA
  • Robert Holte, University of Alberta
  • Lydia Kavraki, Rice University
  • Sven Koenig, University of Southern California
  • Richard Korf, University of California at Berkeley
  • James Kuffner, Carnegie Mellon University
  • Maxim Lihkachev, University of Pennsylvania
  • Wheeler Ruml, University of New Hampshire
  • Jonathan Schaeffer, University of Alberta
  • Bart Selman, Cornell University
  • Shlomo Zilberstein, University of Massachusetts at Amherst
  • Toby Walsh, NICTA
  • Weixiong Zhang, Washington University in St. Louis
  • Rong Zhou, Palo Alto Research Center

Additional Information is contained on the webpage of SOCS 2008.