Navigation


SoCS 2012


Related Conferences


Past SoCS Conferences
2011 Barcelona, Spain
2010 Atlanta, GA
2009 Lake Arrowhead, CA
2008 Chicago, IL


SoCS 2012: The Fifth Annual Symposium on Combinatorial Search

Accepted Papers

Original Full-length Papers
Guni Sharon, Roni Stern, Ariel Felner and Nathan Sturtevant. Meta-agent Conflict-Based Search For Optimal Multi-Agent Path Finding
Jordan Thayer, J. Benton and Malte Helmert. Better Parameter-free Anytime Search by Minimizing Time Between Solutions
Bo Pang and Robert Holte. Multimapping Abstractions and Hierarchical Heuristic Search
Roni Stern, Ariel Felner and Robert Holte. Search-aware Conditions for Probably Approximately Correct Heuristic Search
Jordan Thayer, Roni Stern and Levi Lelis. Are We There Yet? -- Estimating Search Progress
Priyankar Ghosh, Partha Chakrabarti and Pallab Dasgupta. Execution Ordering in AND/OR Graphs with Failure Probabilities
Jarad Cannon, Kevin Rose and Wheeler Ruml. Real-time Motion Planning with Dynamic Obstacles
Neil Burch and Robert Holte. Automatic Move Pruning Revisited
Hootan Nakhost and Martin Mueller. A Theoretical Framework for Studying Random Walk Planning
Christopher Wilt and Wheeler Ruml. When does Weighted A* Fail?
Xi Yun and Susan Epstein. Adaptive Parallelization for Constraint Satisfaction Search
Silvan Sievers, Manuela Ortlieb and Malte Helmert. Efficient Implementation of Pattern Database Heuristics for Classical Planning
Sergio Nunez, Daniel Borrajo and Carlos Linares Lopez. Performance analysis of planning portfolios
Qandeel Sajid, Ryan Luna and Kostas Bekris. Multi-Agent Pathfinding with Simultaneous Execution of Single-Agent Primitives
Ron Alford, Vikas Shivashankar, Ugur Kuter and Dana Nau. HTN Problem Spaces: Structure, Algorithms, Termination
Christer Backstrom and Peter Jonsson. Abstracting Abstraction in Search II: Complexity Analysis
Michael Rice and Vassilis Tsotras. Bidirectional A* Search with Additive Approximation Bounds
Ethan Burns, Michael J. Leighton, Matthew Hatem and Wheeler Ruml. Implementing Fast Heuristic Search Code
Marco Lippi, Marco Ernandes and Ariel Felner. Efficient Single Frontier Bidirectional Search


Original Short Papers
Tomas Balyo, Roman Bartak and Pavel Surynek. On Improving Plan Quality via Local Enhancements
Scott Kiesel, Ethan Burns and Wheeler Ruml. Abstraction-guided Sampling for Motion Planning
Richard Valenzano, Shahab Jabbari Arfaee, Jordan Thayer and Roni Stern. Alternative Forms of Bounded Suboptimal Search
Akihiro Kishimoto, Rong Zhou and Tatsuya Imai. Diverse Depth-First Search in Satisificing Planning
Levi Lelis, Shahab Jabbari Arfaee, Sandra Zilles and Robert Holte. Learning Heuristic Functions Faster by Using Predicted Solution Costs
Meir Goldenberg, Ariel Felner, Roni Stern and Jonathan Schaeffer. A* Variants for Multi-agent Pathfinding
Erion Plaku. Motion Planning with Differential Constraints as Guided Search over Continuous and Discrete Spaces
Gabriele Roger and Malte Helmert. Non-optimal Multi-Agent Pathfinding is Solved
Chonhyon Park, Jia Pan and Dinesh Manocha. Real-time Optimization-based Planning in Dynamic Environments using GPUs
Carlos Hernandez Ulloa, Jorge Baier, Tansel Uras and Sven Koenig. Repeated A* runs faster than D*Lite in most Navigation Tasks in Grid-Like Unknown Terrain (Position Paper)
Glenn Wagner, Howie Choset and Nora Ayanian. Subdimensional Expansion and Optimal Task Reassignment


Short Versions of Papers Published Elsewhere
Levi Lelis, Roni Stern, Ariel Felner, Sandra Zilles and Robert Holte. Predicting Optimal Solution Cost with Bidirectional Stratified Sampling
Guni Sharon, Roni Stern, Ariel Felner and Nathan Sturtevant. Conflict-Based Search For Optimal Multi-Agent Path Finding
Paul Vernaza, Venkatraman Narayanan and Maxim Likhachev. Efficiently finding optimal winding-constrained loops in the plane
Carlos Hernandez, Jorge Baier, Tansel Uras and Sven Koenig. Time-Bounded Adaptive A*
Mike Phillips, Benjamin Cohen, Sachin Chitta and Maxim Likhachev. E-Graphs: Bootstrapping Planning with Experience Graphs
David Tolpin and Solomon Eyal Shimony. MCTS Based on Simple Regret
Ariel Felner, Meir Goldenberg, Guni Sharon, Roni Stern, Tal Beja, Nathan Sturtevant, Robert Holte and Jonathan Schaeffer. Partial-expansion A* with Selective Node Generation
Alex Fukunaga, Akihiro Kishimoto and Adi Botea. Iterative Resource Allocation for Memory Intensive Parallel Search Algorithms on Clouds, Grids, and Shared Clusters
Pavel Surynek. A SAT-Based Approach to Cooperative Path-Finding Using All-Different Constraints


Short Papers on Grid-based Path Planning Competition (GPPC)
Alvaro Parra, Alvaro Torralba and Carlos Linares Lopez. Precomputed-direction Heuristics for Suboptimal Grid-based Path-finding
Adi Botea. Fast, Optimal Pathfinding with Compressed Path Databases
Jose Guivant, Brett Seton and Mark Whitty. 2D Path Planning based on Dijkstra's Algorithm and Pseudo Priority Queues
Daniel Harabor and Alban Grastien. The JPS Pathfinding System
Ken Anderson. Tree Cache
Ioannis Papikas and Ioannis Refanidis. Fast Path Planning through Segmentation of the Map into Manhattan-cohesive Areas
Tansel Uras, Sven Koenig, Carlos Hernandez. Subgoal Graphs for Eight-Neighbor Gridworlds