Solving Optimal CSPs Through Generate and Test Leading Candidates Generate Conflict-directed A* Based on Cost Candidate Test Incremental Sat Candidate Yes Keep Consistent Extract Conflic (Optional) Update Cost Donekres No Threshold 3/17/2004 copyright Brian Williams, 2002 Outline Optimal csps Review of a Conflict-directed A Generating the Best Kernel Intelligent Tree Expansion EXtending to Multiple Solutions Performance Comparison copyright Brian Williams, 20023/17/2004 copyright Brian Williams, 2002 9 Solving Optimal CSPs Through Generate and Test Generate Candidate Test Candidate Keep Consistent? (Optional) Update Cost Below Threshold? Extract Conflict Done Yes No Yes No Leading Candidates Based on Cost Conflict-directed A* Incremental Sat 3/17/2004 copyright Brian Williams, 2002 10 Outline • Optimal CSPs ƒ Review of A* ƒ Conflict-directed A* ƒ Generating the Best Kernel ƒ Intelligent Tree Expansion ƒ Extending to Multiple Solutions ƒ Performance Comparison