discussion.tex 6.31 KB
 Markus Klinik committed May 22, 2019 1 2 \section{Conclusion and Discussion}  Markus Klinik committed May 22, 2019 3 \paragraph{Conclusion}  Markus Klinik committed May 22, 2019 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.  Markus Klinik committed May 22, 2019 10 Evolutionary algorithms calculate sets of solutions, which as a by-product contain the best alternative solutions it has found.  Markus Klinik committed May 22, 2019 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.  Markus Klinik committed Feb 05, 2019 13   Markus Klinik committed May 22, 2019 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.  Markus Klinik committed May 22, 2019 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 committed May 22, 2019 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.  Markus Klinik committed May 22, 2019 25 We now look at our method with respect to these three characteristics.  Markus Klinik committed May 22, 2019 26   Markus Klinik committed May 22, 2019 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 committed May 24, 2019 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.  Markus Klinik committed May 22, 2019 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 committed May 24, 2019 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.  Markus Klinik committed May 22, 2019 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.  Markus Klinik committed May 23, 2019 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.  Markus Klinik committed May 22, 2019 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 committed May 22, 2019 41 42   Markus Klinik committed May 22, 2019 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.  Markus Klinik committed May 22, 2019 48 Our resource affinity constraints can be used to guarantee that all three tasks deal with the same transport.  Markus Klinik committed May 22, 2019 49 50   Markus Klinik committed May 22, 2019 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.