KDiagnose is a collection of scripts and support programs which use the DLV system to compute a diagnosis of a plan execution discrepancy. More in detail, if a plan, i.e., a linear sequence A_0,...,A_n of actions for achieving a goal is executed, it might be discovered during execution that there is a discrepancy between the intermediate state, which is expected according to some "preferred" execution path, and the actual state reached. This might be due to non-deterministic action effects, or indeterminacy of the initial state. In such a case, an explanation of the discrepancy (which indicates an execution failure) is desired.
The paper "Diagnosing Plan Execution Discrepancies in a Logic-Based Action Framework" provides a formal notion of explanation in terms of a point of failure (k,S_k), which is intuitively the stage k closest to the current stage such that taking the respective action A_k in the plan (where the state of the world is S_k) leads to a deviation from preferred execution path(s). An example is given below. Such explanations are useful in the context of execution monitoring, for instance.
A generic algorithm for computing points of failures of plan execution
discrepancies on top of logic-based planners is described in the
report above. This algorithm has been implemented for the DLVK
planning system, which is incorporated into DLV, by Jan Senko. In this implementation, the expected or
desired execution paths are given either implicitly as solutions to
another planning problem, or explicitly as a set of trajectories.
The main script is called diagnose and employs binaries compute_diagnosis, plan_transform1, plan_transform2, state_transform. The shell-script and Linux/i386 binaries in the version of March 2005 can be downloaded here in .tar.gz format. (For installation notes refer to README file.)
This work is part of the project "Answer Set Programming for Reactive Planning and Execution Monitoring"
diagnose PLAN BACKGROUND PLAN STATE TRAJTYPE TRAJ [DIAGTYPE]
| PLAN | File which contains the planning problem described in language K (.plan extension required) | ||||||
| BACKGROUND | File which contains the background logic for the planning problem in Datalog language (.dl extension required) | ||||||
| PLAN | File which contains the plan to diagnose (syntax as in the output of DLV) | ||||||
| STATE | File which contains the state in which to compute diagnose (syntax as in the output of DLV) | ||||||
| TRAJTYPE |
Switch which selects how the preferred trajectories T should be generated:
| ||||||
| TRAJ | Used with previous switch | ||||||
| DIAGTYPE |
Switch which selects the mode of diagnosis:
|
| plan_transformX utilities convert the plan into K rules which enforce that the actions will be taken at the respective steps. | ||
| Original plan | plan_transform1 | plan_transform2 |
PLAN: a; noaction |
fluents: istime(X).
always: caused istime(A) after istime(B), issucc(A,B).
caused false after not a, istime(0).
caused false after not noaction, istime(1).
initially: istime(0).
| issucc(1,0). issucc(2,1). |
Suppose our world consists of 6 blocks - X, P, A, R, I, S. In the initial state, blocks X, A, I, S are on the table, block P is on A and block R is on I.
Our goal is having a tower of blocks P, A, R, I, S on the table and block X on the table. The state we are computing diagnosis for consists of tower of blocks P, R, I, S and two solitary blocks A and X on the table. The discrepacny here is clearly that the block A fell on the table instead of block R, and this is not in any of the preferred trajectories. The diagnosis should pinpoint that this discrepancy could have occured only on the timestamp 3. Formal description of the problem can be found in the Examples 3 to 6 in the technical report above.
We first describe the planning problem in file K.plan:
fluents: on(B,L) requires block(B), location(L).
occupied(B) requires location(B).
supported(B) requires block(B).
actions: move(B,L) requires block(B), location(L).
always: executable move(B,L) if not occupied(B), B <> L.
inertial on(B,L).
caused false if on(B,L), on(B,LL), L <> LL.
caused false if on(B,B).
caused occupied(B) if on(B1,B), block(B).
total on(B,L) after move(B,L1), B <> L, not occupied(L).
caused -on(B,L1) after move(B,L), on(B,L1), L <> L1.
caused supported(B) if on(B,table).
caused supported(B) if on(B,B1), supported(B1).
caused false if not supported(B).
caused false if on(B1,B), on(B2,B), block(B), B1 <> B2.
noConcurrency.
initially: on(x,table). on(a,table). on(p,a). on(r,i). on(i,table). on(s,table).
total on(X,Y).
goal: on(x,table), on(p,a), on(a,r), on(r,i), on(i,s), on(s,table)? (6)
The non-determinism of our planning problem is described using the total keyword, which
expands the number of models to all possible combinations of on and -on.
The file background.dl contains the background knowledge:
location(table) :- true. true. location(B) :- block(B). block(x). block(p). block(a). block(r). block(i). block(s).A feasible plan to reach this goal in six steps (which can be found using DLV) is as follows:
move(r,x); move(i,s); move(r,i); move(p,x) ; move (a,r); move(p,a)
To diagnose discrepancies of the execution of this plan, the file plan contains just one line with plan to diagnose:
PLAN: move(r,x); move(i,s); move(r,i); move(p,x) ; move (a,r); move(p,a)
The file state contains the current stage i and the state information S_i for which we want to check for a discrepancy and compute a diagnosis in case:
STATE 4: on(p,r), on(r,i), on(i,s), on(s,table), on(a,table), on(x,table)
In this example, we want to limit preferred trajectories to trajectories in which no block ends on the table during the execution. We describe this using the switch -add and the file T.plan:
always: caused false if on(B,table) after move(B,L).
home> diagnose K.plan background.dl plan state -add T.plan [o] Diagnosis shell script initiated. [o] Creating temporary files. [o] Temporary files created successfully. [o] Preferred trajectories defined by a constraint, calling DLV. [o] Preferred trajectories generated. [o] Generating evolutions of Match_PLAN function, calling DLV. [o] Evolutions generated. [o] Calling diagnosis subroutine. > State-oriented diagnosis enabled. > Scanned evolution of length 0..4 >> Looking at preferred trajectory 0, state #3: MATCH! >> Looking at preferred trajectory 1, state #3: MATCH! > Current point of failure: 3 > Scanned evolution of length 0..4 > Current point of failure: 3 > Scanned evolution of length 0..4 > Current point of failure: 3 Point of failure: 3 istime(3), occupied(a), occupied(i), occupied(s), on(x,table), on(p,a), on(a,table), -on(r,table), -on(r,x), -on(r,p), on(r,i), on(i,s), on(s,table), supported(x), supported(p), supported(a), supported(r), supported(i), supported(s) istime(3), occupied(a), occupied(i), occupied(s), on(x,table), on(p,a), on(a,table), -on(r,table), -on(r,x), -on(r,p), on(r,i), on(i,s), on(s,table), supported(x), supported(p), supported(a), supported(r), supported(i), supported(s)(The point of failure is duplicated because program found a MATCH! for each of two trajectories. It doesn't compare whether they are the same.)
Created and maintained by Jan Senko