Learning regular expressions from plans

Install

Prerequisities

Following modules should be installed and available in your python environment:

graphviz
ordered-set

Clone the code with: git clone https://github.com/fairf4x/dcklearn.git
git checkout main

Basic help should be displayed when running: python learnFSA.py -h

Usage

In order to use the program you need a directory with plans to learn from. Let us have the directory at PLANDIRPATH. In this directory program expects to find plans. Plans are text files with one action per line in the following format:

(action_name arg1 arg2 arg3 ... )

These actions are used for learning a FSA.

We can render resulting FSA diagram using FILENAME and FORMAT (only png,svg and pdf are supported). Textual graphviz format for further machine processing is gv):

python learnFSA.py -p PLANDIRPATH -o FILENAME -f FORMAT

Resulting FSA diagram should be stored at path given by the FILENAME argument.

If we want to merge learned FSA with existing PDDL domain, we need to specify both DOMAINPATH and resulting domain FILENAME:

python learnFSA.py -p PLANDIRPATH -o FILENAME -m DOMAINPATH

Implementation details

Learning FSA (learnFSA.py)

The algorithm works recursively with sets of plans in order to build a special tree structure which is then used to build the resulting regular expression.

Input always consists of a finite set of plans. All these plans are then splitted into three plan sets (called Head, Middle and Tail). Every split decision is represented as a node in a tree structure. The decision is made by choosing a split action. For example if the plan is (shortened for readability - each letter represents one action):

p = BCABDABCABDC

and we choose split action A, we get:

Head(p) = {BC}
Middle(p) = {BD,BC}
Tail(p) = {BDC}

Each set thus contain fragments of the original plan without selected split action. If we split all plans from the input set (all plans in the input directory) in similar manner we can get lists of all Head, Middle and Tail plans that are used as an input for subsequent recursive steps.

There are following special cases for tree nodes:

Non-trivial node represents split of all the plans using an action a into three sets of plans. After spliting all plans from the input set of plans P (|P| = N), the result of the split with the split action a is:

HeadList(a) = Union{ Head(P1),..., Head(PN) } MiddleList(a) = Union{ Middle(P1),..., Middle(PN) } TailList(a) = Union{ Tail(P1),..., Tail(PN) }

Every such node has at most three children (one for each 'X'List(a)). The node is called non-trivial iff at least one of them can be recursively processed further yielding more complex structures.

Trivial node is a node where all siblings HeadList(a), MiddleList(a), TailList(a) are just sets of actions. A sibling node of this kind is generated when there is no split action selected. The set of actions used is the set used in the selection process. This kind of node has no siblings for further processing. It records only information about short subplan consisting of the actions from its sibling sets and its own split action.
Leaf node is trivial node where all siblings are empty sets. A sibling node of this kind is generated when the set used for action selection is empty. This kind of node store only information about position of its split action in the tree.

Split action selection

The splitting decision is made by trying all available split actions. Data from each such attempt are recorded. These are: minAcnt .. minimal split action count found in all the plans in the input set maxAcnt .. maximal split action count found in all the plans in the input set totalCnt .. cummulative split action count from all the plans in the set headList,middleList,tailList .. subplan sets generated by splitting all the plans

Subplans in [head,middle,tail]List are recorded with arguments.

In the action selection step of the algorithm the recorded data are used to compute score for each split action. This is implemented in selector.py. The score computed is then used to make decision in action selection mechanism. Action selection should always return one and only one action. Multiple levels of disambiguation can be used in order to achieve this. On each level the selectTopSubset function is called with some scoring function. Only top scoring actions are returned in each level with the last level using lexicographic ordering as a ultimate disambiguation in case that there is still more than one action remaining.

Pattern generation

Each plan has its pattern that describe positions of symbols used as action arguments. For short plan fragment:

    ('lift', ('h1', 'c1', 's1', 'p1'))
    ('load', ('h1', 'c1', 't1', 'p1'))

we can have pattern:

A = ['lift','load']
E = [{(1, 0), (0, 0)}, {(0, 1), (1, 1)}, {(0, 3), (1, 3)}]

The list A contain only action names. The list E contain sets that represent sets of equivalence. It contain pairs of indices where firt index represent position of an action from the first list and the second index marks position of its argument. Everything is indexed starting from zero. e.g.:

{(1, 0), (0, 0)}

h1 is in action A[1] at position 0 and at A[0] at position 0.

These patterns are independent of any argument names which may be different in each plan.

FSA merging to PDDL (FSA.py)

FSA is initialized from stack of symbols produced by learnFSA.py module. Four kinds of items can be found on the stack:

action with arguments - tuple ('actionName',['arg1','arg2',...,'argN']) lambda action names should begin with prefix _ This is interpreted as a new FSA transition starting in last state and ending in a new state.
action set - set of strings which is interpreted as a set of loops in last state (one loop for each action from the set)
parenthesis - either ( or ). Modifies stack used for FSA creation.
repetition symbol - *,+ or [:number:]. In this case previous action (or group of action in parenthesis) on the stack is repeated.

Merging learned FSA to PDDL

Merging to PDDL depends on external module pyddl (reading and writing PDDL files). Original domain PDDL file is needed. The file is read and the domain is cloned. Then the clone actions are updated according to FSA transitions.

fairf4x/dcklearn