KDiagnose - A Tool for Plan Execution Diagnosis


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"


User Manual

You can invoke KDiagnose with this syntax:

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:
-add TRAJ contains a constraint in K language which limits the original planning problem (.plan extension required)
-new TRAJ contains a new planning problem in K which outputs the preferred trajectories (.plan extenstion required)
-ext TRAJ contains the list of preferred trajectories which conform to the actions in the plan (syntax as in the output of DLV)
TRAJ Used with previous switch
DIAGTYPE Switch which selects the mode of diagnosis:
-state State-oriented diagnosis (default)
-history History-oriented diagnosis

How it works

Whole process of diagnosis consists of 4 steps:
  1. Preprocessing - Using utilities plan_transform1, plan_transform2 and state_transform we preprocess the planning problem and the state in which we want to diagnose into files which will be used as a new planning problem for diagnosis. These temporary files are called _enforcing.plan, _enforcing.dl and _goal.plan.
    plan_transformX utilities convert the plan into K rules which enforce that the actions will be taken at the respective steps.
    Original planplan_transform1plan_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).
  2. Creating the list of preferred trajectories - We run the DLV system which will produce the list of trajectories in T according to the settings.
  3. Creating the evolutions - We run the DLV system again, to produce all possible evolutions of our domain.
  4. Comparison - Utility compute_diagnosis will take the outputs of previous two steps and will produce the final diagnosis. If there are no points of failure, or if there is no discrepancy, the program will echo a message accordingly.



Consider a version of the Blocks World where a block being moved to a location may end up at a different location because the agent might not grip it properly.

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.


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.
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).


(Lines that begin with [o] are status messages by the main script which mainly document first three steps of the algorithm, and the lines that begin with > or >> are messages printed by the step 4 program. This comparison program sequentially scans all evolutions and compares the states with all the preferred trajectories. If a match is found, that means we have a new point of failure and this match is printed.)
   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.)

Contact us

Created and maintained by Jan Senko