SoCS 2019


Colocated Conference

Past SoCS Conferences
2018 Stockholm, Sweden
2017 Pittsburgh, PA
2016 Tarrytown, NY
2015 Ein Gedi, Israel
2014 Prague, Czechia
2013 Leavenworth, WA
2012 Niagara Falls, Canada
2011 Barcelona, Spain
2010 Atlanta, GA
2009 Lake Arrowhead, CA
2008 Chicago, IL

SoCS 2019: The 12th Annual Symposium on Combinatorial Search

Symposium Program

Program at a Glance

July 16

08:45 - 09:00: Opening
09:00 - 10:00: Invited Talk 1
10:00 - 10:30: Coffee Break
10:30 - 12:00: Session 1 (90 minutes)
12:00 - 14:00: Lunch Break
14:00 - 15:00: Session 2 (60 minutes)
15:00 - 16:30: Poster Session + Coffee Break
17:30 - 21:30: Wine Train (it takes about 30 minutes to walk there from the hotel)

July 17

09:00 - 10:00: Invited Talk 2 (an EurAI sponsored talk)
10:00 - 10:30: Coffee Break
10:30 - 12:00: Session 3 (90 minutes)
12:00 - 14:00: Lunch Break
14:00 - 15:30: Session 4 (90 minutes)
15:30 - 16:00: Coffee Break
16:00 - 17:30: Awards Ceremony + Community Meeting + Closing


On-line Proceedings of SoCS 2019:

Best Paper Awards

Best paper and best student paper award:

  • Shahaf S.Shperberg, Ariel Felner, Solomon Eyal Shimony, Nathan R. Sturtevant, Avi Hayoun
    Improving Bidirectional Heuristic Search by Bound Propagation

Best Paper Award - SoCS 2019 Best Paper Award - SoCS 2019
Best Paper Award - SoCS 2019 Best Paper Award - SoCS 2019

Detailed Program

July 16

8:30 - 8:45


8:45 - 9:00


9:00 - 10:00

Subbarao Kambhampati: Invited Talk 1
Synthesizing Explainable Behavior for Human-AI Collaboration

Chair: William Yeoh

10:00 - 10:30

Coffee Break

10:30 - 12:00

Session 1: Games, Puzzles, and Heuristics

Chair: Wheeler Ruml
  • Stefan Edelkamp
    Challenging Human Supremacy in Skat
  • Robert Clausecker, Alexander Reinefeld
    Zero-Aware Pattern Databases with 1-Bit Compression for Sliding Tile Puzzles
  • Chung-Yao Chuang, Stephen Smith
    Learning and Utilizing Interaction Patterns among Neighborhood-based Heuristics
  • Marco Verzeletti, Adi Botea, Marina Zanella
    Repairing Compressed Path Databases on Maps with Dynamic Changes
  • Majid Namazi, M. A. Hakim Newton, Abdul Sattar, Conrad Sanderson
    A Profit Guided Coordination Heuristic for Travelling Thief Problems
  • Santiago Franco, Alvaro Torralba
    Interleaving Search and Heuristic Improvement

12:00 - 14:00

Lunch Break

14:00 - 15:00

Session 2: Suboptimal and Bi-Directional Search

Chair: Ariel Felner
  • Robert C.Holte, Rubén Majadas, Alberto Pozanco, Daniel Borrajo
    Error Analysis and Correction for Weighted A*’s Suboptimality
  • Jingwei Chen, Nathan R. Sturtevant, William Doyle, Wheeler Ruml
    Revisiting Suboptimal Search
  • Shahaf S.Shperberg, Ariel Felner, Solomon Eyal Shimony, Nathan R. Sturtevant, Avi Hayoun
    Improving Bidirectional Heuristic Search by Bound Propagation
  • Edward Sewell, John Pavlik, Sheldon Jacobson
    An Improved Meet in the Middle Algorithm for Graphs with Unit Costs

15:00 - 16:30

Poster Session + Coffee Break

17:30 - 21:30

Wine Train

July 17

9:00 - 10:00

Torsten Schaub: Invited Talk 2 (an EurAI sponsored talk)
Answer Set Programming in a Nutshell

Chair: Pavel Surynek

10:00 - 10:30

Coffee Break

10:30 - 12:00

Session 3: Multi-Agent Path Finding

Chair: Daniel Harabor
  • Roni Stern, Nathan R. Sturtevant, Dor Atzmon, Thayne Walker, Jiaoyang Li, Liron Cohen, Hang Ma, T. K. Satish Kumar, Ariel Felner, Sven Koenig
    Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks
  • Alfonso E. Gerevini, Nir Lipovetzky, Nico Peli, Francesco Percassi, Alessandro Saetti, Ivan Serina
    Novelty Messages Filtering for Multi Agent Privacy-Preserving Planning
  • Roman Barták, Jiří Švancara
    On SAT-based Approaches for Multi-Agent Pathfinding with the Sum-of-Costs Objective
  • Liron Cohen, Tansel Uras, T.K. Satish Kumar, Sven Koenig
    Optimal and Bounded Suboptimal Multi-Agent Motion Planning
  • Dor Atzmon, Amit Diei, Daniel Rave
    Multi-Train Path Finding

12:00 - 14:00

Lunch Break

14:00 - 15:30

Session 4: Planning

Chair: Malte Helmert
  • Nils Froleyks, Tomas Balyo, Dominik Schreiber
    PASAR -- Planning as Satisfiability with Abstraction Refinement
  • Kalyan Vasudev Alwala, Margarita Safonova, Oren Salzman, Maxim Likhachev
    Intuitive, Reliable Plans with Contingencies: Planning with Safety Nets for Landmark-Based Routing
  • Tim Schulte, Bernhard Nebel
    Trial-based Heuristic Tree-search for Distributed Multi-Agent Planning
  • William Shen, Felipe Trevizan, Sam Toyer, Sylvie Thiebaux, Lexing Xie
    Guiding Search with Generalized Policies for Probabilistic Planning
  • Kai Fieger, Tomas Balyo, Christian Schulz, Dominik Schreiber
    Finding Optimal Longest Paths by Dynamic Programming in Parallel

15:30 - 16:00

Coffee Break

16:00 - 17:30

Awards Ceremony + Community Meeting + Closing

Chair: Pavel Surynek

The program is still subject to change.

Information for Speakers

  • Oral presentations of long papers are allocated 18 minutes: 15 minutes + 3 minutes of Q&A
  • Oral presentations of short papers are allocated 10 minutes: 8 minutes + 2 minutes Q&A

Poster Session

  • Chao Chi Cheng, Wheeler Ruml:
    Real-time Heuristic Search in Dynamic Environments
  • Pavel Surynek:
    Multi-agent Path Finding with Continuous Time Viewed Through Satisfiability Modulo Theories (SMT)
  • Thayne T. Walker, Nathan R. Sturtevant, Ariel Felner:
    Sub-Optimal Constraints in Conflict-Based Search
  • Ryo Kuroiwa, Alex Fukunaga:
    A Case Study on the Importance of Low-Level Algorithmic Details in Domain-Independent Heuristics
  • Haoze Wu, Raghuram Ramanujan:
    Learning to Generate Industrial SAT Instances
  • Narayan Changder, Samir Aknine, Animesh Dutta:
    An Improved Algorithm for Optimal Coalition Structure Generation
  • Alban Grastien:
    Brigitte, a Bridge-Based Grid Path-Finder
  • Hang Ma, Wolfgang Hönig, T. K. Satish Kumar, Nora Ayanian, Sven Koenig:
    Lifelong Path Planning with Kinematic Constraints for Multi-Agent Pickup and Delivery
  • Hang Ma, Daniel Harabor, Peter J. Stuckey, Jiaoyang Li, Sven Koenig:
    Searching with Consistent Prioritization for Multi-Agent Path Finding
  • Shahaf S.Shperberg, Ariel Felner, Nathan R. Sturtevant, Solomon Eyal Shimony, Avi Hayoun:
    Enriching Non-parametric Bidirectional Search Algorithms
  • Sabine Storandt, Stefan Funke:
    Algorithms for Average Regret Minimization
  • Jiaoyang Li, Daniel Harabor, Peter J. Stuckey, Hang Ma, Sven Koenig:
    Symmetry-Breaking Constraints for Grid-Based Multi-Agent Path Finding
  • Carlos Hernández Ulloa, Jorge Baier, William Yeoh, Vadim Bulitko, Sven Koenig:
    A Learning-Based Framework for Memory-Bounded Heuristic Search: First Results
  • Bence Cserna, Kevin C. Gall, Wheeler Ruml:
    Improved Safe Real-time Heuristic Search
  • Jiaoyang Li, Pavel Surynek, Ariel Felner, Hang Ma, T. K. Satish Kumar, Sven Koenig:
    Multi-Agent Path Finding for Large Agents
  • Van Nguyen, Philipp Obermeier, Tran Cao Son, Torsten Schaub, William Yeoh:
    Generalized Target Assignment and Path Finding Using Answer Set Programming
  • Pavel Surynek:
    Unifying Search-based and Compilation-based Approaches to Multi-agent Path Finding through Satisfiability Modulo Theories
  • Rotem Yoeli, Roni Stern, Dor Atzmon:
    Adversarial Multi-Agent Pathfinding
  • Ramkumar Natarajan, Muhammad Suhail Saleem, Sandip Aine, Maxim Likhachev, Howie Choset:
    A-MHA*: Anytime Multi-Heuristic A*
  • Nawal Benabbou, Thibaut Lust:
    A General Interactive Approach for Solving Multi-Objective Combinatorial Optimization Problems with Imprecise Preferences
  • Liat Cohen, Tal Grinshpoun, Roni Stern:
    Assigning Suppliers to Meet a Deadline
  • Jiaoyang Li, Eli Boyarski, Ariel Felner, Hang Ma, Sven Koenig
    Improved Heuristics for Multi-Agent Path Finding with Conflict-Based Search: Preliminary Results
  • Dor Atzmon, Ariel Felner, Roni Stern:
    Probabilistic Robust Multi-Agent Path Finding
  • Vidal Alcazar, Mike Barley, Pat Riddle:
    A Theoretical Comparison of the Bounds of MM, NBS and GBFHS
  • Rodrigo N.Gómez, Carlos Hernández, Jorge Baier:
    Compiling Multi-Agent Pathfinding to ASP

Information for Poster Presenters

Dimensions for posters should be within 40" x 60" (either orientation).

Copyright © 2019 Symposium on Combinatorial Search