Chapter 5 Theory of Task Generation
5.2 Task Automaton
5.2.4 Algorithms for the Task Automaton
The following Algorithm 5.1 describes the overall interaction between the task automaton and its user. Algorithm 5.1 refers to Algorithm 5.2 that describes the actual task generation. The behavior of the task automaton is represented in terms of valid and stable dc-isomorphisms. Remember that in the task automaton the vertices in VB and V are interpreted as roles and tasks, respectively.
Algorithm 5.1: Interaction Between Automaton and User
(1) The automaton is first in the Unstable state (see Figure 5.4, page 73). For a pattern graph (VB, DB) and cardinality function c in VB: construct an ini-tial task graph (V, Ø), by extending a trivial dc-isomorphism Ø Æ VB us-ing the task generation algorithm (see Algorithm 5.2). As a result, the automaton moves from state Unstable to state Stable (Figure 5.4, page 73).
(2) Wait for the user to shake the stable dc-isomorphism. Shaking can be done by executing or undoing tasks or by modifying the roles, dependen-cies or cardinalities of the pattern graph. This step may cause a transition from state Stable to state Invalid or to state Unstable (Figure 5.4, page 73). Task execution leads to state Unstable, if there is a need for generat-ing new tasks; otherwise the automaton stays in state Stable.
(3) If a transition to state Invalid occurred, perform additional modifications so that the validity of the dc-isomorphism is again reached. The modifi-cations cause the automaton to change state from Invalid to Unstable (Figure 5.4, page 73). These modifications are not discussed in detail in this thesis. As an example, undoing a task (i.e. removing a done task), involves recursively removing the tasks (vertices) that depend on the re-moved task.
(4) While in state Unstable, extend the current dc-isomorphism V Æ VB us-ing the task generation algorithm (see Algorithm 5.2). The automaton moves from state Unstable to state Stable (Figure 5.4, page 73).
(5) Go to step 2.
Algorithm 5.2: Task Generation
This algorithm explains how new tasks are generated to move the task automaton from state Unstable to state Stable. The algorithm is used in steps 1 and 4 of Algorithm 5.1. Recall also Figure 5.4 (page 73) that illustrated the overall dy-namics of the task automaton as a state chart.
(1) Goal Setting
In short, the task generation algorithm describes how new tasks with proper states are added to task graph V in order to reach a stable task automaton state from an unstable automaton state. More precisely, in terms of dc-isomorphisms, we show that, if (V, D) and (VB, DB) are dependency graphs (a task graph and a pattern graph) and h : V Æ VB is a valid dc-isomorphism, it is possible to con-struct a dependency graph (V’, D’) and a dc-isomorphism h’: V’ Æ VB so that h’
is a stable dc-isomorphism, V ⊂ V’, D ⊂ D’, and h’ |V = h. (Here h’ |V denotes the restriction of the mapping h’ into V.) We shall call h’ the stable extension of h.
(2) Processing Order
Next we note that the set of all tasks that have been generated is the union of all the A-derived threads. During step 3 of this algorithm, these sets are examined one by one. New tasks are added to those threads in which stability does not hold.
For a vertex (role) vB in VB, we denote:
α(vB) = { A ⊂ V | A is a potential dependency target set associated with vB}
( Equation 5.1 )
Hence, α(vB) consists of all the potential dependency target sets of role vB, i.e. all those sets (of tasks) for which a new task (from vB) might get generated in the task graph. As an example, look at role cc and task graph T4 in Figure 5.3 (page 72). The set of all potential dependency target sets associated with cc, i.e. α(cc), is {{cp1, ac1, cf1}, {cp2, ac2, cf1}, {cp3, ac2, cf2}, {cp4, ac1, cf2}}. Thus, a new task from role cc might get generated for those combinations of tasks in T4.
By using notation α(vB), we can now represent the set of all derived vertices of vB, i.e. h-1(vB), as a union of all the A-derived threads of vB:
( Equation 5.2 )
and thus the set of all vertices (tasks) in V can be expressed as:
( Equation 5.3 )
Note that h-1(vB) contains all the tasks made from role vB. Note also that an A-derived thread might be empty (recall Definition 5.5 on page 77).
As an example, look at pattern P and task graph T5 in Figure 5.5. Equation 5.2 yields {cc1, cc2, cc3, cc4} for h-1(cc), and Equation 5.3, naturally, represents all the vertices of graph T5.
(3) Processing
In this step of the algorithm, all A-derived threads of V are formed and proc-essed, one at a time, as follows. Let vB ∈ VB and A ∈ α(vB), and consider the cor-responding derived thread X = T(A, vB). If A ≠ ∅ and s(A) ≠ {d}, i.e. A contains at least one vertex that is not done, then, because of the validity of dc-isomorphism h, X = Ø and thus also the requirements for stability are fulfilled according to definitions 5.6. and 5.7. So, nothing has to be changed.
vB ∈VB
vB ∈VB A ∈ α(vB)
V = h-1(vB) = T(A, vB) . h-1(vB) T(A, vB)
A ∈ α(vB)
= ,
Let then A = ∅ or s(A) = {d}, i.e. A is empty or all the vertices in A are done. In that case, depending on the value of c(vB):
“ ”: If X = ∅, add a new vertex v and set s(v) = m, otherwise do nothing. (If #X = 1, stability holds without changes.)
(i)
“?”: If X = ∅, add a new vertex v and set s(v) = o, otherwise do nothing. (If #X = 1, stability holds without changes.)
(ii)
“+”: If X = ∅, add a new vertex v and set s(v) = m. If #X ≥ 1 and s(X) = {d}, add new a vertex v and set s(v) = o. Otherwise do nothing. (If X ≠ ∅ and s(X) ≠ {d}, there already exists v in X such that s(v) = m or s(v) = o and stability holds without changes.)
(iii)
“*”: If X = ∅, add a new vertex v and set s(v) = o. If #X ≥ 1 and s(X)
= {d}, add a new vertex v and set s(v) = o. Otherwise do noth-ing. (If X ≠ ∅ and s(X) ≠ {d}, there already exists v in X such that s(v) = o and stability holds without changes.)
(iv)
(4) Results
The added new vertices together with the original V form the new vertex set V’.
If a new vertex v has been added to an A-derived thread T(A, vB), we naturally put the set A as its target set and vB as its base vertex. In this way we get the ex-tensions D’ and h’ from D and h, respectively. Clearly, the constructed h’: V’ Æ VB is a dc-isomorphism and a stable extension of h, since we maintained the con-ditions related to dc-isomorphism and stability while adding vertices.
Note that V’ may include potential dependency target sets that contain added ver-tices. If T(A, vB) is an A-derived thread in V’ where A is such a potential depend-ency target set, T(A, vB) was not processed in step 3. However, this T(A, vB) is empty, since, according to the construction, no vertex depends on a newly added vertex. On the other hand, there is no need to change T(A, vB), since the vertices added during the algorithm have states mandatory or optional, and so the vertices in A are not all in state done. Hence stability holds “automatically” for T(A, vB).
Moreover, the constructed h’ is the minimal stable extension of h in the sense that the vertex additions performed during the construction process to reach stability were not only sufficient but also necessary.
Applying the Task Generation Algorithm
As the “Processing” step of the task generation algorithm specifies, during task generation the pattern roles are examined one by one. For each role we calculate
the potential dependency target sets and the related A-derived threads. For each A-derived thread, we check whether a new task needs to be generated or not.
As an example, let us take a look at Figure 5.3 and Table 5.1. The table shows how the first tasks that comprise task graph T1 are generated from pattern P. The columns of the table from left to right include: (1) all the pattern roles and their cardinalities, (2) all the potential dependency target sets for the roles, (3) the A-derived threads for the potential dependency target sets, (4) the states of the old tasks in the A-derived threads, (5) the new tasks that are generated from the roles, and finally (6) the states of the new tasks.
Table 5.1: Generating the first tasks from pattern P in Figure 5.3 Role and
cardinality
Potential de-pendency tar-get sets
Derived threads
States of old tasks
New tasks States of new tasks
ap, “+” {∅} ∅ - ap1 m
af, “ ” {∅} ∅ - af1 m
cp, “ ” ∅ - - - -
ac, “ ” ∅ - - - -
cf, “+” ∅ - - - -
c, “ ” ∅ - - - -
cc, “ ” ∅ - - - -
The first row shows how task generation is checked for role ap. The role does not depend on any other roles, so the only potential dependency target set associated with ap is empty. Since there are no tasks yet generated from role ap, the derived thread of ap determined by the empty set is also empty. The symbol “-“ in the fourth column denotes that there are no old tasks in the derived threads. Since the potential dependency target set is empty, and the derived thread is empty, and the role has cardinality “+”, we generate a new task (ap1) with state mandatory. This complies with part iii of the task generation algorithm’s Processing step. Task generation is done similarly for role af. This time, however, the cardinality of the role is “ ”, so part i of the Processing step is applied. For the remaining roles, there are no potential dependency target sets and thus no derived threads either.
This means that no tasks are generated from those roles.
Table 5.2 represents another example of applying the task generation algorithm.
This example shows how tasks are generated during the transition from task graph T4 to task graph T5 in Figure 5.3. First, let us assume that the user has just executed tasks ac1, ac2, cp3, and cp4 in task graph T4 (although they are not marked as done in the figure). Table 5.2 shows that no tasks are generated from roles af, cp, ac, or c, because they all have cardinality “ ”, and there already
ex-ists exactly one task in all the derived threads of those roles. (See part i of the Processing step.) Roles ap and cf, on the other hand, both have cardinality “+”, but their derived threads already have a task with state optional, so no tasks are generated from these roles either. However, the derived threads of the potential dependency target sets associated with role cc are all empty and the cardinality of the role is “ ”. This means, according to part i of the Processing step, that new mandatory tasks cc1, cc2, cc3, and cc4 need to be generated.
Table 5.2: Task generation during transition from graph T4 to graph T5 in Figure 5.3 Role
Derived threads States of old tasks
In this manner, the task generation algorithm is applied every time the task automaton has moved to state Unstable (recall Figure 5.4). Task generation then changes the automaton state to Stable.
Note that the task generation algorithm can be optimized so that not all of the patterns roles have to get examined in order to calculate new tasks to be gener-ated after a task execution. In fact, after a task execution we only have to exam-ine the role from which the executed task was generated and the roles that di-rectly depend on that role.