|European Case Law Identifier:||ECLI:EP:BA:2018:T165514.20181012|
|Date of decision:||12 October 2018|
|Case number:||T 1655/14|
|IPC class:||G01C 21/34|
|Language of proceedings:||EN|
|Download and more information:||
|Title of application:||Method for streamlined representation of roads in a geographic database|
|Applicant name:||HERE Global B.V.|
|Relevant legal provisions:||
|Keywords:||Claims - clarity
Claims - main request (yes)
Inventive step - main request (yes)
Summary of Facts and Submissions
I. The applicant lodged an appeal against the decision of the examining division refusing European patent application No. 03255659.9 because the application did not fulfil the requirements of Articles 84, 52(1) and 56 EPC.
II. With the statement setting out the grounds of appeal, the applicant requested that the decision of the examining division be set aside and a patent be granted on the basis of the requests then on file, i.e. the following requests (description pages and drawings are mentioned for the main request only):
Claims 1 to 16
Description Pages 1 to 18 as originally filed
Drawings Sheets 1/10 to 1/10 as originally filed
First auxiliary request:
Claims 1 to 16
Second auxiliary request:
Claims 1 to 15
Third auxiliary request:
Claims 1 to 16
Fourth auxiliary request:
Claims 1 to 16
Fifth auxiliary request:
Claims 1 to 15
All sets of claims have been filed with the statement of grounds of appeal dated 21 July 2014 and are identical to the sets of claims underlying the appealed decision.
III. With a communication dated 7 August 2018 the board informed the applicant about its preliminary opinion that the main request fulfils the requirements of the EPC and asked the applicant to file an adapted description.
IV. With a letter of 4 October 2018 the applicant filed amended description pages 2, 2a, 8, 12 and 16.
V. The present decision refers to the following documents:
D1: EP 0 943 894 A2
D2: EP 1 202 029 A2
D3: EP 0 838 661 A2
D4: US 6 026 384
VI. Claim 1 of the main request reads:
A method of representing a network (120) of road segments located in a geographic region (104) to facilitate calculation of routes along said road segments, wherein the method comprises:
forming representations of transition point pairs (200),
wherein each transition point pair (200) includes an entry point and an exit point,
wherein the entry point and the exit point each correspond to a respective decision point intersection (246) of a plurality of decision point intersections (246),
wherein each decision point intersection (246) is an intersection of at least three road segments wherein a vehicle entering the intersection on one of the road segments can legally exit the intersection on at least two other road segments, and
wherein the exit point corresponds to a first eligible decision point intersection (200) of the plurality of decision point intersections (246) encountered along a unidirectional path of one or more connected road segments in travel from the entry point to the exit point; and
storing the data representations of the transition point pairs (200).
The main request further comprises dependent claims 2 to 13, all referring back to claim 1 and the following independent claims:
14. Apparatus comprising means arranged to carry out the method steps of any of claims 1 to 13.
15. A computer program which when executed by a processor, causes the processor to carry out the method of any one of the preceding claims.
16. A computer readable medium storing a computer program according to claim 15.
Reasons for the Decision
1. Amendments - Article 123 (2) EPC
Claim 1 is based on claim 1 as originally filed. The added feature that "the entry point and the exit point each correspond to a respective decision point intersection..." (amendment marked) is disclosed on page 8, lines 29 to 29 and page 12, lines 27 to 28. The board is thus satisfied that the claims according to the main request fulfil the requirements of Article 123(2) EPC.
No objection of added subject-matter was raised in the contested decision.
2. Clarity - Article 84 EPC 1973
In the decision refusing the application the examining division raised an objection of lack of clarity against claim 14 of the main request and argued, in referring to section F-IV.3.8, first paragraph, last two sentences, of the Guidelines for Examination (edition of November 2014), that in apparatus claim 14 the mere reference to the method claim 1 did not suffice to define the essential features of the invention as required by Article 84 and Rule 43(1) EPC.
The applicant argued that apparatus claim 14 was clear and referred to section F-IV.4.13 of the Guidelines for Examination (edition of November 2014). According to the applicant's arguments, apparatus features of the "means-plus-function" type are allowable in the field of data-processing/computer programs.
The board agrees with the applicant's argument and refers to section F-IV.3.9.1(ii) of the Guidelines for Examination (edition of November 2017) according to which the formulation used in apparatus claim 14 is explicitly listed as an acceptable claim formulation. The board agrees and is satisfied that claim 14 of the main request is clear and fulfils the requirements of Article 84 EPC 1973.
3. Inventive step - Article 56 EPC 1973
3.1 Closest prior art
D1 relates to facilitating access to data in geographical databases and methods for use thereof in a navigation application and is thus directed to a similar purpose as the present application.
D1 discloses a method of representing a network of road segments located in a geographic region to facilitate calculation of routes along said road segments (see figures 2 and 3). The method according to D1 uses data base entries representing road segments (see paragraph ). In order to reduce the number of records in the database, D1 teaches the aggregation of road segments (see section III, paragraphs  and ) and describes aggregation criteria (see paragraphs  and ) and the process of aggregation (see paragraphs  to ). D1 also discloses storing of these data representations (see paragraph  and figure 1).
Document D2 concerns the provision of nominal paths in the representation of routes in order to reduce the amount of data. Document D3 concerns a geographical database where the storage of data relating to different map scales is optimized in order to facilitate changes in the displayed resolution. Both documents are therefore considered less relevant than D1 for the purpose of examining inventive step.
Document D4 is also considered a less promising starting point as discussed in detail in section 4.1 below.
For the assessment of inventive step D1 is therefore considered the document representing the closest prior art.
Document D1 fails to disclose the formation of representations of transition point pairs as defined in claim 1, wherein
- each transition point pair (200) includes an entry point and an exit point,
- the entry point and the exit point each correspond to a respective decision point intersection (246) of a plurality of decision point intersections (246),
- each decision point intersection (246) is an intersection of at least three road segments wherein a vehicle entering the intersection on one of the road segments can legally exit the intersection on at least two other road segments, and
- the exit point corresponds to a first eligible decision point intersection (200) of the plurality of decision point intersections (246) encountered along a unidirectional path of one or more connected road segments in travel from the entry point to the exit point.
3.3 Problem to be solved
The above identified difference has the effect of reducing the amount of stored data representing the road network, which in turn reduces the amount of processing required for route calculation.
The invention thus solves the problem of providing an improved method of representing a road network used for route calculations.
3.4 Inventive step
3.4.1 Document D4 discloses a method of representing a network of road segments located in a geographic region. However, D4 is not primarily concerned with route calculations but with the creation of cost zones, i.e. the identification of all nodes of a network which can be reached within a given cost limit (e.g. travel time). Therefore, the skilled person would not consider D4 in order to find a solution for the given problem.
3.4.2 Furthermore, document D1 already considers travel restrictions as attributes for the road segments (see column 10, lines 12 to 23). Therefore, there is no obvious need to replace the road network representation by (non-directional) road segments of D1 by the directed graphs used in D4.
3.4.3 Even if the skilled person would consider document D4, this would not lead to the claimed method. D4 teaches the use of directed graphs (also referred to as links or edges) which comprise entry and exit points and take into account travel restrictions (see figures 2A and 2B and column 3, line 55 to column 5, line 7). However, combining the use of directed graphs of D4 with the aggregation described in D1 would not result in the omission of non-decision points which result from the method of claim 1. D1 suggests aggregation only for roads with identical or at least similar attributes (see paragraphs  and ). As an example, the two links in figure 2B of D4, the link 104 entering node 100, having no direction of travel restriction, and the link leaving node 100 to the right, having a direction of travel restriction, would not be aggregated, when the aggregation criteria of D1, which explicitly rule out aggregation of roads segments where travel restrictions apply (see column 17, lines 44 to 50), were applied.
3.4.4 In addition, such an aggregation (omitting node 100 when turning right at this node) would also go against the main goal of D4. The method disclosed therein is directed at creating "cost zones" (see title and column 1, lines 9 to 11). In the context of D4, it is therefore not desirable to disregard nodes.
This can be seen from the example described in document D4 (see figure 4 and column 6, line 11 to column 7, line 32) in which the goal is to determine all nodes which are within a certain travel time (column 5, lines 8 to 17). Amongst others, the travelling time from origin node 162 via node 146 to node 148 is calculated to be 4 minutes. In the resulting cost zone (see figure 6) the "intermediate" node 146 is kept, although this route contains a restricted driving manoeuvre (at node 146, coming from node 162, only a left turn is allowed onto the one-way street coming from node 144 and going to node 148). Therefore, D4 actually leads away from disregarding this non-decision point 146, which is however the result of the method as claimed.
In conclusion, even when applying the teaching of D4 to document D1, this would not result in a reduction of the number of nodes as in the claimed method.
3.4.5 The board is therefore of the opinion that the claimed method of representing a network of road segments involves an inventive step over the combination of the teachings of documents D1 and D4.
4. The appealed decision
4.1 D4 as closest prior art
In its decision refusing the application, the examining division considered D4 as the closest prior art.
Document D4 contains a method of representing a road network to facilitate calculation of routes along said road segments and also discloses a number of features of claim 1.
The board is however of the opinion that D4 does not concern route calculation as such but only uses such calculations for the creation of cost zones (e.g. travel time calculations are used to create cost zones, see column 3, lines 55 to 63). Therefore, D4 is not seen as a promising starting point for improving route calculations as such.
4.2 Combination of D4 and D1
4.2.1 In its decision refusing the application, the examining division argued that document D1 also related to the representation of road networks and provides the claimed solution to the problem of improving route calculations.
The board agrees insofar as D1 (see paragraph ) contains a hint for the skilled person that it is advantageous to use segment aggregation in geographical databases in order to "reduce the number of road segments that need to be explored during route calculation" (see column 16, lines 6 to 9). However, in the context of D4 (as already discussed in detail in section 3.4.1), it is not desirable to disregard nodes, because D4's main goal is to create "cost zones" (see title and column 1, lines 9 to 11), i.e. a collection of all nodes in a road network that fulfil certain criteria. Therefore, when starting from document D4, the skilled person has no reason to reduce the number of nodes by aggregation as e.g. taught by D1, because this would go against the main goal of D4.
The board is therefore of the opinion that the skilled person has no reason to combine the teachings of D4 and D1.
4.2.2 According to the examining division's further reasoning (see point 2.1.4 of the decision), D1 taught the general principle of segment aggregation, i.e. the suppression of "bivalent" nodes in the representation of a network of road segments in order to reduce the number of road segments during route calculation. The examining division argued further that the segment aggregation of D1 was not restricted to a particular type of graph and that the skilled person would therefore apply its teachings to the directed graphs of D4 as well.
Further, applying the advantageous segment aggregation of D1 to the directed graphs of D4 would lead the skilled person to the method comprising all steps of claim 1 (see point 2.1.4 of the decision).
The board is not convinced by this argumentation. Even if the skilled person would try to use the segment aggregation hinted at in D1 in the method of creating cost zones disclosed in D4 (which is not the case, as discussed in section 4.2.1 above), this would not result in an aggregation as claimed.
As discussed in detail in section 3.4.3 above, in the example of figure 2B of D4, an aggregation according to the criteria set out in D1 would not omit node 100, i.e. node 100 would be an exit point.
This is in contrast to the aggregation as defined in claim 1 of the application, according to which node 100 would not be the first eligible decision point intersection along a unidirectional path of the road segments 104 and the one leaving node 100 to the right and therefore be disregarded, i.e. it would not be an exit point of a transition point pair.
In addition, although D1 initially defines aggregation rather broadly (see paragraph ), the concrete aggregation criteria given later (see paragraphs  to ) would be considered by the skilled person. These criteria restrict aggregation of road segments (or the directed graphs of D4) to those with the same or similar attributes (e.g. road name, rank, speed category). Therefore, when considering e.g. the example given in figure 10 of the application, a ramp 240 leading onto road 242 would, according to D1, not be aggregated, because there obviously exists a difference in the rank and speed category. Furthermore, in contrast to the application, D1 would also not aggregate in case of a restricted driving manoeuvre, a bifurcated roadway or a toll booth (see paragraph ), whereas the method of claim 1 would disregard these non-decision points in the formation of transition point pairs.
4.2.3 In conclusion, the board is of the opinion that the combination of the teachings of documents D4 and D1 would not lead the skilled person to the subject-matter of claim 1.
In the light of the foregoing, the subject matter of claim 1 of the main request involves an inventive step over the available prior art (Article 56 EPC 1973).
Method claims 2 to 13 are dependent on claim 1 and therefore also involve an inventive step over the available prior art (Article 56 EPC 1973).
Claims 14 to 16, directed at an apparatus, a computer program and a computer readable medium respectively and referring back to method claims 1 to 13 therefore also involve an inventive step over the available prior art (Article 56 EPC 1973).
Since the other requirements of the EPC are also met, the board concludes that the appellant's main request is allowable.
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 with the order to grant a patent on the basis of the following documents:
Claims: Nos. 1 to 16 of the main request as filed with the letter dated 21 July 2014
Description: Pages 1, 3 to 7, 9 to 11, 13 to 15 and 17 to 18 as originally filed
Pages 2, 2a, 8, 12, 16 as filed with the letter dated 4 October 2018
Drawings: Sheets 1/10 to 10/10 as originally filed