## 3 Prediction-Based Assembly Support System
### Providing Choices for the Next Assembly Step through Prediction by Partial Matching  
For the next assembly step prediction, the PPM algorithm is applied, which is, in fact, a hybrid method composed of Markov chains of different order. It was applied in data compression, but it was used also in other applications relying on prediction, like web prefetching [22], branch prediction in microprocessors [23], etc. In a Markov chain of order R, the next state probability can be defined as \(P[q_{t}|q_{t-1},\dots,\)\(q_{1}]=P[q_{t}|q_{t-1},\dots,\)\(q_{t-R}]\), where \(q_{t}\) is the state at time t. As presented in [6; 7], the prediction with Markov models can be performed using a table trained with past data, which stores pairs of patterns of a certain length and the corresponding next states, together with their occurrence frequencies. Figure 4 presents the structure of a Markov predictor of order R. The patterns in this work are composed of human worker characteristics (\(C_{1},\dots,\)\(C_{4}\)) and assembly sequences (\(q_{t-R},\dots,\)\(q_{t-1}\)). The next state can be predicted if the current context is found in the pattern field of the table and then the state \(q_{t}\) with the highest frequency from that entry will be the prediction. A PPM of order R tries to provide a prediction with the Markov predictor of order R and, if it can do that, its prediction is returned by the PPM. Otherwise, the order of the Markov predictor is iteratively decremented until a prediction can be provided. If the Markov predictor of order 1 cannot issue a prediction, then the PPM itself is not able to do that. The PPM's prediction mechanism is depicted in Figure 5. For the PPM implementation, the Markov predictor with padding (presented in [7]) is used. The Markov predictor was enhanced to also use the workers' characteristics. Upon instantiation of the PPM algorithm, the order R should be provided. For each order, starting from R and moving down to 1, a Markov predictor is created. After all the R Markov predictors are created, they are sorted in descending order. When the prediction algorithm is called, it will iterate sequentially through the Markov predictors to find one which has a match for the assembly pattern, and so it can predict. If the Markov predictor of order R has no match, then the next Markov predictor from the sorted list is checked. The first Markov model that has knowledge of the assembly pattern is the one that will make the final prediction. If no Markov model can find a matching sequence, then the PPM algorithm is going to return -1, meaning that it cannot make a prediction. As far as we know, PPM has not been used for next assembly step prediction before. The novelty of this method consists in the combination of different order Markov predictors, which ensures that matches for the occurring assembly patterns can be found easier. There are over 5000 possible ways of assembling the tablet and 4 characteristics that can define the behaviour of a worker, each one with 2 possible outcomes. Thus, the tablet could have over 80,000 unique assembling possibilities. Because of the high diversity of assembly patterns, the current context cannot always be found in the prediction table of the prediction scheme presented above, which negatively affects the prediction rate. Therefore, an enhanced scheme was considered, which explores neighboring characteristics of the user, whenever the current context (with the actual user characteristics) does not have an exact match. This approach would be practicable even if several additional characteristics were considered. Figure 4: R\({}^{\text{th}}\) order Markov predictor. Neighboring context exploration involves changing one characteristic of the worker at a time. A single trait of the worker is changed sequentially at a time, after which making a prediction is attempted.