discussion.tex 6.31 KB
Newer Older
Markus Klinik's avatar
Markus Klinik committed
1
2
\section{Conclusion and Discussion}

Markus Klinik's avatar
Markus Klinik committed
3
\paragraph{Conclusion}
Markus Klinik's avatar
Markus Klinik committed
4
5
6
7
8
9
We have presented an algorithm that calculates solutions to the C2 scheduling problem.
The C2 scheduling problem expresses the scheduling requirements in damage control scenarios on board of navy ships.
It is a variant of the MSRCPSP, and extends it with resource affinity constraints and user-defined quality functions.
We use an evolutionary algorithm to search the solution space for schedules that have a good score according to the weighted product of all objectives.

We argue that evolutionary algorithms lend itself well for our problem, because we are not only interested in the best schedule, but also in alternative solutions.
10
Evolutionary algorithms calculate sets of solutions, which as a by-product contain the best alternative solutions it has found.
Markus Klinik's avatar
Markus Klinik committed
11
12
Furthermore, evolutionary algorithms do not need knowledge about the function they are trying to optimize.
This is useful for our purpose, because user-defined quality functions can be arbitrary Turing-complete calculations, and there can be no general heuristic that could take advantage of them to guide the search.
13

Markus Klinik's avatar
Markus Klinik committed
14
15
16
17
18
\paragraph{Coactive design}
We envision our algorithm to be part of an integrated mission management system, where the computer is part of the team.
Humans and machines should contribute to the joint activity of mission management with their respective strengths.
In his Ph.D. thesis, \citet{Johnson2014} argues that for interdependent teamwork, the computer must not be a black box.
Its internal process must be exposed.
19
20
21
In order to trust and rely on the computer, it must have three key characteristics: \emph{observability}, \emph{predictability}, and \emph{directability}.
Johnson defines them as follows.
Observability is making relevant aspects of the machine's status, knowledge and environment available to others.
Markus Klinik's avatar
Markus Klinik committed
22
23
24
Predictability means that others can rely on their prediction about the machine's behaviour.
Directability is the ability to be influenced by others.
This can be for example through direct commands, guidance, preferences, or suggestions.
25
We now look at our method with respect to these three characteristics.
Markus Klinik's avatar
Markus Klinik committed
26

27
Observability in our case means that the user can see what the machine knows about the ship's status, in other words the user should have access to the operational picture.
Markus Klinik's avatar
Markus Klinik committed
28
If the user-defined quality functions make use for example of the weather conditions, the location of people on board, or the degradation status of equipment, this information should be accessible in a clear and user-friendly manner.
29
30
31
32
Representation and display of the operational picture is out of the scope of this article, so this point is not applicable to the discussion.

Predictability in our case means that given similar situations, the algorithm should come up with similar solutions.
The probabilistic nature of evolutionary algorithms makes our method come off less well in this respect.
Markus Klinik's avatar
Markus Klinik committed
33
For some problem instances, where good solutions are isolated between many bad solutions, we observed that it can take a long time or lots of runs to find a good solution again that we have seen before.
34
35
36
37
We believe that this problem can be mitigated by developing parameter sets that are appropriately dimensioned for typical problems.

Directability in our case means that the user can guide the search towards solutions that fulfil certain desired properties.
This is where the strength of our method lies.
38
User-defined quality functions, the weighted product, and resource affinity constraints were specifically included to give users instruments to express preferences about the kind of solutions they desire.
39
40
The example in \cref{sec:example-conflicting-objectives} shows how emphasizing the makespan produces quick solutions where less capable resources are being utilized, while de-emphasizing the makespan assigns more work to fewer high-quality resources, resulting in schedules that take longer to complete.
The example in \cref{sec:example-search-and-rescue} demonstrates how arbitrary constraints can be encoded in user-defined quality functions, in this case to prevent Bob from having to fly the helicopter.
Markus Klinik's avatar
Markus Klinik committed
41
42


43
44
45
46
47
\paragraph{Planning versus scheduling}
In \cref{sec:planning-vs-scheduling} we argue that planning and scheduling can not always be clearly separated.
Nonetheless, many such situations can be expressed as C2 scheduling problems, by choosing an appropriate level of abstraction.
For example, even though choosing between a helicopter and a boat requires different setup and cleanup procedures, we can model the situation as three generic tasks: setup, perform, and cleanup.
We assume that the personnel is sufficiently educated to know which setup and cleanup procedures are required for either transport.
48
Our resource affinity constraints can be used to guarantee that all three tasks deal with the same transport.
Markus Klinik's avatar
Markus Klinik committed
49
50


51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
\paragraph{Stop criterion}
In our current implementation, the algorithm stops after a fixed number of generations.
This guarantees termination of the algorithm after a pre-determined time, but it might stop at an unfortunate moment where a new area of the search space has been discovered but not yet fully explored.
Other stop criteria have been proposed for evolutionary algorithms.
One could use different kinds of convergence criteria, like that the distance between the best and the worst solution in the population falls below a certain threshold, or that the best best solution has not been improved for some time.



\paragraph{Feasibility checking}
A scheduling problem is called \emph{feasible} when it has at least one valid solution.
Not every C2 scheduling problem is feasible.
It could be helpful to check feasibility of a scenario before setting out to finding the best solution.
Checking feasibility of C2 problems is tricky, because resources can have multiple capabilities.
Take for example a scenario with one task that requires two capabilities A and B, and one resource that has both.
Just looking at the cardinalities of the sets of resources with required capabilities is not sufficient.
One might conclude that there is one resource with capability A and one resource with capability B, but when assigning the resource to either, it becomes unavailable for the other.
\citet{CorreiaLS2012} describe a method of checking feasibility for scheduling problems with flexible resources, based on finding a flow in a specifically constructed network.