Class of 3/6/2003 , Planning and learning methods in AI 

A discussion about compilation to IP (Integer Programming)  
IP is a very broad field that needs more amount of discussion, Basically IP involves solving problems with resource constraints where variables can take real values (rather than true or false) 

Converting a planning problem to IP actually does turn out to be faster to solve. There are 2 ways in which this can be done 

The first method can be used for any type of problem, For eg if it is a SAT encoding then we need to take each SAT clause and convert it into a IP clause Some improvement in speed is possible 
The second method is State Change Formulation - Combination of 2 ideas one of which is related to IP and another which works for all problems, the latter is removal of dependant variable. 

In any encoding (ie SAT/CSP/IP) if any 2 randomly generated problems are given, we need to know if it it is actually easier to solve one than the other . This fact can actually be harder to tell .We could look at either the number of variables or the number of constraints (Both of these are syntactic measures) . i.e. we could say that the CSP problem with the larger number of variables/constraints is harder to solve. But this isn't the right approach because hardness isn't directly related to the number of variables. 


Another approach would be to take the ratio of number of clauses with the number of variables. if we plot this ratio vs the time taken to solve randomly generated SAT/CSP problems, we find that in the left most part(ie where the above ratio is low)  the problems are very easy to solve . Also at the other end where the ratio is high the problems are still easy to solve in terms of time, but not because they actually get solved in less time but because they fail very soon due to hardness of the problem. 

This gives us a lesson that we need to look not just at the time taken to solve a problem but also at another measure called the probability of satisfaction. For the same example above, the probability of satisfaction of the former would be 1 and the latter would be zero. 

The above example(s) deals with randomly generated CSP problems but generally it is found that in terms of real world CSP problems, the number of variables is a fairly good indicator of hardness to solve. 

Solution Extraction from PG
 	SAT has variables corresponding to propositions and actions 

	Typically a proposition supports an action, which in turn supports another proposition. One might think of removing either the propositions or the actions while encoding in order to make the encoding more compact. This is called removal of dependant variables. 

In state change formulation that is mentioned above, removal of action variables is done. 

In case of IP we can reformulate the constraints by finding the weighted sum of all inequalities to give a single inequality. (Refer the slides for the example) 

This idea in IP is similar to the idea of resolution in SAT , ie if we have p V q, p v q v z and ~q v m V k, on resolving we get p v z V m V k . 

We need to understand that certain types of constraints are easier to write as IP than CSP/SAT and vice versa. To decide upon which combinatorial substrate to use we need to know the relative advantages of each and write down whichever  suits the problem. 

The primary  advantage / feature of IP is that it gives integer values to variables. so it can be used in metric temporal planning ie planning with resource constraints . 

comparative advantages of different encoding ( See slides for more info) 

CSP : 
	Supports implicit constraint representation 

ILP 
	Supports numerical inequalities , So optimization problems are best solved with IP

Whenever IP is used in planning problems either we set optimal function to constant and use it to reduce number of actions . 
If actions have non uniform costs and a shortest parallel plan is needed its harder to solve in CSP/SAT/GP  then IP because we first find a solution and the do further search to check if it is the best possible solution. ie we exhaust the search space . 

"What is the best way to find a cost optimal parallel plan " is still a open research problem. Graph plan finds optimal parallel plan but under the assumption that actions have same cost. Graph Plan needs more exhaustive search to actually make sure that its plan is optimal in terms of cost when actions with costs/duration are given. For such problems usually IP encoding is better. 

Writing certain constraints, as IP is sometimes batter than in CSP and the converse is also true; Two examples for these are as follows. 
N - ary mutex constraint : can be written by just adding them all up in IP whereas in CSP it is exponentially large. 

All Different Constraint(ie all propositions have to be assigned different actions, this is easier to write in CSP but exponential in IP) 

Notye: Equivalent of EBL's for IP: 
	Bendell's decomposition is a technique that is like a generalization of EBL in GP . 

Another factor to consider is the people who are going to be working in the problem, For people who are familiar with OR and Linear integer programming, find such constraints easier to write than propositional logic based constraints. 

Also more of research in finding faster solvers goes on in CSP/SAT rather than in IP. This could also be a deciding factor. 

LP relaxation: 
	A big issue in understanding IP problems is LP relaxation. LP relaxation means ignoring the integrality constraints in the IP problem,and then solving it. If the solution so obtained is optimal then we can say that the problem is solvable in polynomial time. We also saw earlier that constraint propagation in IP and finding weighted sum of constraints in IP are equivalent. Similarly LP relaxation in IP is equivalent to checking for inconsistency (gloabal constrint propogation), ie if there is no solution with relaxed constraints there is no solution at all. 


When to go for direct solution from Planning graph and when to use the various encodings? 

	The best bet would be to figure out the idea in the encoding method that makes it work fatser and then try to incorporate that into the planning graph solution extraction method . The main advantage in planning graph is that the reason to fail in level K can be learnt and used in subsequent levels, however this isn't possible in direct encoding methods as they have no notion of levels. 

About LPG: 
	LPG(Local  Search on planning graphs) is the latest planner which won the planning competition in 2002, , this planner does local search on planning graphs (i.e. without converting it into CSP or any other encoding) . It extends the planning graph, and it was found to do better than graph plan and also better than heuristic based planners. 

A question asked is what exactly is graph plan buying us when compared to direct encoding methods? The answer would be " directed partial consistency enforcement" . Three types of proof are progression regression and causal proof. Each proof can also have its own encodings like SAT CSP, etc . (See the class notes slide on naïve encoding, state based proof and causal  proofs) 

Basically what they say is that PG does consistency enforcement and mutexes on naïve encoding structure ie it's a refinement on naïve encoding. For state based proof regression is better than forward proof in typical problems.