A constructional approach to planning, plan emulation and plan recognition.

1. Planning in Fluid Construction Grammar

The problems of planning, plan emulation and plan recognition are strikingly similar to those of language production and comprehension. In this demo, we aim to demonstrate these similarities by implementing an architecture supporting planning, plan emulation and plan recognition in the language processing framework Fluid Construction Grammar.

2. An example situation

In this demo, we will plan for the following situation. We have a set of agents (a-1 to a-n) and a set of locations (l-1 to l-n). The locations can have different properties. They can be empty (e.g. (empty l-2)) meaning that no agent is at this location. They can also be sleeping-locations (e.g. (sleeping-location l-3)), meaning that an agent can sleep there. They can also be connected to other locations (e.g. (connected l-1 l-2)). Agents can be a certain location (e.g. (agent-at a-1 l1)).

The grammar consists of only one construction, the move action. As shown below, the move action can apply if an agent is at a certain location and this location is connected to another location that is empty. If the action applies, it changes the location of the agent and the 'emptyness' of the source and target locations. Note that the => sign denotes 'changes to'. For the moment the overwriting operator is not visualised in sets yet, but also the args change accordingly.

3. Planning: from goal to plan

In planning, the goal and intial state are provided. Then the actions can apply. Once the goal is reached, the plan is returned. It is a lot like formulation in language processing, but the 'utterance' to be formulated is here the set of moves or 'plan'.

In the example below, we specify as a goal that agent age0 should find a sleeping-location. The initial structure shows which locations exist, which are empty, at which location the agent is and which locations are sleeping-locations. Then, the move-action can apply. As we are interested in the shortest plan and as we could easily get caught in a circular plan, we search for a solution in a breadth-first manner and limit the number of desired solutions to 3.

We can see that the first, shortest, solution is found in only one step: the agent can move to l4, which is a sleeping-location connected to l1. Alternatively, he can move from l1 to l2 and then to l3, which is also a sleeping-location. Finally, he could go to l2, back to l1 and then to l4.

Planning (max 3 solutions) 

Goal:

Initial State:

Computing max 3 solutions for application of

FCG CONSTRUCTION SET (1)

in planning

Plans: (MOVE AGE0 L1 L4), (MOVE AGE0 L1 L2) (MOVE AGE0 L2 L3), (MOVE AGE0 L1 L2) (MOVE AGE0 L2 L1) (MOVE AGE0 L1 L4)

4. Plan Emulation: from plan to goal

In plan emulation, the plan and the initial state is provided to the agent, and the agent should find the goal. As it is very difficult and situation-dependent to find which properties of the final state could be meaningful goals (is it more meaningful that a location is empty or that an agent is at a certain location?), we provide a set of possible goals to the agent. These possible goals should be seen as an indication of which properties are more relevant (salient) then others.

Plan Emulation is a lot like comprehension. Instead of a set of strings, a set of actions is given, and instead of a meaning, a goal should be found.

In the example below, we use the same inital state as above, specify the plan as agent-0 moving from l1 to l2 and then from l2 to l3 and as possible goals that some agent ends up at some sleeping-location.

We can see that the agent 'emulates' the two specified move-actions and finds the final state. He checks the final state against the relevant properties and hypothesizes that the goal was that agent0 ended up in sleeping-location l3.

Emulating (max 3 solutions)

Plan:

(MOVE AGE0 L1 L2), (MOVE AGE0 L2 L3)

Initial State:

Possible goals:

Computing max 3 solutions for application of

FCG CONSTRUCTION SET (1)

in plan emulation

Emulated goals:

Solution 1

5. Plan Recognition: from partial plan to hypothesized goal

In plan recognition, the initial state and a partial plan is provided to the agent. The agent should then find the goal. Again, a set of meaningful properties (possible-goals) is provided to the agent.

In the implementation, we achieve this by first emulating the partial plan. We then extract the final state and plan to each of the possible goals. Plan recognition is thus a combination of plan emulation and planning. This is a lot like the use of formulation to aid comprehension, as shown in (Van Eecke 2015).

In the example below, we use the same inital state as above, specify the partial plan as agent-0 moving from l1 to l2 and the possible goals that some agent ends up at some sleeping-location.

We can see that the agent 'emulates' the move action first. Then, he extracts the final state and plans to the underspecified possible goal. He sees that the agent now has to move from l2 to l3 to end up in sleeping-location l3.

Note that plan recognition starts with a plan emulation phase, and then goes to a planning phase.

Emulating (max 1 solutions)

Plan:

(MOVE AGE0 L1 L2)

Initial State:

Possible goals:

Computing max 1 solutions for application of

FCG CONSTRUCTION SET (1)

in plan emulation

Emulated goals:

None of the possible goals were satisfied in the final state.

Planning (max 1 solutions) 

Goal:

Initial State:

Computing max 1 solutions for application of

FCG CONSTRUCTION SET (1)

in planning

Plans: (MOVE AGE0 L2 L3)