A dynamic and complex process environment forces the automated execution and monitoring of processes to face a lot of hard problems. This paper shows how the execution of agile workflows can be assisted by AI planning techniques. In contrast to previous approaches, this method allows for an online adaption of simple process models to changes in the process environment. It can handle a manifold of unexpected events and guarantees the soundness and completeness of the adapted workflow.
Business processes today are commonly automated by formalizing and
instantiating them to workflows. Established comprehensive industry standards support
modeling, processing and monitoring of these workflow instances by a workflow
management system [
Here, we will present and discuss an approach to workflow adaption via plan repair. First, we will formally define how processes based on a simple plan model can fail, i.e. the corresponding failure model. Next, we will give a sketch and an example for adapting a plan by fragmentation and partial plan repair. Having related our work to previous approaches we will then conclude with a short summary and an outlook on future work.
For our approach, we assume a very basic workflow model. It consists of semantically annotated real world operations and allows parallel and sequential processing of (sub)workflows. This simple model can easily be transformed to a partial order plan and vice versa.
A partial order plan in set theoretically representation is a tuple π = (Aπ, ≺)
consisting of a set Aπ of partially ordered actions [
Although there is the assumption of a static world in classical planning, we have to handle the dynamics of real life scenarios as they are typical for workflow applications. Plan execution therefore has to deal with a wide range of events, which were not considered at the time of planning. These can affect all aspects of a plan and the planning domain: states, sets of actions and goals. In the following we assume that the actions of a partial order plan π are processed one after the other. As a consequence, the execution state sπ′ that results from the linear plan fragment π′ ⊆ π of already executed actions is uniquely defined. An unexpected event can influence this state by implicitly adding or deleting fluents. Therefor we can define an (unexpected) external event as a pseudo action ǫ = (∅, effect+(ǫ), effect−(ǫ)) which transforms sπ′ to the new state s′ = γ(ǫ, sπ′). Internal unexpected events (planned actions that failed) can be formally treated in the same way. Process dynamics can also unexpectedly influence the set of actions available for planning thus changing Σ to the new domain Σ′ = (S, A′, γ′). Our approach also allows for (unexpectedly) changing the goals from g to g′ during plan execution. We assume, that an event or goal change always occur in between the processing of two actions and that the plan domain is fully observable. In real world scenarios unexpected events of the mentioned types can happen in combination.
Once an unexpected event eu is recognized in state s′ after execution of the plan fragment π′ its impact on the overall plan π has to be assessed. If the remaining plan πR = π \ π′ is not a solution for the planning problem P′ = (Σ′, s′, g′) the plan π failed. One way to fix the plan would be to find a solution for P′ that is to fix π by re-planning. The fix we propose is to repair π by isolating and partially replanning only that part of πR which is affected by eu. A plan fragment is called affected by eu, if it contains failed actions. An action a ∈ πR is failed, if a 6∈ A′ or if there is a linearization of πR, where a is not applicable.
In order to affect the plan or workflow execution as little as possible we identify minimal parts of πR that fail and try to find alternatives for them.
For this purpose we first choose an inner fragment πE = (AE, ≺) of πr by selecting a connected plan fragment, which contains all failed actions Afail ⊆ AE. A plan fragment πE is called connected, if for all a, b ∈ AE and c ∈ Aπ, we have that c ∈ AE if a ≺ c ≺ b. AE may also be empty if πR only fails due to an unexpected goal change. The outer fragment πF is the plan containing all actions, which are unordered to every action in πE and not contained in πE. So πF is connected as well. Finally we define the remaining fragment πP as the plan fragment containing all actions a ∈ AR which are neither in the inner nor the outer fragment. By definition AE, AF and AP are disjoint, but contain all actions of πR in union. Therefor we call (πE, πF , πP ) a fragmentation of πR (see fig. 1).
The plans πE and πF in a fragmentation (πE, πF , πP ) are independent and πE contains all failed actions of π. The plan repair mechanism we propose searches for an alternative πE′ for πE which is similar to the original, can be executed independently of πF and together with πF and πP is a solution of P′. To ensure the independent (unordered) execution of πF in relation to πE′ , we introduce the so called context of πF . The context CF of πF is a pair (HF , SF ) of two fluent sets: the soft criteria SF and the hard criteria HF . SF contains all fluents which are used in preconditions or added, but not deleted by actions in πF .
SF := (
a∈AF b∈AF m : _ ^ m ∈ effect+(a) ∪ precond(a) ∧ ¬ m ∈ effect−(b) ) The fluents in SF can also be used, added but not deleted in πE′ without resulting in plan flaws. On the other hand, fluents are not allowed to be added or used if they are deleted in πF . These fluents make up HF := {m : Wa∈AF m ∈ effects−(a)}. (
a∈AP
With the help of the context, it is possible to formulate an extended planning problem PE = (Σ′, sE, gE , CF ). Compared to a classical planning problem like P an extended planning problem also takes into account the dynamic environment described by the context CF . As described in section 2, a failure may occur after the state where the unexpected event took place that triggered the plan repair. This happens for example, if a state change event affects the applicability of prospective actions in the plan. We therefore identify a fragment πV of πP that contains all actions a ∈ AP with a ≺ aE for all aE ∈ AE . The plan fragment πV is used to produce the starting state sE for the extended planning problem PE from the state s′ which contains those fluents that for sure hold once πV is completely executed: sE := T{si : si ∈ Γ ∗(πV , s′)}. Thus our method is able to repair parts of the plan which are far ahead of the current execution state without expanding the inner fragment. Finally, the goal gE is constructed from open preconditions in πP and the goal set g′. To simplify this procedure, the goal is represented by an implicit goal action agoal = (g′, ∅, ∅) which is inserted into πP after all other actions a ∈ AP . The goal gE for PE is then chosen to: m ∈ L : _ m ∈ precond(a) and b ≺π a → m 6∈ effects+(b) )
.
^ b∈AP ∪AF In order to handle extended plan problems the planning procedure uses a generalized definition of applicability which uses the context CF = (HF , SF ) to avoid flaws between the computed plan solution and πF . An action a is applicable in a state s wrt. a context CF , if precond(a) ⊆ s and
m 6∈ HF and ^ m∈precond(a)
^ n∈effects−(a) n 6∈ SF .
The parameters for the extended planning problem and the resulting applicability of actions are all determined by the selection of the inner plan fragment of πE : the smaller πE , the bigger CF and the more constrained is the planning process. For a good choice of πE we propose to first attempt the repair process with the smallest πE possible followed by iterative attempts with bigger fragments until πE = πR which amount to classical replanning. It can be shown, that the solution πE′ of PE can replace the defective πE without producing flaws wrt. πF . By processing πE′ all open preconditions of πP and all (maybe changed) goal fluents will be satisfied: the repaired plan πR′ is a sound and correct solution for the plan problem P ′ that summarizes the failure of the original plan. 4
The generic repair method, introduced in this paper, was developed in the
context of the Mops project1. The target of this joint research project is adaptive
1 Mops is funded by the European Union (European Regional Development Fund)
and the Federal State of Thuringia of Germany.
planning and secure execution of mobile processes for human agents in dynamic
scenarios [
The application of Mops is based on a generic scenario of service staff completing missions (on site repair jobs, delivery tasks, facility management). In order to exemplify our repair method, let us assume an extremely reduced scenario with 3 service technicians and 3 missions that can be represented by the following simple set-theoretic planning domain with the fluent set L = {a1 , ..., a3 , done1 , ..., done3 , 1doing1 , ..., 3doing3 }. For every technician, there is a fluent aX , which means “technician X is available”. Likewise there is a fluent doneX for every job, which means “job X is successfully accomplished.” For every job and every technician there is a fluent XdoingY , which means “technician X is assigned to job Y ”. The planning domain further contains two types of actions. The first one actually assigns a job to a technician, if the technician is available. assign1to2 = ({a1 }, {1doing2 }, {a1 }), e.g., allocates job2 to technician1. The second type of action initializes the execution of a job by its assigned technician. 1do2 = ({1doing2 }, {done2 , a1 }, {1doing2 }), e.g., means “technician 1 is doing job 2”. The solution of the planning problem P = (Σ, s0, {done1 , done2 , done3 }) with s0 = {a1 , a2 , a3 } then results in a plan like π as shown in fig. 2.
Let us now assume that the current execution state sπ = s0 and that in this state a technician reports to be sick resulting in the new actual state s′ = γ((∅, ∅, {a3 }), sπ) = {a1 , a2 }. This event leads to a failure of the remaining plan π′, because action assign3to2 is no longer applicable. Because this action is the only action affected by the failure we can reasonably set AE = {assign3to2 }, which implies AF = {assign1to3 , 1do3 , assign2to1 , 2do1 } and AP = {3do2 }. This fragmentation leads to a context CF with HF = {a1 , a2 , 1doing3 , 2doing1 } and SF = {done3 , done1 }) and the extended planning problem PE = (Σ, ∅, gE, CF ) with the open precondition of 3do2 as goal gE = {3doing2 } It is impossible to find a solution for this problem because job 2 can not be assigned to any other technician due to {a1 , a2 } ⊂ HF (an assignment action deletes the availability fluent for its agent and therefore is not applicable as long as the fluent is contained in the context). If we now widen the inner fragment to AE = {assign3to2 , 3do2 } (hence AP = ∅) then the corresponding new extended planning problem PE = (Σ, ∅, {done2 }, CF ) still has no solution because AF and CF remained the same. A further widening of the inner fragment to AE = {assign3to2 , 3do2 , 2do1 } (AP = AV = {assign2to1 }) diminishes the outer fragment to AF = {assign1to3 , 1do3 } and the context to SF = {done3 } and HF = {a1 , 1doing3 }. The resulting extended planning problem PE = (Σ, {2doing1 }, {done1 , done2 }, CF ) is now solvable with the plan alternative πR′ as shown in fig. 3
This little example already shows that the choice of the inner fragment AE significantly influences the context and therefore the degrees of freedom for the replanning problem. For this choice we propose to use the control-flow structure, respectively the partial plan order: in order to maximize the part of the workflow that can be executed concurrently to the adaption process for the failed part, the outer fragment AF and AV of the remaining fragment should stay as big as possible. 5
A lot of workflow related approaches for adaption while runtime are based on the
reusability of pre-modeled workflow fragments. AdaptFlow [
Besides case based approaches there are two strategies in AI planning for
performing a plan adaption: re-planning from scratch or plan repair. Nebel and
Koehler [
Usually there is no unique solution for a planning problem, thats why
alternatives have to be considered. Fox et. al, e.g., discuss in [
We have introduced a domain independent method for adapting partial order plans. In contrast to present approaches, this method follows a formally defined complex failure model that captures the relevant characteristics of the underlying process model. The approach is able to adapt processes at runtime, i.e. concurrently to process execution, and is guaranteed to produce sound and correct solutions.
At the moment there still is a big gap between the expressive power of the plan representation we used and that of state of the art workflow models but we are working hard to generalize our method to more complex representations, which are able to represent additional aspects of todays workflow languages — among them complex control structures as well as explicitly coded data flow, organizational and security aspects.