Beschluss des BPatG München 23. Senat vom 15.06.2021, AZ 23 W (pat) 18/19

Die vorliegende Anmeldung mit dem Aktenzeichen 10 2013 008 936.0 und der Bezeichnung „Erstellung und Verwendung einer Datenstruktur für die Pfadermittlung in einem Verkehrswegenetz“ wurde am 24. Mai 2013 beim Deutschen Patent- und Markenamt angemeldet und am 27. November 2014 mit der DE 10 2013 008 936 A1 offengelegt. Gleichzeitig mit der Anmeldung wurde Prüfungsantrag gestellt.

Die Prüfungsstelle für Klasse G01C hat im Prüfungsverfahren auf den Stand der Technik gemäß den folgenden Druckschriften verwiesen:

D1 WO 2012 065 726 A1,

D2 EP 1 548 686 B1,

D3 DE 10 2005 029 334 A1,

D4 US 6 167 332 A,

D5 US 2010 / 0 292 913 A1,

D6 DE 10 2011 104 258 A1,

D7 US 2010 / 0 106 403 A1 und

D8 US 2011 / 0 301 837 A1.

Sie hat in zwei Prüfungsbescheiden ausgeführt, dass einzelne Merkmale des Anspruchs 1 nicht klar seien und beim nebengeordneten Anspruch 15 die Technizität nicht gegeben sei. Darüber hinaus seien der Gegenstand des Patentanspruchs 1 dem Fachmann aus der Druckschrift D1 i.V.m. der Druckschrift D2 nahegelegt, sowie die Gegenstände der Ansprüche 1, 15 und 30 aus der Druckschrift D8 bekannt, und die Gegenstände der nebengeordneten Ansprüche 21 und 32 dem Fachmann aus der Druckschrift D8 nahegelegt.

Die Anmelderin hat der Prüfungsstelle in zwei Erwiderungen widersprochen und jeweils die Patenterteilung auf Basis des ursprünglich eingereichten Anspruchssatzes beantragt.

In einem Zusatz zur Ladung vom 14. Januar 2019 führte die Prüfungsstelle aus, dass die Merkmale der Ansprüche 1, 15 und 30 jeweils kein technisches Problem beträfen, das mit technischen Mitteln gelöst werde. Die technischen Merkmale erschöpften sich darin, dass das beanspruchte Verfahren durch eine Datenverarbeitungsanlage durchgeführt werde. Eine erfinderische Tätigkeit gegenüber dem Stand der Technik könne dadurch nicht begründet werden.

Mit Eingabe vom 15. Februar 2019 widersprach die Anmelderin den Ausführungen der Prüfungsstelle und reichte drei weitere Sätze Patentansprüche als Hilfsanträge 1 bis 3 ein.

In der daraufhin am 19. März 2019 durchgeführten Anhörung hat die Anmelderin die Patenterteilung mit dem ursprünglichen Anspruchssatz als Hauptantrag, den mit der Eingabe vom 15. Februar 2019 eingereichten Anspruchssätzen als Hilfsanträge 1 bis 3, sowie mit einem in der Anhörung überreichten Anspruchssatz als Hilfsantrag 4 beantragt, von denen die Prüfungsstelle die jeweiligen Gegenstände des Anspruchs 1 des Hauptantrags und der Hilfsanträge 1 bis 3 als nicht patentfähig angesehen, die Patenterteilung zu Hilfsantrag 4 jedoch in Aussicht gestellt hat.

Mit Eingabe vom 18. April 2019 reichte die Anmelderin Reinschriften und angepasste Unterlagen gemäß Hilfsantrag 4 ein, woraufhin die Prüfungsstelle durch Beschluss vom 9. Mai 2019 die Anmeldung im Umfang des Hauptantrags und der Hilfsanträge 1 bis 3 zurückgewiesen hat, da bei den jeweiligen Verfahren nach Anspruch 1 ein Programm für Datenverarbeitungsanlagen als solches vorliege, das gemäß § 1 Abs. 3 Nr. 3, Abs. 4 PatG vom Patentschutz ausgeschlossen sei. Auf Basis des Hilfsantrags 4 wurde ein Patent erteilt.

Gegen diesen der Anmelderin mit Anschreiben vom 9. Mai 2019 am 13. Mai 2019 zugestellten Beschluss hat die Anmelderin mit Schriftsatz vom 5. Juni 2019, am selben Tag beim Deutschen Patent- und Markenamt elektronisch eingegangen, Beschwerde eingelegt und diese mit Schriftsatz vom 11. September 2019 begründet.

In der mündlichen Verhandlung am 15. Juni 2021 hat die Anmelderin neben einer neuen Beschreibung einen neuen Anspruchssatz mit Ansprüchen 1 bis 31 vorgelegt.

Sie beantragt:

1. den Beschluss der Prüfungsstelle für Klasse G01C des Deutschen Patent- und Markenamts vom 9. Mai 2019 aufzuheben.

2. Ein Patent zu erteilen mit der Bezeichnung „Erstellung und Verwendung einer Datenstruktur für die Pfadermittlung in einem Verkehrswegenetz“,
dem Anmeldetag 24. Mai 2013 auf der Grundlage folgender Unterlagen:

– Patentansprüche 1 bis 31,

– Beschreibungsseiten 1 bis 33, jeweils überreicht in der mündlichen Verhandlung am 15. Juni 2021;

– 7 Blatt Zeichnungen mit Figuren 1, 2a, 2b, 2c, 2d, 3, 4a, 4b, 4c, 4d, 5, 6a und 6b eingegangen im Deutschen Patent- und Markenamt am Anmeldetag.

Der in der mündlichen Verhandlung überreichte Anspruch 1 lautet (
Gliederung bei unverändertem Wortlaut eingefügt):

1.0 Verfahren zum Erstellen einer Datenstruktur zur Verwendung durch einen Algorithmus, der Pfade in einem Verkehrswegenetz ermittelt,

1.1 wobei aneinandergrenzende geometrische Strukturen, die jeweils durch mindestens drei Strukturgrenzen definiert sind, auf das Verkehrswegenetz gelegt sind, wobei das Verfahren umfasst:

1.2 Ermitteln (305) mindestens einer geometrischen Struktur mit mindestens zwei Verkehrswegschnittpunkten,

1.2.1 wobei ein Verkehrswegschnittpunkt ein Schnittpunkt zwischen einer Strukturgrenze und einem Verkehrsweg ist;

1.3 Ermitteln (310), ob bei der mindestens einen geometrischen Struktur mit mindestens zwei Verkehrswegschnittpunkten mindestens ein Verkehrswegschnittpunktpaar nicht durch einen Verkehrsweg verbunden ist;

1.4 Unterteilen (315) der mindestens einen geometrischen Struktur in Unterstrukturen, wobei jede Unterstruktur mindestens drei Unterstrukturgrenzen aufweist,

1.4.1 wobei das Unterteilen der mindestens einen geometrischen Struktur in Unterstrukturen auf geometrische Strukturen mit mindestens einem Verkehrswegschnittpunktpaar, das nicht durch einen Verkehrsweg verbunden ist, beschränkt ist;

1.5 Ermitteln (320) von ersten Unterstrukturinformationen (425) für die mindestens eine unterteilte geometrische Struktur,

1.5.1 wobei die ersten Unterstrukturinformationen anzeigen, über welche der Unterstrukturgrenzen einer Unterstruktur ein Verkehrsweg aus der Unterstruktur in eine angrenzende Unterstruktur oder eine angrenzende geometrische Struktur führt; und

1.6 Speichern der ersten Unterstrukturinformationen (425) in einer Datenstruktur.

Der selbstständige Anspruch 13 lautet (
Gliederung bei unverändertem Wortlaut eingefügt):

13.0 Datenstruktur zur Verwendung durch einen Algorithmus, der Pfade in einem in geometrische Strukturen unterteilten Verkehrswegenetz ermittelt,

13.1 wobei mindestens eine geometrische Struktur in Unterstrukturen unterteilt ist,

13.2 wobei die Datenstruktur umfasst:

13.3 mindestens einen Strukturdatensatz, der umfasst:

13.3.1 – Strukturidentifizierungsdaten (410), die eine geometrische Struktur identifizieren;

13.4 mindestens einen Unterstrukturdatensatz, der umfasst:

13.4.1 – Strukturidentifizierungsdaten (420), die eine geometrische Struktur identifizieren, die in Unterstrukturen unterteilt ist; und

13.4.2 – erste Unterstrukturinformationen (425) für die unterteilte geometrische Struktur, die anzeigen, über welche Unterstrukturgrenze einer Unterstruktur ein Verkehrsweg aus der Unterstruktur in eine angrenzende Unterstruktur oder eine angrenzende geometrische Struktur hinausführt,

13.5 wobei die Datenstruktur nur einen oder mehrere Unterstrukturdatensätze für geometrische Strukturen mit mindestens zwei Verkehrswegschnittpunkten und mit mindestens einem Verkehrswegschnittpunktpaar, das nicht durch einen Verkehrsweg verbunden ist, umfasst,

13.5.1 wobei ein Verkehrswegschnittpunkt ein Schnittpunkt zwischen einer Strukturgrenze und einem Verkehrsweg ist.

Der selbstständige Anspruch 19 lautet (
Gliederung bei unverändertem Wortlaut eingefügt):

19.0 Verfahren zum iterativen Ermitteln eines oder mehrerer Pfade in einem in geometrische Strukturen unterteilten Verkehrswegenetz,

19.1 wobei mindestens eine geometrische Struktur in Unterstrukturen unterteilt ist,

19.2 wobei das Verfahren die folgenden Schritte umfasst:

19.3 a) Ermitteln (510) einer geometrischen Startstruktur, in der eine Startposition eines Pfads in dem Verkehrswegenetz liegt;

19.4 b) Ermitteln (515) mindestens einer angrenzenden geometrischen Struktur, in die ein Verkehrsweg aus der Startstruktur führt;

19.5 c) Ermitteln (525), wenn zu einer angrenzenden geometrischen Struktur Unterstrukturen existieren, einer Unterstruktureingangsgrenze zugehörig zu der angrenzenden geometrischen Struktur, wobei der Verkehrsweg über die Unterstruktureingangsgrenze führt;

19.6 d) Ermitteln (530), auf Basis der Datenstruktur gemäß einem der Ansprüche 13 bis 18, mindestens einer Unterstrukturausgangsgrenze zugehörig zu der angrenzenden geometrischen Struktur, wobei über die Unterstrukturausgangsgrenze ein Verkehrsweg in eine weitere angrenzende geometrische Struktur führt;

19.7 e) Ermitteln (535) mindestens einer weiteren angrenzenden geometrischen Struktur, die an die mindestens eine ermittelte Unterstrukturausgangsgrenze angrenzt;

19.8 f) Festlegen (560) der mindestens einen weiteren angrenzenden geometrischen Struktur als jeweils neue Startstruktur; und

19.9 g) Wiederholen der Schritte b) bis f) für die mindestens eine neue Startstruktur bis eine Iterationsgrenze erreicht ist.

Der selbstständige Anspruch 28 lautet (
Gliederung bei unverändertem Wortlaut eingefügt):

28.0 Vorrichtung (100) zum Erstellen einer Datenstruktur zur Verwendung durch einen Algorithmus, der Pfade in einem Verkehrswegenetz ermittelt,

28.1 wobei aneinandergrenzende geometrische Strukturen, die jeweils durch mindestens drei Strukturgrenzen definiert sind, auf das Verkehrswegenetz gelegt sind,

28.2 wobei die Vorrichtung umfasst:

28.3 ein Prozessorsystem (110), das eingerichtet ist, das Verfahren nach einem der Ansprüche 1 bis 12 durchzuführen.

Der selbstständige Anspruch 30 lautet (
Gliederung bei unverändertem Wortlaut eingefügt):

30.0 Vorrichtung zum Ermitteln eines oder mehrerer Pfade in einem in geometrische Strukturen unterteilten Verkehrswegenetz,

30.1 wobei mindestens eine geometrische Struktur in Unterstrukturen unterteilt ist,

30.2 wobei die Vorrichtung umfasst:

30.3 ein Prozessorsystem, das eingerichtet ist, das Verfahren nach einem der Ansprüche 19 bis 27 durchzuführen.

Hinsichtlich der Unteransprüche 2 bis 12, 14 bis 18, 20 bis 27, 29 und 31, sowie der weiteren Einzelheiten wird auf den Akteninhalt verwiesen.

Die form- und fristgerecht erhobene Beschwerde der Anmelderin ist zulässig und erweist sich nach dem Ergebnis der mündlichen Verhandlung vom 15. Juni 2021 auch als begründet. Sie führt zur Aufhebung des Beschlusses der Prüfungsstelle für Klasse G01C vom 9. Mai 2019 und zur Erteilung des Patents gemäß dem in der mündlichen Verhandlung gestellten Antrag (§ 79 Abs. 1 PatG i. V. m. § 49 Abs. 1 PatG), denn die geltenden Patentansprüche sind zulässig (§ 38 PatG), und ihre gewerblich anwendbare Lehre (§ 5 PatG) ist auch patentfähig (§§ 1 bis 4 PatG).

1. Die Anmeldung betrifft ein Verfahren zum Erstellen einer Datenstruktur zur Verwendung durch einen in einem Verkehrswegenetz Pfade ermittelnden Algorithmus, die Datenstruktur, ein Verfahren zum Ermitteln von Pfaden in dem Verkehrswegenetz mit Hilfe dieser Datenstruktur sowie eine Vorrichtung zur Ausführung eines der Verfahren (
vgl. geltende Beschreibung, S. 1, Z. 8 bis 12).

Bestimmte Algorithmen, wie sie in Navigationsgeräten eingesetzt werden, bieten die Möglichkeit, bestimmte Pfade in einem Verkehrswegenetz zu ermitteln. Beispielsweise kann von einer Startposition zu einer Zielposition ein Pfad durch das Verkehrswegenetz ermittelt werden. Eine andere Anwendung solcher Algorithmen bietet die Möglichkeit, eine Restreichweite eines Fahrzeugs in einer Kartenansicht darzustellen. In beiden Fällen ermitteln die Algorithmen von der Startposition aus Pfade durch das Verkehrswegenetz unter Berücksichtigung einer bestimmten Kostenfunktion. Im ersten Fall wird mindestens ein Pfad zur Zielposition gesucht, während im zweiten Fall alle Pfade um die Startposition herum ermittelt werden, die mit einer Restenergie des Fahrzeugs erreicht werden können. Häufig wird bei der Pfadermittlung ein Routengraph eingesetzt, dessen Knotenpunkte mit den Knoten im Verkehrswegenetz übereinstimmen und dessen Kanten (bzw. Kantengewichte) die Kosten einer Durchfahrung des Verkehrswegs von einem Verkehrswegenetzknoten zum nächsten widerspiegeln. Ein Algorithmus, der mit solch einem Routengraph arbeitet, ist zum Beispiel der Dijkstra-Algorithmus. In die Kostenfunktion fließen systemseitig festgelegte oder benutzerdefinierte Vorgaben ein, wie zum Beispiel die kürzeste, schnellste oder energieeffizienteste Strecke, bevorzugte Straßenklassen etc., um den entsprechenden Pfad durch das Verkehrswegenetz zu ermitteln (
vgl. geltende Beschreibung, S. 1, Z. 18 bis 37).

Die Druckschrift DE 10 2011 104 258 A1 (D6) geht darauf ein, dass insbesondere für die Restreichweitenberechnung dieser Ansatz verhältnismäßig aufwendig ist. Bei einer hohen Restenergie müssen nämlich sehr viele Verkehrswege für die Pfadermittlung durch den Algorithmus berücksichtigt werden. Ein Ansatz zur Vereinfachung dieser Berechnung ist ein Unterteilen des Verkehrswegenetzes in bestimmte Flächensegmente. Bei der Verwendung solcher Flächensegmente definiert jede Seite bzw. Kante dieser Flächensegmente einen Knoten in einem Routengraph. Als Kantengewichte werden Durchfahrungsinformationen oder Energiekosten zwischen den Seiten eines Flächensegments angegeben, die in die Kostenfunktion des Algorithmus (zum Beispiel wieder der Dijkstra-Algorithmus) einfließen können. Wenn mehrere Verkehrswege von einer Seite zu einer anderen Seite eines Flächensegments führen, kann ein Durchschnittswert der Kosten dieser Verkehrswege als Kantengewicht zur Durchfahrung des Flächensegments herangezogen werden (
vgl. geltende Beschreibung, S. 2, Z. 1 bis 14).

Hiervon ausgehend liegt der Anmeldung als technisches Problem die Aufgabe zugrunde, eine Datenstruktur für einen Routengraphen bereitzustellen, auf deren Grundlage eine präzisere Ermittlung von Pfaden durch das Verkehrswegenetz ohne große Einbußen bei der Geschwindigkeit der Pfadberechnung möglich ist (
vgl. geltende Beschreibung, S. 4, Z. 14 bis 17).

Gelöst wird diese Aufgabe durch das Verfahren zum Erstellen einer Datenstruktur nach Anspruch 1, durch die Datenstruktur des nebengeordneten Anspruchs 13, durch das Verfahren zum iterativen Ermitteln eines oder mehrerer Pfade nach Anspruch 19, durch die Vorrichtung zum Erstellen einer Datenstruktur des nebengeordneten Anspruchs 28, sowie durch die Vorrichtung zum Ermitteln eines oder mehrerer Pfade gemäß dem nebengeordneten Anspruch 30.

2. Als Fachmann ist hier ein Physiker oder Informatiker mit mehrjähriger Erfahrung in der Programmierung von Navigationssystemen zu definieren.

3. Die Merkmale in den geltenden Ansprüchen bedürfen der näheren Betrachtung:

Der Anspruch 1 bezieht sich auf ein Verfahren zum Erstellen einer Datenstruktur. Die Datenstruktur soll von einem Algorithmus, der Pfade in einem Verkehrswegenetz ermittelt, verwendbar sein (Merkmal 1.0). Der Pfadermittlungsalgorithmus ist somit nicht Teil des Verfahrens.

Dabei sind aneinandergrenzende geometrische Strukturen auf ein Verkehrswegenetz gelegt. Die geometrischen Strukturen sind jeweils durch mindestens drei Strukturgrenzen definiert (Merkmal 1.1). Die geometrischen Strukturen können beispielsweise Polygone wie Rechtecke oder Quadrate sein. Da es sich um Verkehrswege auf einem Globus handelt, ist es vorteilhaft, wenn die Grenzen der geometrischen Strukturen auf einer geographischen Länge bzw. Breite liegen (
vgl. geltende Beschreibung, S. 13, Z. 4-7 und Fig. 2a, 2b). Die Strukturgrenzen werden auch als Seite oder Kante bezeichnet (
vgl. Beschreibung, S. 13, Z. 26, S. 14, Z. 13-14).

Figur 2a der Anmeldung

Gemäß den Merkmalen 1.2 und 1.2.1 umfasst das Verfahren zum Erstellen einer Datenstruktur das Ermitteln mindestens einer geometrischen Struktur mit mindestens zwei Verkehrswegschnittpunkten, wobei ein Verkehrswegschnittpunkt ein Schnittpunkt zwischen einer Strukturgrenze und einem Verkehrsweg ist. Es wird somit zunächst mindestens eine geometrische Struktur ermittelt, die mindestens zwei Schnittpunkte zwischen einer Strukturkante und einem Verkehrsweg aufweist.

In dem folgenden Verfahrensschritt 310 wird ermittelt, ob bei dieser mindestens einen geometrischen Struktur mit mindestens zwei Verkehrswegschnittpunkten mindestens ein Verkehrswegschnittpunktpaar nicht durch einen Verkehrsweg verbunden ist (Merkmal 1.3). Somit wird ermittelt, ob von einem Verkehrswegschnittpunkt jeder andere Verkehrswegschnittpunkt durch einen Verkehrsweg erreicht werden kann. In der mittleren geometrischen Struktur der Figur 2c (markiert) sind die von West nach Nord und die von Süd nach Ost verlaufenden Straßen nicht miteinander verbunden. Der Schnittpunkt auf der westlichen (markierten) Strukturgrenze ist mit mindestens einem Verkehrswegschnittpunkt, hier sowohl der auf der südlichen als auch auf der östlichen (markierten) Strukturgrenze, nicht über einen Verkehrsweg verbunden. Das gleiche gilt für den Schnittpunkt auf der nördlichen Grenze. In Schritt 310 des Verfahrens wird daher ermittelt, dass mindestens ein Verkehrswegschnittpunktpaar, hier vier Paare, nicht über einen Verkehrsweg verbunden ist (
vgl. Beschreibung, S. 20, Z. 20 bis S. 21, Z. 2).

Figur 2c mit Markierung des Senats

Gemäß Merkmal 1.4 wird die mindestens eine geometrische Struktur in Unterstrukturen unterteilt, wobei jede Unterstruktur mindestens drei Unterstrukturgrenzen aufweist. Gemäß Merkmal 1.4.1 ist dieses Unterteilen auf geometrische Strukturen mit mindestens einem Verkehrswegschnittpunktpaar, das nicht durch einen Verkehrsweg verbunden ist, beschränkt. Somit erfolgt eine Unterteilung geometrischer Strukturen in Unterstrukturen ausschließlich, wenn zwei Schnittpunkte zwischen Strukturgrenze und Verkehrsweg, wie in Fig. 2c dargestellt, nicht miteinander verbunden sind. Wenn die geometrische Struktur entlang der geographischen Länge und Breite angelegt ist, können auch die dazu gehörigen Unterstrukturen beispielsweise entlang von geographischen Längen und Breiten unterteilt werden (
vgl. Beschreibung, S. 21, Z. 12-15).

Im Anschluss an die Unterteilung werden erste Unterstrukturinformationen für die mindestens eine unterteilte geometrische Struktur ermittelt (Merkmal 1.5). Diese ersten Unterstrukturinformationen zeigen an, über welche der Grenzen bzw. Kanten einer Unterstruktur ein Verkehrsweg aus der Unterstruktur in eine angrenzende Unterstruktur oder eine angrenzende geometrische Struktur führt (Merkmal 1.5.1). Beispielsweise sind die Unterstrukturinformationen zu jeweils vier Bit pro Unterstruktur gegliedert. Jedes Bit dieser Gruppen zeigt an, ob über eine Unterstrukturgrenze der Unterstruktur ein Verkehrsweg aus der Unterstruktur in eine angrenzende Unterstruktur oder eine angrenzende geometrische Struktur führt oder nicht. Beispielsweise kann der Bit-Wert auf “1“ gesetzt werden, falls ein Verkehrsweg aus der Unterstruktur herausführt (
vgl. Beschreibung, S. 22, Z. 6-14 und Fig. 2c, 4c). Im Beispiel der Figur 4c führt ein Verkehrsweg im Osten und im Süden aus der Unterstruktur SP
₀ heraus.

Ausschnitt aus Figur 4c der Anmeldung

Gemäß Merkmal 1.6 werden diese ersten Unterstrukturinformationen in einer Datenstruktur gespeichert. Die Datenstruktur umfasst beispielsweise einen adressierbaren Unterstrukturdatensatz, der die ersten Unterstrukturinformationen für die unterteilte geometrische Struktur umfasst. Die Figur 4b zeigt einen beispielhaften Unterstrukturdatensatz (
vgl. Beschreibung, S. 7, Z. 12-18; S. 11, Z. 14-17; S. 12, Z. 17-18; S. 21, Z. 35-37 und Fig. 4b).

Figuren 4b, 4c der Anmeldung

Der Anspruch 13 bezieht sich auf eine Datenstruktur. Diese soll zur Verwendung durch einen Algorithmus, der Pfade in einem in geometrische Strukturen unterteilten Verkehrswegenetz ermittelt, geeignet sein (Merkmal 13.0).

Das Merkmal 13.1 gibt an, dass mindestens eine geometrische Struktur in Unterstrukturen unterteilt ist.

Gemäß den Merkmalen 13.2 und 13.3 umfasst die Datenstruktur mindestens einen Strukturdatensatz. Dieser Strukturdatensatz umfasst Strukturidentifizierungsdaten, die eine geometrische Struktur identifizieren (Merkmal 13.3.1). Bei den Strukturidentifizierungsdaten des Strukturdatensatzes der Datenstruktur handelt es sich beispielsweise um eine Struktur-ID, wie z.B. eine Zahl oder eine alphanumerische Kennzeichnung, die die geometrische Struktur innerhalb aller geometrischen Strukturen eindeutig identifiziert (
vgl. Beschreibung, S. 19, Z. 5-7 und Fig. 4a).

Die Datenstruktur umfasst darüber hinaus mindestens einen Unterstrukturdatensatz (Merkmal 13.4), also einen Datensatz zu mindestens einer Unterstruktur.

Dieser Unterstrukturdatensatz umfasst, gemäß Merkmal 13.4.1, zum einen Strukturidentifizierungsdaten, die eine geometrischen Struktur identifizieren, die in Unterstrukturen unterteilt ist. Dieser Unterstrukturdatensatz besteht beispielsweise ebenfalls aus einer Struktur-ID, die eine geometrische Struktur identifiziert (
vgl. Beschreibung, S. 21, Z. 36-37 und Fig. 4b).

Zum anderen umfasst der Unterstrukturdatensatz gemäß Merkmal 13.4.2 erste Unterstrukturinformationen für die unterteilte geometrische Struktur, die anzeigen, über welche Unterstrukturgrenze einer Unterstruktur ein Verkehrsweg aus der Unterstruktur in eine angrenzende Unterstruktur oder eine angrenzende geometrische Struktur hinausführt. Dieses können beispielsweise, wie zum Merkmal 1.5.1 ausgeführt, vier Bit pro Unterstruktur sein (
vgl. Beschreibung, S. 22, Z. 6-14 und Fig. 4c).

Gemäß Merkmal 13.5 umfasst die Datenstruktur ausschließlich einen oder mehrere Unterstrukturdatensätze für geometrische Strukturen mit mindestens zwei Verkehrswegschnittpunkten und mit mindestens einem Verkehrswegschnittpunktpaar, das nicht durch einen Verkehrsweg verbunden ist. Somit enthält die Datenstruktur ausschließlich (feinere) Unterstrukturdatensätze für (grobe) geometrische Strukturen, wenn die (groben) geometrischen Struktur mindestens ein nicht verbundenes Verkehrswegschnittpunktpaar aufweisen.

Entsprechend Merkmal 1.2.1 ist auch gemäß Merkmal 13.5.1 ein Verkehrswegschnittpunkt ein Schnittpunkt zwischen einer Strukturgrenze und einem Verkehrsweg.

Der Anspruch 19 bezieht sich auf ein Verfahren zum iterativen Ermitteln eines oder mehrerer Pfade in einem in geometrische Strukturen unterteilten Verkehrswegenetz. Dabei ist mindestens eine geometrische Struktur in Unterstrukturen unterteilt (Merkmale 19.0, 19.1).

Gemäß den Merkmalen 19.2 und 19.3 wird zunächst eine geometrische Startstruktur ermittelt, in der eine Startposition eines Pfads in dem Verkehrswegenetz liegt. Diese Standortposition kann beispielsweise durch einen GPS-Empfänger ermittelt worden sein (
vgl. Beschreibung, S. 25, Z. 21-22). Bei der geometrischen Startstruktur handelt es sich somit um die (grobe) geometrische Struktur, in der sich die Startposition befindet.

Im Anschluss wird mindestens eine angrenzende geometrische Struktur ermittelt, in die ein Verkehrsweg aus der geometrischen Startstruktur führt (Merkmal 19.4). Dabei handelt es sich somit um eine benachbarte (grobe) geometrische Struktur. „Mindestens eine“ versteht der Fachmann als Möglichkeit, dass die Ermittlung in verschiedene Richtungen durchgeführt werden kann.

Gemäß Merkmal 19.5 wird, wenn zu einer angrenzenden geometrischen Struktur Unterstrukturen existieren, eine zu der angrenzenden geometrischen Struktur zugehörige Unterstruktureingangsgrenze ermittelt, wobei der Verkehrsweg über die Unterstruktureingangsgrenze führt. Bei der Unterstruktureingangsgrenze handelt es sich um eine Unterstrukturgrenze, die auf der Grenze der geometrischen Struktur liegt und über die ein Verkehrsweg von der ausgehenden geometrischen Struktur (Startstruktur) in die angrenzende geometrische Struktur verläuft (
vgl. Beschreibung, S. 27, Z. 23-26).

In dem nachfolgenden Schritt 530 wird gemäß Merkmal 19.6, auf Basis der Datenstruktur gemäß einem der Ansprüche 13 bis 18, mindestens eine Unterstrukturausgangsgrenze, zugehörig zu der gerade betrachteten angrenzenden (groben) geometrischen Struktur, ermittelt. Diese Unterstrukturausgangsgrenze ist eine Unterstrukturgrenze, über die ein Verkehrsweg in eine weitere angrenzende (grobe) geometrische Struktur führt (
vgl. Beschreibung, S. 27, Z. 28-31). Während sich das Merkmal 19.5 auf eine Unterstruktureingangsgrenze auf der Unterstrukturebene der angrenzenden (groben) geometrischen Struktur bezieht, betrifft das Merkmal 19.6 eine Unterstrukturausgangsgrenze auf der Unterstrukturebene, die aus der angrenzenden (groben) geometrischen Struktur herausführt. Diesen Angaben entnimmt der Fachmann, dass sich die zu ermittelnde Unterstrukturausgangsgrenze dabei in derselben Unterstruktur befinden kann, in die der Verkehrsweg auch hineinführte, oder aber auch in einer anderen am Rand der angrenzenden (groben) geometrischen Struktur befindlichen Unterstruktur. Die Figur 2c zeigt das letztere Beispiel, bei dem sich eine Unterstruktureingangsgrenze in der zweiten Unterstruktur von oben befindet, die am linken Rand der mittleren (groben) geometrischen Struktur angeordnet ist. Die Unterstrukturausgangsgrenze befindet sich am oberen Rand in der dritten Unterstruktur von links:

Figur 2c mit Ergänzungen des Senats

Anschließend wird in Schritt 535 mindestens eine weitere angrenzende geometrische Struktur ermittelt, die an die mindestens eine ermittelte Unterstrukturausgangsgrenze angrenzt (
vgl. Beschreibung, S. 27, Z. 33-35; Merkmal 19.7). Im Ausführungsbeispiel der Figur 2c würde gemäß Merkmal 19.7 die obere mittlere (grobe) geometrische Struktur als eine weitere angrenzende geometrische Struktur ermittelt.

Diese mindestens eine weitere angrenzende geometrische Struktur wird, gemäß Merkmal 19.8, im Schritt 560 als jeweils neue Startstruktur festgelegt.

Gemäß Merkmal 19.9 werden die Schritte b) bis f) der Merkmale 19.4 bis 19.8 für die mindestens eine neue Startstruktur solange wiederholt, bis eine Iterationsgrenze erreicht ist. Solch eine Iterationsgrenze kann das Erreichen einer Zielstruktur sein, in der sich eine Zielposition befindet. Für den Fall, dass eine Restreichweitenbestimmung durchgeführt wird, ist die Iterationsgrenze das Erreichen einer bestimmten Distanz (die dem noch vorhandenen Energievorrat entsprechen kann) oder eines bestimmten Energieverbrauchs (z.B. angegeben in Litern verfügbaren Tankinhalts) (
vgl. Beschreibung, S. 31, Z. 8-16).

Der Anspruch 28 bezieht sich auf eine Vorrichtung zum Erstellen einer Datenstruktur. Die Vorrichtung kann beispielsweise ein Computer, Server, Laptop, Netbook, Notebook, Tablet-PC, Smartphone, Navigationsgerät etc. oder ein Bestandteil davon sein. Die Vorrichtung kann auch fest in einem Fahrzeug verbaut sein, zum Beispiel als Teil eines Fahrerinformationssystems (
vgl. Beschreibung, S. 12, Z. 3-6). Die Datenstruktur dient zur Verwendung durch einen Algorithmus, der Pfade in einem Verkehrswegenetz ermittelt, wobei aneinandergrenzende geometrische Strukturen, die jeweils durch mindestens eine Strukturgrenze definiert sind, auf ein Verkehrswegenetz gelegt sind (Merkmale 28.0, 28.1). Gemäß den Merkmalen 28.2 und 28.3 umfasst die Vorrichtung ein Prozessorsystem, das eingerichtet ist, das Verfahren zum Erstellen einer Datenstruktur nach einem der Ansprüche 1 bis 12 durchzuführen.

Der Anspruch 30 bezieht sich auf eine Vorrichtung zum Ermitteln eines oder mehrerer Pfade in einem in geometrische Strukturen unterteilten Verkehrswegenetz, wobei mindestens eine geometrische Struktur in Unterstrukturen unterteilt ist (Merkmale 30.0, 30.1). Die Vorrichtung dient somit der Routenberechnung. Diese Vorrichtung umfasst ein Prozessorsystem, das eingerichtet ist, das Verfahren nach einem der Ansprüche 19 bis 27 durchzuführen (Merkmale 30.2, 30.3).

4. Die in der Verhandlung überreichten Ansprüche 1 bis 31 sind zulässig.

Der Anspruch 1 umfasst die Merkmale der ursprünglichen Ansprüche 1, 3 und 4. Die Änderungen in den Merkmalen 1.1 und 1.4 sind in der ursprünglichen Beschreibung auf der Seite 13, Z. 3 bis 5, sowie auf der Seite 22, Z. 21 offenbart.

Der selbstständige Anspruch 13 geht aus dem ursprünglichen Anspruch 15 hervor (Merkmale 13.0 bis 13.4.2). Zudem wurden aus der ursprünglichen Beschreibung, S. 3, Z. 16 bis 25 weitere Merkmale (13.5, 13.5.1) aufgenommen.

Der Anspruch 19 basiert auf dem ursprünglichen Anspruch 21. Die Ergänzung im Merkmal 19.6 ist in den Zeilen 26 bis 29 der Seite 25, sowie ab Seite 25, Zeile 35 bis S. 26, Zeile 9 der ursprünglichen Beschreibung offenbart.

Die nebengeordneten Ansprüche 28 und 30 entsprechen den ursprünglichen nebengeordneten Ansprüchen 30 und 32.

Die Unteransprüche 2 bis 12, 14 bis 18, 20 bis 27, 29 und 31 entsprechen den ursprünglichen Ansprüchen 2, 5 bis 14, 16 bis 20, 22 bis 29, 31 und 33 bei Anpassung der Rückbezüge.

Die Gegenstände und Verfahren der Ansprüche sind somit ursprünglich offenbart und damit zulässig.

5. Die Lehren der Ansprüche sind in den Anmeldeunterlagen so deutlich und vollständig offenbart, dass ein Fachmann sie ausführen kann (§ 34 Abs. 4 PatG).

6. Der jeweilige Gegenstand der Ansprüche 1, 13, 19, 28 und 30 liegt auf technischem Gebiet und ist dem Patentschutz zugänglich, da er eine Lösung eines konkreten technischen Problems mit technischen Mitteln liefert.

6.1 Die jeweiligen Gegenstände der unabhängigen Ansprüche liegen auf einem technischen Gebiet im Sinne des § 1 Abs. 1 PatG.

Nach der Rechtsprechung des Bundesgerichtshofs ist bei Erfindungen mit Bezug zu Vorrichtungen und Verfahren der elektronischen Datenverarbeitung zunächst zu klären, ob der Gegenstand der Erfindung auf technischem Gebiet liegt. Dies ist vorliegend gegeben. Denn das Verfahren zum Erstellen einer Datenstruktur (vgl. Anspruch 1), die Datenstruktur zur Verwendung durch einen Algorithmus (vgl. Anspruch 13), das Verfahren zum iterativen Ermitteln eines oder mehrerer Pfade (vgl. Anspruch 19), die Vorrichtung zum Erstellen einer Datenstruktur (vgl. Anspruch 28) und die Vorrichtung zum Ermitteln eines oder mehrerer Pfade (vgl. Anspruch 30) lehren jeweils die Nutzung einer Datenverarbeitungsanlage, die in bestimmter Weise programmtechnisch eingerichtet ist (
vgl. geltende Beschreibung, S. 12, Z. 2-9: „eine Vorrichtung zur Datenverarbeitung … Die Vorrichtung 100 kann ein Computer, Server, Laptop, Netbook, Notebook, Tablet-PC, Smartphone, Navigationsgerät etc. oder ein Bestandteil davon sein. Die Vorrichtung 100 kann auch fest in einem Fahrzeug verbaut sein, zum Beispiel als Teil eines Fahrerinformationssystems. Die Vorrichtung 100 umfasst ein Prozessorsystem 110, welches in der Lage ist, Programme auszuführen.“; S. 13, Z. 11-12: „Die Erzeugung der Datenstruktur kann zum Beispiel durch die Vorrichtung 100 (Fig. 1) vorgenommen werden.“). Damit wird die Nutzung einer Datenverarbeitungsanlage gelehrt und eine Anweisung zum technischen Handeln gegeben, womit der jeweilige Gegenstand der Erfindung dem Gebiet der Technik zuzurechnen ist (
vgl. BGH, Beschluss vom 22. April 2010, Xa ZB 20/08, GRUR 2010, 613, erster Leitsatz – Dynamische Dokumentengenerierung; BGH, Urteil vom 24. Februar 2011, X ZR 121/09, GRUR 2011, 610, zweiter Leitsatz – Webseitenanzeige).

6.2 Die jeweiligen Gegenstände der unabhängigen Ansprüche 1, 13, 19, 28 und 30 sind gemäß § 1 Abs. 3 Nr. 3 i. V. m. Abs. 4 PatG dem Patentschutz zugänglich. Diese Ansprüche enthalten Anweisungen, die der Lösung eines konkreten technischen Problems mit technischen Mitteln dienen.

Nach der Rechtsprechung des Bundesgerichtshofs ist ein Verfahren, das sich zur Herbeiführung des angestrebten Erfolges eines Programms bedient, mit dessen Hilfe eine Datenverarbeitungsanlage so gesteuert wird, dass der gewünschte Erfolg erzielt wird, nicht schon wegen des Vorgangs der elektronischen Datenverarbeitung dem Patentschutz zugänglich. Da das Gesetz Programme für Datenverarbeitungsanlagen als solche vom Patentschutz ausschließt (§ 1 Abs. 3 Nr. 3 i. V. m. Abs. 4 PatG) muss die beanspruchte Lehre vielmehr Anweisungen enthalten, die der Lösung eines konkreten technischen Problems mit technischen Mitteln dienen (BGH, Beschluss vom 19. Oktober 2004 – X ZB 34/03, GRUR 2005, 143 – Rentabilitätsermittlung, III. 4. a; BGH, – Webseitenanzeige, III. 1. b, a. a. O.).

Welches technische Problem durch eine Erfindung gelöst wird, ist objektiv danach zu bestimmen, was die Erfindung tatsächlich leistet (vgl. BGH, Beschluss vom 19. Oktober 2004 – X ZB 33/03, GRUR 2005, 141, II. 4. b) – Anbieten interaktiver Hilfe).

Das Verfahren des Anspruchs 1 dient der weiteren Unterteilung einer Karte mit vorhandenem Raster und der Ermittlung von Schnittpunkten von Verkehrswegen mit dem weiter unterteilten Raster. Die Ermittlung der Schnittpunkte erfolgt durch einen Vergleich der graphischen Verkehrswegenetzdaten mit den graphischen Daten der Strukturgrenzen (
vgl. geltende Beschreibung, S. 17, Z. 16 bis 18). Die Unterteilung erfolgt jedoch nur für ein Raster, indem zwei Verkehrswegeschnittpunkte nicht durch einen Verkehrsweg verbunden sind (
vgl. S. 7, Z. 23-25). Somit wird eine präzisere Navigationskarte für ein Navigationssystem erzeugt, die die Verkehrswege detaillierter abbildet und eine fehlerhafte Routenberechnung vermeidet (
vgl. geltende Beschreibung, S. 15, Z. 3-11).

Darüber hinaus sieht das mit dem Anspruch 1 beanspruchte Verfahren auch technische Mittel zur Lösung eines technischen Problems vor.

Nach der gefestigten Rechtsprechung des Bundesgerichtshofs liegt ein technisches Mittel zur Lösung eines technischen Problems nicht nur dann vor, wenn Systemkomponenten modifiziert oder in neuartiger Weise adressiert werden. Es reicht vielmehr aus, wenn der Ablauf eines Datenverarbeitungsprogramms, das zur Lösung des Problems eingesetzt wird, durch technische Gegebenheiten außerhalb der Datenverarbeitungsanlage bestimmt wird oder wenn die Lösung gerade darin besteht, ein Datenverarbeitungsprogramm so auszugestalten, dass es auf die technischen Gegebenheiten der Datenverarbeitungsanlage Rücksicht nimmt (
vgl. BGH, Urteil vom 24. Februar 2011 – X ZR 121/09 Webseitenanzeige; BGH, Beschluss vom 22. April 2010 – Xa ZB 20/08 Dynamische Dokumentengenerierung).

Die Prüfungsstelle argumentierte im Beschluss vom 9. Mai 2019, dass das Verfahren gemäß Anspruch 1 nicht durch technische Gegebenheiten außerhalb der Datenverarbeitungsanlage bestimmt werde. Solche technischen Gegebenheiten außerhalb der Datenverarbeitungsanlage könnten beispielsweise gemessene Sensordaten, die Einfluss auf das Verfahren haben, sein. Entsprechende technische Einflüsse von außen seien nicht zu erkennen. Auch werde nicht auf spezielle technische Gegebenheiten der Datenverarbeitungsanlage z.B. durch technische Wechselwirkung oder Rückkopplung mit einem später zu verwendenden Navigationsgerät Rücksicht genommen. Die Rücksichtnahme beschränke sich auf das allgemeine Bedürfnis nach schneller, effizienter und fehlerfreier Routenberechnung. Die Verfahrensschritte gingen dabei nicht über eine digitale Verarbeitung und Speicherung von Daten hinaus.

Dieser Argumentation konnte nicht überzeugen, denn der Ablauf des Verfahrens nach Anspruch 1 ist abhängig von den Grunddaten des Verkehrswegenetzes, das auf realen Messwerten beruht, und somit durch technische Gegebenheiten außerhalb der Datenverarbeitungsanlage bestimmt wird. Die ermittelten und anschließend gespeicherten Unterstrukturinformationen sind dabei abhängig von den Pfaden in dem Verkehrswegenetz und ihren Schnittpunkten mit Unterstrukturgrenzen und somit abhängig von äußeren Gegebenheiten. Darüber hinaus erfolgt eine Unterteilung gemäß Merkmal 1.4.1 ausschließlich, wenn Verkehrswegeschnittpunktpaare nicht durch einen realen Verkehrsweg verbunden sind, so dass auch der Ablauf des Verfahrens durch die gemessenen Verkehrswegedaten beeinflusst wird.

Somit fällt das Verfahren nach dem Patentanspruch 1 auch nicht unter den Ausschlusstatbestand des § 1 Abs. 3 Nr. 3 i. V. m. Abs. 4 PatG und ist deshalb dem Patentschutz zugänglich.

Entsprechendes gilt für die jeweiligen Gegenstände der unabhängigen Ansprüche 13, 19, 28 und 30.

7. Die gewerblich anwendbaren (§ 5 PatG) Gegenstände der geltenden Ansprüche 1, 13, 19, 28 und 30 sind jeweils gegenüber dem ermittelten Stand der Technik neu (§ 3 PatG) und beruhen diesem gegenüber auf einer erfinderischen Tätigkeit (§ 4 PatG) des Fachmanns, so dass sie patentfähig sind (§ 1 Abs. 1 PatG).

7.1 Die Druckschrift D8 offenbart in Übereinstimmung mit dem Wortlaut des geltenden Anspruchs 1 ein

1.0 Verfahren zum Erstellen einer Datenstruktur (
vgl. Abs. [0003]: „a method … for pre-processing road segment data“) zur Verwendung durch einen Algorithmus, der Pfade in einem Verkehrswegenetz ermittelt (
vgl. Abs. [0003]: „a method … for determining an optimum route based on pre-processed road segment data“),

1.1 wobei aneinandergrenzende geometrische Strukturen (
vgl. Abs. [0033]: „tiles 80“), die jeweils durch mindestens drei Strukturgrenzen definiert sind (
vgl. Abs. [0119]: „The step of defining a tiling may include providing edge … data for each tile“ und Fig. 1), auf das Verkehrswegenetz gelegt sind (
vgl. Abs. [0033]: „The set of tiles 80 is overlaid on a road network“ und Fig. 1), wobei das Verfahren umfasst:

1.2 Ermitteln mindestens einer geometrischen Struktur (
vgl. Abs. [0035]: „tile 82“ und Fig. 1) mit mindestens zwei Verkehrswegschnittpunkten (
vgl. Abs. [0033]: „vertex 95“; Abs. [0035]: „vertex 98“ und Fig. 1),

1.2.1 wobei ein Verkehrswegschnittpunkt ein Schnittpunkt zwischen einer Strukturgrenze und einem Verkehrsweg ist (
vgl. Abs. [0033]: „The endpoints of a road segment or road segment junctions or crossings define vertices indicated in FIG. 1 by solid circles such as vertex 95.“; Abs. [0035]: „add vertices at each point where a road segment crosses a tile edge or a tile comer“ und Fig. 1);

[…]

1.4
_teils Unterteilen
einder mindestens einen geometrischen Struktur in Unterstrukturen (
„96“, „97“), wobei jede Unterstruktur mindestens drei Unterstrukturgrenzen aufweist (
vgl. Abs. [0034]: „a tile may be subdivided to create smaller tiles in an area with high item density. This concept is illustrated by small tiles 96 and 97 in FIG. 1“),

[…]

1.5 Ermitteln von ersten Unterstrukturinformationen (
vgl. Abs. [0035]: „is to add vertices at each point where a road segment crosses a tile edge“, “breaks the original road segment 81 into segments 84 and 85”; Abs. [0047]: “The road segment data may include geographic information relating to road segment position and orientation, such as the geographic location of the start and end points for the road segment”; Abs. [0096]: “an index file may be provided containing information on where in the road segment database the data relating to a specific tile size, tile, and rank information may be found”; Abs. [0119]: „defining a tiling may include providing edge … data for each tile“) für die mindestens eine unterteilte geometrische Struktur,

1.5.1 wobei die ersten Unterstrukturinformationen (
„add vertices“-„road segment data“-„index file“-„edge data“) anzeigen, über welche der Unterstrukturgrenzen (
„edge data“) einer Unterstruktur ein Verkehrsweg (
„road segment“) aus der Unterstruktur in eine angrenzende Unterstruktur oder eine angrenzende geometrische Struktur führt; und

1.6 Speichern der ersten Unterstrukturinformationen in einer Datenstruktur (
vgl. Abs. [0046]: „System 1 may include a first storage unit 10 for storing road segment data, a second storage unit 20 for storing tiling definition data, and a third storage unit 30 for storing the rank information for individual road segments. The first, second, and third storage units (10, 20, and 30) may be different physical devices as shown in FIG. 1 but may also be combined into one physical storage unit“; Abs. [0096]: „index file“).

Damit unterscheidet sich das Verfahren des Anspruchs 1 von dem in Druckschrift D8 offenbarten dadurch, dass ermittelt wird, ob bei der mindestens einen geometrischen Struktur mit mindestens zwei Verkehrswegschnittpunkten mindestens ein Verkehrswegschnittpunktpaar nicht durch einen Verkehrsweg verbunden ist (Merkmal 1.3) und, dass das Unterteilen der mindestens einen geometrischen Struktur in Unterstrukturen auf geometrische Strukturen mit mindestens einem Verkehrswegschnittpunktpaar, das nicht durch einen Verkehrsweg verbunden ist, beschränkt ist (Merkmale 1.4
_rest, 1.4.1). Damit ist das Verfahren des Anspruchs 1 gegenüber der Offenbarung der Druckschrift D8 neu (§ 3 PatG).

Es beruht zudem auch auf einer erfinderischen Tätigkeit (§ 4 PatG).

Der Druckschrift D8 ist keinerlei Hinweis zu entnehmen, insbesondere im Sinne des Merkmals 1.4.1 ausschließlich geometrische Strukturen zu unterteilen, bei denen mindestens ein Verkehrswegschnittpunktpaar nicht durch einen Verkehrsweg verbunden ist. Die D8 offenbart dem Fachmann lediglich, die Kachelgröße in städtischen Gebieten mit hoher Dichte an Straßensegmenten und Eckpunkten zu verringern (
vgl. dort Abs. [0034]). Darüber hinaus sind sowohl der Figur 1, als auch der Figur 3 der D8 nicht weiter unterteilte Kacheln zu entnehmen, in denen Schnittpunkte von Kachelkanten und Verkehrswegen nicht miteinander verbunden sind (
vgl. in Figur 1 die Kachel 83, sowie in Figur 3 die Kachel 365).

Auch die übrigen Druckschriften geben darauf keinen Hinweis.

Die Druckschrift D1 offenbart keine Unterteilung geometrischer Strukturen und verweist lediglich darauf, dass die geometrischen Strukturen bzw. Flächensegmente unterschiedliche Größen aufweisen können, um eine effiziente Berechnung langer Überlandetappen genauso zu ermöglichen, wie eine genaue Berechnung von Gebieten mit einer Vielzahl unterschiedlicher Straßen (
vgl. D1, S. 7, 2. Absatz).

Die Druckschrift D2 lehrt zwar eine Unterteilung größerer Blöcke in mehrere Maschen (
vgl. D2, Abs. [0018]: „Each block 102 is divided into a plurality of meshes 103 and is managed with the meshes. In the embodiment, the data in the block are managed as m x n sets of mesh data. The blocks 102 of map data at the same level are each divided into m x n meshes.“, sowie Figur 3), jedoch ist auch dieser kein Hinweis zu entnehmen, ausschließlich größere Blöcke zu unterteilen, bei denen mindestens ein Verkehrswegschnittpunktpaar nicht durch einen Verkehrsweg verbunden ist.

Die Druckschrift D3 betrifft ein Verfahren zum Ermitteln einer von einem Fahrzeug zu befahrenden Wegstrecke wobei zumindest zu einzelnen Gitterelementen Vorzugstrajektorien definiert sind, die einen bevorzugten Weg von diesen einzelnen Gitterelementen zu weiteren Gitterelementen definieren, wobei die zu befahrende Wegstrecke durch eine Kombination von sich aus der Zusammenfügung von Gitterpunkten ergebenden Streckenelementen mit einer oder mehreren Vorzugstrajektorien definierbar ist. Dadurch lässt sich insbesondere bei größeren Entfernungen schneller ein Weg ermitteln, weil optimierte Wegstrecken in Form der Vorzugstrajektorien bereits bekannt sind (
vgl. D3, Abs. [0001], [0004], [0005], [0025]). Somit ist der D3 durch die Verwendung von Vorzugstrajektorien eine gröbere und keine feinere Strukturierung mittels Unterstrukturen zu entnehmen.

Die Druckschrift D4 offenbart ein Verfahren für ein selbstgeführtes Fahrzeug, das in der Lage ist, ohne direkten menschlichen Eingriff in einem fremden, manchmal feindlichen Gelände, zu arbeiten. Das Fahrzeug hat vorzugsweise Sensoren zur Erfassung des Geländes in seiner Umgebung. Mit diesen Sensoren kann eine Karte der Region erstellt werden, die das Fahrzeug und sein Ziel umfasst. Auf die Geländekarte wird ein Gitter aufgelegt, das ein Array aus Zellen erzeugt. Das Fahrzeug bewegt sich von Zelle zu Zelle von seinem aktuellen Standort zu seinem Zielort und folgt dabei einem Pfad mit dem geringsten Widerstand (minimale Kosten). Die Gittermaschengröße (Zellengröße) wird vorzugsweise so ausgewählt, dass sie ausreichend klein ist, um eine ausreichende Unterscheidung der lokalen Bedingungen und Merkmale des Geländes zu ermöglichen. Anfänglich ist die Zellengröße relativ grob und wird später relativ fein, wenn sich das Vehikel seiner Zielzelle nähert. Ferner kann jede Zelle hierarchisch behandelt werden. Vorzugsweise wird ein gewichteter Kantengraph aus den Zellen des Arrays konstruiert. Die Knoten dieses Diagramms bezeichnen die Zellen, und die Verbindungskanten stellen die Verknüpfungen zu benachbarten Zellen dar, die direkt erreicht werden können. Die Aufgabe für das Fahrzeug besteht darin, vom Grundknoten zum Zielknoten zu fahren, d.h. dem Knoten, der die Zielzelle darstellt, um die Summe der gewichteten Kanten der durchquerten Knoten zu minimieren (
vgl. D4, Sp. 2, Z. 59 bis Sp. 3, Z. 53). Die Figuren 6 und 7 der D4 offenbaren zwar ein hierarchisches Gitter, das einer lokalen Zelle des Geländes auferlegt wird und zu einer Gitterverfeinerung führt (
vgl. Sp. 4, Z. 34-39 und Fig. 6, 7), jedoch sind der D4 keine weiteren Angaben zur Verfeinerung, insbesondere keine Hinweise auf eine Ermittlung geometrischer Strukturen ohne verbundene Verkehrswegschnittpunkte und deren ausschließliche Unterteilung, im Sinne der Merkmale 1.3 und 1.4.1 zu entnehmen.

Die Druckschrift D5 offenbart ein Speichermedium, auf dem geografische Daten einer geografischen Region zusammen als Karteneinheiten gespeichert sind, ein entsprechendes Verfahren zum Erzeugen einer Karte aus den geografischen Daten und eine entsprechende Navigationsvorrichtung (
vgl. D5, Abs. [0001]). Die Karteneinheiten sind hierarchisch strukturiert, wobei Karteneinheiten einer n-ten Ordnung jeweils einer geografischen Teilregion entsprechen (
vgl. Abs. [0006], [0038] und Fig. 4). Weitere Hinweise zur Unterteilung in Teilregionen, insbesondere im Sinne der Merkmale 1.3 und 1.4.1, sind der D5 nicht zu entnehmen.

Die Druckschrift D6 offenbart ein Verfahren zur Ermittlung einer die Restreichweite eines Kraftfahrzeugs beschreibenden Teilfläche einer durch Merkmale beschriebenen Karte, wobei die Restreichweite in Abhängigkeit einer in dem Energiespeichersystem gespeicherten Energie durch einen von der aktuellen Position des Kraftfahrzeugs ausgehend expandierenden Algorithmus ermittelt wird, wobei eine in gleich große, insbesondere rechteckige geometrische Strukturen aufgeteilte Karte verwendet wird, wobei immer dann, wenn im Rahmen der Expansion ein in einer Struktur liegendes oder einer Struktur entsprechendes Merkmal hinzugefügt wird, die Struktur zu der Teilfläche hinzugefügt wird (
vgl. D6, Abstract, Abs. [0001], [0009]). Hinweise auf ein Unterteilen im Sinne der Merkmale 1.3 und 1.4.1 sind der D6 nicht zu entnehmen.

Die Druckschrift D7 offenbart ein Verfahren zum Bereitstellen von geografischen Daten für mobile Einheiten von Endbenutzern von einem entfernt gelegenen Navigationsdienstanbieter, so dass Navigationsfunktionen lokal auf den mobilen Einheiten bereitgestellt werden können (
vgl. D7, Abstract). Eine Karte einer geografischen Region wird mit einem Gitter überlagert. Das Gitter unterteilt den geografischen Bereich in mehrere Kartenkacheln. Die Linien des Gitters repräsentieren die Grenzen der Kartenkacheln. Die herunterladbaren geografischen Daten sind in Kartenkacheln gruppiert. Eine Gruppierung von Daten, die einer Kartenkachel entsprechen, enthält mehrere einzelne Datensätze, die die geografischen Merkmale wie Straßen, Kreuzungen, Sonderziele und andere Merkmale darstellen, die in dem Kartenkachelbereich enthalten sind (
Abs. [0025] – [0027]). Als Teil eines Routenberechnungsprozesses bestimmt der Navigationsdienstanbieter einen oder mehrere Ausstiegspunkte für Kartenkacheln entlang einer Route. Beispielsweise kann sich der Ausgangspunkt der Kartenkachel am Rand der Kartenkachel befinden, an dem die Route die Kartenkachel für eine andere Kartenkachel verlässt. Eine Routenberechnungsfunktion in der mobilen Einheit berechnet eine Route von der aktuellen Position der mobilen Einheit zum am weitesten entfernten Kartenkachelausgangspunkt, für den Kartenkacheldaten vom Navigationsdienstanbieter empfangen wurden (
vgl. Abs. [0042] – [0046]). Die Kartenkacheln, die zum Organisieren der geografischen Daten verwendet werden, können unterschiedliche Dimensionen haben (
vgl. Abs. [0059]). Damit unterscheidet sich das Verfahren des Anspruchs 1 von dem aus Druckschrift D7 insbesondere dadurch, dass gemäß den Merkmalen 1.3 und 1.4.1 ermittelt wird, ob mindestens ein Verkehrswegeschnittpunktpaar einer Kartenkachel nicht durch einen Verkehrsweg verbunden ist und eine Kartenkachel ausschließlich bei Bejahen dieser Bedingung die Kartenkachel unterteilt wird. Entsprechende Hinweise sind der D7 auch nicht zu entnehmen.

Das Verfahren zum Erstellen einer Datenstruktur des Anspruchs 1 ist daher neu gegenüber den Druckschriften D1 bis D8, und es wird dem Fachmann durch diesen Stand der Technik auch nicht nahegelegt, so dass es patentfähig ist.

7.2 Auch die in Anspruch 13 beanspruchte Datenstruktur ist patentfähig.

So weist diese Datenstruktur neben einem Strukturdatensatz mit Strukturidentifizierungsdaten, die eine geometrische Struktur identifizieren (Merkmale 13.3 und 13.3.1), nur einen oder mehrere Unterstrukturdatensätze für geometrische Strukturen mit mindestens zwei Verkehrswegschnittpunkten und mit mindestens einem Verkehrswegschnittpunktpaar, das nicht durch einen Verkehrsweg verbunden ist, auf (Merkmal 13.5). Wie bereits zum Verfahren zum Erstellen einer Datenstruktur des Anspruchs 1 ausgeführt, gibt es im ermittelten Stand der Technik insbesondere keinen Hinweis darauf, zum Erstellen einer Datenstruktur geometrische Strukturen mit mindestens einem Verkehrswegschnittpunktpaar ausschließlich in Unterstrukturen zu unterteilen, wenn mindestens ein Verkehrswegschnittpunktpaar nicht durch einen Verkehrsweg verbunden ist. Folglich ist dem ermittelten Stand der Technik auch kein Hinweis zu entnehmen, dass eine Datenstruktur ausschließlich einen oder mehrere Unterstrukturdatensätze für geometrische Strukturen mit mindestens zwei Verkehrswegschnittpunkten und mit mindestens einem Verkehrswegschnittpunktpaar, das nicht durch einen Verkehrsweg verbunden ist, im Sinne des Merkmals 13.5, umfasst.

Damit ist auch die Datenstruktur nach Anspruch 13 neu (§ 3 PatG) und beruht auf einer erfinderischen Tätigkeit (§ 4 PatG), so dass diese patentfähig ist (§ 1 Abs. 1 PatG).

7.3 Auch das in Anspruch 19 beanspruchte Verfahren zum iterativen Ermitteln eines oder mehrerer Pfade in einem in geometrische Strukturen unterteilten Verkehrswegenetz ist patentfähig, denn es weist u.a. auch die Datenstruktur gemäß Anspruch 13 auf, welche bereits die Patentfähigkeit begründet.

7.4 Für die Vorrichtung zum Erstellen einer Datenstruktur des Anspruchs 28 gelten die Ausführungen zum Anspruch 1 in gleicher Weise.

7.5 Für die Vorrichtung zum Ermitteln eines oder mehrerer Pfade in einem in geometrische Strukturen unterteilten Verkehrswegenetz des Anspruchs 30 gelten die Ausführungen zum Anspruch 19 in gleicher Weise.

8. An die selbständigen Patentansprüche 1, 13, 19, 28 und 30 können sich die Unteransprüche 2 bis 12, 14 bis 18, 20 bis 27, 29 und 31 anschließen, da sie vorteilhafte Weiterbildungen der beanspruchten Verfahren und Gegenstände angeben, welche nicht platt selbstverständlich sind.

9. In der geltenden Beschreibung ist der Stand der Technik, von dem die Erfindung ausgeht, angegeben und die Erfindung anhand der Zeichnung ausreichend erläutert.

10. Bei dieser Sachlage war der angefochtene Beschluss der Prüfungsstelle für Klasse G01C aufzuheben und das Patent wie beantragt zu erteilen.