ENCODING BASED ON CAUSAL PROOFS: ================================== Variables and constraints: =========================== Each partial order step is mapped to exactly one action. Such mapping constitues a variable, i.e. Si=A1 A constraint would be for example: ~(Si=A1 and Si=A2), that is Si cannot be equal to both A1 and A2. There is a solution, when all top level goals are satisfied. Which ever action supporting the top level goal we pick, its preconditions must be satisfied. If these conditions are to be satisfied, we have a causal link. If we have a set of causal links, we can write a set of constraints. If all of these constraints are satisfied, it will correspond to a valid plan. Looking for a valid assignment, for a plan is called model finding. Writing an incomplete list of constraints may result in assignment that does not correspond to a valid plan. Writing too many constraints may result in missing an assignment corresponding to a valid plan. Bidirectional proof guarantees that all constraints have been written. A bidirectional proof says that every assignment is a solution to a problem and every solution to a problem corresponds to a valid assignment. Types of variables: ==================== 1. Assignemnts: Si=Aj => Adds(Si,Pa) & Needs(Si,Pp) & Deletes(Si,Pd). Every step Si is assigned to exactly one Action Aj. It inherits all of this action's adds, needs and deletes. 2. Add: Adds(Si,Pa) => Si=Aj v Si=Ak, meaning that actions Aj, Ak add predicate Pi to step Si 3. Delete: Deletes(Sj,Pb), which includes assignment of all actions that delete Pb from step Sj 4. Need: Needs(Si,Pj) => Estab(S1,Pj,Si) v Estab(S2,Pj,Si), meaning that step Si needs Pj, and Pj was established either by S1 or S2 (that is Pj came from S1 or S2) 5. Establishment: Estab(S1,Pj,Si) => Link(S1,Pj,Si), meaning that if S1 supports Pj to Si, then there is a causal link from S1 supporting Pj to Si 6. Link: (Si,Pj,Sk) => Adds(Si,Pj) & Precedes (Si,Sk), meaning that Pj was added to step Si and step Si preceded step Sk 7. Preced: Link(Si,Pj,Sk) & Deletes(Sm,Pj) => Precedes(Sm,Si) v Precedes(Sk,Sm). If there is a causal link that supports Pj from Si to Sk, then no other step Sm that deletes Pj can come between Si and Sk. Sm has to be either scheduled before Si or after Sk. Precedence is: a) irreflexive - step Si does not preceed itself b) asymmetric - if Si preceds Sj, then Sj does not precede Si c) transitive - if Si preceds Sj and Sj preceds Sk, then Si preceds Sk A step is bound to an action and it inherits all of action's needs, adds and deletes. For exapmle if Si=Aj, then if Sj needs Pk, Si needs Pk too. If Aj deletes Pk, Si deletes Pk as well. Counting number of variables and constraints: ============================================== n = number of steps m = number of actions l = number of literals There are O(n*m) variables and O(n) constraints to say that each step is bound to some action and O(n * mC2) constraints saying that no step can be bound to two actions at the same tiem. Adds, Deletes and Needs yield 3 * n * l variables. Link yields n^2 * l variables Precedence yields n^2 variables Overall variables: O(n^2) Total number of constraints: O(n^3) Causal encoding ends up having more constraint and variables than state-based encoding. Regression encoding is the smallest size from the ones we looked at. The less variables and constraint the encoding has, the easier and smaller it is. There are ways of decreasing the number of constraint and variables: Reducing size of the Causal encoding ============================== 1. White-knight based establishment: Establishement variables can be written in terms of adds and preceds. For every preceding step that deletes needed predicate, there is a white-knight (another step) that adds it back. Such white knight is inserted between a step that deletes the predicate and step that needs it. This approach eliminates a need for O(n^2) causal link variables in link based establishment. 2. Contiguity based precedence: A smaller set of precedence variables can substitute a larger set of O(n^3) transitivity clauses. If we go a step further and start thinking in terms of steps having a particular position, rather than being described by precedence, the encoding starts looking like a regression proof. General ideas for simplifying any encoding ============================== 3. Literal elimination: If a particular literal occurs in all constraints with the same polarity (either always true or always false), we can reduce the number of constraints. For example if P is always true, and we have a constraint: P v Q v R, the constraint will always be true, so we can get rid it. If on the other hand P does not occur at all, we can set it to true and not concern ourselves with it. 4. We can get rid of establishment variables and use directly link variables. Whenever there are dependencies between variables, we can remove dependency variables. We can consider one as always independent and the other one as dependent. 5. We can split an n-ary relation into n 1-ary relations. Let's say we have a n-ary relation, i.e. xyz actions that can occur anywhere in k positions in the encoding and must be done together. In other words we have action xyz1, action xyz2, ... action xyzk. Instead of writing them as variables, we can write them as constraints. The increase in number of constraints will be smaller than decrease in number of variables. Lifting - writing original constraints in terms of variables. For example instead of writing: deletes(Sd,clear(A)), we can write: deletes(Sd,clear-X), where X is a variable. Then we can write constraints on that variable X. Even though graphplan-based encodings are better than backward-proof encodings (due to mutex propagation), proof based encodings are useful for unusual problems, where we don't yet have established effective method of mutex propagation. Finding a plan might be more costly and harder, but at least we will be able to find a solution using proof-based encoding. KNOWLEDGE-BASED PLANNING =========================== Search algorithms using domain knowledge are more informed and can solve problems better (faster, more optimal). There are two ways in which domain knowledge can be obtained: by acquiring external expert knowledge or automatically by learning from mistakes. We will concentrate on external knowledge. External knowledge makes search algorithm more informed but it also narrows down the number of problems that can be solved with this knowledge. Domain specific planners may solve a set of problems from specific domain better than a general planners, but general planners can solve wider variety problems. An example of an external knowledge for travel logistics might be: "take bus only if taxi is not available", or in general: "if you take action a1, it is a good idea to take action a2 as well". It's hard to draw a line between cheating and using avaiable knowledge. There is a middle ground between abusing available knowledge and not wanting to accept any external knowledge at all. It is sometimes hard to say how much of domain knowledge is naturally available and how much of it is provided externally. For example in the blocks-world example, if we want to move a block to a particular position, that is say 5 squares away (if we are thinking grid-wise) we can do it in one move, instead of advancing the block square by square to achieve the final position in 5 moves. It can be viewed as being intuitive and natural, or it can be viewed as an external piece of information. There is also a problem with responsibility for plan failing because of a defective knowledge or defective knowledge control (how the knowledge is used). Who exactly is responsible for a plan failure? On the other hand, if one planner A performed better than planner B, does it mean that its domain knowledge was better defined, or that it was able to use the existing knowledge better?