Anytime diagnosis for reconfiguration

Knowledge-based configuration is one of the most successful application areas of Artificial Intelligence (Felfernig et al. 2014; Frayman and Mittal 1987; Haag 2014; Hvam et al. 2008; Sabin and Weigel 1998; Salvador and Forza 2007; Stumptner 1997). There exist many application domains ranging from telecommunication systems (Fleischanderl et al. 1998; Stumptner et al. 1994), railway interlocking systems (Falkner and Schreiner 2014), the automotive domain (Sinz et al. 2003; Tiihonen and Anderson 2014; Walter and Küchlin 2014), software product lines (Benavides et al. 2010) to the configuration of services (Tiihonen et al. 2014a).

Configuration technologies must be able to deal with inconsistencies which can occur in different contexts. First, a configuration knowledge base can be inconsistent, i.e., no solution can be determined. In this context, the task of knowledge engineers is to figure out which constraints are responsible for the unintended behavior of the knowledge base. Bakker et al. (1993) show how to apply model-based diagnosis (Reiter 1987) to determine minimal sets of constraints in a knowledge base that are responsible for a given inconsistency. A variant thereof is documented in Felfernig et al. (2004) where an approach to the automated debugging of knowledge bases with test cases is introduced. Test cases are interpreted as positive or negative examples that describe the intended behavior of a knowledge base. If some positive examples induce conflicts in the configuration knowledge base, some of the constraints in the knowledge base are faulty and have to be adapted or deleted. If some negative examples are accepted (i.e., not rejected) by the configuration knowledge base, further constraints have to be included in order to take these examples into account (in Felfernig et al. (2004) this issue is solved by simply including negative examples in negated form into the configuration knowledge base). A related approach in the area of software product lines is proposed in White et al. (2010). Second, customer requirements can be inconsistent with the underlying knowledge base.¹Felfernig et al. (2004) also show how to diagnose customer requirements that are inconsistent with a configuration knowledge base. The underlying assumption is that the configuration knowledge base itself is consistent but combined with a set of requirements is inconsistent.

The so far mentioned configuration-related diagnosis approaches are based on conflict-directed hitting set determination where conflicts have to be calculated in order to be able to derive one or more corresponding diagnoses (Crow and Rushby 1991; Janota et al. 2014; Junker 2004; Reiter 1987; Shah 2011). These approaches often determine diagnoses in a breadth-first search manner which allows the identification of minimal cardinality diagnoses. The major disadvantage of applying these approaches is the need of determining minimal conflicts which is inefficient especially in cases where only the leading diagnoses (the most relevant ones) are sought. Furthermore, in many application domains it is not necessarily the case that minimal cardinality diagnoses are the preferred ones – Felfernig et al. (2009) show how recommendation technologies (Jannach et al. 2010) can be exploited for guiding the search for preferred (minimal but not necessarily minimal cardinality) diagnoses.

Algorithms based on the idea of anytime diagnosis are useful in scenarios where diagnoses have to be provided in real-time, i.e., within given time limits. Efficient diagnosis and reconfiguration of communication networks is crucial to retain the quality of service, i.e., if some components/nodes in a network fail, corresponding substitutes and extensions have to be determined immediately (Nica et al. 2014; Stumptner and Wotawa 1999). In today’s production scenarios which are characterized by small batch sizes and high product variability, it is increasingly important to develop algorithms that support the efficient reconfiguration of schedules. Such functionalities support the paradigm of smart production, i.e., the flexible and efficient production of highly variant products. Further applications are the diagnosis and repair of robot control software (Steinbauer et al. 2005), sensor networks (Provan and Chen 1999), feature models (Janota et al. 2014; White et al. 2010), the reconfiguration of cars (Walter et al. 2013), and the reconfiguration of buildings (Friedrich et al. 2011). In the diagnosis approach presented in this paper, we assure diagnosis determination within certain time limits by systematically reducing the number of solver calls needed. This specific interpretation of anytime diagnosis requires a trade-off between diagnosis quality (evaluated, e.g., in terms of minimality) and the time needed for diagnosis determination.

Algorithmic approaches to provide efficient solutions for diagnosis problems are manyfold. Some approaches focus on improvements of Reiter’s original hitting set directed acyclic graph (HSDAG) (Reiter 1987) in terms of a personalized computation of leading diagnoses (DeKleer 1990) or other extensions that make the basic approach (Reiter 1987) more efficient (Wotawa 2001). Wang et al. (2009) introduce an approach to derive binary decision diagrams (BDDs) (Andersen et al. 2010; Bryant 1992) on the basis of a pre-determined set of conflicts – diagnoses can then be determined by finding paths in the BDD that include given variable settings (e.g., requirements defined by the user). A predefined set of conflicts can also be compiled into a corresponding linear optimization problem (Fijany and Vatan 2004); diagnoses can then be determined by solving the given problem. In knowledge-based recommendation scenarios, diagnoses for user requirements can be pre-compiled in such a way that for a given set of customer requirements, the diagnosis search task can be reduced to querying a relational table (see, for example, Jannach 2006; Schubert and Felfernig 2011). All of the mentioned approaches either extend the approach of Reiter (1987) or improve efficiency by exploiting pre-generated information about conflicts or diagnoses.

An alternative to conflict-directed diagnosis (Reiter 1987) are direct diagnosis algorithms that determine minimal diagnoses without the need of predetermining minimal conflict sets (Felfernig et al. 2012; Shchekotykhin et al. 2014). The FastDiag algorithm (Felfernig et al. 2012) is a divide-and-conquer based algorithm that supports the determination of diagnoses without a preceding conflict detection. Such direct diagnosis approaches are especially useful in situations where not the complete set of diagnoses has to be determined but users are interested in the leading diagnoses, i.e., diagnoses with a high probability of being relevant for the user. Also in the context of SAT solving, algorithms have been developed that allow the efficient determination of diagnoses (also denoted as minimal correction subsets) in an efficient fashion (Bacchus et al. 2014; Gregoire et al. 2014; Marques-Silva et al. 2013; Mencia et al. 2014). Beside efficiency, prediction quality of a diagnosis algorithm is a major issue in interactive configuration settings, i.e., those diagnoses have to be identified that are relevant for the user. A corresponding comparison of approaches to determine preferred minimal diagnoses and unsatisfied clauses with minimum total weights is provided in Walter et al. (2016). The authors point out theoretical commonalities and prove the reducibility of both concepts to each other.

In this paper we show how the FastDiag approach can be converted into an anytime diagnosis algorithm (FlexDiag) that allows tradeoffs between diagnosis quality (minimality and accuracy) and performance. In this paper we focus on reconfiguration scenarios (Friedrich et al. 2011; Nica et al. 2014; Stumptner and Wotawa 1999; Walter and Küchlin 2014), i.e., we show how FlexDiag can be applied in situations where a given configuration (solution) has to be adapted conform to a changed set of customer requirements. Our contributions in this paper are the following. First, based on previous work on the diagnosis of inconsistent knowledge bases, we show how to solve reconfiguration tasks with direct diagnosis. Second, we make direct diagnosis anytime-aware by including a parametrization that helps to systematically limit the number of consistency checks and thus make diagnosis search more efficient. Finally, we report the results of a FlexDiag-related evaluation conducted on the basis of real-world configuration knowledge bases (feature models and configuration knowledge bases from the automotive industry) and discuss quality properties of related diagnoses not only in terms of minimality but also in terms of accuracy.

The remainder of this paper is organized as follows. In Section 2 we introduce an example configuration knowledge base from the domain of resource allocation. This knowledge base will serve as a working example throughout the paper. Thereafter (Section 3) we introduce a definition of a reconfiguration task. In Section 4 we discuss basic principles of direct diagnosis on the basis of FlexDiag and show how this algorithm can be applied in reconfiguration scenarios. In Section 5 we present the results of an analysis of algorithm performance and the quality of determined diagnoses. A simple example of the application of FlexDiag in production environments is given in Section 6. In Section 7 we discuss issues for future work. With Section 8 we conclude the paper.

A configuration system determines configurations (solutions) on the basis of a given set of customer requirements (Hotz et al. 2014). In many cases, constraint satisfaction problem (CSP) representations are used for the definition of a configuration task.² A configuration task and a corresponding configuration (solution) can be defined as follows:

An example of a configuration task represented as a constraint satisfaction problem (CSP) is the following.

It can be the case that an existing configuration S has to be adapted due to new customer requirements. Examples thereof are changing requirements in production schedules, failing components or overloaded network infrastructures in a mobile phone network, and changes in the internal model of the environment of a robot. In the following we assume that the pallet of paper should be reassigned to container 3 and the personal computer and games pallets should be assigned to the same container. Formally, the set of new requirements is represented by \(\phantom {\dot {i}\!}R_{\rho }: \{r_{1}^{\prime }: pc = games, r_{2}^{\prime }: paper = 3\}\). In order to determine reconfigurations, we have to calculate a corresponding diagnosis Δ (see Definition 2).

On the basis of the definition of a minimal diagnosis, we can introduce a formal definition of a reconfiguration task.

In the following discussions, the set AC = C ∪ R_ρ ∪ S represents the union of all constraints that restrict the set of possible solutions for a given reconfiguration task. Furthermore, S represents a set of constraints that are considered as candidates for being included in a diagnosis Δ. The idea of FlexDiag (Algorithm 1) is to systematically filter out the constraints that become part of a minimal diagnosis using a divide-and-conquer based approach.

In this section, we present the evaluation we executed to verify the performance of FlexDiag. We first analyze how FlexDiag performs in front of real and randomly generated models and then, compare it with an evolutionary approach.

The following simplified reconfiguration task is related to scheduling in production where it is often the case that, for example, schedules and corresponding production equipment has to be reconfigured. In this example setting, we do not take into account configurable production equipment (configurable machines) and limit the reconfiguration to the assignment of orders to corresponding machines. The assignment of an order o_i to a certain machine m_j is represented by the corresponding variable o_im_j. The domain of each such variable represents the different possible slots in which an order can be processed, for example, o₁m₁ = 1 denotes the fact that the processing of order o₁ on machine m₁ is performed during and finished after time slot 1.

Further constraints restrict the way in which orders are allowed to be assigned to machines, for example, o₁m₁ < o₁m₂ denotes the fact that order o₁ must be completed on machine m₁ before a further processing is started on machine m₂. Furthermore, no two orders must be assigned to the same machine during the same time slot, for example, o₁m₁≠o₂m₁ denotes the fact that order o₁ and o₂ must not be processed on the same machine in the same time slot (slots 1..3). Finally, the definition of our reconfiguration task is completed with an already determined schedule S and a corresponding reconfiguration request represented by the reconfiguration requirement R_ρ = {r1′ : o₃m₃ < 5}, i.e., order o₃ should be completed within less than 5 time units.

This reconfiguration task can be solved using FlexDiag. If we keep the ordering of the constraints as defined in S, FlexDiag (with m = 1) returns the diagnosis Δ : {s₁,s₂,s₃,s₇,s₈,s₉} which can be used to determine the new solution S^′ = {s₁ : o₁m₁ = 3,s₂ : o₁m₂ = 4,s₃ : o₁m₃ = 5,s₄ : o₂m₁ = 2,s₅ : o₂m₂ = 3,s₆ : o₂m₃ = 4,s₇ : o₃m₁ = 1,s₈ : o₃m₂ = 2,s₉ : o₃m₃ = 3} (see Table 7). If we change the parametrization to m = 2, FlexDiag returns the same diagnosis but in approximately half of the time (with 10 iterations, 16 milliseconds were needed on an average for m = 2 whereas 31 milliseconds were needed for m = 1). This is consistent with the estimates in Table 1.

Possible ordering criteria for constraints in such rescheduling scenarios can be, for example, customer value (changes related to orders of important customers should occur with a significantly lower probability) and the importance of individual orders. If some orders in a schedule should not be changed, this can be achieved by simply defining such requests as requirements (R_ρ), i.e., change requests as well as stability requests can be included as constraints \(\phantom {\dot {i}\!}r_{i}^{\prime }\) in R_ρ.

In our work, we focused on the evaluation of reconfiguration scenarios where the knowledge base itself is assumed to be consistent. In future work, we will extend the FlexDiag algorithm to make it applicable in scenarios where knowledge bases are tested (Felfernig et al. 2004). An example issue is to take into account situations where unintended configurations are accepted by the knowledge base. In this context, we will extend the work of Felfernig et al. (2004) by not only taking into account negative test cases but also automatically generate relevant test cases, for example, on the basis of mutation testing approaches. We plan to extend our empirical evaluation to further industrial configuration knowledge bases. Furthermore, we want to analyze in which way we are able to further improve the output quality (e.g., in terms of minimality and accuracy) of FlexDiag, for example, by applying different constraint orderings depending on the observed interaction patterns (of users) and probability estimates for diagnosis membership derived thereof. The better potentially relevant constraints are predicted the better the diagnosis quality in terms of the mentioned metrics of minimality and accuracy. Note that, for example, counting the number of elements already identified as partial diagnosis elements in FlexDiag does not help to keep diagnosis determination within certain time limits, however, this mechanism could be used when determing more than one diagnosis to include diagnosis size as a relevance criterion. Also, in this context will analyze further alternatives to evaluate the quality of diagnoses which go beyond the metrics used in this article.

Efficient reconfiguration functionalities are needed in various scenarios such as the reconfiguration of production schedules, the reconfiguration of the settings in mobile phone networks, and the reconfiguration of robot context information. We analyzed the FlexDiag algorithm with regard to potentials of improving existing direct diagnosis algorithms. When using FlexDiag, there is a clear trade-off between performance of diagnosis calculation and diagnosis quality (measured, for example, in terms of minimality and accuracy).