Ahmad Abdul Karim

Thibaut Gaudin

Alexandre Meyer

Axel Buendia

Saïda Bouakaz

Saida Bouakaz

Adding physical like reaction effects to skeleton-based animations using controllable pendulums

Introduction

Fig. 1: Some example uses of our system. Red arrows represent external perturbations. Green arrows represent the system's response There is a lot of research into developing convenient methods for adapting existing articulated body animations to suit other environments and characters. The joints in a given articulated body can typically have many degrees of freedom, many constraints of length or angles, and additionally are generally required not to allow the body to self-penetrate. Thus, the physics that govern its movement is computationally expensive, numerically imprecise, and often difficult to predict and to control. A recent survey by Welbergen et al. [START_REF] Van | Real time character animation: A trade-off between naturalness and control[END_REF] gives a good overview of the different methods and paradigms used and most importantly the trade offs between animation control and motion naturalness. In this context, there is a crucial demand for real-time methods providing physically plausible, but controllable effects [START_REF] Barzel | Plausible motion simulation for computer graphics animation[END_REF].

We propose an original system, to our knowledge, that adds physical like reaction effects to any skeleton-based object, in real-time with a full user control using our 3D pendulums. The effects we seek to obtain are based on damped oscillatory motions that propagate through an articulated chain. The effect may be visually plausible like a rope moving in the wind, or a body reacting to external forces. They may also be made more cartoonish which is shown in the accompanied video by giving a dancing like effect. In our system each bone of the articulated body is animated by a 3D pendulum. The pendulum is guided by a spring-damper that pulls it toward a user-definable target direction. Our approach has two objectives. Firstly, we ensure body length constraint between any two joints by only working on the angle between the bodies. Secondly, we make a predictable real-time system in which we can control the reaction time to reach a user-defined direction and also the regime (critical or underdamped) of the oscillations around this direction. Our pendulums have three degrees of control: reaction time, damping and target direction. This concept of 3D pendulums may be applicable in a multitude of scenarios with some of them illustrated in Figure 1. We must emphasize that our system is better suited for acyclic bodies and that we do not address the balancing problem in the case of the biped example. Our system is really easy to implement, as we will see in section 3, with no need for a full physics simulation, nor any kind of complex calculations (like the inertia matrix). The mesh of the 3D model is animated with the classical linear blend skinning technique [START_REF] Gain | A survey of spatial deformation from a user-centered perspective[END_REF].

Related Work

Our pendulums oscillate visually like real 3D pendulums by computing their movements with a mass-spring approach. A mass-spring approach is a very simple way to simulate physics-based animation [START_REF] Müller | Real time physics: class notes[END_REF], as it offers an intuitive and flexible means of modeling a mechanical system. In Pixar's movie WALL-E [START_REF] Kanyuk | Brain springs: Fast physics for large crowds in wall-e[END_REF], they used a mass-spring system in a derived fashion to animate large crowds of humans and robots in a believable way.

Editing the motion of an articulated body (producing or modifying an existing animation) is an important topic in computer animation. For instance, some methods aim at warping the time of an existing motion [START_REF] Hsu | Guided time warping for motion editing[END_REF], or combining/blending existing motions (often represented in an animation graph) [START_REF] Reitsma | Evaluating motion graphs for character animation[END_REF]. Others propose the use of signal processing tools to modify animations [START_REF] Bruderlin | Motion signal processing[END_REF].

Parallel of these approaches, an important aspect is to add physical reactions to animations, like blending an existing motion with a physical response [START_REF] Arikan | Pushing people around[END_REF]. Zordan et al. in [START_REF] Zordan | Dynamic response for motion capture animation[END_REF][START_REF] Zordan | Interactive dynamic response for games[END_REF] use a Proportional-Derivative (PD) controller to drive the dynamic body motion toward a re-entry in motion capture data. Our method may be related to a PD controller, and also to the MRAC controller that uses the Adaptive Control proposed by [START_REF] Landau | Adaptive control : the model reference approach / Yoan D. Landau[END_REF] and used in [START_REF] Kokkevis | User-controlled physics-based animation for articulated figures[END_REF]. All of these controllers are like our pendulum bringing a bone to a preferred direction but we differ in several essential ways. Firstly, the other methods always try to return to a preferred direction (or position), even if there is no external perturbations. This introduces a delay in the produced animation between the target pose (keyframe or motion capture data) and the response of the PD controller (as seen in [START_REF] Zordan | Motion capture-driven simulations that hit and react[END_REF]). On the other hand, our system is a superimposed layer over the motion data and only reacts when there is an external perturbation. Our system plays exactly the motion data with no delay, and only adds the reaction effects when needed. Another difference is the controllability; our system is designed to be temporally controlled (control over the reaction time). Temporal control in the case of the PD controller is hard to achieve and demands some hand tuning of the gain constants. In [START_REF] Allen | On the beat!: timing and tension for dynamic characters[END_REF] they show the ability to temporally control PD controllers (using adaptive calculation of the gain constants), but it involves some heavy calculations of the inertia matrix of each joint on each keyframe, with specific calculations in the case of an external perturbation (calculating the re-entry key frame). Finally, all the mentioned controllers are always critically damped. On the other hand, our pendulums can be critically damped or underdamped while maintaining the temporal control. An MRAC controller is designed to be temporally controlled but it calculates and adapts its gain constants on each frame using forces and torque calculations. Our pendulums do not need any adaptive pass once the user sets the reaction time and damping. Additionally, they can be modified in real time.

We differ from other systems of skeleton-driven deformations like [START_REF] Capell | Interactive skeletondriven dynamic deformations[END_REF] in that we concentrate only on deforming the skeleton of the articulated body, without any specific treatment to the mesh. Our mesh is animated by the classical linear blend skinning [START_REF] Gain | A survey of spatial deformation from a user-centered perspective[END_REF]. With no intention to compete against realistic fabric simulation seen in [START_REF] Volino | A simple approach to nonlinear tensile stiffness for accurate cloth simulation[END_REF], we show a rigid tissue represented by a tree of bones animated by our approach with a large time-step and controllable computation.

3D pendulums

In our system, a bone of an articulated body is animated as a pendulum with a configurable target direction as illustrated in Figure 2(a). A pendulum is an anchored bar, with a fixed length L, attracted to its target direction by a spring. This spring pulls the pendulum toward this direction (described in Section 3.1). This idea allows the system to easily add plausible oscillations to any animation with a temporal control (explained in Section 3.2). In Section 3.3 and 3.4 we present our linear algorithm that deals with a tree of pendulums or a skeleton, by propagating the motion of a single pendulum to its father and sons.

3D pendulum principle

We design a pendulum -→ V as a rotating bar attracted to its preferred direction by two springs: one spring on each 2D plane XY and ZY as illustrated in We choose this scheme with two springs instead of one spring to avoid spiral rotation motion around the target direction. The computation of pendulum -→ V motion is done using its projections

--→ V XY , --→ V ZY independently. During the motion, after calculating the two new spring positions in 2D --→ V XY and --→ V ZY , the 3D position - → V is obtained by combining them and ensuring that - → V = --→ V XY = --→ V ZY = L.
In the current implementation we omit the twist component around the axe of the 3D pendulum -→ V which is the third degree of freedom, we plan to add it in a future work. It is interesting to notice that by using the target direction --→ -Y , we can give the impression of gravity that always pulls the bodies toward the ground.

Time Based control for spring dampers

Let m be a mass connected to a spring with stiffness constant k. This mass oscillates around a rest position x 0 with a viscous damper that has a damping coefficient c. Based on Newton's second law of physics the acceleration is ẍ = -(k(x -x 0 ) + c ẋ)/m where x is the current position of the mass, and ẋ is its velocity. We integrate this motion using the Verlet scheme [START_REF] Müller | Real time physics: class notes[END_REF] which was numerically stable during our experiment described in Section 4. Giving a random position x to the mass, it oscillates around the rest value x 0 , seeking to minimize the error (x -x 0 ) until reaching zero. This oscillation depends directly on the constants (k, c, m). In order to achieve temporal control on the spring damper movement, we use the Settling Time T s principle. It is the time required for the mass position x to reach its max amplitude inside a given error interval (See Figure 3(a)) and remains inside it. This interval is symmetrical around x 0 .

T s = - ln(tolerancef raction) ζ * w 0 (1)
Where the tolerance fraction is the needed error interval shown in Figure 3(a), w 0 is the natural frequency and ζ is the damping of the ordinary differential equation governing a damped harmonic oscillator:

mẍ + c ẋ + k(x -x 0 ) = 0 or ẍ + 2 * ζ * w 0 * ẋ + w 2 0 * (x -x 0 ) = 0 with ζ = c 2mw 0 , w 0 = k m (2)
By fixing the tolerance fraction to 5% in equation ( 1) and by using the user provided settling time and damping (critically damped or underdamped), the spring damper constants k and c are calculated from equation ( 2), achieving total control over the curve of the spring damper while maintaining its dynamic aspect.

Under damped Under damped Critical damping Starting

Needed Error Interval The third spring damper is a critical spring damper which converges toward x 0 faster than the others, and without oscillation.

Tree of 3D pendulums

The skeleton of an articulated body is a tree of connected joints (articulations). By connecting several 3D pendulums and by defining the target direction for each one of them, the final result is a tree of pendulums that map the articulated structure, as shown in Figure 3(b). Some of the 3D pendulums act as a father node for several others. When they move, the anchor points of their children move. In order to have a visually believable reaction, these 3D pendulums need to interact with each other. We define two strategies used in conjunction to achieve this goal: Father Pursuit strategy and Son Pursuit strategy. In the accompanying video we show the similarities between the motion of a chain of pendulums fullyphysically simulated and our chain of 3D pendulums that incorporate these strategies. For simplicity, these strategies will be described in a 2D plane.

3.3.1 Father Pursuit Strategy. The objective of this strategy is to propagate the motion of the father 3D pendulum toward its children, thus they need to incorporate this movement in their own motion. Figure 4(a) illustrates two connected pendulums P A ,P B , A,B are the positions of each mass, L A ,L B are the lengths of the bars, and θ A ,θ B are the errors that each pendulum seeks to minimize. In this example the preferred direction of the pendulums are identical (the dashed --→ Y ). The update system is a top-down system scheme, starting from the anchor toward the leaf. First, on time t 1 (in black) the error that we try to minimize is θ A1 in P A and θ B1 in P B . Now, on time t 2 (in red):

1. P A moves, its spring damper tries to minimize the error, and has a new position A2. 2. P B : the angle ε AB between the two vectors ---→ B1A1 and ---→ B1A2 is added to its own error, α B = θ B1 + ε AB . Without this process, the new position of P B would have been B3 (in green), which is not correct and would have produced a non-logical disconnected motion. This Father Pursuit process is extended to every pendulum in the chain. A third pendulum P C follows the motion of its father P B , and so on. By extending this process in 3D we have a totally plausible physical chain of 3D pendulums (as seen in the accompanying video). Each one reacting to its father's movement while oscillating around its target direction.

Son Pursuit Strategy.

The objective of this strategy is to reflect the perturbation that can occur on the son level, to reflect it on its father. It occurs when the mass of P B takes a perturbation as seen in Figure 4(b) (in green). The perturbation is regarded as a change in the position, as if we only take the final position resulted of an impulse applied to a rigid body.

1. The perturbation induces its full impact as if the mass P B was not attached (in red). 2. P B 's mass has two positions: B1 (the old one) and B3 (the new one).

Inverting the previously detailed computation of the father induced error ε AB , we calculate the child error ε BA , the angle between ---→ A1B3 and ---→ A1B1 and adding it to θ B1 , we obtain α B = θ B1 + ε BA . 3. The mass of P A should follow, as it is being pulled by its son now. The new position A3 is calculated easily by choosing on the line A1B3 the point A3 where A1B1 = A3B3 . 4. This process propagates toward the anchor. 5. The new positions are recalculated based on the fixed anchor position.

With this scheme, all the errors that the spring dampers need to minimize because of a perturbation are calculated in a bottom-up way starting from the son that took the perturbation toward the anchor.

Final workflow.

In a tree of pendulums, calculation cycles may occur when two nodes are influencing each others in an endless loop (father influencing its son, then the son influencing its father, and so on.). To avoid these kinds of loops, we use an update system inspired by Featherstone's divide and conquer algorithm [START_REF] Featherstone | A divide-and-conquer articulated body algorithm for parallel o(log(n)) calculation of rigid body dynamics. part 1:basic algorithm[END_REF][START_REF] Featherstone | A divide-and-conquer articulated-body algorithm for parallel o(log(n)) calculation of rigid-body dynamics. part 2:trees,loops,& accuracy[END_REF]. This algorithm eliminate any cyclic calculation problems and breaks the computation into two main linear passes. The first is a bottom-up pass through the articulated body tree, and the second is carried out from the top to the bottom. We adopt this paradigm completely. Only the calculations differ, as listed below:

1. For each 3D pendulum perturbed in the tree: resolve this perturbation by applying it on its mass then calculate the errors ε in a bottom-up iteration toward its ancestors according to the Son Pursuit strategy. 2. For each father 3D pendulum integrate all the children errors (ε 1 ,ε 2 etc.) to its own error θ. 3. Start the standard top-down pass starting from the anchor toward the leaf according to the Father Pursuit strategy.

In the previous step 2, there are many ways to calculate the integration:

-Summing up all the perturbation errors coming from its children: it is the method used to produce all of our results. It is the simplest method, and the one we chose after testing. -Calculating an average: the father node will be perturbed in the same direction as the previous method, but with less amplitude. It is useful when the application decides that the father should be less affected by its children.

-Doing a weighted average based on:

• The Mass: the heavier son has more influence on its father.

• The importance of each branch: assigning predefined priorities on the children.

We can imagine many other possibilities based on a specific application's needs.

Our system is quite easy to implement and the actual calculations in each strategy require only basic knowledge of 3D vector math. No prior knowledge of physics systems is required; we do not compute the inertia matrix nor we use the notion of force. At the same time we can use physics principles to enhance the end result like in the case of the father pendulum integrating its children's errors based on the inertia matrix.

3D model Skeleton Vs. 3D pendulums tree

In the following section we demonstrate our system with skinned 3D models, using a predefined skeleton to construct the pendulums tree. Starting from the bind pose (rest pose) of the skeleton, we create a 3D pendulum for each skeletal connection (bone) with the same length and with its preferred rest direction calculated from the bone rest pose orientation. By maintaining the hierarchy of the base skeleton, we have a pendulums tree that maps this skeleton perfectly. While playing motion data, we modify the target direction of each corresponding pendulum, mimicking the base animation exactly. If the 3D pendulums start to react to an external perturbation, each of the 3D pendulums orientation and position is applied to its corresponding bone.

Applications and Results

In this section, we present several ways to use the 3D pendulums tree: adding physical effects to lifeless models like an octopus, modifying pre-defined motion data with physics reactions, and anecdotally a cloth simulation (which is normally a closed-loop problem). In all cases, the pendulum's reaction time, damping, and target direction is totally controllable. The results were computed on an Intel Core 2 Duo 2GHz, 2 GB RAM, with an ATI X1400, 256 MB. Our experimentation does not manage collisions, but we can easily imagine a system that creates an impulse (change in the position) on each 3D pendulum to counter any penetrations that occur.

Adding physical reaction effects to any skeleton-based bodies

In Figure 5, we use our system on a lifeless octopus model. By adding some simple procedural animation to its tentacles (pulling only the root node of each tentacle toward the center at random intervals) the rest of the model reacts in a passive way, modifying the animation and adding plausible physics effects. The octopus model consists of 150 joints and the computation time of our superimposed physical effects is only 0.3 ms. Fig. 5: From top left: [START_REF] Allen | On the beat!: timing and tension for dynamic characters[END_REF] the model with its 3D pendulums, [START_REF] Arikan | Pushing people around[END_REF] rest pose, [START_REF] Barzel | Plausible motion simulation for computer graphics animation[END_REF] we pull all the tentacles toward the center, [START_REF] Bruderlin | Motion signal processing[END_REF] reacting, [START_REF] Capell | Interactive skeletondriven dynamic deformations[END_REF] tentacles overshooting (underdamped regime), [START_REF] Featherstone | A divide-and-conquer articulated body algorithm for parallel o(log(n)) calculation of rigid body dynamics. part 1:basic algorithm[END_REF] return to rest pose

We can also use our system on animated models. In that case on each frame, the motion data takes control of the skeleton changing the preferred direction of each pendulums. With no external perturbations, the 3D pendulums rigorously follow the animation data. When an external perturbation occurs, our system reacts to this while continuously trying to return to the desired target pose. With such a technique, our system adds plausible physical reaction effects to predefined animation data, as a superimposed animation layer. These reactions can furthermore be customized by making a section of the body more rigid, more flexible, changing the reaction time, or tuning the damping. This gives the end user a powerful tool to modulate the reaction of the body in a very easy and intuitive way. Fig. 6: From top Left: [START_REF] Allen | On the beat!: timing and tension for dynamic characters[END_REF] Original (on the left) and our simulated articulated body (on the right), [START_REF] Arikan | Pushing people around[END_REF] Two perturbations, [START_REF] Barzel | Plausible motion simulation for computer graphics animation[END_REF] to [START_REF] Capell | Interactive skeletondriven dynamic deformations[END_REF] Reaction and returning to the original keyfarme By playing only the animation data on our test machine, for the previous model in Figure 6 with 92 joints, the average computation time for each frame is 0.06 ms. When playing the same animation using our pendulums and two perturbations, the computation time rises to an average of 0.46 ms, which stays negligible. This added cost is the result of reading the motion capture data in order to change the pendulum's target direction, integrating the perturbation, and then performing the main integration (as previously described).

Cloth Simulation

Although cloth is a closed loop problem, we are capable of giving the impression of an animated cloth by simply creating several vertical 3D pendulums that cover . By doing a weighted average between the positions of all horizontal pendulums activated by their vertical father, weighted based on the distance between each horizontal pendulum and its vertical father, we compute the final cloth position. This results in a fully reactive cloth, without any tearing problems, that maintains its horizontal and vertical dimensions, while giving total control over the reaction time. We are not aiming to compete against more general, visually and physically accurate cloth simulators that are better suited to simulate actual human cloth, for example. We are just proposing a less sophisticated, but stable and relatively fast method that can plausibly simulate the motion of reactive cloth. In Figure 7(b), an external perturbation is applied to the middle three vertical pendulums. In order to optimize calculation time, those three vertical pendulums are the only ones actively being simulated (with the horizontal children of each one of them). The mesh is simulated using approximately 1500 3D pendulums. The average calculation time of these pendulums with the post calculations for the final cloth is around 5 ms.

Conclusion and Future Work

Our system is linear, straightforward, and based on simple 3D pendulums. It is capable of adding physical like reaction effects to skeleton-based body very easily. Additionally it is highly customizable: we can control reaction time, target direction and damping of the motion. The current system does not enforce angular constraints. We need to incorporate them into our future work in order to simulate real-life joint constraints that exists in most skeleton-based bodies. In addition to this, we are investigating coupling the system with a balance solver. This work would provide a body with the ability to actively work to maintain its balance, in opposition to the passive reactions described in this paper. Our system could also be used to mimic hair, which is an acyclic system and fits neatly in the domain that the 3D pendulums system can simulate.

Fig. 2 :

 2 Fig. 2: (a) 3D pendulum (b) A 3D pendulum composed of two 2D pendulums with Y as their preferred direction

Fig. 3 :

 3 Fig. 3: (a) Spring oscillation under different damping (b) 3D pendulums Tree in Black with target direction in Grey

3 .Fig. 4 :

 34 Fig. 4: (a) Father Pursuit Strategy (b) Son Pursuit strategy

Fig. 7 :

 7 Fig. 7: (a) A cloth represented as a tree of pendulums (b) Cloth being pulled in the middle with a visual representation of the 3D pendulums


domain: spi info

text:
Lei Lin

Ivana Rasovska
email: ivana.rasovska@insa-strasbourg.fr

Roland De Guio

Sébastien Dubois
email: sebastien.dubois@insa-strasbourg.fr

Algorithm for identifying generalised technical contradictions in experiments

Keywords: TRIZ, generalised technical contradiction, design of experiments, binary programming. MOTS-CLES : TRIZ, contradiction technique généralisée, plan d'expériences, programmation binaire

This paper proposes an algorithm for identifying and extracting generalised technical contradictions from experiments, Contradictions are used as the starting point for certain approaches to inventive problem solving. These methods are based on dialectical contradictions, which are used for understanding and representing inventive problems. The resolution of such problems is actually the resolution of the identified contradictions, which cannot be solved by optimisation methods and must be solved using inventive principles. The proposed algorithm uses the output data from design of experiments based on statistical theory as input data. The objective of this algorithm is to identify the complete set of generalised technical contradictions.

RESUME. Ce papier propose un algorithme d'identification et d'extraction des contradictions techniques généralisées utilisées comme point de départ de certaines démarches de résolution de problème d'invention. Ces approches basées sur la dialectique identifient les contradictions afin de mieux comprendre et représenter les problèmes d'invention. La résolution du problème passe ensuite par la résolution de la contradiction qui empêche a priori de résoudre le problème par le biais des méthodes d'optimisation et nécessite l'utilisation des principes de résolution inventives. L'algorithme proposé utilise comme entrée les données issues d'une méthode statistique connue dans le domaine technique comme le plan d'expérience. L'objectif de l'algorithme est d'identifier l'ensemble complet des contradictions techniques généralisées. Dans le papier nous présentons le problème combinatoire, sa complexité et évaluons ses limites sur des exemples.

Introduction

Inventive design involves special problem-solving principles for proposing new creative solutions that satisfy design requirements. Among these special problemsolving methods is the theory of inventive problem solving (TRIZ) proposed by [START_REF] Altshuller | Creativity as an Exact Science[END_REF]. According to [START_REF] Savransky | Engineering of Creativity Introduction to TRIZ Methodology of Inventive Problem Solving[END_REF], the TRIZ ideology is based on two major ideas: contradiction and ideality. Contradiction is the basic law of materialist dialectics and is linked to technical problem formulation, whereas ideality is the essence of idealism and is related to the final solution. Both of these concepts should be consciously included in any inventive problem-solving process. As a dialectical based theory, the TRIZ attributes the existence of system evolution problems to a set of contradictions between system parameters. The principal motivations for the use of dialectical based approaches are twofold: identify contradictions to better understand and express inventive design problems and to view the procedure of inventive problem solving as a procedure of contradiction resolution. At the beginning of the problem-solving process, the contradictions must be clearly defined and comprehensible. Indeed, a misguided contradiction choice may lead to a decrease in the efficiency or even effectiveness of the problem-solving process. Hence, contradiction extraction and interpretation play a dominant role in the dialectical problem-solving approach.

Despite the fact that different models of contradictions were introduced by [START_REF] Altshuller | Creativity as an Exact Science[END_REF] based on patent analysis, there are gaps in procedures for contradiction gathering and representation. The concept of representing a design problem as a network of contradictions and using semantic rules to drive design using this network was introduced in [START_REF] Cavallucci | Towards inventive design through management of contradictions[END_REF]. A formal definition of contradiction and its potential variations was proposed in [START_REF] Rousselot | Towards a formal definition of contradiction in inventive design[END_REF]. The concept of a "contradiction cloud" as a three-value graphical representation of a set of elementary contradictions was presented in [START_REF] Cavallucci | On contradiction clouds[END_REF]. Another algorithm for extracting the most important contradiction in a network of problems [START_REF] Khomenko | A framework for OTSM-TRIZ Based Computer Support to be used in Complex Problem Management[END_REF] was proposed in [START_REF] Baldussu | Network of contradictions analysis and structured identification of critical control parameters[END_REF]. Almost all of these proposals are based on technical contradictions. A technical contradiction that occurs between two system parameters is a contradiction in which the improvement of one parameter leads to a degradation in the other. Given a set of situations, a TRIZ technical contradiction between two parameters Y1 and Y2 exists if each time parameter Y1 meets the design objectives, the parameter Y2 does not and vice versa.

Searching for this type of contradiction is simple because the goal is to find pairs of parameters that are never satisfied at the same time. In actuality, this classical TRIZ model of technical contradictions does not always exist. Indeed, the general trend that is observed can be summarised as follows: the more experiments and knowledge about a system there are, the lower the chance of there being a technical contradiction is (i.e., an input for inventive problem-solving methods). Moreover, this model takes into account only two evaluation parameters. Let us suppose that there exists a technical contradiction, we are able to solve it, and we cannot say anything about the satisfaction of the other evaluation parameters. Such a case exemplifies the interest in generalised technical contradictions (GTCs). The GTC model, which was presented in (Rasovska et al., 2008), replaces the two evaluation parameters that exhibit a classical technical contradiction with two concepts of evaluation parameters. A concept consists of an evaluation parameter or a logical disjunction of several evaluation parameters. One parameter can only participate in one of the two concepts involved in a GTC. The desired result is the simultaneous satisfaction of the two concepts. In each concept, there is at least one or more evaluation parameters, the solution of each generalised technical contradiction should satisfy all of the evaluation parameters associated with the two concepts. Thus, the result will be better than that in the case of classical technical contradictions.

To extract contradictions, information about the technical system of interest is required. Our method uses the outputs of a design of experiments (DoE), which is a statistical optimisation method that can be used to describe relations between the input and output parameters of a system and/or optimise the output of a system for a given set of input parameters [START_REF] Montgomery | Design and Analysis of Experiments[END_REF]. A theoretical bridge between the DoE and generalised technical contradictions was presented in (Dubois et al., 2009a).

In an effort to design operational methods using this link, this paper proposes an exact algorithm for identifying the entire set of generalised technical contradictions that occur in the design of experiments (DoE). To the best of our knowledge, no exact algorithm has been developed to address this problem. First, the principals of the DoE and generalised technical contradictions are illustrated using the concrete example of an electrical circuit breaker. The research space of generalised technical contradictions is defined by the number of system parameters and the number of experiments involved. The difficulty of resolving the problem is discussed, and we will show that the problem is NP-hard. The theoretical assumptions and the binary programming model used to extract the generalised technical contradictions and the search algorithm are introduced using time and space complexity analysis. The final section of the paper introduces the results of the real case of an electrical circuit breaker. Moreover, the interpretation of the results for the general population of binary matrices is presented in accordance with the principles of the design of experiments and with the aid of statistical analysis methods. Finally, different experiments in which our algorithm can be implemented are discussed to demonstrate the algorithm's time consumption and its limitations.

Problem description

Design of experiments and generalised system of contradictions

The design of experiments (DoE) [START_REF] Montgomery | Design and Analysis of Experiments[END_REF] is based on the analysis of experimental data. For the purposes of our study, DoE results were transformed and summarised into a binary rectangular matrix. Because generalised technical contradictions are not related to action parameters, the binary matrix can be reduced to its evaluated form denoted Z, as shown in figure 1a. The rows of the matrix represent the experiments, and the columns correspond to the evaluation parameters.

The generic term z ij of matrix Z equals 1 when the experiment e i meets the design requirements for the evaluation parameter y j and 0 otherwise. The design goal is to satisfy all of the evaluation parameters, i.e., to find any row of ones. When it is not possible to obtain such output using only the action parameters, inventive methods must be implemented. The binary matrix used in our case is illustrated using the example of an electrical circuit breaker. The circuit breaker is a simple technical system whose components are shown in figure 2.

Figure 2. Components of electrical circuit breaker

When an overload occurs, the overload creates a force (due to magnetic and electrical fields), which operates a piece called a firing pin. The firing pin opens the circuit by activating the switch located in the circuit breaker. In the case of a high overload, the firing pin-a plastic stem-cannot be reused. The problem has been studied and the main evaluation parameters defined as follows: y1: circuit breaker disrepair (satisfied -1, unsatisfied -0) y2: circuit breaker reusability (satisfied -1, unsatisfied -0) y3: spring core mounting (satisfied -1, unsatisfied -0) y4: firing pin bobbin mounting (satisfied -1, unsatisfied -0) y5: normal mode release (satisfied -1, unsatisfied -0) y6: firing pin initial position return (satisfied -1, unsatisfied -0)

The system's behaviour under the design parameters was modelled by a DoE, the outputs of which were transformed into the binary matrix Z shown in Fig. 1b. This experiment does not exhibit any classical TRIZ contradiction. Indeed, each pair of evaluation parameters is simultaneously satisfied in at least one experiment (for instance, y1 and y2 in experiment e4, as shown in figure 3a). Nevertheless, there always exists a generalised technical contradiction (Dubois et al., 2009b). An example of a GTC is illustrated in figure 3b: when the first concept of evaluation parameters "y1 and y3 fit requirements" is satisfied, the second concept "y2 and y5 fit requirements" is not satisfied and vice versa. Identifying GTCs in the customised DoE table representation requires defining the properties of GTCs. GTCs can be characterised by the set of definitions that allow for the extraction of GTCs from a DoE. Let us suppose that there is no experiment satisfying all of the evaluation parameters at the same time. Identifying a GTC in such a DoE involves searching for:

y1 y2 y3 y4 y5 y6 e1 1 0 1 1 1 1 e3 1 0 1 0 0 0 e7 1 0 1 0 0 0 e5 1 0 1 0 1 1 e8 1 0 0 1 1 1 e6 0 1 0 1 1 1 e9 0 1 0 1 1 1 e2 0 1 0 0 1 1 e4 1 1 1 1 0 0 Y1 Y2 Y0 y1 y3 y2 y5 y4 y6 e1 1 1 0 1 1 1 E1 e3 1 1 0 0 0 0 e7 1 1 0 0 0 0 e5 1 1 0 1 0 1 e6 0 0 1 1 1 1 E2 e9 0 0 1 1 1 1 e2 0 0 1 1 0 1 e4 1 1 1 0 1 0 E0 e8 1 0 0 1 1 1 (a) (b)
1. Three sets of evaluation parameters ( )

0 , 2 1 , Y Y Y
whose union is the entire set of evaluation parameters and whose intersection is an empty set.

2. Three sets of experiments ( )

0 , 2 1 , E E E
whose union is the entire set of experiments and whose intersection is an empty set.

3. The satisfaction of the first set of evaluation parameters Y 1 for the first set of experiments E 1 and the satisfaction of the second set of evaluation parameters Y 2 for the second set of experiments E 2 .

4. At least one evaluation parameter from the second set of parameters Y 2 that is not satisfied in each experiment of the first and third sets of experiments E 1 and E 3 .

5. At least one evaluation parameter from the first set of parameters Y 1 that is not satisfied in each experiment of the second and third set of experiments E 2 and E 3 .

Formulating generalised technical contradiction

Using the requirements described above, we can formulate the GTC as shown in figure 4.

Figure 4. Generalised technical contradiction expressed in DoE

We denote the original DoE result by matrix Z (the rows are the experiments; the columns are the responses). Figure 4 shows the matrix of the DoE derived by grouping the columns and the rows. The matrix has been divided into 9 blocks, and in the figure, we have formulated the features into blocks. In the blocks E1×Y1 and E2×Y2, all of the elements are equal to 1. In the remaining 4 blocks associated with Y1 and Y2, there must be at least one element equal to 0 in each row.

Difficulty of problem resolution -NP-hard problem

To identify the generalised technical contradictions, we are first interested in the size of our search space. In other words, we are interested in answering the following question: how many candidate solutions can we find when searching for generalised technical contradictions? If this problem is viewed as a searching problem, we can use a brute force algorithm to browse the solution space by an enumeration method. Although enumeration is feasible for some small matrices, it can be difficult or even impossible for large matrices. In fact, the search space grows exponentially with the number of rows M and number of columns N of the matrix Z. The following section discusses the analysis of the complexity of a search space.

Quantifying a search space is mainly a combinatorial problem because all possible matrix blocks can be expressed using Stirling numbers of the second kind [START_REF] Brualdi | Chapter 8 Special Counting Sequences[END_REF]. In actuality, the sets 0 0 , E Y may be empty. Therefore, row combinations and column combinations can be addressed using two types of combinatorial models. In the first case, when φ = 0 Y , the problem can be described as a type of Ball-Box Matrix [START_REF] Brualdi | Chapter 8 Special Counting Sequences[END_REF] , which describes the situation in which N (N>2) different balls are placed in two identical boxes and neither box is empty. In this case, the number of combinations, expressed as a Stirling number of the second kind, is ( )

2 , N s . In the second case, when φ ≠ 0 Y
, the problem can be described by a Ball-Box Matrix that describes the situation in which N different balls are placed in three identical boxes and no box is empty; however, here, we must select 2 of 3 boxes 1 Y and2 Y . Thus, the result is ( )

3 2 3 , C N s
× . The same applies to the column number; thus, the number of combinations of column numbers is ( ) ( )

2 , 3 , 3 2 N s C N s + ×
. In addition, when we permute two column sets and two row sets for

1 1 Y E × and 2 2 Y E × ,
only two distinct cases arise. To summarise, we conclude that the search space size is

( ) ( ) ( ) 2 , 3 , 3 2 M s C M s + × ( ) ( ) ( ) 2 2 , 3 , 3 2 × + × × N s C N s .
According to the equation for Stirling numbers of the second kind [11],

( ) ( ) ( ) ∑ = - ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ - = k t N t t k t k k k N s 0 1 ! 1 , (1) ( ) 1 2 2 , 1 - = - N N s (2)
Using equations ( 1) and ( 2) and supposing

3 , 3 ≥ ≥ M N
, we obtain the size of our search space:

2 2 2 1 3 2 2 1 3 × ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ - + × ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ - + M M N N (3)
Clearly, the browsing of the search space is an NP-hard problem.

Problem formulation

Transformation of the generalised technical contradiction research problem into a binary integer program problem

Our problem is similar to several problems in different research areas. The problem can be classified as a data mining problem (methods and models used in data mining are reviewed in [START_REF] Larose | Data mining methods and models[END_REF]. Data mining is the analysis of observational data sets to find relationships between parameters and to represent the data in understandable and useful ways for the data owner. Our problem is also quite similar to seriation and matrix reordering problems, which seek to reorder objects into a sequence along a one-dimensional continuum [START_REF] Liiv | Seriation and matrix reordering methods: An historical overview[END_REF] by exploratory combinatorial data analysis techniques. Our problem can also be approached using two-mode clustering methods [START_REF] Mechelen | Two-mode clustering methods: a structured overview[END_REF], [START_REF] Marcotorchino | A unified approach of the Block-Seriation Problems[END_REF]. Such methods provide a simultaneous clustering of the rows and columns of a rectangular data matrix but cannot restrict other parts of the matrix. All available methods associated with the above-mentioned approaches can be used to find one or several unique solutions to our problem, but not one can find all of them. In this paper, we use the binary integer programming model to analyse our problem, which results in a specific algorithm providing all of the solutions of this problem.

Identifying GTCs is generally considered a problem of defining how to group the columns and rows of matrix Z, which is a yes-or-no decision problem that can be transformed into a binary integer program, a linear programming problem in which all of the variables are restricted to binary values [START_REF] Chen | Applied Integer Programming -Modeling and Solution[END_REF]. Specifically, in BIP, each variable can only take a value of 1 or 0 denoting yes or no. Thus, a BIP can be used to model real-world situations using logical expression. In our problem, a BIP is used to express decision variables that indicate whether the columns or rows pertain to the columns and rows of a matrix block.

Suppose that matrix Z has M rows and N columns. Let us denote the parts of a 3partition of the columns and rows as { }

0 2 1 , , Y Y Y and { } 0 2 1 , , E E E , respectively.
Our goal is to find all of the 3-partitions of the column set and 3-partitions of the row set that meet the requirements indicated in figure 4.

First, we use two N-dimensional binary vectors C 2 , 1 = i to denote the two sets of columns ( 2 1 ,Y Y ).
If one vector component of C 1 (resp. C 2 ) equals 1, the corresponding column belongs to the column set Y 1 (resp. Y 2 ); otherwise, it does not belong to Y 1 (resp. Y 2 ). Second, we use two M-dimensional binary vectors R i= 1,2 to denote the two sets of rows ( 21 , E E

). If one vector component of R 1 (resp. R 2 ) equals 1, the corresponding row belongs to the row set E 1 (resp. E 2 ). The vectors are as follows:

( ) N i N i i i i c c c c C ,..., , , 3 2 1 2 , 1 = = , ( ) M i M i i i i r r r r R ,..., , , 3 2 1 2 , 1 = = ; C 2 , 1 = i represents 2 , 1 = i Y , 2 , 1 = i R represents 2 , 1 = i E .
For convenience, we assume that

⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ = ∑ j j c N 1 1 , ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ = ∑ j j c N 2 2 , ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ = ∑ j j r M 1 1 , ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ = ∑ j j r M 2 2 .
Our problem can then be transformed into an integer programming problem. The restrictions regarding block 4 can become an objective function, as

1 1 Y E × and 2 2 Y E × indicated in figure
T i i ZC R is equal to the sum of all elements in the block i i Y E × . i i M N
is the product of the number of rows and columns of the block

( ) i i Y E , .When the blocks ( ) 1 1 ,Y E and ( ) 2 2 ,Y E are full of "ones", the quantity ∑ ∑ = = - 2 , 1 2 , 1 i i i i T i i M N ZC R
is equal to zero and negative otherwise. It is clear that the maximum value of this equation is zero.

The restriction for the block 4 indicates that the cardinality of 1 Y is greater than the sum of the elements in each row of the block 1 2 Y E × . Thus, we have the inequalities for each row of

1 2 Y E × shown in figure
1 2 Y E × : 1 1 1 1 , 1 : 1 ≥ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ - ∑ ∈ = C c c j ij j j z N .
Using the same method to model the block

2 1 Y E × , 2 0 Y E × and 1 0 Y E × provide
three additional groups of inequalities. It should be noted that the membership of a row to 0 E is determined by the complementary set

2 1 E E ∪ .

Definition of integer programming problem

To summarise, the search problem subject to the restrictions shown in figure 4 becomes a problem of calculating all of the solutions of the following integer programming problem: Decision variables:

( )

1 1 3 1 2 1 1 1 ,... , , n c c c c C = , (
)

2 2 3 2 2 2 1 2 ,... , , n c c c c C = , (
)

1 1 3 1 2 1 1 1 ,... , , m r r r r R = , ( )
2 2 3 2 2 2 1 2 ,... , , m r r r r R = . Input parameter: matrix Z Objective function: Maximise ∑ ∑ = = - 2 , 1 2 , 1 i i i i T i i M N ZC R (4) subject to 1 1 1 1 , 1 : 1 ≥ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ - ∑ ∈ = C c c j ij j j z N , { } 2 2 2 , 1 | R r r i i i i ∈ = ∈ ∀ (5) 1 2 2 2 , 1 : 2 ≥ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ - ∑ ∈ = C c c j ij j j z N , { } 1 1 1 , 1 | R r r i i i i ∈ = ∈ ∀ (6) 1 1 1 1 , 1 : 1 ≥ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ - ∑ ∈ = C c c j ij j j z N , { } 1 1 1 2 2 2 , 0 , , 0 | R r r R r r i i i i i i ∈ = ∈ = ∈ ∀ (7) 1 2 2 2 , 1 : 2 ≥ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ - ∑ ∈ = C c c j ij j j z N , { } 1 1 1 2 2 2 , 0 , , 0 | R r r R r r i i i i i i ∈ = ∈ = ∈ ∀ (8) ( ) M R R 1 ,..., 1 , 1 2 1 ≤ + (9) ( ) N C C 1 ,..., 1 , 1 2 1 ≤ + (10) 1 , 0 ; 1 , 0 = = j i j i r c (11) 0 , , , 2 1 2 1 ≠ R R C C (12)
This BIP is nonlinear because the object function is a polynomial; however, the program can be transformed into a linear one according to the procedure described in reference [START_REF] Chen | Applied Integer Programming -Modeling and Solution[END_REF].

Relaxation of binary programming problem into sub-problems

The binary programming problem described above cannot be solved by any ordinary method. On the one hand, the search space grows exponentially with the parameters N and M; therefore, the problem cannot be solved by brute force searching. On the other hand, our goal is to obtain all solutions meeting the maximum number of conditions; thus, the basic approach to linear BIPs, such as branch and bound or branch and cut, are invalid, giving rise to the design of a new algorithm for solving this problem. ; thus, we want to simplify the binary problem to a set of sub-problems, the merging of which provides the solution to the original problem. The generic search sub-problem is illustrated in figure 5.

We use the vectors We can use the same approach used previously to define the object function:

( ) M M r r r R ,..., , 2 1 1 = , = 1 C ( ) N N c c c c ,... , ,
1 1 1 1 N M ZC R T -
, the maximum value of which is zero. Moreover, its accompanying block ( ) Y E, underneath has at least one element equal to 0 for each row, which can be formulated by the inequalities:

1 1 , 1 : 1 ≥ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ - ∑ ∈ = C c c j ij j j z N , { } 1 , 1 | R r r i i i i ∈ = ∈ . Decision variables: ( ) M M r r r R ,..., , 2 1 1 = , ( ) N N c c c c C ,... , , 3 2 1 1 =
Input parameter: matrix Z; Maximise:

1 1 1 1 N M ZC R T - (13) Subject to: 1 1 , 1 : 1 ≥ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ - ∑ ∈ = C c c j ij j j z N , { } 1 , 0 | R r r i i i i ∈ = ∈ (14) 1 , 0 ; 1 , 0 = = i i c r (15) ; R φ ≠ 1 φ ≠ 1 C
After all of the results of the sub-problems are gathered, we need to combine the blocks to solve the original problem. The combinatorial strategy is to examine all of the combinations of the two results of the sub-problem with the following rule: If the intersection of their row sets and column sets are empty (

φ = ∩ 2 1 E E φ = ∩ 2 1 , Y Y
), the blocks ( )

Problem resolution

Search algorithm for the sub-problem

Now, we describe the method for addressing the sub-problem. We can generally search the pattern along two directions: along columns and rows. Because our problem has a restriction regarding E , we search the blocks row by row.

The searching procedure consists of five steps:

1. Let i =1.

2. Select the columns' set, the elements of which equal 1 in row i.

3. Select one subset of the columns' set defined in step 2. If the column set was previously selected in another row, reselect the subset. If not, mark the column set as having been checked.

4. Store this column set as the block column set, and add row number i to the row set of the block. Look up the row k, k>i, if it has the same column set in which elements equal 1, add the row number in the block row set.

5. Output block as one solution: if the column set in row i does not finish traversing, return to 3. Else, if i=M, the algorithm terminates; otherwise increment i by 1, and return to 2.

In step 3, another problem that must be addressed is traversing the subsets of subsets. The problem is essentially a Generating All n-Tuples Problem.

Equivalently, we want to visit all n-Tuples ( )

n y y y ,... , 2 1
where each

1 or 0 = i y .
One can find more details in reference [START_REF] Knuth | Chapter 7 Combinatorial Searching. The art of computer programming. volume 4A combinatorial algorithm[END_REF].

In the following, we explain why the search algorithm can obtain all of the solutions of the sub-problem. First, we prove that the blocks are solutions of the subproblem. It is explicit that the elements in block are equal to 1; thus, they meet the requirements of the objective function. Equivalently, it is clear that each row in block ( ) Y E, has at least one element equal to 1; if not, according to the algorithm, the row whose elements are equal 1 will be added to the block row set. Second, we prove that the algorithm can gather all of the solutions. Suppose that there exists a block that is the solution of the sub-problem. Thus, all of its elements are equal to 1 to meet the requirements of the objective function, and each row in the block ( ) Y E, has at least one element equal 1 to satisfy the restriction. The block's row number set must have its smallest element ranked above the others; when the algorithm operates on this row, the block column set pertains to this row column set, as long as it has not been previously checked. Thus, this algorithm yields all of the solutions.

Time and space complexity analysis

We presume that the maximum number of elements equal to 1 in each row is n and the row number is M ; thus, the time consumed by visiting all of the possible combinations of elements equal to 1 is ( )

n M O 2 × .
Moreover, we must scan the remaining rows (fewer than M rows remain). Therefore, the time complexity in the searching phase is (

)

n M M O 2 × ×
. Suppose that the number of blocks in the searching phase is S ; thus, time complexity in the comparing phase is ( )

( ) 2 2 1 S O S S O = ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ -
. In conclusion, the time complexity is ( )

2 2 2 S M O n + ×
.The principal space cost is related to the storage of the blocks in the searching step. Because the number of blocks is lower than N 2 , the space complexity is ( )

N O 2

Illustration of results in the case of electrical circuit breaker

The purpose of this section is twofold: in the first part, we will use a circuit breaker example to illustrate the various concepts of technical contradictions presented in the paper. The algorithm used on the concrete case helps us to measure the number of technical contradictions as well as generalised technical contradictions in the real case. In the second part, we will examine a sample of matrices with the same number of rows and columns as the matrix considered in the electrical circuit breaker example but with different numbers of evaluation parameters equal to 1. This study is done to confirm the real case results and to measure and compare different possible but quite similar cases. In our future research we want to compare the results of our automatic approach with the results of human expert's analysis. For the moment our study points out the complexity of such a search and relatively small number of found technical contradictions versus a big quantity of found generalised technical contradictions. Furthermore, the effect of the density of ones (the number of satisfied evaluation parameters) on the number of technical and generalised technical contradictions will be studied.

Generalised technical contradictions

The first set of experiments concerned the search for generalised technical contradictions in the case of an electrical circuit breaker (figure 7). We identified 117 generalised technical contradictions within the 341 possible pairs of concepts. As an example, we discuss four different GTCs, which can be interpreted as follows.

GTC #1 represents the contradiction between the circuit breaker reusability y2 and both the spring core mounting y3 and normal mode release y5. GTC #2 represents the contradiction between the following pairs of parameters: the circuit As mentioned before the results of our algorithm shows the big complexity in the search of technical and generalised technical contradictions. In some conditions we can be faced with the situation that there is no technical contradiction and so we cannot solve the inventive problem overcoming no existing technical contradiction. On the contrary, at the same time there is a lot of generalised technical contradictions and the human expert is not able to deal with so many possibilities. Then we should choose in our future work the "best" set of generalised technical contradictions to solve the inventive problem. For this we will identify the important factors influencing the number of technical and generalised technical contradictions in order to reduce this complexity. This section reveals how the number of columns (parameters) and rows (experiments) and the density of ones (number of satisfied parameters) affect the number of found TCs and GTCs. We generated several populations of random matrices according to the three previously mentioned influencing factors. Each factor has three levels (i.e., 6, 9, and 13 columns-50, 100, and 200 rows-20%, 50%, and 80% density). Finally, for each combination, 15 matrices with no line full of ones and no column full of zeros were created randomly. Overall, the sample contained a total of 405 different matrices.

Factors affecting the number of TCs in the general population

To identify the main factors affecting the number of TCs, we used the general complete factorial design of experiments and variance analysis. Three factors were studied, i.e., the column number, the row number, and the density of ones in the matrix. The results obtained for the design of experiments revealed three different populations and thus three Henry's curves (figure 10a). Each population should be treated independently because the populations do not show similar behaviour (their variances are not the same, as shown in figure 10b). There is a large variance in the number of TCs for the matrices with a small number of rows, and the variance in the number of TCs also increases with the number of columns. The variance in the density was not studied because technical contradictions were identified only for the case of 20% density and the number of TC varied from 0 to 19. The matrices with 200 rows and the matrices with densities greater than 50% almost never featured any TCs.

With the aid of an interaction diagram, a graphical representation of the main effects, and the ANOVA table, different hypotheses were tested for each factor. As shown in figure 11a, the column number has a positive factual effect on the number of possible technical contradictions, but it is correlated with the negative effect of the number of rows and the density, especially for the matrices with fewer than 100 rows and a density less than 50%. At densities greater than 50%, the number of technical contradictions is always zero; thus, other effects are counteracted against. These results confirm intuition and seem to generalise the average limiting zone for the existence of TCs.

Factors affecting the number of GTCs in the general population

We identified the main influencing factors for the number of GTCs using the same procedure followed for TC case. The general complete factorial design of experiments and variance analysis were used to study three factors: the column number, the row number, and the density of ones in the matrices. As in the case of the TCs, three different populations and thus three Henry's curves (figure 12a) were detected. Their variances were compared by the test of variance equality, as shown in figure 12b. The variance in the number of GTCs increases with the number of columns, whereas the variance does not change with row number. The variance is smaller at densities of 20% and 80% but large at a density of 50%. The variance tests confirm the results of the main effect analysis and interaction diagram shown in figure 13. As shown, the number of rows does not have a significant effect on the number of GTCs. The most positive significant effect is the number of columns. The second most significant effects are the density and the interaction between the density and the number of columns. It appears that the shape of the number GTC versus density curve does not change with the number of columns and rows: it increases up to a density of 50% and decreases thereafter. This behaviour will have an impact on our future strategy for filtering for GTCs.

Time consumption of the algorithm

To estimate the algorithm's time consumption for a given matrix, we consider that the block number mainly affects the searching time. In the following, we analyse the interaction between the block number, the density of ones, and the maximum density of ones per row for the general population of matrices similar to the matrix for the electrical circuit breaker.

Relationship between block number and density of ones in the case of the electrical circuit breaker

In the case of the electrical circuit breaker, we studied the relationship between the number of blocks, which indicates the time consumption of the algorithm and the density of ones in the matrix. Figure 14a shows that the number of blocks and thus the time consumption increase almost linearly with the density of ones, by monitoring the mean values. In figure 14b, the number of blocks is plotted as a function of the maximum density of ones per row in the matrix. For convenience, we use MDOPR to denote the maximum density of ones per row. In summary, for a given matrix similar to that of the electrical circuit breaker, the most influential factor affecting the algorithm's time consumption is block number. Moreover, the results of the experiments indicate that the time consumption is approximately proportional to the density of ones in the matrix. We cannot conclude that the number of rows has a significant effect on the block number. The most positive significant effects are the number of columns and the density. The interaction between the density and the number of columns also has a significant effect.

Large-scale matrices and time consumption of our algorithm

This part of the study concerns large-scale matrices and the relation between the number of satisfied evaluation parameters (equal to 1) and the time cost of the algorithm. We used matrices in which each element is equal to 1 owing to the dominating effect of the number of evaluation parameters whose values equal 1 on the time complexity. We performed the test for five large-scale matrices and present the time consumption -the matching time and searching time-in Table 1. The test was performed on five matrices containing only ones as the elements and with an increasing number of evaluation parameters (columns). The number of matrix blocks is proportional to the maximum of satisfied parameters in each row. Data 1 has 5 evaluation parameters (columns) and 1500 experiments (rows). Data 2 has 8 evaluation parameters and 1500 experiments. Data 3 has 10 evaluation parameters and 1500 experiments. Data 4 has 12 evaluation parameters and 1500 experiments. Data 5 has 15 evaluation parameters and 1500 experiments. The computer used to run the tests was 64-bit machine with 8G of memory and a dualcore CPU operating at 3.4 GHz.

From Table 1, we draw the following conclusion: the time cost grows exponentially with the number of evaluation parameters equal to 1; the time consumed in the searching block is less than that consumed in the matching block. Thus, in these experiments, the time cost is determined by the matching phase. Because we need to store all of the blocks in memory during the matching phase, the space consumption is beyond the capability of the experimental computer (8G) when the number of evaluation parameters is greater than 15 and the number of experiments is equal to 1500.

Conclusions

In the design of a technical system, two types of optimisation problems are confronted: one can be solved by improving the engineering parameters of existing systems, and the other concerns the reconstruction of the technical system. When the design objective cannot be attained by improving the stated parameters, we must use inventive problem-solving principles. In this study, we used the principle based on the dialectical approach, which identifies contradictions to understand and represent design problems better. The design problem-solving procedure involves the resolution of the best contradiction.

Our goal was to identify the complete set of generalised technical contradictions. The results of the experiments indicate that the more technical parameters and experiments describing the technical system there are, the greater the number of possible combinations there is. Thus, a human expert is not able to identify and consider all of the combinations, which is why we tried to automate the search for generalised technical contradictions. The method is reliable when the maximum number of evaluation parameters is less than 15. The matching time is the main factor affecting the algorithm's speed. Thus, to improve the algorithm, we should find some restriction for discarding blocks before the matching phase. This problem can also be classified as a data mining problem and is quite similar to seriation and matrix reordering problems, such as the two-mode clustering problem; however, these methods do not propose to find all possible solutions.

Thanks to the algorithm it becomes possible to evaluate quantitatively the volume of contradictions and check the hypothesis about rarity of TC existence. In the experimental section of this paper, first is provided the result of our algorithm for the case of an electrical circuit breaker. It confirms the large number of GTCs. Second an analysis of the number of GTCs and TCs versus density of ones for the population of binary matrices with the same number of rows and columns than the circuit breaker was performed. The result shows that the average number of GTCs increases with density until 50% and then decreases, while the number of TCs decreases with density and is generally equal to zero after 60%. The values of TC and GTCs of the circuit breaker example are consistent with the results of this general population of matrices. Third, in order to generalise previous results, we evaluated the impact of the number of columns, density and rows on the number of GTCs and TCs. The analysis of the results shows that, for a given number of rows and columns, the average value of GTCs and TCs evolve in the same way than for the circuit breaker (i.e. the average number of GTCs increases with density until 50% and then decreases, while the number of TCs decreases with density and is generally equal to zero after 60%). Nevertheless, the number of columns acts as a shape factor. For instance, the maximum value of GTCs, which is obtained for density equal to 50%, increases exponentially with the number of columns. The main factors affecting the number of technical contradictions and generalised technical contradictions was identified with the aid of the principles of the design of experiments and statistical analysis tests. These results will have an impact on our strategy for solving inventive design problems and selecting the most appropriate technical or generalised technical contradictions to solve such problems. Once all generalised technical contradictions are identified, several elimination strategies are subsequently needed to choose only the GTCs leading to resolution of the design problem. Two different criteria were proposed in [18] to select the most meaningful generalised technical contradictions. Nevertheless, generalised technical contradictions provide only a partial solution in TRIZ problem solving. To resolve the contradictions, we need more details about the system parameters and the relationships thereof. The next step in our research will be the identification of physical contradictions according to the identified GTCs.

Figure 1 .

 1 Figure 1. Generic matrix Z (a) and the example of an electrical circuit breaker (b)

Figure 3 .

 3 Figure 3. Example of false classical technical contradiction (a) and generalised technical contradiction (b)

Figure 5 .

 5 Figure 5. Sub-problem blocks in matrix Z

  seek the block expressed by ( )1 1 ,Y Ein which all of the elements in the block are equal to 1.

  original problem. Correctness of the strategy: if the solution sets of two problems include each other, they are equal.

i=1Figure 6 .

 6 Figure 6. Flow chart of algorithm

Figure 9 .

 9 Figure 8. TC/ GTC number versus density for 9 x 6 matrices

  Figure 10. Residual values (a) and test of the variance equality (b) for TC number

Figure 13 .

 13 Figure 12. Residual values (a) and test of the variance equality (b) for GTC

Figure 14 .

 14 Figure 14. Scatter plots of block number versus density of ones (a) and versus maximum density of ones per row (b)

Figure 15 .

 15 Figure 15. Residual values (a) and test of the variance equality (b) for block number

Figure 16 .

 16 Figure 16. Principal effects of factors (a) and interactions between the factors (b) for block number

Table 1 .

 1 Experimental Results

		Nu m of Columns Matching time(s) Num of Blocks Searching tim e(s)
	Data1	5	0.007	31	0.190
	Data2	8	0.240	255	0.197
	Data3	10	3.632	1023	0.234
	Data4	12	50.159	4095	0.401
	Data5	15	3666.167	32767	2.283

JESA. Volume 47 -n° 4-8/2013

JESA. Volume 47 -n° 4-8/2013

breaker reusability y2 and normal mode release y5 and the couple circuit breaker disrepair y1 and spring core mounting y3. GTC #3 represents the contradiction between the couple circuit breaker reusability y2 and firing pin initial position return y6 and the couple spring core mounting y3 and normal mode release y5. Finally, GTC #4 represents the contradiction between the couple circuit breaker reusability y2 and firing pin initial position return y6 and the rest of the evaluation parameters.

Figure 7. Four examples of GTCs in the case of an electrical circuit breaker

Relationship between TC /GTC and density of ones

We randomly created 377 matrices that were similar to the circuit breaker matrix except with respect to their density of ones: 9 rows and 6 columns with no column full of zeros and no row full of ones. Figure 8 shows the evolution of the number of TCs/GTCs with the density of ones. Some trends can be observed: the number of TCs decreases with the density and tends to zero at a density of up to 50%. The average number of GTCs increases up to a density of 50% and then decreases. The mean values of each population are correlated to observe the general trend. The points indicated by a star point in figure 8 represent the real characteristics of the electrical circuit breaker matrix; the results confirm that this example is not an exception.