The2008ClassicPaperAward: SummaryandSignificance Peter F

"Solving Large-Scale Constraint Satisfaction and Scheduling Problems Using a Heuristic Repair Method," by Steve Minton, Mark Johnston, Andy Phillips, and Phil Laird clearly achieved both. It proved that local search and repair was applicable to a wide class of constraint-satisfaction problems and clearly explicated the theory behind that proof. The work epitomizes the guiding philosophy of that laboratory: AI research can simultaneously advance the state of the art and provide practical solutions to key problems faced by the Space Agency and its collaborators. Minton and colleagues developed a heuristic repair method, called "min-conflicts" for solving large-scale constraint-satisfaction problems (CSP), with a particular focus on massive scheduling tasks. Mark Johnston, an astronomer and computer scientist from the Space Telescope Science Institute at Johns Hopkins, served simultaneously as domain expert and codeveloper.