--------------------------------------------------------------------------------
Note on March 1 Class. Note taker: Son Cao Tran
Notes revised and augmented by Romeo 
Last paragraphs written by BinhMinh.
--------------------------------------------------------------------------------

* Term paper/project: select a topic and get appointment to talk 
about your term paper/project asap! Possible topics are listed in 
Rao's email. 

* Topics of the day: DDB and EBL


DDB and EBL are two techniques that can be applied under the independent framework of refinement search, either in constraint satisfaction problems or planning for example. Both of them depend of the theory of explaining search failures and doing regression based on those explanations to higher levels in the search tree.

There are many search techniques: systematic search (exhaust search), local search (not always exhaust all possibilities), prioritized search (priorities are used in selecting branches), etc.

Usually, we start with an empty solution and construct a search tree whose nodes contain partial assignments to the variables of the problem. A solution to the problem is a complete assignment for all the variables, which does not violate any constraint. A node containing a solution to the problem is called a success node. So, under this assumption in DDB&EBL you give an explanation of failure for a particular node, specifying which are the possible partial assignments that violate a constraint. Basically, explanation of failure is a subset of constraints for a node, which together with the set of constraints of the problem will help you to derive falsity (such that you can avoid doing unnecessary search).


Check article "On the relations between intelligent backtracking and ..." given by Dr. Rao (fig 3. Page 167).


In what follows, I denote a search tree with nodes N1, N2, ... Nm. For simplicity, I assume that the assignments which we are interested in are of the form x = C (variable x is assigned the value C). The partial assignments at node Ni will be denoted by P(Ni). An assignment A2 is called a completion of an assignment A1, denoted by A1 < A2, if every assignment of the form x = C in A1 is contained in A2. Following this logic in figure 3 (page 167 of article) N3 is a completion of N2. An assignment A is complete if for every variable x of the problem, there is an assignment x = C for some values C from the domain of x.

In doing an assignment at a node Ni we can consider: 

     (a) Create new branches to the node with children Ni+1, ...,Ni+2,..., 
         where P(Ni) < P(Ni+k) for k=1,...n values of the new variable being 
   assigned.
     (b) Regress from Ni if P(Ni) violates a constraint
         or        

     (c) If no children for Ni (no more values and variables left to assign) 
	   and no constraints violated, then success.

If (b) happens, Ni is called a failure node.
 
As we can see, there are two sources of conflict:

     (1) The node contains an assignment conflicting with the constrains of 
         the problem. 
     (2) None of its children leads to a successful node.

If (2) happens we can conclude that the partial assignment at the node also represents a constraint which should be avoided. Remember this constraint (added to the constraint set) could help reducing the search in paths of the tree containing the same label, such that we can prune those branches as soon as we detect the failure. EBL basically remembers this new kind of constraints such that the next time you do not have to rediscover the failure.
 
However, we should identify the minimal set of assignments that causes the conflict. The reason for this minimally is that the smaller the conflict set is the more nodes we can prune during the search, and hence, improves the efficiency. Furthermore, remembering the full assignment is identical to "Chronological backtracking" which is known for its bad efficiency. 
This minimal set of assignments that causes the conflict is detected and stored as the failure explanation of the node. Then, you backtrack this explanation of failure over the tree until it changes. There is no reason to go to nodes in the tree where this explanation does not change since you still have your failure (notion of regression). If not possible assignment can be made then you want to remember the explanation of failure that led us to this dead end. As we said before this new constraint is learned with the set of constraints of the problem such that the next time we do not make the same mistake (this new constraint is called interior node failure explanation).

Basically, we have three main notions: notion of regression, notion of interior node failure explanation and notion of remembering.

Note 1: if consistency is checked at every expansion of the tree and a conflict is detected after one expansion, then the conflict set must contain the last assignment.

Note 2: Remembering a constraint after learning it is good but should be done with discretion. On one side the set of constraints is the deductive closure of the constraints of the problem. On the other side, searching through a large constraint set could also be costly.

EBL for across problems: one can also remember the rules in the background knowledge that causes failure. A learned constraint set can be used in solving another problem.

As discussed in note 2, the number of constrains also plays an important role in the search performance. Thus, keeping a reasonable number of constraints in memory is an important issue. 

Also of importance is that the size of the constraint (size-based EBL).
The bigger the size of a constraint, the less possible it will be used.
On the search tree, smaller size constraints can be used to prune nodes at higher levels of the tree (near to the root).

There are some issues that arise from these techniques, for example, what happens if one assignment gives multiple explanation of failures? One idea is to store the smallest explanation of failure, another idea is to pick the explanation of failure that guides you to the highest nodes in the tree, and the last idea is to use the biggest one.

We have a problem in storing the explanation of failures, which is linear memory in increasing constraints. So, how many should be remembered? What is the policy to store the explanation of failures? There are different approaches that we can consider:

- Remember a default number of explanation of failures (constant).
- Remember the explanation of failures more used.
- Remember the explanations that in the past led you to big improvements in the search.

Another kind of approach is called "Syntactic approach": 
- Do not have a limit in the number of explanations you can store, but do have some properties that need to be satisfied. For example: Do not remember explanations with more than "x" constraints involved.

 
*Relevant-based learning: (Written by Binhminh)

Given that remember all the nogoods of arbitrary sizes is impractical, 
due to the memory blowup, and the cost of checking. There are two
dominant methods in selecting which nogoods to remember. The first one 
mentioned above is size-based, which limit the maximum size of no-good
to remember. However, even if we remember nogoods of smaller size,
there is still a great chance that we will remember many useless
nogoods (in the sense that they will never be used again), and
checking again those nogoods take time too. Knowing this drawback, in
the relevance-based EBL, we only remember nogoods which are "relevant" 
to current search branch, and throwaway all nogoods which are
Not relevant. So, what is the definition of "relevant"? Suppose that
the current search branch has n variables assigned, and a specific
no-good (which is a set of compound labels) is matched with current
branch by m label, and different by l labels. In the relevant-k EBL,
we will throw out that specific no-good if k < l, and keep all nogoods
with l < k. In this method, we sacrify the time of bookkeeping to get
the benefit of less checking again non-relevant nogoods. Note that
when the no-good is first memorized, l = 0.

Dynamic directed backtracking: (Written by Binhminh)

In the class, Rao rarely mention about DDB, so it may confuse a little 
bit about what's DDB. DDB stand for Dependency Directed Backtracking,
which is the technique that makes use the conflict set to direct
the backtracking. Actually, in Rao's example in the class, he had demonstrated how DDB work (when we backtrack to variable y and skip v, based on the conflict set (x=a, y=b)). So why we normally always stick DDB, and EBL together? Because they both make use of the conflict set, but in different ways. When we find the conflict set (firstly) at the leave nodes, and propagate them upward to the interior nodes, we can make  use of conflict sets in two different ways:
* Use it to direct the backtracking to the "nearest" variable that
participate in the conflict set. This is DDB (or CBJ: Conlict-directed 
BackJumping). In the example, we have to jumpback to y=a, which is
nearest to w in the search tree.
* Remember it so we can prune any latter come search branch that
contain that conflict set. In our example, whenever we have a search
branch that contain (x=a,y=b), then we can prune that branch right
away.

Note that if we only want to do DDB, then we don't need to remember
(x=a,y=b) as the conflict set at node w, but (x,y) is
enough. However, if we want to do EBL, then we have to remember
(x=a,y=b).

As Rao mention in the class, DDB, EBL are "lazy" techniques, where we
find the extra constraints when the failure occur, while constraint
propagation finds extra constraints up-front. DDB, EBl normally be used 
in conjunctive with some "eager" techniques like forward-checking,
arc-consistency and so on. It's worthy to notice that if you combine
with techniques like forward-checking, arc-c..., then DDB&EBL will work a little 
differently (technical). For example, in our example, if we use DDB&EBL 
with forward-checking, then the place we find (x=a,y=b) as the
conflict set will be at (y=b) but not at the place when we try to
assign w. Moreover, if we use DDB&EBL alone, then remember (x=a,y=b)
is good, but if we use with forward-checking, then remember that one
will be of useless. Why?? :-))