SoCS
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:30 | Depart LAX |
| 6:30 | Arrive Lake Arrowhead |
| 7:00 | Buffet dinner |
| Thursday, July 9 | |
| 7:00 - 8:30 | Breakfast |
| 8:50 - 9:00 | Introductory remarks |
| 9:00 - 10:05 | Invited talk: The Performance of Swarm Search Methods by Gerard Holzmann. |
| 10:05 - 10:30 | Common Misconceptions in Heuristic Search. R. Holte [Session Chair: Rong Zhou] |
| 10:30 - 11:00 | Coffee |
| 11:00 - 12:40 | Search 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:00 | Lunch |
| 2:00 - 3:40 | Search 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:00 | Coffee and poster setup |
| 4:00 - 6:30 | Poster 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:00 | Dinner |
| Friday, July 10 | |
| (combined sessions with SARA) | |
| 7:00 - 8:30 | Breakfast |
| 8:30 - 8:35 | Welcome |
| 8:35 - 9:40 | Invited talk: Abstraction and Search by Rob Holte |
| 9:40 - 10:30 | Abstraction 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:00 | Coffee |
| 11:00 - 12:40 | Abstraction 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:00 | Lunch |
| 2:00 - 3:15 | Approximation 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:45 | Coffee |
| 3:45 - 5:00 | Abstraction 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:15 | Stretch break |
| 5:15 - 6:05 | Approximation 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:00 | Dinner |
| 8:00 | Bus departs for Pasadena |
Acknowledgment
We thank NSF and Adventium Labs for their generous support.
Adventium Labs