webmaster: Sven Koenig

International Symposium on Combinatorial Search (SoCS)

SoCS 2009 Program

Link to download all SoCS'09 papers in a single WinZip file.

Wednesday, July 8
2:30Depart LAX
6:30Arrive Lake Arrowhead
7:00Buffet dinner
Thursday, July 9
7:00 - 8:30Breakfast
8:50 - 9:00Introductory remarks
9:00 - 10:05Invited talk: The Performance of Swarm Search Methods by Gerard Holzmann.
10:05 - 10:30Common Misconceptions in Heuristic Search. R. Holte [Session Chair: Rong Zhou]
10:30 - 11:00Coffee
11:00 - 12:40Search with real-time and novel constraints [Session Chair: Nathan Sturtevant]
 Lookahead, Propagation and Moves in Real-Time Heuristic Search. C. Hernandez and P. Meseguer
 Contract Search: An Adaptive Heuristic Search Strategy under Node Expansion Constraints. S. Aine, P. P. Chakrabarti and R. Kumar
 A Depth-First Approach to Target-Value Search. T. Schmidt, L. Kuhn, B. Price, J. de Kleer and R. Zhou
 Search-based Planning for a Legged Robot over Rough Terrain. P. Vernaza, M. Likhachev, S. Bhattacharya, A. Kushleyev, D. Lee and S. Chitta
12:40 - 2:00Lunch
2:00 - 3:40Search in games and constraint satisfaction problems [Session Chair: Toby Walsh]
 Analysing the Behaviour of Crossword Puzzles. A. Botea and Anbulagan
 Error Minimizing Minimax: Avoiding Search Pathology in Game Trees. B. Wilson, A. Parker and D. Nau
 Integrating Systematic and Local Search Paradigms: A New Strategy for MaxSAT. L. Kroc, A. Sabharwal, C. Gomes and B. Selman
 Online Heuristic Selection in Constraint Programming. A. Arbelaez, Y. Hamadi and M. Sebag
3:40 - 4:00Coffee and poster setup
4:00 - 6:30Poster session
 Best-First Search with Lookaheads. T. Kulberis, R. Stern and A. Felner
 Canadian Traveler Problem with Remote Sensing. Z. Bnaya, A. Felner and S. Shimony
 Combined Constraint Models in Planning: Where to Search? R. Barták and D. Toropila
 Duplicate Avoidance in Depth-First Search with Applications to Treewidth. P. Dow and R. Korf
 Dynamic Fringe-Saving A*. X. Sun, W. Yeoh and S. Koenig
 Improving Collaborative Pathfinding Using Map Abstraction. N. Sturtevant and M. Buro
 Making Solutions of Multi-robot Path Planning Problems Shorter Using Weak Transpositions and Critical Path Parallelism. P. Surynek
 New Improvements in Optimal Rectangle Packing. E. Huang and R. Korf
 Phi*:Incremental Any-Angle Path Planning on Grids. A. Nash, S. Koenig and M. Likhachev
 Parallel Best-First Search for Optimal Sequential Planning (Research Statement). A. Kishimoto, A. Fukunaga and A. Botea
 Predicting the optimal combination of pattern databases for solving a problem. S. Franco and M. Barley
 Real-Time A* Search With Depth-k Lookahead. E. Sefer, U. Kuter and D. Nau
 Search and Optimization in Small-World and Scale-Free Networks. R. Araujo and L. Lamb
 Search on Constraint Satisfaction Problems with Sparse Secondary Structure. S. Epstein and X. Li
 Solving POMDPs: RTDP-BEL vs. Point-based Algorithms. B. Bonet and H. Geffner
 Time-bounded Lattice for Efficient Planning in Dynamic Environments. A. Kushleyev and M. Likhachev
 Trading Off DCOP Solution Quality for Faster Computation. W. Yeoh, X. Sun and S. Koenig
 Using Distance Estimates in Search: A Re-evaluation. J. Thayer, W. Ruml and J. Kreis
6:30 - 8:00Dinner
Friday, July 10
(combined sessions with SARA)
7:00 - 8:30Breakfast
8:30 - 8:35Welcome
8:35 - 9:40Invited talk: Abstraction and Search by Rob Holte
9:40 - 10:30Abstraction and Planning [Session Chair: Blai Bonet]
 Abstract Planning with Unknown Object Quantities and Properties. S. Srivastava, N. Immerman and S. Zilberstein
 Integrating Constraint Models for Sequential and Partial-Order Planning. R. Barták and D. Toropila
10:30 - 11:00Coffee
11:00 - 12:40Abstraction and State-Space Search [Session Chair: Malte Helmert]
 Abstraction-Based Heuristics with True Distance Computations. A. Felner, N. Sturtevant and J. Schaeffer
 Downward Path Preserving State Space Abstractions. S. Zilles and R. Holte
 Dynamic State-Space Partitioning in External-Memory Graph Search. R. Zhou and E. Hansen
 1.6-bit Pattern Databases. T. Breyer and R. Korf
12:40 - 2:00Lunch
2:00 - 3:15Approximation and Reformulation for Constraint Programming [Session Chair: Andrea Rendl]
 Light Algorithms for Maintaining Max-RPC During Search. J. Vion and R. Debruyne
 Posting Static Symmetry Breaking Constraints Dynamically. G. Katsirelos and T. Walsh
 Cluster Graphs as Abstractions for Constraint Satisfaction Problems. S. Epstein and X. Li
3:15 - 3:45Coffee
3:45 - 5:00Abstraction in Parallel Search [Session Chair: Alex Fukunaga]
 Parallel Best-First Search: Optimal and Suboptimal Solutions. E. Burns, S. Lemons, W. Ruml and R. Zhou
 Parallel State Space Search on the GPU. S. Edelkamp and D. Sulewski
 ESP: Pursuit Evasion on Series-Parallel Graphs. R. Borie, C. Tovey, K. Daniel and S. Koenig
5:00 - 5:15Stretch break
5:15 - 6:05Approximation by Forgetting [Session Chair: Adi Botea]
 A Practical Use of Imperfect Recall. K. Waugh, M. Zinkevich, M. Johanson, M. Kan, D. Schnizlein and M. Bowling
 The Joy of Forgetting: Faster Anytime Search via Restarting. S. Richter, J. Thayer and W. Ruml
6:30 - 8:00Dinner
8:00Bus departs for Pasadena


We thank NSF and Adventium Labs for their generous support.

Adventium Labs