SoCS'11 is the Fourth installment of the The International Symposium on Combinatorial Search. Heuristic search and other forms of combinatorial search are currently very active areas of research in Artificial Intelligence, Robotics, Planning and other areas of Computer Science. The International Symposium on Combinatorial Search (SoCS) is meant to bring researchers in such areas together to exchange their ideas and cross-fertilize the field. Topics of Interest SoCS is targeting researchers and submissions in all fields that use combinatorial search, including artificial intelligence, planning, robotics, constraint programming, operations research and bioinformatics. Overall, the main focus of SoCS is on the design of novel heuristic search methods, analysis of existing heuristic search methods and their applications. More specifically, topics of interest include but are not limited to the following: Analysis of search algorithms Automated synthesis of lower bounds Bounding and pruning techniques Combinatorial puzzles 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 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 trade-offs Special Scope This Year: Search in Robotics SoCS-2011 will include a special session covering search in robotics. Heuristic search has been used to solve effectively a number of challenging planning problems in robotics. Furthemore, planning problems in robotics present a number of research challenges that are frequently absent in classic planning problems. We invite all researchers who use search in robotics to participate and/or submit their work to SoCS-2011. In particular, we are interested in position papers covering the relationship between these fields.