Departement Informatik, Universität Basel
Departement Informatik, Universität Basel
Departement Informatik, Universität Basel
Departement Informatik, Universität Basel

Colloquium - 01.06.2017

TitleThe Phase Transition in Heuristic Search
SpeakerProf. J. Christopher Beck (University of Toronto)
TimeThursday 1 June 2017, from 17:15 - 18:15 o'clock
LocationDepartment of Mathematics and Computer Science, Seminar Room 00.003, University of Basel, Spiegelgasse 1, Basel
Abstract

The Phase Transition in Heuristic Search

In the mid-1990s, it was observed, over many problem classes such as SAT and CSP, that the likelihood that a randomly generated problem instance has a solution transitions quickly from almost definitely one to almost definitely zero over a narrow range of a problem generation parameter. Furthermore, the observed computational difficulty peaked during this transition at a point where approximately half of the generated problems had a solution. This phenomenon has come to be known as the phase transition with the most popular example being seen in parameter of the clause-to-variable ratio of random SAT problems. Much empirical and theoretical work ensued with one result in the constraint programming community being an acknowledgement that numeric experiments should take into account the phase transition when generating suites of test problems for algorithm comparison.

While recent work in heuristic search has addressed problem difficulty for algorithms such as greedy best first search (GBFS), there has been very little work on whether the phase transition can be observed in heuristic search problems. In this work, we develop two problem generation models that admit a parameter that empirically leads to both the rapid transition between soluble and insoluble problems and the accompanying peak in search effort for GBFS. We show that the phase transition phenomenon has implications for work on problem difficulty in heuristic search including the comparison of heuristics, the impact of operator cost ratio, and the decision of whether to re-open nodes.

This is joint work with Eldan Cohen at the University of Toronto.

Bio: J. Christopher Beck is a Professor in the Department of Mechanical & Industrial Engineering at the University of Toronto. Chris' MSc and PhD degrees both come from the Department of Computer Science, University of Toronto, in the area of Artificial Intelligence. His research interests include scheduling, constraint programming, hybrid optimization techniques, mixed integer programming, AI planning, reasoning under uncertainty, and queueing theory. He has published over 100 papers in international journals and conferences in these areas.

Chris has served as the the President of the Executive Council for the International Conference on Automated Planning and Scheduling and held editorial responsibilities at the Journal of Artificial Intelligence Research, Constraints, the Journal of Scheduling, and the Knowledge Engineering Review. He has been the program chair or co-chair of the International Conference on Automated Planning and Scheduling, the International Conference on the Integration of AI and OR Technology in Constraint Programming, and, in 2017, the International Conference on the Principles and Practice of Constraint Programming.