I 1111 1011111 011111101011111 DIII DIII 1101 11111 11111 H 11111 11111 hID 1111 DII Ill
`
`US 20120095682A1
`
`(19) United States
`(12) Patent Application Publication
`Wilson
`
`(10) Pub. No.: US 2012/0095682 Al
`(43) Pub. Date:
`Apr. 19, 2012
`
`(54) METHODS AND SYSTEMS FOR CREATING
`DIGITAL STREET NETWORK DATABASE
`
`filed on Aug. 3, 2009, provisional application No.
`61/279,981, filed on Oct. 29, 2009.
`
`(76)
`
`Inventor:
`
`Christopher Kenneth Hoover
`Wilson, Emerald Hills, CA (US)
`
`(21) Appl. No.:
`
`13/378,717
`
`(22) PCT Filed:
`
`May 21, 2010
`
`(86) PCT No.:
`
`PCT1U510135694
`
`§ 371 (c)(l),
`(2),(4) Date:
`
`Dec. 16, 2011
`
`Related U.S. Application Data
`
`(60) Provisional application No. 61/187,494, filed on Jun.
`16, 2009, provisional application No. 61/273,185,
`
`Publication Classification
`
`(51)
`
`Int.Cl.
`GOJC 21/26
`
`(2006.01)
`
`(52) U.S. Cl. ........................................................
`
` 701/532
`
`(57)
`
`ABSTRACT
`
`In a method for creating a digital representation of a trans-
`portation network location measurement data is acquired, and
`a plurality of maneuvers between choke points are generated
`from the location measurement data. The digital representa-
`tion of the transportation network is then created and stored
`based on the plurality of maneuvers.
`
`Bradium Exhibit 2046
`Unified Patents Inc. v. Bradium Technologies LLC
`IPR2018-00952
`Page 1 of 27
`
`

`

`
`
`Patent Application Publication Apr. 19, 2012 Sheet 1 of 12
`
`US 2012/0095682 Al
`
`NA\.*iTJO]
`DEVICE
`Lo
`
`COMMUNICATION
`NETWORK 110
`
`WIRELESS
`154
`
`L-----------
`
`COMPUTING
`FACILITY
`158
`
`108
`
`GEOGRAPHIC DATABASE
`MANAGEMENT FACILITY 104
`
`COLLECTION
`FACILITY 138
`
`PROBE
`TRANSPORTATION
`SEGMENT
`GEOMETRY
`ANALYSIS FACILITY
`144
`
`GEOMETRY &
`ATTRIBUTE
`COMPARE 148
`
`ALTERATIONS
`150
`
`GEOGRAPHIC
`DATABASE
`152
`
`FIG. I
`
`Bradium Exhibit 2046
`Unified Patents Inc. v. Bradium Technologies LLC
`IPR2018-00952
`Page 2 of 27
`
`

`

`204
`
`208
`
`RVER
`
`Processorl ITransmitter
`
`2
`
`210
`
`Memory
`
`Receiver
`
`202
`
`212
`
`214
`
`Mass
`Data
`Storage
`
`Geographic
`Database
`Management
`Facility (104)
`
`Communication
`N etwork (11 O)
`
`H
`
`NAVIGATION DEVICE
`
`FIG. 2
`
`Bradium Exhibit 2046
`Unified Patents Inc. v. Bradium Technologies LLC
`IPR2018-00952
`Page 3 of 27
`
`

`

`200
`
`520
`
`226
`
`580
`
`Communication
`Network (110)
`
`GPS H
`
`550
`
`595
`1
`
`Input
`Device
`
`510
`
`525
`
`- -;A 4
`
`575 —J
`
`530 -\
`
`Antenna/
`Receiver
`
`I
`
`560
`
`I Output
`Device
`
`555 Processor
`
`535
`
`Memory
`
`
`
`5 65
`
`540
`
`545
`
`585
`
`599
`
`Display
`Device
`
`Probe
`Data
`Collection
`
`592
`
`FIG. 3
`
`Bradium Exhibit 2046
`Unified Patents Inc. v. Bradium Technologies LLC
`IPR2018-00952
`Page 4 of 27
`
`

`

`
`
`Patent Application Publication Apr. 19, 2012 Sheet 4 of 12
`
`US 2012/0095682 Al
`
`CD
`
`- ---1__
`
`IRT
`
`Bradium Exhibit 2046
`Unified Patents Inc. v. Bradium Technologies LLC
`IPR2018-00952
`Page 5 of 27
`
`

`

`Patent Application Publication Apr. 19, 2012 Sheet 5 of 12
`
`US 2012/0095682 Al
`
`Maneuver BC
`
`Maneuver AC
`
`FIG. 5
`
`Bradium Exhibit 2046
`Unified Patents Inc. v. Bradium Technologies LLC
`IPR2018-00952
`Page 6 of 27
`
`

`

`ACQUIRED
`PROBE
`TRACES
`
`3404
`
`FIG. 6
`
`
`2O4I510
`
`r
`I
`
`CHOKE POINT
`CREATION MODULE
`
`
`
`3204
`
`DIGITAL
`TRANSPORTATION
`NETWORK
`GENERATION
`MODULE
`
`312/530
`
`MASS
`DATA
`STORAGE
`
`MANEUVER
`GENERATION
`MODULE
`
`3104
`
`Bradium Exhibit 2046
`Unified Patents Inc. v. Bradium Technologies LLC
`IPR2018-00952
`Page 7 of 27
`
`

`

`Patent Application Publication Apr. 19, 2012 Sheet 7 of 12
`
`US 2012/0095682 Al
`
`ACQUIRE PROBE TRACES FORI r S601
`
`AN AREA OF INTEREST
`
`1
`
`REMOVE ii:iffIJ_
`PROBE TRACES
`
`S602
`
`8603
`
`REFINE PROBE TRACES
`
`CLUSTER PROBE TRACES
`THAT FOLLOW SAME
`PATH
`
`IDENTIFY DECISION POINTS WHERE PROBE TRACE
`CLUSTERS DIVERGE
`
`S605
`
`CREATE CHOKE POINTS Li- S606
`
`BETWEEN DECISION POINTS
`
`CREATE MANEUVERS FROM ADJACENT CHOKE POINTS
`FOLLOWING PATH OF MEAN PROBE TRACE ALONG
`MANEUVER PATH
`
`S607
`
`CONVERT MANEUVERS INTO DIGITAL
`TRANSPORTATION NETWORK
`
`STORE DIGITAL TRANSPORTATION
`NETWORK
`
`FIG. 7
`
`S608
`
`S610
`
`Bradium Exhibit 2046
`Unified Patents Inc. v. Bradium Technologies LLC
`IPR2018-00952
`Page 8 of 27
`
`

`

`Patent Application Publication Apr. 19, 2012 Sheet 8 of 12
`
`US 2012/0095682 Al
`
`600
`
`FIG. 8
`
`Bradium Exhibit 2046
`Unified Patents Inc. v. Bradium Technologies LLC
`IPR2018-00952
`Page 9 of 27
`
`

`

`Patent Application Publication Apr. 19, 2012 Sheet 9 of 12
`
`US 2012/0095682 Al
`
`Road Centreline
`(II
`
`10
`
`Edge of Road
`
`Probe Trace
`
`North Bound
`Traces
`
`Frequency
`of
`Trace
`
`Frequency
`
`Trace
`
`11
`
`All Traces
`
`Distance
`South
`"çun1'
`
`Distance
`
`Fig. 9
`
`Bradium Exhibit 2046
`Unified Patents Inc. v. Bradium Technologies LLC
`IPR2018-00952
`Page 10 of 27
`
`

`

`Patent Application Publication Apr. 19, 2012 Sheet 10 of 12
`
`US 2012/0095682 Al
`
`0
`
`LL
`
`Bradium Exhibit 2046
`Unified Patents Inc. v. Bradium Technologies LLC
`IPR2018-00952
`Page 11 of 27
`
`

`

`MANEUVER
`
`It
`
`I
`
`SION
`KE
`
`'ER
`)INT)
`
`CA
`
`Bradium Exhibit 2046
`Unified Patents Inc. v. Bradium Technologies LLC
`IPR2018-00952
`Page 12 of 27
`
`

`

`Patent Application Publication Apr. 19, 2012 Sheet 12 of 12
`
`US 2012/0095682 Al
`
`Straight
`Lane/
`
`
`Exit Ramp
`
`No of
`Trees
`
` —f
`
`Perpendicular
`Distance
`
`Fig. 12
`
`Bradium Exhibit 2046
`Unified Patents Inc. v. Bradium Technologies LLC
`IPR2018-00952
`Page 13 of 27
`
`

`

`US 2012/0095682 Al
`
`Apr. 19, 2012
`
`METHODS AND SYSTEMS FOR CREATING
`DIGITAL STREET NETWORK DATABASE
`
`CROSS-REFERENCE TO RELATED
`APPLICATION(S)
`
`[0001] This application claims priority under 35 U.S.C.
`§119(e) to U.S. provisional application Nos. 61/187,494,
`filed on Jun. 16,2009; 61/273,185, filed onAug. 3,2009; and
`61/279,981, filed on Oct. 26, 2009. The entire contents of
`each of these provisional applications is incorporated herein
`by reference.
`
`FIELD
`
`[0002] The present application generally relates to naviga-
`tion methods and devices. More specifically, at least some
`example embodiments relate to methods and systems for
`creating and storing digital representations of transportation
`networks.
`
`BACKGROUND
`
`[0003] A transportation network is any navigable system of
`roads, pedestrian walkways, paths, rivers, shipping lanes or
`other network that is utilized to transport humans or vehicles.
`A transportation network can also include combinations of
`routes for the above modes of transportation. These combi-
`nations of routes are referred to as multimodal transportation
`networks. A segment of a transportation network (referred to
`as a transportation network segment) is a portion of the trans-
`portation network that represents a path of travel for a vehicle
`or pedestrian without a method of entry or exit other than at its
`end points.
`[0004] One method of creating or updating a digital trans-
`portation network is by traversing paths/elements ofthe trans-
`portation network with highly specialized location measuring
`and recording systems designed for this purpose. In alterna-
`tive methods, transportation network information is gleaned
`from aerial images or compiled from existing localized digi-
`tal transportation networks. In addition, combinations of the
`above methods can be utilized.
`[0005] More recently, probe traces acquired from location
`sensors carried in a series of uncoordinated vehicles or by
`numerous pedestrians has been used for creating/updating
`and/or refining a transportation network. Probe traces are a
`plurality of sequential location measurements from location
`sensors. Location sensors are usually part of a navigation
`system or housed in a multi-purpose device such as a smart-
`phone.
`[0006] Utilization of uncoordinated probe traces has gen-
`erally been limited to updating an existing transportation
`network because the approximate location of transportation
`segments must be known in order to determine if a given
`probe trace traverses a particular segment. Thus, probe traces
`are typically used only to refine and improve accuracy. Con-
`ventionally, digital transportation networks are not generated
`or built (e.g., created from scratch) based on uncoordinated
`probe traces. In addition, the conventional art does not
`address the junction of transportation network segments in an
`automated fashion.
`[0007] Moreover, location measurements from a single
`location sensor are typically not sufficiently accurate to gen-
`erate a digital transportation network for certain applications
`such as an Advance Driver Assistance System (ADAS). For
`example, positional accuracy for a road network in anADAS
`
`should be less than about 5 meters. But, typical location
`measurements from conventional location sensors are on the
`order of about +/—lo to 15 meters.
`
`SUMMARY
`
`[0008] Example embodiments relate to methods for creat-
`ing digital representations of transportation networks. At
`least some other example embodiments relate to methods for
`storing digital transportation networks.
`[0009] Transportation network databases according to
`example embodiments maybe used in routing and navigation
`applications requiring relatively high accuracy and/or preci-
`sion such as Advanced Driver Assistance Systems (ADASs).
`100101 Methods described herein are also suitable for
`building and/or creating a digital transportation network
`based on a series of sequential location measurement data or
`series of probe traces acquired by on-board navigation
`devices (NDs), personal navigation devices (PNDs) or other
`location sensors capable of: collecting sequential location
`measurement data, storing the sequential location measure-
`ment data and transmitting the sequential location measure-
`ment data to a central storage or processing unit for process-
`ing. Combinations of sequential location measurement data
`(or probe traces) from sources of varying accuracy can also be
`combined with traces derived from aerial imagery.
`100111 Methods described herein are also suitable for
`building and/or creating a digital transportation network
`based on a series of sequential location measurement data or
`series of probe traces acquired by on-board navigation
`devices (NDs), personal navigation devices (PNDs) or other
`location sensors capable of: collecting sequential location
`measurement data, storing the sequential location measure-
`ment data and transmitting the sequential location measure-
`ment data from one navigation device to one or more other
`navigation devices via in-vehicle communications, without a
`central storage or processing unit. In this example, each navi-
`gation device may build and/or create at least a portion of its
`own digital transportation network on-the-fly based on infor-
`mation received from one or more other navigation devices.
`100121 At least some example embodiments provide meth-
`ods for determining which intersecting road segments are
`connected in terms of traffic flow. The location and informa-
`tion regarding, or associated with, connections between road
`segments enables a transportation network suitable for
`vehicle routing.
`[0013] Although example embodiments described herein
`refer to roadways and transportation networks utilized by
`automobiles, the methods described herein are also pertinent
`to other types of transportation networks such as pedestrian or
`bicycle networks, railroads, shipping lanes, etc. In addition,
`the combinations of the above modes of transportation may
`also be utilized in a multimodal navigation network. Like-
`wise, as there are location sensors capable of functioning
`within buildings, the transportation networks may also be
`located indoors.
`100141 Although example embodiments will be described
`with regard to sequential location measurements or sequen-
`tial location measurement data, example embodiments may
`be based on random location measurement data. Moreover,
`example embodiments may also be based on a combination of
`sequential location measurement data and random location
`measurement data.
`
`Bradium Exhibit 2046
`Unified Patents Inc. v. Bradium Technologies LLC
`IPR2018-00952
`Page 14 of 27
`
`

`

`US 2012/0095682 Al
`
`Apr. 19, 2012
`
`2
`
`[0015] At least some example embodiments described
`herein do not require a 'seed" or basic representation of the
`transportation network being created to generate the trans-
`portation network geometry.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`[00161 Various aspects of the teachings of the present dis-
`closure, and arrangements embodying those teachings, will
`hereafter be described by way of illustrative example with
`reference to the accompanying drawings, in which:
`[0017] FIG. 1 is a block diagram detailing various compo-
`nent parts of a map database system according to an example
`embodiment;
`[0018] FIG. 2 is a schematic illustration of the manner in
`which a navigation device may receive or transmit informa-
`tion over a wireless communication channel;
`10019] FIG. 3 is a schematic illustration of a navigation
`device according to an example embodiment;
`10020] FIG. 4 is a schematic illustration of a Global Posi-
`tioning System (GPS);
`[0021] FIG. 5 shows two example maneuvers AC and BC
`that traverse an intersection;
`10022] FIG. 6 illustrates an example embodiment of a pro-
`cessor 204/510 shown in more detail;
`[0023] FIG. 7 shows a flowchart for illustrating an example
`embodiment of a method for creating and storing a digital
`transportation network;
`[0024] FIG. 8 illustrates example probe traces along a
`transportation network segment and corresponding cross-
`sectional graphs;
`[0025] FIG. 9 shows example probe traces along a two-lane
`road;
`[0026] FIG. 10 shows expected data from a 'going straight'
`and 'off-ramp' maneuver;
`[0027] FIG. 11 is a simplified diagram showing an example
`transportation network segment including a maneuver
`according to an example embodiment.
`100281 FIG. 12 shows an example distribution change from
`a single normal distribution prior to an off-ramp to a more
`bimodal distribution.
`
`DETAILED DESCRIPTION OF EXAMPLE
`EMBODIMENTS
`
`[0029] Various example embodiments will now be
`described more fully with reference to the accompanying
`drawings in which some example embodiments are illus-
`trated.
`[0030] Accordingly, while example embodiments are
`capable of various modifications and alternative forms,
`embodiments thereof are shown by way of example in the
`drawings and will herein be described in detail. It should be
`understood, however, that there is no intent to limit example
`embodiments to the particular forms disclosed, but on the
`contrary, example embodiments are to cover all modifica-
`tions, equivalents, and alternatives falling within the scope of
`example embodiments. Like numbers refer to like elements
`throughout the description of the figures.
`[0031]
`It will be understood that, although the terms first,
`second, etc. may be used herein to describe various elements,
`these elements should not be limited by these terms. These
`terms are only used to distinguish one element from another.
`For example, a first element could be termed a second ele-
`ment, and, similarly, a second element could be termed a first
`
`element, without departing from the scope of example
`embodiments. As used herein, the term "and/or" includes any
`and all combinations of one or more of the associated listed
`items.
`It will be understood that when an element is
`100321
`referred to as being "connected" or "coupled" to another
`element, it can be directly connected or coupled to the other
`element or intervening elements may be present. In contrast,
`when an element is referred to as being "directly connected"
`or "directly coupled" to another element, there are no inter-
`vening elements present. Other words used to describe the
`relationship between elements should be interpreted in a like
`fashion (e.g., "between" versus "directly between," "adja-
`cent" versus "directly adjacent," etc.).
`100331 The terminology used herein is for the purpose of
`describing particular embodiments only and is not intended to
`be limiting of example embodiments. As used herein, the
`singular forms "a," "an" and "the" are intended to include the
`plural forms as well, unless the context clearly indicates oth-
`erwise. It will he further understood that the terms "com-
`prises," "comprising," "includes" and/or "including," when
`used herein, specify the presence of stated features, integers,
`steps, operations, elements and/or components, but do not
`preclude the presence or addition of one or more other fea-
`tures, integers, steps, operations, elements, components and/
`or groups thereof.
`100341 Spatially relative terms such as "beneath," "below,"
`"lower," "above," "upper" and the like, may be used herein for
`ease of description to describe one element or a relationship
`between a feature and another element or feature as illustrated
`in the figures. It will be understood that the spatially relative
`terms are intended to encompass different orientations of the
`device in use or operation in addition to the orientation
`depicted in the figures. For example, if the device in the
`figures is turned over, elements described as "below" or
`"beneath" other elements or features would then be oriented
`"above" the other elements or features. Thus, for example, the
`term "below" can encompass both an orientation which is
`above as well as below. The device may be otherwise oriented
`(rotated 90 degrees or viewed or referenced at other orienta-
`tions) and the spatially relative descriptors used herein should
`be interpreted accordingly.
`100351
`It should also be noted that in some alternative
`implementations, the functions/acts noted may occur out of
`the order noted in the figures. For example, two figures shown
`in succession may in fact be executed substantially concur-
`rently or may sometimes be executed in the reverse order,
`depending upon the functionality/acts involved.
`(0036] Unless otherwise defined, all terms (including tech-
`nical and scientific terms) used herein have the same meaning
`as commonly understood by one of ordinary skill in the art to
`which example embodiments belong. It will be further under-
`stood that terms, for example, those defined in commonly
`used dictionaries, should be interpreted as having a meaning
`that is consistent with their meaning in the context of the
`relevant art and will not be interpreted in an idealized or
`overly formal sense unless expressly so defined herein.
`[0037] Portions of example embodiments and correspond-
`ing detailed description are presented in terms of software, or
`algorithms and symbolic representations of operation(s) on
`data bits within a computer memory. These descriptions and
`representations are the ones by which those of ordinary skill
`in the art effectively convey the substance of their work to
`others of ordinary skill in the art. An algorithm, as the term is
`
`Bradium Exhibit 2046
`Unified Patents Inc. v. Bradium Technologies LLC
`IPR2018-00952
`Page 15 of 27
`
`

`

`
`
`US 2012/0095682 Al
`
`Apr. 19, 2012
`
`used here, and as it is used generally: is conceived to be a
`self-consistent sequence of steps leading to a desired result.
`The steps are those requiring physical manipulations of
`physical quantities. Usually, though not necessarily, these
`quantities take the form of optical, electrical, or magnetic
`signals capable of being stored, transferred, combined, com-
`pared, and otherwise manipulated. It is convenient at times,
`principally for reasons of common usage, to refer to these
`signals as bits, values, elements, symbols, characters, terms,
`numbers, or the like.
`In the following description, illustrative embodi-
`100381
`ments will be described with reference to acts and symbolic
`representations of operations (e.g., in the form of flowcharts)
`that may be implemented as program modules or functional
`processes include routines, programs, objects, components,
`data structures, that perform particular tasks or implement
`particular abstract data types and may be implemented using
`existing hardware at existing network elements or control
`nodes (e.g., a database). Such existing hardware may include
`one or more Central Processing Units (CPUs), digital signal
`processors (DSPs), application-specific-integrated-circuits,
`field programmable gate arrays (FPGAs) computers or the
`like.
`It should be borne in mind, however, that all of these
`[0039]
`and similar terms are to be associated with the appropriate
`physical quantities and are merely convenient labels applied
`to these quantities. Unless specifically stated otherwise, or as
`is apparent from the discussion, terms such as "processing,"
`"computing," "calculating," "determining," "displaying" or
`the like, refer to the action and processes of a computer
`system, or similar electronic computing device, that manipu-
`lates and transforms data represented as physical, electronic
`quantities within the computer system's registers and memo-
`ries into other data similarly represented as physical quanti-
`ties within the computer system memories or registers or
`other such information storage, transmission or display
`devices.
`[0040] Note also that the software implemented aspects of
`example embodiments are typically encoded on some form of
`computer readable medium or implemented over some type
`of transmission medium. The computer readable medium
`maybe magnetic (e.g., a floppy disk or a hard drive) or optical
`(e.g., a compact disk read only memory, or "CD ROM"), and
`may be read only or random access. Similarly, the transmis-
`sion medium may be twisted wire pairs, coaxial cable, optical
`fiber, or some other suitable transmission medium known to
`the art. Example embodiments are not limited by these
`aspects of any given implementation.
`In at least some cases, example embodiments of the
`100411
`present disclosure are described with particular reference to a
`geographic database. It should be remembered, however, that
`the teachings of the present disclosure are not limited to any
`particular form of database but are instead universally appli-
`cable to any type of database and/or any processing device
`that is configured to execute a program to access data in a data
`structure, the data being associated with mapping data, but
`not exclusively mapping data. It follows therefore that in the
`context of the present application, a geographic database is
`intended to include any database accessible to a server, com-
`puter or computing device configured for accessing data,
`generating new maps and/or updating maps based on the
`accessed data.
`[0042] Example embodiments of the present disclosure
`may be described with particular reference to a navigation
`
`device (ND) or personal navigation device (PND). It should
`be remembered, however, that the teachings of the present
`disclosure are not limited to NDs or PNDs, but are instead
`universally applicable to any type of processing device that is
`configured to execute navigation software so as to provide
`route planning and navigation functionality. It follows, there-
`fore, that in the context of the present application, a naviga-
`tion device is intended to include (without limitation) any
`type of route planning and navigation device, irrespective of
`whether that device is embodied as a PND, a navigation
`device built into a vehicle, or a computing resource (such as a
`desktop or portable personal computer (PC), mobile tele-
`phone or portable digital assistant (PDA)) executing route
`planning and navigation software. In addition to street/road
`networks, example embodiments may be implemented in
`pedestrian navigation networks and/or any other type of
`transportation network (e.g., a metro train) or combinations
`of transportation networks (referred to as multimodal trans-
`portation networks).
`[0043] Segments in these transportation networks (e.g., a
`portion of a road and/or sidewalk) are often referred to as
`navigable features. Boundaries of these segments (e.g., cen-
`terlines, shoulder lines, stop signs, etc.) may be referred to as
`geometric features. Navigable and geometric features are not
`limited in any way to the aforementioned examples.
`[00441 While example embodiments described herein uti-
`lize GPS measurements (probe trace points) including lati-
`tude and longitude coordinates as location measurements, it
`should be understood that location measurements may be
`obtained from any source and are not limited to GPS. For
`example, other Global Navigation Satellite Systems (GNSSs)
`such as GLONAS, Galileo, Compas, etc. or non-GNSS sys-
`tems (e.g., inertial indoor systems may be used.
`10045] Further, while location measurements described
`herein operate in two spatial dimensions, the discussed
`example embodiments may be implemented in three or more
`dimensions.
`It will be apparent from the following description
`100461
`that the teachings of the present disclosure have utility in
`circumstances where a user is not seeking instructions on how
`to navigate from one point to another, but merely wishes to be
`provided with a view of a given location.
`100471 A transportation network canbe modeled and stored
`as a digital representation in a digital map database. In so
`doing, the transportation network is usually represented by
`geometry and associated attribution. In the context of a trans-
`portation network, attribution limits how travel can flow on
`the network and can be referred to as travel restrictions. For
`example, attribution may include: speed of travel, whether or
`not a turn at an intersection is allowed, etc.
`100481 Geometry can be stored in the digital map database
`as a series of polylines connected at nodes. Polylines are a
`series of sequential coordinates that usually represent the
`centerline of a transportation segment. Nodes are points
`where two or more polylines connect, and generally occur at
`intersections where there is a decision point with respect to
`travel from one transportation network segment to another.
`Nodes can also occur at intersections with other map features
`such as a political boundary, geographic feature (e.g., a river),
`etc.
`100491 Alternatively, geometry can be stored as maneuvers
`in the digital map database by fitting a polyline to a path taken
`by a group of vehicles (a population) all traveling from one
`point to another. Examples of maneuvers through an intersec-
`
`Bradium Exhibit 2046
`Unified Patents Inc. v. Bradium Technologies LLC
`IPR2018-00952
`Page 16 of 27
`
`

`

`US 2012/0095682 Al
`
`Apr. 19, 2012
`
`tion are: a left turn, traveling straight through, or a right turn.
`If legal, a u-turn is also a possible maneuver. In this case,
`nodes do not coincide with intersections. Rather, nodes are
`placed at non-decision points (or choke points) where all
`traffic must travel in the same direction and there is no option
`to turn off a given path. In this example, geometry describes
`a maneuver or maneuvers, which defines the path taken
`between two non-decision points, and the nodes represent
`locations where one can transition between maneuvers.
`100501 Yet another method to store transportation network
`geometry, rather than as polylines, is a series of mathematical
`curves. A curve would replace a polyline in either the con-
`ventional or maneuver based storage. Examples of curves are
`a polynomial and clothoid.
`100511 Avast majority of geographical information system
`(GIS) digital maps represent linear features (e.g., streets,
`water, political, land use, recreational boundaries, etc.) as
`chained polyline segments connected by mutual endpoints,
`which are often referred to as shape points. These points
`represent a point in 21) or 3D space deemed to be along the
`path of the line of travel, service, or boundary. These shape
`points are usually inflections or bends along a single path,
`such that when two line edges meet at any shape point they are
`generally not co-linear. The clear intention of such lines is to
`represent the real-world feature to a reasonably good approxi-
`mation in a reasonably simple and compact form. Travel
`along the actual real-world path or boundary can be approxi-
`mately represented by traversing each successive line seg-
`ment.
`100521 The above-described polyline format is a simplified
`model of real-world paths; its primary strength is its simplic-
`ity. This format is relatively easy to draw on a raster screen,
`and readily allows computations for length, distance, and
`other geometric queries. However, representation by
`polylines is plagued with representation error because actual
`linear features are much more complex and composed of
`non-line segment components. Any attempt to reduce this
`representation error requires an increase in the density of the
`data; no finite amount of data stored in a line segment format
`can perfectly represent a non-line segment shape.
`[0053] A clothoid is a two-dimensional shape or path
`defined to have constant change in curvature over the travel
`distance. In one example, a clothoid resembles a clock spring,
`with zero curvature at one end, and then coiling ever tighter at
`the other end. Arcs and line segments are simply special cases
`of the clothoid. A circular arc is a clothoid because the circular
`arc has a constant curvature—that is, zero curvature change—
`wherein the curvature magnitude is inversely related to that
`circle's radius. A straight line is also a clothoid, having both a
`no-curvature change and a constant curvature of zero over its
`entire length.
`100541 Clothoids and their special cases (e.g., circular arcs
`and straight lines) are used in much real-world construction.
`Roads, in particular, are often constructed from pieced seg-
`ments including straight lines, circular arcs, and clothoids.
`Roadbed designers recognize that roadway curvature directly
`relates to movement of steering wheels and axle components
`of vehicles traversing the roadway. For them, limiting any
`abrupt changes in curvature by choosing clothoid design
`where feasible represents a decision that improves and/or
`maximizes vehicular safety and comfort, while reducing and/
`or minimizing wear on roadway components.
`[0055] The concept of splines is available in mathematics.
`Though originally referring to a thin flexible rod used to draw
`
`curves, the term is mathematically understood as a function fit
`in which the fitting function has some number of continuous
`derivatives. Taking the above-discussed example, one can see
`that in order to reduce and/or minimize disruptive changes in
`steering, a vehicular path should be a spline with respect to
`heading change over distance traveled, with the first deriva-
`tive of heading change per unit distance (e.g., curvature)
`being a continuous function. This type of function is referred
`to herein as the "clothoid spline."
`100561
`In a database, the geometry of a multiple-lane two-
`way traffic roadway may be represented as a single polyline
`(or mathematical curve) that traverses the centerline of the
`roadway. However, for Advanced Driver Assistance System
`(ADAS) applications, it may be necessary to store an indi-
`vidual centerline for each lane and/or for each direction of
`traffic. [his is especially true if the database is stored as
`maneuvers because it may not be possible to exit a right side
`off-ramp on an interstate highway from a left side lane. There-
`fore, a separate maneuver including the right bound lane
`turning into an off-ramp would need to be stored. An addi-
`tional maneuver would follow a left bound lane until such
`time as it intersects another freeway. For a transportation
`network including multiple lane roadways, storage of geom-
`etry and attribution in the transportation network will vary
`depending on the level of sophistication of the application
`utilizing the data and the accuracy at which the geometry
`information can be measured.
`100571 Example embodiments discussed herein utilize a
`'maneuver' as a fundamental unit to create a digital represen-
`tation of a transportation network.
`100581 At least some example embodiments create and
`store the resulting digital network as connected polylines
`with segment endpoints at intersections.
`100591 At least some example embodiments create and
`store the resulting digital network as polyline representations
`of maneuvers with endpoints at choke points.
`100601 At least some example embodiments create and
`store the digital network as a series of mathematical curve
`representations of maneuvers connected at choke points.
`100611 According to at least one example embodiment, a
`'maneuver' refers to the average path of numerous vehicles
`that travel along the same or substantially the same route or
`path between