The model dependency diagrams identify (i) the case models that are constructed during problem solving, (ii) the domain models that are required during this construction process and (iii) the dependencies which relate these various models to each other. Let us first start with the case models. We will start with a general description and gradually introduce more detail in the analysis.
Initially, the human problem solver (the expert) is confronted with a particular problem that he wants to solve. A ``problem'' consists of an arbitrary number of trains that the expert has selected from the timetable database. Given these trains, the task of the expert is to come up with an allocation of equipment (engines) such that each train can actually be driven. An allocation is a set of sequences whereby each sequence indicates the set of trains that are driven by one particular engine of a certain type.
From this information, we deduce that the following models are required. A first set of case models describes the initial problem (let us call these the ``problem case model''). Here, we find a ``components model''. This model describes the components of the problem, i.e. the various trains that are present. Let us call this model the ``train components model''. Each train in the components model has an associated ``descriptive model'' (which we shall call ``train descriptive model''). This model describes the different features of each train such as the train number, the station of departure and arrival, the time of departure and arrival, the period of the year during which the train drives and finally the days of the week when the train drives. To illustrate this, we show an example of such a train descriptive model below:
To summarize, we can say that we start with a ``problem description case model'' that is built out of two other models: a ``train components model'' which lists the components (trains) that are present and (for each component) a ``train descriptive model'' which describes the various properties of the component.
Let us now focus on the final output of the equipment allocation task. This output consists of a set of sequences of trains. Each sequence indicates (in time order) the trains that will be driven by one particular engine of a certain type. In addition, sequences have an associated characteristic (like the trains) which refers to the days of the week when that particular sequence is present. Note that there are two notions of time here. First, we have a time order which is imposed on the various trains within one particular sequence. This order is, of course, determined by the time of arrival and departure of the various trains within that sequence. Second, each sequence can occur on more than one day of the week which is indicated by a characteristic. This characteristic is the second time component.
In terms of the various models in the components of expertise framework, we deduce the following models. The output of the equipment allocation task is a kind of plan (let us call this the ``plan case model'') which consists out of several components (``plan components model''). In our case, the components are sequences of trains (where each sequence is driven by one engine of a particular type). Next, we have to indicate how the different sequences are modeled. To describe one sequence we will use a ``sequence case model'' which consists out of four other kinds of models.
First, we have to indicate the engine that will drive the sequence of trains (e.g. engine ``A023''). To describe this, we can simply use a ``descriptive model'' (engine descriptive model). This model will indicate the type of the engine (e.g. type A0) and the number of the engine (e.g. 23). An example of an ``engine descriptive model'' is shown below:
Secondly, we have to specify the trains that occur in a sequence. This can again be done using a ``components model''. The components of the sequence are the trains that, as before, are described using a ``descriptive model'' (see above). An example is shown below:
Finally, we need to describe the two notions of time that were discussed above. This is done using ``temporal models''. A first ``temporal model'' (which we call ``seqence order model'') describes the order of trains that is present in a particular sequence and is therefore associated with that particular sequence. In addition, since the same sequences may re-occur on different days of the week, we have to introduce a second ``temporal model'' (which we call ``sequence temporal model''). The latter model indicates the days of the week when the sequence is present.
To illustrate these four kinds of models in more detail, we show an example of a ``plan case model'' that contains three sequences:
To summarize, we start with a ``problem case model'' which consists of (i) a set of trains (described using a ``components model'') and (ii) a description of the different properties of each of these components (indicated by means of a ``descriptive model''). When the task is done, we end up with a ``plan case model''. The latter consists of (i) a ``components model'' which indicates the sequences in the plan, (ii) a ``descriptive model'' which indicates the engine that will drive that sequence, (iii) a ``temporal model'' which describes the order imposed on the various components (trains) in the sequence and (iv) a ``temporal model'' which indicates the days of the week when that particular sequence is present.
Based on these results, we can draw the following model dependency diagram (see figure 3) between the ``problem case model'' and the ``plan case model''.
In figure 4 we have indicated the role of the user (the expert). He is responsible for defining the initial problem case model by selecting the trains that he wants from the timetable database. The timetable database can be considered as the ``domain model'' that the expert uses to construct the initial ``problem case model''.
It is clear that the construction of the ``plan case model'' does not happen in a single unitary step and that various intermediate models will be required during this construction process. Let us now go into more detail and see how this picture (figure 3) can be refined.
The basic paradigm that the expert uses to construct the ``plan case model'' has been described most adequately in [Chandrasekaran1990] and is called ``design by decomposition''. In design by decomposition, the initial problem is first decomposed into a number of subproblems that are ``nearly independent'' from each other. The decomposition of problems in subproblems may be Each of these subproblems is then solved separately from the other ones. Finally, the different solutions are glued back together in order to form a solution for the initial problem. Figure 5 illustrates this process.
Let us first concentrate on how the expert decomposes the initial problem into subproblems that can be solved independently from each other. In the case of the equipment allocation task the initial problem is decomposed into two stages. A first decomposition step will generate subproblems such that all the trains in one particular subproblem belong to the same passenger relation. The reason for this kind of decomposition is that the trains in one relation should be driven by a different type of engines than the trains that belong to another relation. Consequently, if one set of trains belongs to relation X and another set of trains belongs to relation Y, then both relations can be scheduled independent from each other. The result of the first decomposition step is therefore a set of subproblems that are completely independent from each other. Note that we can again use a ``problem case model'' (see above) to describe each of these subproblems.
Each of these independent subproblems is further decomposed in the following way. The trains that belong to one passenger relation are grouped such that each group contains all the trains that have the same characteristic. For example, suppose that there are trains in a passenger relation that drive on weekend days and trains that do not drive on weekend days (as frequently happens in the passenger transport). The expert will then separate the weekdays from the weekend days and construct a plan for each of these two periods. The reason why the expert makes this decomposition is simple. If all the trains drive within the same period of the week, then the specification of the sequences of trains only has to happen on one particular day of that period. The same sequences can then be used for all the other days that fall within the same period of days. For example, if we have a problem that consists of trains that all drive during every weekday, then we can specify sequences for Monday and copy these sequences to all the other weekdays. The second kind of decomposition is thus a decomposition in time: group the trains according to the days of the week such that all the trains in one group re-occur on every day within a particular period. As before, the subproblems that come up during the second decomposition step can be described using the ``problem case model'' that we had before.
Let us now describe how we can fit this decomposition process into the model framework that we had before. Initally, we started with the ``problem case model'' that basically describes a group of trains. This ``problem case model'' is decomposed into a number of new ``problem case models'' in two steps. In a first step, the trains from the original case model are grouped such that all the trains in one group belong to the same passenger relation. This results in a number of new ``problem case models''. Each of these case models described a situation that is independent from the other ones. For each of the new ``problem case models'' there is a second decomposition which groups the trains together that share a similar characteristic (e.g. N67 and R67). Note that we have hierarchical relations between the various problems and subproblems. We first go from arbitrary trains to trains that belong to the same relation. Next, we go from trains in one relation to groups of trains that share the same characteristic. This is illustrated below (figure 6).
In terms of models, we can say the following. The initial ``problem case model'' is transformed into a number of new ``problem case models'' that are related hierarchically to the initial ``problem case model''. Therefore, we need a ``connection model'' (which we call ``decomposition connection model'') that will indicate these hierarchical relations. We can then refine the previous model dependency diagram as follows (figure 7).
Figure 8 shows another view on this model construction proces. For each problem and subproblem, we have a model construction process that will yield a description of the subproblems of that problem.
It is clear that the previous diagram is incomplete. The first decomposition step requires that we know some kind of relationship between a particular train and the passenger relation to which that train belongs. We therefore need a domain model which will allow us to determine to which passenger relation a particular train belongs. With each passenger relation, there is an associated interval of numbers. Trains that belong to a certain relation receive a number that lies within this interval (see table 2 for some examples).
In terms of models we come to the following conclusion. There is a ``descriptive domain model'' (let us call this the ``relation domain model'' that indicates the different passenger relations that are present. This domain model contains the name of the different relations and also the interval of train numbers that is associated with the relation. Adding this domain model to the previous model dependency diagram yields (figure 9).
Let us re-iterate what we have so far. Initially we have a ``problem case model'' that describes an arbitrary number of trains that require equipment to be allocated to them. In a first step, this initial case model is transformed in a number of new case models. Each of these case models describes sets of trains that belong to the same passenger relation. These case models represent new (sub)problems that are independent from each other because the trains from one relation are scheduled independently from the trains in another relation. In addition, each of these models is further decomposed into a set of new case models. The latter ones describe new (subsub)problems that group the trains that have the same characteristic. Finally, there is a connection model which indicates the hierarchical relations among the various problems, subproblems and subsubproblems.
After the initial problem has been decomposed into subproblems, each of the subproblems must actually be solved. This implies that a ``plan case model'' must be constructed for each of the ``problem case models'' which are at the leaves of the problem decomposition tree (see figure 3). The ``plan case models'' that are constructed during this phase of the problem solving represent partial solutions to the overall problem that needs to be solved. For each ``problem case model'' at the bottom of the decomposition tree of problems and subproblems (see figire 5) we will have a corresponding ``plan case model'' which represents the solution for that particular problem. We shall now describe how these ``plan case models'' are constructed. Recall that, at the bottom of the problem decomposition tree, we start off with a ``problem case model'' which describes a set of trains such that the following two constraints are satisfied: (i) all trains belong to the same passenger relation and (ii) all the trains have the same characteristic.
The ``plan case model'' is constructed iteratively. In each step, the expert will either (i) specify a new sequence, (ii) add a train to an existing sequence or (iii) end a sequence. Whenever a new train is added to an existing sequence, several constraints have to be taken into account. Indeed, in many cases it is impossible to re-use the same piece of equipment to drive a train which, for example, immediately departs after the train that had been driven with that piece of equipment. This implies that during the construction of the ``plan case models'' we will have to introduce domain models that will allow us to determine whether or not certain connections are feasible.
The time required to make connections between two trains basically depends upon the topology of the station in which the first train arrives. We therefore need to introduce a structural model of the different stations. This model is composed out of a ``components'' model (which described the different stations and tracks that are present) and a ``connection model'' which indicates how the tracks and the stations are connected to each other (let us call this combination the ``topology domain model'').
Using this information, we can describe how the construction of the ``plan case model'' proceeds. Through each iteration, the expert will specify one sequence of trains that will be driven by one particular engine. The specification of such a sequence happens in several steps.
First, the expert has to select the engine that will drive the particular sequence. This requires knowledge about the characteristics of the different types of equipment that are available. Not all types of engines can be used to drive the trains that belong to a certain relation. As an example, consider the relation Amsterdam-Brussels. Since this is an international line, we need a type of engine that can work with two kinds of voltages. The Belgian electrical railway network operates on 20,000 volts while the Dutch network operates on 3000 volts. In terms of models, we will find a ``descriptive model'' (let us call this the ``engine domain model'') which specifies the characteristics of the different kinds of engines. Note also that we need the ``relation domain model'' (see above) during the selection of the engine.
To actually specify the engine that will drive a particular sequence, the ``engine descriptive model'' (which is part of the ``plan case model'' that describes the solution for the current problem) must be filled in. Selecting an engine can therefore be described using the following model dependency diagram (figure 10).
The second step in the specification of the sequence is the selection of a train that will be the first one in the sequence. In terms of models, we again start from the ``problem case model'' (containing a description of the trains that need to be scheduled) and we have to select a train that will be the first member of a sequence. We thus start with a ``problem case model'' and select a ``descriptive model'' of the first train of the sequence (figure 11). In addition, we have to update ``sequence components model'' and the ``sequence order model'' of the current ``plan case model''.
Next, we have to iteratively determine the next train in the current sequence. Again, this amounts to selecting a ``descriptive model'' (describing that train) from the ``problem case model'' and updating the current ``plan case model''. However, during this selection we have to take into account that the connection between the previous train and the newly selected train is only possible when the time difference between arrival of the first train and departure of the second train is sufficient to actually re-use the engine. We thus have to exploit a domain model which describes the topology of the station in which we are going to make the connection. In terms of models, we extend the (partial) ``plan case model'' with a new train but we use the ``topology domain model'' to actually check whether or not this extension is feasible (figure 12).
To spell this out more explicitly, recall that the ``plan case model'' was composed out of four other models: (i) a ``components model'' describing the sequences that are present, (ii) a ``descriptive model'' (describing the engine associated with each sequence), (iii) a ``temporal model'' (describing the order of trains within a sequence and (iv) another ``temporal model'' (describing the characteristic of that plan). When the expert starts the specification of a sequence, he will first fill in the ``descriptive model'' for the selected engine. Filling in this model starts the specification of one sequence. Next, he will construct the ``temporal model'' which describes the characteristic of the sequence. This characteristic is equal to the characteristic of the trains that occur in the particular ``problem case model'' that he is currently working with. Afterwards, the expert will select a descriptive model which indicates the first train that will occur in the sequence driven by that particular engine. Then, the next train of the sequence has to be determined taking into account the feasibility of the connection between the trains. As we indicated above the topology of the station in which the connection is being made is the primary constraining factor here. These steps are then re-iterated until there are no nore trains left to make a connection. Afterwards, the expert will start with the specification of the next sequence. In terms of model dependency diagrams, this brings us to the following picture (figure 13).
We have now described how the ``plan case models'' are constructed for the problems that appear at the leafs of the problem decomposition hierarchy (figure 8). Figure 14 illustrates this in terms of the ``problem case models'' and the ``plan case models''.
We now have to explain how the partial solutions are re-composed in order to get a solution for the problem which is one level up the problem decomposition tree, i.e. we have to explain how to get from figure 14 to figure 15.
The first recomposition step integrates two partial solutions. From the problem decomposition hierarchy, we now that these partial solutions are solutions for one and the same passenger relation, but that they are solutions for different days of the week (e.g. N67 and R67). In order to integrate these solutions to a single solution for the complete passenger relation, the expert has to determine how many empty trains have to be scheduled.
In terms of the model dependency diagram this gives us the following picture 16. Two ``plan case models'' are first used to determine a ``descriptive model'' which describes the empty trains that are required to restore the balance in the plan (let us call this model the ``empty train descriptive model''). Next, a new ``plan case model'' is constructed by merging the ``plan case models'' which represent partial solutions.
The second recomposition step integrates the solutions for different passenger relations into a solution for the initial problem (figure 17). However, this decomposition step is obvious since the solutions for different passenger relations are completely independent from eachother. This implies that we can simply combine the ``plan case models'' that represent these solutions into a single (top-level) ``plan case model''. Figure 18 shows the associated model dependency diagram.
___________________________________________________