0
$\begingroup$

Can somebody explain me how can I join forward checking with conflict directed backjumping in my CSP solver? I understand that when the consistency fails when I add a value to a variable, I should save all the instantiated variables of the restriction that fails, on the conflict set of the variable to which I gave a value. But what happens when there's no consistency failure but when I'm doing the inferences of the forward checking I found a contradiction? Do I need to know which restrictions failed and add the variables to the current variable conflict set?

My current approach:

My function that solves the CSP is recursive. So right now I'm doing the following, for each the current variable (the one I'm in the recursive step) I'm checking if the value that I give to her is consistent, if not, I add all the attributed variables of the restriction that fails to the conflict set of this variable. When I'm backjumping in the recursivity, I return this conflict set, and if any variable is contained in this set, it will try to change his value. (this implements the basic backjumping and with some other small changes I put my algorithm using conflict directed backjumping). I tested this part and it's working.

Now, when I add the forward checking, I need to get from the forward checking some informations when it finds contradictions (and this is the problem). Right now, I'm getting the variable where the contradiction occurs and all the attributed variables related to restrictions that failed.

Is this all the infromation I need from the backjumping?

$\endgroup$

closed as unclear what you're asking by jmite, David Richerby, R B, András Salamon, Kaveh Jan 3 '15 at 8:30

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    $\begingroup$ Cross-posted to computer science, CS Theory and Stack Overflow. Please do not do this. It is against site policy because it fragments answers and it wastes people's time when they work on a question that's already been answered somewhere else. $\endgroup$ – David Richerby Nov 28 '14 at 9:48
  • $\begingroup$ I don't know if this gives enough context to be answerable. (It sure does not for me, but I'm no AI expert.) $\endgroup$ – Raphael Nov 28 '14 at 10:31
  • 2
    $\begingroup$ Maybe give a bit more context, and precise references. The question can be longer. As it is, I tried to improve a bit the syntax, but I could not be sure of what you intended to say. I guess this is the context. If I am right, you could add it to your question. Maybe there is more. $\endgroup$ – babou Nov 28 '14 at 10:51
  • $\begingroup$ Generally speaking, LA or FC is just an inference task that you can use in any search algorithm (i.e. CBJ). So in your search algorithm, if you got a room to do inference when you initialize a variable, do FC and detect inconsistencies (zero domain size). $\endgroup$ – seteropere Nov 28 '14 at 19:02
  • $\begingroup$ @seteropere My problem is what information do I need to send on the backjumping when I find a contradiction. Also, my algorithm is recursive. I updated my post with some more information. $\endgroup$ – Luis Alves Nov 28 '14 at 20:04
3
$\begingroup$

If forward checking detects that the potential assignment of a variable $x_1$ leaves no valid assignments for the variable $x_2$, one simple strategy is to just make the assignment to $x_1$ and then queue $x_2$ as the next variable to be assigned. When the assignment of $x_2$ inevitably fails, your backjumping machinery will do what it always does and you need not code any special information gathering related to forward checking. In the meantime, you've saved all the time that would have been wasted doing (and undoing) a potentially exponential number of unrelated assignments that do nothing to resolve the inevitable conflict between $x_1$ and $x_2$.

$\endgroup$
  • $\begingroup$ Thanks for the answer, I'll try to implement it. Btw, can I use the same approach to implement no-goods? $\endgroup$ – Luis Alves Nov 29 '14 at 18:31
  • $\begingroup$ Yes. The conflict analysis needed for backjumping naturally yields one or more CNF clauses that can be added to the formally as nogoods. $\endgroup$ – Kyle Jones Nov 29 '14 at 18:50
  • $\begingroup$ Btw do I need to add to the conflict set of a variable anything from the forward checking? $\endgroup$ – Luis Alves Nov 30 '14 at 19:22

Not the answer you're looking for? Browse other questions tagged or ask your own question.