Conflict-directed A* Increasing Cost Conflict 1 Infeasible ○ Conflict 2 Feasible 3/17/2004 opyright Brian Williams, 2002 Conflict-directed A* Increasing Cost Conflict 1 Infeasible Conflict 2 Feasible copyright Brian Williams, 2002
3/17/2004 copyright Brian Williams, 2002 21 Increasing Cost Feasible Infeasible Conflict 2 Conflict 1 Conflict-directed A* 3/17/2004 copyright Brian Williams, 2002 22 Increasing Cost Feasible Infeasible Conflict 2 Conflict 1 Conflict-directed A*
Conflict-directed A* Increasing Cost Conflict 1 Infeasible ○ Conflict 2 Feasible 3/17/2004 opyright Brian Williams, 2002 Conflict-directed A* Increasing Cost Conflict 1 Infeasible oO Conflict 2 Feasible copyright Brian Williams, 2002
3/17/2004 copyright Brian Williams, 2002 23 Increasing Cost Feasible Infeasible Conflict 3 Conflict 2 Conflict 1 Conflict-directed A* 3/17/2004 copyright Brian Williams, 2002 24 Increasing Cost Infeasible Conflict 3 Conflict 2 Conflict 1 Conflict-directed A* Feasible
Conflict-directed A* Function Conflict-directed-A"(OCSP returns the leading minimal cost solutions Conflicts[ocs月←吾 OCSP+ Initialize-Best-Kernels(OCSP) Solutions[OCS月← loop do decision-state Next-Best-State-Resolving-Conflicts(OCSP) if no decision -state returned or Terminate?(OCSP) then return Solutions[OCSPl if Consistent? (CSP[OCSP], decision-state) then add decision-state to Solutions[OCSP] new-conflicts <-Extract-Conflicts(CSP[OCSP], decision-state) Conflicts[OCSPI <Eliminate-Redundant-ConflictsConflicts[OCSP]U new-conflicts) nd 3/17/2004 copyright Brian Williams, 2002 Conflict-directed A* Function Conflict-directed-A"(OCSP returns the leading minimal cost solutions Conflicts[OCS月← OCSP+Initialize-Best-Kernels(OCSP) Solutions[OcsF←鲁 oop do decision-state Next-Best-State-Resolving-Conflicts(OCSP) if no decision-state returned or Terminate? (OCSP) then return Solutions[OCSPI if Consistent? (CSP[OCSP ], decision-state then add decision-state to Solutions[OCSP new-conflicts < Extract-Conflicts(CSP[OCSP], decision-state) Conflicts[OCSP fEliminate-Redundant-Conflicts(Conflicts[OCSP]u new-conflicts) d copyright Brian Williams, 2002
3/17/2004 copyright Brian Williams, 2002 25 Conflict-directed A* Function Conflict-directed-A*(OCSP) returns the leading minimal cost solutions. Conflicts[OCSP] ← {} OCSP ← Initialize-Best-Kernels(OCSP) Solutions[OCSP] ← {} loop do decision-state ← Next-Best-State-Resolving-Conflicts(OCSP) if no decision-state returned or Terminate?(OCSP) then return Solutions[OCSP] if Consistent?(CSP[OCSP ], decision-state) then add decision-state to Solutions[OCSP] new-conflicts ← Extract-Conflicts(CSP[OCSP], decision-state) Conflicts[OCSP] ← Eliminate-Redundant-Conflicts(Conflicts[OCSP] ∪ new-conflicts) end 3/17/2004 copyright Brian Williams, 2002 26 Conflict-directed A* Function Conflict-directed-A*(OCSP) returns the leading minimal cost solutions. Conflicts[OCSP] ← {} OCSP ← Initialize-Best-Kernels(OCSP) Solutions[OCSP] ← {} loop do decision-state ← Next-Best-State-Resolving-Conflicts(OCSP) if no decision-state returned or Terminate?(OCSP) then return Solutions[OCSP] if Consistent?(CSP[OCSP ], decision-state) then add decision-state to Solutions[OCSP] new-conflicts ← Extract-Conflicts(CSP[OCSP], decision-state) Conflicts[OCSP] ← Eliminate-Redundant-Conflicts(Conflicts[OCSP] ∪ new-conflicts) end
Conflict-directed A* Feasible subregions described by kernel assignments E Approach: Use conflicts to search for kernel assignment containing the best cost candidate Increasing Cost Conflict 1 Infeasible Conflict 2 Feasible Kernel 3 Kernel I Kernel 2 3/17/2004 opyright Brian Williams, 2002 Conflicts Kernels for Optimal CsPs 12 M3 Conflict: A set of decision variable assignments that are inconsistent with the constraints Constituent Kernel: An assignment A that resolves a conflict C A entails口-C Kernel: A minimal set of decision variable assignments that resolves all known conflicts copyright Brian Williams, 2002
3/17/2004 copyright Brian Williams, 2002 27 Increasing Cost Infeasible Conflict 3 Conflict 2 Conflict 1 Conflict-directed A* • Feasible subregions described by kernel assignments. Ö Approach: Use conflicts to search for kernel assignment containing the best cost candidate. Kernel 1 Kernel 2 Kernel 3 Feasible 3/17/2004 copyright Brian Williams, 2002 28 Conflicts & Kernels for Optimal CSPs Conflict: A set of decision variable assignments that are inconsistent with the constraints. Constituent Kernel: An assignment A that resolves a conflict C. A entails ¬ C Kernel: A minimal set of decision variable assignments that resolves all known conflicts. M1 M2 A1 A B C D E 3 2 2 3 F G X Y Z 10 6 6 12 M3 A2 ? 3 ? 2 2 3 3 M1 M3 A1 A B C D E F G X Y Z 10 12 ?