T 1565/17 (Configuring a system-of-systems with membrane computing/SIEMENS) 09-01-2018
Method for the configuration of a system-of-systems
Claims - clarity (no)
Inventive step - effect not made credible within the whole scope of claim
Inventive step - effect not technical
I. The appeal is against the decision of the examining division, with reasons dated 16 February 2017, to refuse European patent application No. 13 196 458.7 for lack of inventive step over the document
D1: Dhungana D et al., "Generation of conjoint domain models for system-of-systems", Proceedings of the 12th International Conference on Generative Programming: Concepts & Experiences (GPCE'13), ACM Press, October 2013, pages 159-168.
II. In the application (see page 7, lines 17-20), a scientific paper is mentioned, which will hereinafter be referred to as
D2: Pérez-Jiménez M J et al., "A Linear-Time solution to the Knapsack Problem Using P Systems with Active Membranes", Workshop on Membrane Computing (WMC) 2003, LNCS 2933, Springer-Verlag, 2004, pages 250-268.
III. Notice of appeal was filed on 14 April 2017, the appeal fee being paid on the same day. A statement of grounds of appeal was received on 13 June 2017. The appellant requested that the decision be set aside and a patent be granted based on the application documents on file, i.e. the description pages 1-14 as originally filed, in combination with claim 1 and drawings sheet 1/1 as received on 14 December 2015.
IV. Sole claim 1 reads as follows:
"Method for the configuration of a system-of-systems by use of a computer, comprising the following phases:
- the phase of scoping, where the component systems (Sl, S2, ...Sn) are identified and their roles described by specifying a series of participation statements (statement l, statement 2, statement 3, statement ..., statement m);
- the phase of attribute extraction and system characterization, where the participation statements are analyzed and configuration parameters are extracted from them;
- the phase of impulse configuration where a set of requirements is defined, and by means of membrane computing a configuration for the System-of-systems which fulfills the requirements is derived and output from the computer."
V. With a communication dated 18 July 2017, the board informed the appellant of its preliminary opinion that the application was deficient under Articles 83, 84 and 56 EPC.
VI. With a letter dated 20 November 2017, the appellant filed a short response to the board's preliminary opinion.
VII. Oral proceedings were not requested.
1. The application relates to what is called the "configuration of a system-of-systems" (see page 1, lines 5-6).
1.1 The term "system-of-systems" is said to have arisen in the systems engineering community, where it "reflects the concepts and developments" of real systems such as "smart grids, integrated supply chains, collaborative enterprises, and next-generation air traffic management" (lines 20-24).
1.2 It is further explained that a system-of-systems is "a collection of independent systems that work together to create a new, more complex system which offers more functionality and performance than simply the sum of the constituent systems" (page 1, lines 26-29). Configuration of a system-of-systems is said to be "the task of selecting the optimal subset of component systems, that can perform the required task" (lines 32-34).
1.3 This problem is rephrased in mathematical terms as a selection problem as follows. The relevant "characteristics" C of any system-of-systems SoS are defined as a set of pairs of attributes A and values from a set Domain(A) of all values which the respective attributes can take: Hence, the set of all possible such characteristics is C(SoS) = union of all attribute-value pairs Ai x Domain(Ai) (see page 2, esp. lines 10, 17 and 24). The available components for any particular system are given as a set S of components Si, each having some characteristics: Thus C(Si) is a subset of C(SoS) for any Si. The required characteristics are given as a subset of all possible ones too: C(R) is a subset of C(SoS) (see page 2, lines 30 and 37). The configuration problem is then said to be the problem of finding an "optimal" subset Simpuls of the available components S so that their characteristics include the required ones: C(R) must be a subset of C(Simpuls) (see page 3, paragraph 1). The notion of optimality is not defined in the application.
1.4 The declared objective of the invention is to solve this "system-of-systems configuration problem" with "membrane computing", which is disclosed as being "a variation of" P-systems, a computational model "inspired" by biological processes (see page 3, lines 7-14). The invention is said to rely on "a new kind of solver" which is "constructed using membranes, also called P-systems, and uses metaphors of chemical reactions occurring in living cells" (see the paragraph bridging pages 6 and 7). Reference is made to D2 which reports on a linear-time solution of the well known "knapsack problem" with P-systems, based on the creation of "an exponential workspace in linear time", and it is suggested that "this kind of breakthrough" allows the solving of the "NP-complete configuration problem in linear time", too (see page 7, paragraph 2; page 14, paragraph 3).
The prior art
2. D1 relates to the "design of system-of-systems" (SoS) in a way "comparable to a product line configuration problem" (see the abstract, lines 8-12).
2.1 It is disclosed that the components of a system-of-systems, i.e. the individual systems, are often modelled and developed independently (see section 2.1) but that "dependencies arise if the systems are to be integrated" (see section 2.2, paragraph 1; see also figure 5). The paper is thus concerned with the problem of providing a "conjoint model" (or "conjoint domain model") of the systems in an SoS (see section 2.3, and figure 2).
2.2 The problem is rephrased in mathematical terms as follows: The systems and their dependencies are given as a directed graph referred to as a "portfolio" (see section 3.1, lines 8-11), and a "conjoint domain model" is defined as a "minimal subset" of the portfolio (i.e. a subgraph) containing selected component systems and all systems that are used directly or indirectly from the selected systems (see lines 12-21).
2.3 This problem is solved by "identif[ying] all components required for [a] concrete project" as the "transitive closure of all systems dependent on the initially selected systems" (see section 3.6, paragraph 1). D1 also discloses the use of constraints to model restrictions or requirements on the possible combinations of model elements (see section 3.7).
2.4 The proposed approach has been evaluated within a particular application scenario in terms of practical applicability and usability (see sections 4-4.2).
3. D2 considers the knapsack problem in the following "decision" form (see section 4):
Given a knapsack of capacity k e N, a set A of n elements, where each elements has a "weight" wi e N, and given a constant c e N, decide whether or not there exists a subset of A such that its weight does not exceed k and its value is greater than or equal to c.
3.1 Then, a proof is presented (see section 6) that "the family [...] of P systems [...] defined in Section 4 provides a polynomial solution for the Knapsack problem" defined above.
3.2 In the concluding section 8 it is stated that the solution presented in D2 is "very similar" to a solution to the "Subset-Sum" problem published elsewhere, and that the "multiple common points" make the authors "optimistic about future adaptations for other relevant numerical problems".
The issue to be decided
4. In its decision (see reasons 7.4.1), the examining division found that the subject-matter of claim 1 differed from D1 only in that "membrane computing" was used to determine the configuration for the system-of-systems. As this lacked a surprising technical effect, and membrane computing being known in the art (see in particular reasons 7.4.2 and 7.4.4), the examining division further found claim 1 to lack inventive step (reasons 7.4.7).
5. The appellant agrees that the use of membrane computing is the only difference over D1 (see grounds of appeal, page 2, lines 1-2).
5.1 According to the appellant, this difference has the effect of making it "possible to solve the occurring NP-hard problems [...] in linear time" (grounds of appeal, page 2, lines 3-4), the objective technical problem solved by the invention thus has to be seen as "improv[ing] the time behavior of a method for the configuration of a system-of-systems" (lines 5-6), and the claimed invention involves an inventive step because "there is no teaching in the prior art that would have prompted the skilled person, faced with the objective technical problem, to modify" D1 "by means of membrane computing" (lines 7-10).
5.2 Neither the grounds of appeal nor the appellant's submission of 20 November 2017 provides any elaboration of this argument or any alternative argument.
5.3 In response to the summons, the appellant states that a "skilled person, confronted with the invention and with the information about" D2 "would accept" that by using "membrane computing" the "occurring NP-hard problems in the method" for the configuration of a complex system-of systems "can be solved in linear time" (page 1, lines 2-9) and takes the view that D2 "is conclusive proof" of "the claimed technical effect" (line 10).
5.4 At the same time, the appellant states that "it is principally not possible for the applicant to prove the expected technical effect", suggesting that the invention was "a theory in the empirical sciences", which, according to Sir Karl Popper, "can only be falsified" (see page 1, lines 11-14, and page 2, lines 1-2). This obliged the board to accept the effect unless it could "falsify" it (page 2, lines 3-4).
5.5 Regarding clarity and sufficiency of disclosure, the appellant asserts that to the relevant skilled person, thought as being an engineer with an academic education and experience with scientific work, the "claimed method is clear enough for the implementation of the method" (see lines 5-8).
The board's position
6. Claim 1 refers to "configuration of a system-of-systems" without defining either "system-of-systems" or the problem of "configur[ing]" one, apart from mentioning that a "components system" has "roles described by [...] participation statements" and "a set of requirements" which a configuration has to "fulfill".
6.1 The board considers both terms to be unclear. There is no indication in the application that the term "system-of-systems", or the problem of configuring one, has an established clear meaning in the art.
6.2 The application itself uses these terms in two significantly different ways. On the one hand, the term "system-of-systems" is used as referring to industrial "control systems" characterised by being "large-scale", "complex", "decentralized, distributed, networked", "heterogeneous and (semi)autonomous" (see page 1, lines 8-24), its configuration being "the task of select ing the optimal subset of component systems, that can perform the required task" (see lines 32-34). On the other hand, the problem of configuring a system-of-systems is rendered as the mathematical problem of finding a subset of available "components" such that the attribute-value pairs in that subset contain another set of attribute-value pairs called the "configuration requirements".
6.3 D1 stresses further differing aspects of a "system-of-systems", namely that the system components are related to each other by "use" relationships. This is reflected by the fact that systems-of-systems are modelled as graphs rather than sets. The application does not describe or model "use" relationships between system components (see pages 1 and 2). Also, the "participation statements" characterise individual component systems but not their relationships (see page 4, lines 8-19, and table 1). The fact that the application and D1 define systems-of-systems in different ways supports the board's view that the term is not clearly defined in the art.
7. Claim 1 states that the configuration of the system-of-systems is computed "by means of membrane computing".
7.1 The board considers the term "membrane computing", and the notion of computing something "by means of" membrane computing, to be unclear in this generality.
7.2 It is disclosed that "membrane computing" is "a variation of the so called P system", a "computational model [...] that performs calculations using a biologically-inspired process", which is defined in terms of "membranes", "chemicals", "catalysts" and "rules which determine possible ways in which chemicals may react with one another to form products". As P-systems are computation models, the skilled person would understand that the biological and chemical terms like "membranes", "chemicals" and "catalysts" (see also page 7, last paragraph) are used metaphorically and cannot replace a formal definition.
7.3 It is disclosed that "for the present invention a variant of a P-system with active membranes is used" (see page 7, lines 10-11). It can be derived that there are P-systems with membranes that are not "active" but which still fall within the scope of membrane computing.
7.4 Likewise, D2 refers to "P-systems with input" and, possibly, with "external output", suggesting that there are P-systems without "input" and/or without "external output" as well (see page 251, definition 1 and the paragraph before definition 3). D2 also refers to families of P-systems with different properties (see e.g. page 253, definition 9) and defines a problem to be "solvable" in this context "if there exists a [suitable] family of P systems".
7.5 Again, this implies that there are a large number of P-systems, all having "membranes" and thus falling within the scope of what is called "membrane computing", with decisively different properties.
7.6 The board also notes that, in order to solve the knapsack problem "by means of" membrane computing, D2 defines a particular family of P-systems (see page 255, line 7 et seq.), and only refers to computational complexity in relation to this particular family of P-systems (see section 5, and section 6, paragraph 1). In contrast, claim 1 merely states that computation takes place "by means of membrane computing", without defining any specific "family of P-systems".
8. In response to the board's objections relating to clarity (see in particular the communication of 14 August 2017, points 3.1, 3.2, and 5.1), the appellant has merely asserted that the claims are "clear enough" for the relevant skilled person. This sweeping asserting does not sway the board's opinion. In this respect it is only of passing relevance that the skilled person is insufficiently characterised as having an unspecified "academic" education and "scientific work experience".
9. The board thus concludes that claim 1 does not specify in clear terms the problem addressed ("configuration of a system-of-systems") or the solution proposed (at least with regard to the phrase "by means of membrane computing") and is thus unclear, Article 84 EPC.
10. Since claim 1 does not specify the problem to be solved or its solution, it is impossible to determine the complexity class of the problem or the computational complexity of the solution. For this reason alone, the appellant's allegation that the claimed invention solved "the occurring NP-hard problems [...] in linear time" is without merit.
11. The board notes at this point that computational complexity theory is not, as the appellant seems to suggest, an empirical theory which is not amenable to proof. To the contrary, complexity theorems are established by mathematical proof and their limits are precisely indicated. For the former statement, D2 as a whole is illustrative; with regard to the latter statement, the board notes that the authors of D2 state that their "design [...] is very similar" to one known from the literature and that they are "optimistic" - but not sure - that "other relevant numerical problems" can be successfully tackled in a similar manner (see section 8). In passing, the board notes that the appellant appears to contradict itself here (see points 5.3 and 5.4 above).
12. Therefore, if, as in the present case, the appellant's inventive step argument turns on an improved time behaviour, a rather specific one in particular, it is for the appellant to establish that the proposed solution has the claimed time complexity, and in which situations or under which circumstances it applies.
13. Even if, tentatively, it was assumed that the claimed configuration problem was the one defined in the application (page 2, to page 3, paragraph 1), a precise complexity-theoretic statement and an application of the teaching of D1 to that problem is not evident.
13.1 Firstly, the application does not define in what way the solution is meant to be optimal (see page 3, paragraph 1). Claim 1 does not even specify that the computed configuration is optimal at all.
13.2 The reference to the knapsack problem via D2 (see point 3 above) might suggest that each component system is associated with a specific "weight" and that a set of components possessing the required characteristics (a "solution") may be called optimal if no other solution has at smaller cumulative weight. Since the application does not mention weights, however, one might rather assume that every component system has "unit weight" 1, so that a solution may be called optimal if no other solution has smaller cardinality.
14. Secondly, the configuration problem disclosed in the application is not precisely the knapsack problem addressed in D2. Apart from the mentioned fact that the component systems according to the invention have no associated "weights" and that "optimality" is undefined, the requirement is not defined in terms of the "capacity" of the knapsack, but rather as a set of attribute-value pairs, viz. "characteristics". The corresponding mapping may or may not be straightforward. In any event, the application does not define it.
15. Finally, the board notes the claimed system-of-systems is not defined in technical terms. It is not specified as being a technical system (such as those mentioned on page 1 of the description) or in terms of specific technical components. Rather, it subsumes the entirely abstract, mathematical formulation also disclosed, and lacks any specific indication as to how the computed configuration might solve a concrete technical problem. Also, the computing platform is undefined. Hence, the board considers that the claimed subject-matter boils down to the modelling of an abstract computing problem with a known and also abstract model of computation. As a consequence, the board considers that the claimed subject-matter as it stands does not make a technical contribution to the art and thus lacks inventive step, Article 56 EPC (see also T 1630/11, point 6). This objection was raised in the board's communication dated 14 August 2017 and the appellant chose not to address it in its reply of 20 November 2017.
16. In view of the foregoing, the question raised in the decision under appeal, namely whether the skilled person would consider "membrane computing" to try solving the problem of D1, is left open.
For these reasons it is decided that:
The appeal is dismissed.