SoCS

Heuristic search and combinatorial optimization 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 solve sequences of similar search problems faster than with isolated searches, how to improve the runtime of the searches over time, how to trade-off between the runtime and memory consumption of the search and the resulting solution quality, 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 International Symposium on Combinatorial Search (SoCS) is meant to bring these researchers together to exchange their ideas and cross-fertilize the field. Thus, in addition to seeking separate answers to questions like how to design more accurate memory-based heuristics, more I/O-efficient disk-based search algorithms, or more efficient clause-learning strategies, the symposium will stimulate thoughts on combining various techniques originated from different areas of search.

SoCS is targeting researchers in all fields that use combinatorial search, including artificial intelligence, robotics, constraint programming, operations research and bioinformatics. The symposium's scope includes both complete and incomplete methods. Work discussing a specific application domain (for example, robotic motion planning, constraint programming, planning, ...) is welcomed, as long as the emphasis is on the search strategy employed and a serious effort is made to suggest how the ideas might be relevant in another domain.

Relevant Topics

• Analysis of search algorithms
• Automated synthesis of lower bounds
• Bounding and pruning techniques
• Continuous problem solving
• External-memory and parallel search
• Incremental and active learning in search
• Meta-reasoning and search
• Methodology and critiques of current practice
• Model-based search
• Meta-reasoning and search
• Random vs systematic search strategy selection
• Pattern databases
• Portfolios of search algorithms
• Real-time search
• Search focus in goal-directed problem solving
• Search space discretization for continuous state-space problems
• Self-configuring and self-tuning algorithms
• Symmetry handling
• Time, memory, and solution quality tradeoffs
• ... and all other topics related to combinatorial search and path planning

Attendance will be limited to those who have either a regular technical paper (AAAI style, 6 pages preferred, 8 pages maximum) or short research statement (2 pages maximum) accepted. Papers will be carefully peer-reviewed by multiple reviewers and low-quality or off-topic papers will not be accepted. Please read the submission instructions.

Because SoCS will have an informal, web-only proceedings, submissions to SoCS may be later resubmitted to other venues without complications. Also, papers that have already appeared or been accepted at other venues are welcome as SoCS submissions. However, we ask that authors note such prior publication on their submissions and we will give preference for oral presentation at SoCS (as opposed to poster presentation) to new work. We also wish to encourage the submission of non-standard papers, such as thoughtful critiques of the field, historical perspectives and analyses, methodological contributions, and insightful reports on new and demanding applications.

If you are interested in SoCS, please join the search-list on google groups. We gratefully acknowledge funding for the symposium series in 2008 from the National Science Foundation (NSF). We anticipate having assistance available for student presenters at SoCS in 2009 - please stay tuned for application instructions.

SoCS 2009 is organized in cooperation with SARA 2009 (the Symposium on Abstraction, Reformulation, and Approximation). SARA is focussed on abstraction, while SoCS is focussed on search. The last day of SARA and the first full day of SoCS (July 9) will be an overlap day on the use of abstraction in search. It will be possible to register for either or both symposia. If you have work on abstraction in search but can only attend one symposium, the choice of where to submit is up to you. SARA has a formally printed proceedings, a higher registration fee, and ends on July 9. SoCS has a web-only proceedings, accepts previously published work, has a lower fee, and ends on July 10. It will have some support for student presenters (exact amount to be determined). Both events will be great!

Sponsors

We thank NSF and Adventium Labs for their generous support.

Important Dates

Technical paper submission deadline

April 6, 2009

Technical paper notification date

April 18

Statement of interest submission deadline

May 4

Statement of interest notification date

May 6

Registration deadline

May 8

Final versions of papers due

June 8

SoCS symposium starts

July 8: bus leaves LAX in the afternoon, stops at ONT, arrives at Lake Arrowhead for dinner

SoCS and SARA overlap day

July 9: single track for the combined attendees. SARA ends after dinner

SoCS ends

July 10: full day of technical sessions, then bus to Pasadena leaves Lake Arrowhead after dinner

Program Committee

• Adi Botea (NICTA)
• Ariel Felner (Ben-Gurion University)
• Bart Selman (Cornell University)
• Blai Bonet (Universidad Simon Bolivar)
• Eric Hansen (Mississippi State University)
• Hector Geffner (Universitat Pompeu Fabra)
• Lydia Kavraki (Rice University)
• Malte Helmert (Albert-Ludwigs-Universitat Freiburg)
• Max Likhachev (University of Pennsylvania)
• Michela Milano (Universita di Bologna)
• Mike Trick (CMU)
• Nathan Sturtevant (University of Alberta)
• Patrik Haslum (NICTA)
• Rich Korf (UCLA)
• Rob Holte (University of Alberta)
• Sheila McIlraith (University of Toronto)
• Stefan Edelkamp (Technische Universitat Dortmund)
• Susan Epstein (Hunter College, CUNY)
• Toby Walsh (NICTA)
• Weixiong Zhang (Washington University in St Louis)
• Youssef Hamadi (Microsoft Research, Cambridge)

Organizers

• Sven Koenig, University of Southern California
• Wheeler Ruml, University of New Hampshire
• Rong Zhou, Palo Alto Research Center

Contact Email

• ruml at cs unh edu

Additional Information is contained on the webpage of SOCS 2009.