T 2035/11 (Navigation system/BEACON NAVIGATION) of 25.7.2014

Summary of Facts and Submissions

I. The applicant (appellant), which at the time was Beacon Navigation Inc., lodged an appeal against the decision of the Examining Division refusing European patent application No. 97942552.7.

II. The decision cited the following document:

D1: US 5 184 303 A, 2 February 1993.

The Examining Division decided that the subject-matter of claim 1 of the sole request before it lacked an inventive step over "a system comprising a storing means adapted to store data and a [sic] input means adapted to input data". Such a system was so well-known before the priority date of the present application as not to require further evidence. In addition, the subject-matter of independent claims 11 and 20 was found to be excluded from patentability under Article 52(2) and (3) EPC. Document D1 was mentioned as an example of a commonplace navigation system that could be used for the implementation of the non-technical scheme underlying the invention as defined by claim 1.

III. With the statement of grounds of appeal, the appellant filed a main request and auxiliary requests 1 to 3. The appellant conditionally requested oral proceedings.

IV. With effect from 19 January 2012 the application was transferred to Beacon Navigation GmbH, which thereby obtained the status of appellant.

V. In a communication accompanying a summons to oral proceedings, the Board inter alia raised objections on clarity, support and added subject-matter and expressed as its preliminary opinion that the subject-matter of claim 1 of all requests lacked an inventive step within the meaning of Articles 52(1) and 56 EPC over the navigation system discussed in the background section of the present application.

VI. With a letter dated 25 June 2014, the appellant replaced the then pending requests with a main request and auxiliary requests 1 to 4.

VII. The oral proceedings took place on 25 July 2014. During the oral proceedings, the Board expressed a negative opinion in respect of inventive step for the subject-matter of claim 1 of the main request and of auxiliary requests 1 to 4. The appellant then replaced auxiliary request 1 with a new auxiliary request 1. At the end of the oral proceedings, the chairman announced the decision of the Board.

VIII. The appellant requested that the decision under appeal be set aside and that a patent be granted on the basis of the claims of the main request filed with the letter dated 25 June 2014 or, in the alternative, on the basis of the claims of auxiliary request 1 filed during the oral proceedings or of one of auxiliary requests 2 to 4 filed with the letter dated 25 June 2014.

IX. Claim 1 of the main request reads as follows:

"A navigation system comprising:

a database of road segments to be travelled by a user, said database including a cost associated with each said road segment, wherein an estimated time of travel and an estimated length of travelare [sic] associated as costs with each said road segment;

a system for selecting a beginning point relative to said database of roads;

a user input device for selecting a desired destination relative to said database of roads;

a system which is configured to allow the user to adjust said cost of at least one selected said road segment proportionally to its estimated time of travel or estimated length of travel utilizing said user-input device; and

a system for determining a route from said database of roads between said beginning point and said desired destination based upon said adjusted cost of said road segments, wherein the navigation system evaluates the cost of the road segments to be traveled in several potential routes and recommends the potential route having the lowest total cost."

X. Claim 1 of (new) auxiliary request 1 reads as follows:

"A navigation system comprising:

a database of road segments to be travelled by a user, said database including a cost associated with each said road segment, wherein an estimated time of travel, an estimated length of travel and a congestion level are associated as costs with each said road segment;

a system for selecting a beginning point relative to said database of roads;

a user input device for selecting a desired destination relative to said database of roads;

a data receiving device which is configured to receive congestion information regarding congested road segments and automatically update congestion levels associated with appropriate road segments;

a system which is configured to allow the user to adjust said congestion level of at least one selected said road segment utilizing said user-input device; and

a system for determining a route from said database of roads between said beginning point and said desired destination based upon said adjusted congestion level of said road segments, and which multiplies the cost of each road segment by the congestion level for that road segment,

wherein the navigation system evaluates the cost of the road segments to be traveled in several potential routes and recommends the potential route having the lowest total cost."

Claim 10 of auxiliary request 1 reads as follows:

"A method for determining a route implemented in a navigation system, the method including the steps of:

a) providing a database of road segments to be travelled by a user, said database including a cost associated with each said road segment, and wherein an estimated time of travel, an estimated length of travel and a congestion level are associated as costs with each said road segment;

b) selecting a beginning point relative to the database of roads;

c) selecting a destination relative to said database of roads;

d) receiving congestion information regarding congested road segments by a data receiving device and automatically updating congestion levels associated with appropriate road segments,

e) the user adjusting the congestion level associated with a selected road segment in said database of roads; and

f) the navigation system determining a route from said database of roads from said beginning point to said destination based upon said adjusted congestion level, and multiplying the cost of each road segment by the congestion level for that road segment, wherein the navigation system evaluates the cost of the road segments to be traveled in several potential routes and recommends the potential route having the lowest total cost."

Claims 2 to 9 and 11 to 19 of auxiliary request 1 are dependent claims.

XI. In view of the outcome of the appeal, the text of the claims of auxiliary requests 2 to 4 need not be given.

Reasons for the Decision

1. The appeal complies with the provisions referred to in Rule 101 EPC and is therefore admissible.

2. Since the main request, auxiliary request 1 and auxiliary requests 2 to 4 represent serious attempts to overcome objections raised in the contested decision and in the Board's communication accompanying the summons to oral proceedings, the Board exercises its discretion to admit them into the proceedings (Article 13(1) and (3) RPBA).

3. The invention

3.1 The application mainly relates to navigation systems that can be tailored to a user's particular wishes. The focus of the application is on the route-planning functionality of a navigation system, and the application in fact discloses that the navigation system need not be installed in a vehicle, but can be located in a personal computer (see page 1, lines 11 and 12, and page 4, line 29, to page 5, line 4).

3.2 The navigation system comprises a database of road segments, a system for selecting a beginning point, a user input device for selecting a desired destination, and a system for determining a route between said beginning point and said desired destination.

3.3 Examples of user input devices for selecting the desired destination include a mouse and a keyboard (page 4, lines 19 and 20). The system for selecting a beginning point may be a GPS system, but may also be a user input device (page 2, lines 27 to 29).

3.4 The database of road segments includes, for each road segment, an "estimated time of travel" and an "estimated length of travel". In addition, each road segment may be associated with a "congestion level" and a "road type". Based on this data and on routing criteria set by the user, the "system for determining a route" evaluates the cost of relevant road segments and determines (and recommends) the route having the lowest total cost.

3.5 The congestion level of a road segment determines a factor by which the estimated time and length of travel of the road segment are multiplied for the purpose of evaluating the cost of that road segment. The application explains that the user may increase the congestion level of an area or road that he wishes to avoid "for purely personal reasons" (page 6, lines 20 to 30). The application further discloses that congestion levels may be updated in response to received congestion information, either manually by the user listening to radio reports on traffic conditions or automatically by a data receiving device.

3.6 The routing criteria described in the application are a "time/distance factor", a "highway preference/avoidance factor" and a "toll roads preference/avoidance factor". These may be used to influence the evaluation of the cost of a road segment as follows:

- the time/distance factor is used to weight estimated time of travel against estimated length of travel;

- the highway preference/avoidance factor is used to adjust the cost of road segments with road type "highway";

- the toll roads preference/avoidance factor is used to adjust the cost of road segments with road type "toll road".

Main request

4. Interpretation of claim 1

4.1 Claim 1 of the main request defines the database of road segments as including an estimated time of travel and an estimated length of travel as costs associated with each road segment. Claim 1 further specifies that the user is allowed to "adjust said cost of at least one selected said road segment proportionally to its estimated time of travel or estimated length of travel". The formulation of the latter feature is somewhat problematic: "said cost" appears to refer to the estimated time of travel and/or estimated length of travel, but it is not immediately apparent what is meant by "adjusting" a cost "proportionally to" itself. This feature therefore requires interpretation.

4.2 In its letter dated 25 June 2014, the appellant submitted that this feature referred to the modification of the time/distance factor discussed in the description on page 7, lines 1 to 19. At the oral proceedings, the appellant submitted that the feature was intended to cover all cost adjustments disclosed in the application, i.e. both the adjusting of congestion levels and the adjusting of the time/distance factor and of the preference/avoidance factors.

4.3 Given that the feature refers to the cost "of at least one selected said road segment", the Board considers that it can only refer to the adjustment of congestion levels. Indeed, the time/distance factor and the two preference/avoidance factors are applied to the route calculation as a whole and not to one or more selected road segments, whereas it follows from the description on page 6, line 13, to page 7, line 4, in combination with Figure 2 that congestion levels are specific to individual road segments.

4.4 Another point of discussion at the oral proceedings was whether claim 1 had to be understood as being limited to a navigation system operating in a vehicle, or whether it also covered a personal computer executing route-planning software. The appellant insisted that the claim was not limited to navigation systems operating in a vehicle, but also covered navigation systems to be used on a bike or while walking, and indeed covered a personal computer executing route-planning software. The Board notes that this broad interpretation does indeed find support in the description (see point 3.13.1 above).

5. Inventive step - Article 56 EPC

5.1 In the Board's view, the term "navigation system" would normally be understood as a system comprising route-planning functionality as well as a position-determining device and being configured to provide route-guidance information in dependence on the actual real-world position of the system as discussed in the description on page 9, line 12, to page 10, line 4.

However, the description explicitly supports the broader interpretation of this term advocated by the appellant (see point 4.44.4 above), and claim 1 of the main request does not exclude this interpretation. The Board hence adopts it.

5.1.1 At the oral proceedings the Board noted that claim 1 encompassed a personal computer programmed to execute a particular optimisation algorithm. This algorithm takes the following input:

- a graph of which the edges represent road segments;

- cost values ("estimated length of travel", "estimated time of travel") associated with the edges of the graph;

- multiplication factors ("congestion levels") associated with at least some of the edges;

- a first graph node ("beginning point") and a second graph node ("destination").

The aim of the optimisation algorithm is to determine a path (consisting of a series of graph edges) connecting the first graph node to the second graph node and having the lowest total cost.

The claim leaves it undefined how this total cost is based on the "estimated length of travel" cost values and the "estimated time of travel" cost values, but in the light of the description it is clear that the total cost of a path may be based for example solely on the "estimated length of travel" costs (adjusted by the "congestion level" multiplication factors), or solely on the (adjusted) "estimated time of travel" costs, or on a weighted average of both.

5.1.2 According to claim 1, the graph is provided by means of a "database of road segments". This database also stores "estimated length of travel" and "estimated time of travel" cost values for each road segment. The claim does not define the database in terms of technical features and it may therefore be assumed to be a conventional storage means.

The "beginning point" graph node, "destination" graph node and "congestion level" multiplication factors may be input by a user using a conventional "user input device" (cf. point 3.33.3 ).

The determined optimal path is "recommended", which for example could take the form of displaying the ordered list of graph edges on a conventional display device.

5.1.3 Optimisation algorithms are mathematical methods, excluded "as such" from patentability under Article 52(2) and (3) EPC. Mathematical algorithms may contribute to the technical character of an invention only in so far as they serve a technical purpose (see e.g. decision T 1784/06 of 21 September 2012, reasons 3.1.1).

In the present case the purpose of the algorithm is the mere display of an optimal path to the user for cognitive processing. The user may act on the information, but does not need to. As stated in decision T 1670/07 of 11 July 2013, reasons 13, a technical effect may arise from either the provision of data about a technical process, regardless of the presence of the user or its subsequent use, or from the provision of data (including data that on its own is excluded, e.g. produced by means of an algorithm) that is applied directly in a technical process. In the present case the data is produced by means of an algorithm and is not applied directly in a technical process, so that neither possibility applies.

The Board hence considers that the optimisation algorithm of claim 1 does not serve a technical purpose and therefore does not make a technical contribution.

5.1.4 The appellant essentially argued that the skilled person concerned with the field and teachings of the invention was a person skilled and active in the field of developing and manufacturing navigation systems and the technical and environmental circumstances involved therewith. He was required to have knowledge about topographical information concerned with map data used with such navigation systems, environmental conditions involved with such topographical information, traffic routing and planning, and human-machine interfaces involved in operating a navigation system. The algorithm was concerned with real-world facts. The costs associated with road segments reflected technical and geographical conditions and specifics to the topographical information which were to be considered when determining the route.

However, the present invention is not concerned with the specifics of the constitution of road maps and corresponding databases. The database of road segments of claim 1 is essentially a graph comprising nodes and edges with cost values assigned to the edges. Calculating a route having the lowest total cost does not require knowledge of environmental conditions or traffic routing and planning. The database of road segments serving as input to the algorithm may reflect real-world facts, but the mere fact that the input to an algorithm has a particular meaning in the real-world is insufficient for the algorithm to make a technical contribution (see e.g. decision T 154/04, OJ EPO 2008, 46, reasons 20).

5.1.5 The appellant also argued that it made no difference whether the route planning algorithm is implemented in a general-purpose computer or in a navigation system installed in a vehicle or used on a bicycle or while walking. It was also not relevant whether the beginning point or destination were received by GPS or entered manually.

The Board notes that the view that the (claimed) context in which an algorithm is used is of no relevance for the question whether the algorithm contributes to the technical character of the claim is simply incorrect. Features that as such are excluded from patentability may provide a technical contribution to the extent that they interact with the technical subject-matter of the claim for solving a technical problem (see decision T 154/04, reasons 5, under (f), and reasons 13). If an invention resides in the application in a technical process of data produced by an algorithm (the example given in decision T 1670/07, reasons 13, see point 5.1.35.1.3 above), the application of the produced data in the technical process should be properly reflected in the claim.

5.1.6 The appellant's further argument that the invention gives the user more options to influence the determination of a route in accordance with his personal needs than existing algorithms has no bearing on whether the algorithm underlying the claimed subject-matter serves a technical purpose.

5.1.7 The Board concludes that the technical content of claim 1 consists in a computing system comprising conventional storage means and conventional input means. Since, as the Examining Division correctly considered, such computing systems were notorious knowledge at the filing date of the application, the subject-matter of claim 1 lacks an inventive step within the meaning of Articles 52(1) and 56 EPC.

5.2 For the sake of completeness, the Board notes that the same conclusion of lack of inventive step is reached if the term "navigation system" is given the narrower interpretation of a system comprising route-planning functionality as well as a position-determining device and being configured to provide route-guidance information in dependence on the actual real-world position of the system. The reasoning is however different.

5.2.1 In the Board's view, providing real-time route-guidance information to a user in dependence on the user's real-world position is a technical task. It involves an interaction between the user and the navigation system, wherein the navigation system continuously measures the user's position using technical means and, on the basis of these measurements, provides the user with information aimed at enabling the user to manage the technical task of moving a vehicle to a desired destination.

Although the completion of this technical task depends on the user acting upon the provided route-guidance information and hence on an intervention by the user, it does not rely on subjective considerations by the user or on psychological effects. The user may still decide to ignore the route-guidance information, but that does not detract from the technical character of the navigation system as a technical tool to be used interactively in a technical process and not merely in a preparatory phase as a substitution of what could also be done using pencil and paper.

5.2.2 It follows that a mathematical route-planning algorithm, when used in a navigation system as described in point 5.2, contributes to the technical character of the system at least to the extent that it produces information that enables the route-guidance functionality. A route-planning algorithm does this by producing a route in the form of an ordered list of road segments based on real-world map data.

5.2.3 In this context, features resulting in a different choice of route may contribute to the technical character of the invention, but only in so far as they are based on technical considerations which influence the provided route-guidance information. In other words, while moving a vehicle along a different route always has physical consequences, for the purpose of determining the technical contribution of the route-planning algorithm such consequences are only to be taken into account as technical effects to the extent that they result from the choice of a route based on technical considerations. In the case of claim 1, basing the route calculation on estimated time of travel and/or estimated length of travel, both of which arguably reflect technical characteristics of a real-world road network, would seem to be an example of such a technical aspect.

5.2.4 The background section of the present application describes features of a conventional navigation system installed in a vehicle (page 1, lines 11 and 12). It comprises a database of road segments to be travelled by a user (page 1, lines 8 to 11), a system for selecting a beginning point relative to the database of road segments (page 1, lines 8 to 15), an implicit user input device for selecting a desired destination relative to said database of road segments (page 1, lines 8 to 11) and a position-determining device (page 1, lines 12 to 15). The navigation system displays the current position of the vehicle and turn-by-turn instructions to the driver (page 1, line 30, to page 2, line 2).

5.2.5 This acknowledged prior art further comprises a system for determining a route from the starting point to the destination. This is performed using an algorithm that is said to be well-known to those in the art and in use in many navigation systems at the priority date of the application (page 1, lines 16 to 18). This algorithm works by selecting, among the many potential routes between the selected starting point and the desired destination, the route that has the shortest total length, the lowest total time, or some weighted average of length and time. The total length and total time of a route is determined based on "cost" values associated with each road segment in the database, these cost values including the length of the road segment and the estimated time of travel through the road segment (page 1, lines 18 to 27).

5.2.6 For the sake of completeness, the Board notes that document D1 discloses such a known navigation system intended for installation in a vehicle (column 3, lines 20 to 22). The navigation system of document D1 comprises a database of road segments to be travelled by a user (column 3, lines 25 to 28) and a user input device for selecting a desired destination (column 3, lines 22 to 25 and lines 53 to 56). Document D1, column 6, lines 6 to 13, confirms that it is conventional to recommend the route with the shortest total length ("shortest mileage route") or with the lowest total time ("shortest time route").

5.2.7 The navigation system of claim 1 differs from the acknowledged prior art in that (in accordance with points 4.34.3 and 3.53.5 above) it further comprises a system configured to allow the user to adjust the "congestion level" of at least one selected road segment utilising the user-input device, thereby determining a factor by which the estimated time and length of travel of the road segment are multiplied for the purpose of evaluating the cost of that at least one selected road segment.

5.2.8 By increasing or decreasing the congestion level associated with a particular road segment, the user may make it less or more likely for the road segment to be included in the route calculated by the route-planning algorithm. In this way, the user may express his subjective preference for the road segment. The description of the application on page 6, lines 23 to 25, confirms that the motivation for adjusting the congestion level of a route may reside in "purely personal reasons". At the oral proceedings, the appellant also stressed that the invention gave the user more options to influence the route calculation in accordance with the user's personal needs.

5.2.9 The Board considers that the idea of allowing the user to set congestion levels for selected road segments which serve as multiplication factors in the route-calculation algorithm is not technical and can therefore not contribute to an inventive step. This is because accommodating the user's personal preferences is as such not technical and the Board does not see any other (technical) purpose that the congestion levels serve in the context of claim 1. Although the user of the claimed navigation system could certainly use this option for a technical purpose (for example in order to avoid a particular road for which he knows that his car is technically less suitable), the claim is not limited to such uses.

5.2.10 The implementation of this non-technical idea essentially consists in enabling the user to utilise the conventional user input device to select at least one road segment and to adjust the congestion level for the selected at least one road segment. The Board considers this implementation to be obvious, and the appellant has not argued otherwise.

5.2.11 The appellant argued that recognising the possibility of allowing the user to influence road calculation by letting him adjust costs of selected road segments was not obvious, as there were many other ways in which route calculation could be influenced and the solution claimed was not suggested by the prior art. In addition, it was not relevant that the distinguishing features served the purpose of accommodating the user's personal needs. At the oral proceedings, the appellant drew an analogy with manufacturing a more beautiful product, which could also represent an inventive step.

However, the Board's reasoning does not rely on a particular suggestion in the prior art, but on the finding that the proposed algorithmic change has no technical motivation and that its implementation is, uncontestedly, trivial. In so far as it is the appellant's view that technicality is irrelevant for the assessment of inventive step, this view is contrary to the established case law.

5.2.12 It follows that the subject-matter of claim 1 lacks an inventive step within the meaning of Articles 52(1) and 56 EPC even if the term "navigation system" is given a narrow interpretation.

5.2.13 The Board notes that the German Federal Supreme Court has come to a similar conclusion in respect of a navigation system offering the user the possibility to exclude road segments based on a user-selectable property such as the road segment being a toll road (see BGH, 18 December 2012, X ZR 3/12, GRUR 2013, 275 -Routenplanung).

5.3 For the above reasons, the main request is refused.

Auxiliary request 1

6. Added subject-matter and clarity

6.1 Independent claim 1 of auxiliary request 1 differs from claim 1 of the main request essentially in that the claimed navigation system further comprises a data receiving device configured to receive congestion information regarding congested road segments and automatically update congestion levels associated with appropriate road segments.

This feature finds a basis in the description as filed and published on page 3, lines 17 to 20, page 5, lines 9 to 12, and page 7, line 30, to page 8, line 3.

6.2 The remaining amendments to claim 1 were made with a view to improving its clarity. In particular, the issue discussed in points 4.14.1 to 4.34.3 has been resolved.

6.3 The Board notes that claim 1 in one place refers to "congestion level" as a "cost", which strictly speaking it is not. However, the meaning of the term "congestion level" is rendered sufficiently clear by the feature "a system (...) which multiplies the cost of each road segment by the congestion level for that road segment".

6.4 Similarly, the Board considers the feature "a system which is configured to allow the user to adjust said congestion level of at least one selected said road segment utilizing said user-input device" to sufficiently clearly express that this system also enables the selection by the user of said road segment.

6.5 Consequently, the requirements of Articles 84 and 123(2) EPC are fulfilled in respect of independent claim 1 and of corresponding independent method claim 10.

7. Remittal to the department of first instance

7.1 The Board considers that the inclusion in claim 1 of a data receiving device configured to receive congestion information excludes the broad interpretation of the term "navigation system" covering a personal computer executing route-planning software and that the claim is now restricted to a navigation system operating in a vehicle as discussed in point 5.25.2 above.

7.2 The background section of the present application is silent on the receipt of congestion information, so that the feature added to claim 1 further distinguishes the claimed subject-matter from the acknowledged prior art.

7.3 The passage of the detailed description on page 5, lines 4 to 15, which discusses the added feature, mentions that "[c]ongestion-monitoring devices are known and currently used to automatically monitor the congestion levels of certain road segments, typically near intersections" and that "[p]referably, information regarding congestion from the congestion-monitoring devices is broadcast to the surrounding area and received by the data receiver 42".

The Board does not consider this passage to be an admission that at the filing date of the present application it was known for navigation systems to automatically receive congestion information from congestion-monitoring devices. Suitable congestion-monitoring devices were apparently known, but they may have been used for entirely different purposes.

Document D1 also does not disclose a navigation system configured to automatically receive congestion information.

7.4 The Board is of the view that the received congestion information provides an indication of real-time real-world road conditions and that basing the calculation of a route on such conditions in the context of actual navigation is technical. There is therefore the potential of an inventive step. Auxiliary request 1 hence overcomes the reasons for the refusal.

7.5 However, before an inventive step can be acknowledged, a further investigation has to be made of the prior art, in particular of the documents cited in the international search report and the supplementary European search report. In addition, if the independent claims are found to involve an inventive step, the dependent claims have to be examined at least under Articles 84 and 123(2) EPC, and the description will have to be adapted. The Board therefore remits the case to the department of first instance for further prosecution.

7.6 The present application was filed under the PCT on 17 September 1997 and entered into the regional phase before the EPO on 15 March 2000. After a single communication under Article 96(2) EPC it was refused during oral proceedings, the written decision being posted on 17 March 2011. In view of this considerable delay and, in case of an eventual grant, the remaining term of the patent, the Board expects the department of first instance to deal with the case expeditiously.

Order

For these reasons it is decided that:

1. The decision under appeal is set aside.

2. The case is remitted to the department of first instance for further prosecution.