Login| Sign Up| Help| Contact|

Patent Searching and Data


Title:
GENERATING INTERSECTION DATA
Document Type and Number:
WIPO Patent Application WO/2013/160471
Kind Code:
A2
Abstract:
A method of generating data in relation to one or more intersections in a geographic area involves obtaining positional data relating to the movement of a plurality of devices with respect to time in the area. For one or more particular manoeuvres at the or each said intersection, the method comprises filtering the positional data to obtain positional data relating to the movement of devices performing the particular manoeuvre at the intersection, and analysing the positional data to obtain a free flow time indicative of the time taken to perform the given manoeuvre under free flow traffic conditions, and a set of one or more time delays for the given manoeuvre. The or each time delay is in respect of a given time period, wherein the or each time delay is indicative of the time delay incurred when performing the manoeuvre in the respective time period with respect to the free flow time. The method further comprises storing data indicative of the or each time delay in association with data indicative of the manoeuvre, the intersection and the time period to which it relates.

Inventors:
MEIJER ARNOLD MARK (NL)
KROOTJES PETER (NL)
COHN NICHOLAS DAVID (NL)
Application Number:
PCT/EP2013/058805
Publication Date:
October 31, 2013
Filing Date:
April 26, 2013
Export Citation:
Click for automatic bibliography generation   Help
Assignee:
TOMTOM INT BV (NL)
International Classes:
G08G1/01; G01C21/34
Foreign References:
EP2136345A12009-12-23
JP2007248183A2007-09-27
Attorney, Agent or Firm:
DOBSON, Adrian (De Ruyterkade 154, AC Amsterdam, NL)
Download PDF:
Claims:
CLAIMS:

1 . A method of generating data in relation to one or more intersections in a geographic area, the method comprising:

obtaining positional data relating to the movement of a plurality of devices with respect to time in the area; and,

for one or more particular manoeuvres at the or each said intersection, filtering the positional data to obtain positional data relating to the movement of devices performing the particular manoeuvre at the intersection, and analysing the filtered positional data to obtain:

a free flow time indicative of the time taken to perform the particular manoeuvre under free flow traffic conditions; and

a set of one or more time delays for the particular manoeuvre, the or each time delay being in respect of a given time period, wherein the or each time delay is indicative of the time delay incurred when performing the manoeuvre in the respective time period with respect to the free flow time; the method further comprising:

storing data indicative of the or each time delay in association with data indicative of the manoeuvre, the intersection and the time period to which it relates.

2. The method of claim 1 wherein the manoeuvre includes a turning movement.

3. The method of claim 1 or 2 wherein the step of obtaining the free flow time for the manoeuvre comprises analysing positional data relating to the movement of devices that performed the manoeuvre within a given predetermined time period. 4. The method of claim 3 wherein the step of obtaining the free flow time comprises obtaining data indicative of the times taken by the devices to perform the manoeuvre from said positional data relating to the movement of devices that performed the manoeuvre within a given predetermined time period, and using the time data to obtain the free flow time, optionally wherein the free flow time is obtained by averaging the times taken by different devices to perform the manoeuvre in the given time period.

5. The method of claim 4 wherein the data indicative of the times is indicative of a distribution profile of the times taken by the different devices to perform the manoeuvre in the given predetermined time period.

6. The method of claim 5 wherein the free flow time is a percentile time obtained from said data indicative of the distribution profile of the times.

7. The method of claim 4 or 5 wherein the free flow time is obtained using the time data and a reference free flow time, the reference free flow time being used to select that time data which may be considered to relate to manoeuvres under free flow conditions. 8. The method of any of claims 2 to 7 wherein the step of obtaining the or each time delay for the manoeuvre comprises analysing positional data relating to the movement of devices that performed the manoeuvre within a respective given predetermined time period that is shorter than the given predetermined time period used in determining the free flow time. 9. The method of any preceding claim wherein the step of obtaining the time delay for a given time period comprises obtaining data indicative of a distribution profile of the times taken by different devices to perform the manoeuvre in the respective time period, and using the time distribution profile data to obtain the time delay. 10. The method of any preceding claim wherein the step of obtaining the time delay for a given time period comprises obtaining data indicative of an average time taken by different devices to perform the manoeuvre in the respective time period, wherein the time delay is representative of the difference between the determined average time and the free flow time obtained. 1 1 . The method of any preceding claim wherein the set of time delays obtained comprises a plurality of time delays in respect of different time periods.

12. A data product storing electronic map data indicative of the locations of one or more intersections in an area, the product further comprising data associated with the location data for the or each intersection being indicative of a particular manoeuvre which may be performed at the intersection, and data indicative of a time delay for performing the manoeuvre in a given respective time period with respect to a free flow time for performing the manoeuvre, wherein the time delay is obtained in accordance with the method of any one of the preceding claims. 13. A computer readable medium comprising the data product of claim 12.

14. A system, optionally a server, arranged to process data relating to an electronic map covering an area including one or more intersections, the system being arranged to generate data in relation to the one or more intersections by:

obtaining positional data relating to the movement of a plurality of devices with respect to time in the area; and, for one or more particular manoeuvres at the or each said intersection, filtering the positional data to obtain positional data relating to the movement of devices performing the particular manoeuvre at the intersection, and analysing the filtered positional data to obtain:

a free flow time indicative of the time taken to perform the particular manoeuvre under free flow traffic conditions; and

a set of one or more time delays for the particular manoeuvre, the or each time delay being in respect of a given time period, wherein the or each time delay is indicative of the time delay incurred when performing the manoeuvre in the respective time period with respect to the free flow time; and storing data indicative of the or each time delay in association with data indicative of the manoeuvre, the intersection and the time period to which it relates.

15. A computer program product comprising computer readable instructions executable to perform a method according to any of claims 1 to 11 .

Description:
GENERATING INTERSECTION DATA

Field of the Invention

The invention relates to a method of generating data in relation to one or more intersections in the area covered by an electronic map as well as a data product storing such data, and system, a server and a navigation device on which part or all of the method may be implemented. In particular, but not exclusively, the invention relates to determining a time delay incurred when performing a particular manoeuvre at an intersection in a given time period.

Background of the Invention

Map data for electronic navigation devices, such as GPS-based personal navigation devices, comes from specialist map vendors. Such devices are also referred to as Portable Navigation Devices (PND's). This map data is specially designed to be used by route guidance algorithms, typically using location data from the GPS system. For example, roads can be described as lines, i.e. vectors (e.g. start point, end point, direction for a road, with an entire road being made up of many hundreds of such segments, each uniquely defined by start point/end point direction parameters). A map is then a set of such road vectors, data associated with each vector (speed limit, travel direction, etc), plus points of interest (POIs), plus road names, plus other geographic features like park boundaries, river boundaries, etc, all of which are defined in terms of vectors. All map features (e.g. road vectors, POIs, etc.) are typically defined in a co-ordinate system that corresponds with or relates to the GPS co-ordinate system, enabling a device's position as determined through a GPS system to be located onto the relevant road shown in a map and for an optimal route to be planned to a destination.

Typically, each such road segment has associated therewith speed data for that road segment which gives an indication of the speed at which a vehicle can travel along that segment and is an average speed generated by the party that produced the map data. The speed data is used by route planning algorithms on PND's on which the map is processed. The accuracy of such route planning thus depends on the accuracy of the speed data. For example, a user is often presented with an option on his/her PND to have it generate the fastest route between the current location of the device and a destination. The route calculated by the PND may well not be the fastest route if the speed data is inaccurate.

It is known that parameters such as density of traffic can significantly effect the speed profile of a segment of road and such speed profile variations mean that the quickest route between two points may not remain the same. Inaccuracies in the speed parameter of a road segment can also lead to inaccurate Estimated Times of Arrival (ETA) as well as selection of a sub-optimal quickest route.

The map data also contains a time allowance for performing particular manoeuvres at intersections between road segments. These time allowances or "time delays" may be expressed as a "cost", being a property of the given manoeuvre. For example, a time delay may be relatively high for a manoeuvre which involves a vehicle having to enter, or cross, a heavy-traffic road, that has right-of-way. The time delay may be relatively low for a manoeuvre which involves taking a straight path across the intersection. The time delays (or "transit times") can be used to allow more accurate routes to be planned by devices using the map data.

Of course, knowledge of time delays at intersections is also of interest in other, non-route planning applications. For example, knowledge of delay at intersections association with given manoeuvres is useful when planning infrastructure, ensuring efficient intersection control, etc, and may be used in the context of optimizing road geometry, intersection control and dynamic traffic management.

While embodiments of the present invention are described with reference to road segments. It should be realised that the invention may also be applicable to other navigable segments, such as segments of a path, river, canal, cycle path, tow path, railway line, or the like. For ease of reference these are commonly referred to as a road segment, but the broader term "navigable segment" may replace the term "road segment" where used.

Conventionally time delay data was obtained from fixed road-side sensors or loop detection systems. However, the use of such systems is inflexible, as data can only be obtained where appropriate sensing infrastructure is present, and considerable expense can be involved in maintaining such systems. Such systems are not well suited to providing detailed manoeuvre level time delay data at intersections.

Another technique used to obtain time delay data uses positional data relating to the movement of a plurality of devices with respect to time when passing through the intersection. Such data may be known as "probe data", and may be obtained from mobile devices such as PNDs with positioning, e.g. GPS, capability which have travelled through the intersection. Techniques using so-called "probe data" are described in WO 2010/063508, entitled "Method of Creating Map Data Comprising Transit Times for Intersections".

The Applicant has realised, however, that there remains a need for improved methods of obtaining time delay information relating to particular manoeuvres performed at an intersection using such positional data.

Summary of the Invention

In accordance with a first aspect of the invention there is provided a (computer implemented) method of generating data in relation to one or more intersections in a geographic area, the method comprising: obtaining positional data relating to the movement of a plurality of devices with respect to time in the area; and,

for one or more particular manoeuvres at the or each said intersection, filtering the positional data to obtain positional data relating to the movement of devices performing the particular manoeuvre at the intersection ;

the method further comprising:

using the filtered positional data to obtain: a free flow time indicative of the time taken to perform the particular manoeuvre under free flow traffic conditions; and a set of one or more time delays for the particular manoeuvre, wherein the or each time delay is indicative of the time delay incurred when performing the manoeuvre in a given respective time period and is with respect to the free flow time; and

storing data indicative of the or each time delay in association with data indicative of the manoeuvre, the intersection and the time period to which it relates.

In accordance with the invention, therefore, positional data obtained from devices performing a manoeuvre at an intersection is used to obtain a free flow time for performing the manoeuvre under "free flow" traffic conditions, and additionally, a set of one or more time delays for performing the manoeuvre in respect of one or more (different) given time periods. In other words, the probe or positional data is used to determine the free flow time and the time delay for the manoeuvre. The time delays are in respect of, e.g. relative to, the free flow time. It has been found that by determining a time delay by reference to a free flow time for a manoeuvre, where both the free flow time and time delay are determined using positional data i.e. probe data, as set out herein, then accurate and useful time delay data may be obtained for use, e.g. in infrastructure and route planning or other applications, without the constraints involved in prior art techniques using fixed sensors or loops. The use of the positional data provides a cost effective and flexible technique, which allows time delay data and free flow data to be obtained readily, using existing databases of probe data, by analysing the data appropriately to obtain the data relating to the time periods and manoeuvres of interest. Time delay information may be obtained for any intersection/manoeuvre for which positional data is available.

It will be appreciated that the time delay(s) and free flow time may be determined in accordance with the invention in relation to one, or preferably a plurality of manoeuvres at the or each intersection which is considered. A set of time delay(s) and a free flow time may be determined for each possible manoeuvre at the or each intersection.

In accordance with the invention, the method involves obtaining the positional data relating to movement of the plurality of devices in a geographic region containing the intersection or intersections.

The positional data may be historical positional data that is not necessarily received specifically for the purposes of the present invention. For example, the data may be data obtained from an existing database of such "probe" data, from which the relevant data may be filtered out. The step of obtaining the positional data may or may not comprise receiving the data from the devices. In some arrangements the step of obtaining the data may comprise accessing the data, i.e. retrieving data that had previously been received and stored. In arrangements in which the method involves receiving the data from the devices, it is envisaged that the method may further comprise storing the received positional data before proceeding to filtering the data and carrying out the other steps of the present invention. The step of obtaining the positional data need not take place at the same time or place as the other step or steps of the method.

In embodiments the positional data is in the form of a plurality of positional or probe traces, each representing the position of a device at different times. In embodiments the positional data is received at a central controller, such as a server. For example, the central controller may be a controller of a navigation system associated with a plurality of devices, e.g. navigation devices, used to provide positional data.

The positional data relates to the movement of the devices with respect to time, and may be used to provide a positional "trace" of the path taken by the device. As mentioned above, the data may be received from the devices or may first be stored. The devices may be any mobile devices that are capable of providing the positional data and sufficient associated timing data for the purposes of the present invention. The device may be any device having position determining capability. Typically the device may comprise a GPS or GSM device. Such devices may include navigation devices, mobile telecommunications devices with positioning capability, position sensors, etc. The device may be associated with a vehicle. In these embodiments the position of the device will correspond to the position of the vehicle. The vehicle may be a powered or non-powered vehicle, such as an automobile, train, boat, bicycle etc. The device may be integrated with the vehicle, e.g. an in-built sensor or navigation apparatus, or may be a separate device associated with the vehicle such as a portable navigation apparatus. The present invention is not limited to the use of vehicle positional data, however, and the data may be obtained from devices associated with pedestrians. For example, the device may be any device which may, for example, be carried or worn or otherwise associated with a pedestrian such that the position of the device will correspond to the position of the pedestrian. Examples include mobile telecommunication devices, GPS watches, etc. Of course, the positional data may be obtained from a combination of different devices, or a single type of device.

It will be appreciated that the positional data obtained from the plurality of devices, may be referred to as "probe data". The data obtained from devices associated with vehicles or pedestrians respectively may be referred to as vehicle or pedestrian probe data. References to probe data herein should therefore be understood as being interchangeable with the term "positional data", and the positional data may be referred to as probe data for brevity herein.

In this method a plurality of time-stamped position data is preferably captured/uploaded from a plurality of devices having positioning capability e.g. navigation devices, such as portable navigations devices (PNDs). Techniques of analysing such data e.g. to obtain average speed data are known, for example as described in WO 2009/05341 1 ; the entire contents of which is enclosed herein by reference.

The method of the present invention comprises, for the or each intersection, and each manoeuvre at an intersection, that is considered, filtering the positional data to obtain positional data relating to the movement of devices performing a given manoeuvre at the intersection. Thus the time delay that is obtained is a manoeuvre-dependent time delay.

The steps of the present invention may be carried out in relation to one or more, or any ones of the intersections in the electronic map. The intersection is an intersection of the electronic map being representative of an actual intersection. The intersection may be an intersection between one or more navigable segments of the electronic map. It will be appreciated that a plurality of manoeuvres may be performed at the intersection. A manoeuvre through the intersection herein refers to any given (legal) path through the intersection from an entrance point to an exit point. The manoeuvre may be direction specific. The manoeuvre may or may not involve a turning movement. For example, a manoeuvre may involve traversing an intersection along a straight path. However, it may still be useful to obtain a time delay for such a manoeuvre representing the time delay relative to a free flow time, as such a time delay may vary for different times of day, depending upon traffic levels, or, where a traffic signal is present, signal phasing, etc.

Filtering the positional data to obtain data relating to the movement of devices performing a given manoeuvre at an intersection may be carried out in any given manner. In some techniques, the data may be filtered to obtain the positional data relating to the movement of devices passing through the intersection, i.e. via any route, and then determining the manoeuvre performed by consideration of the route taken by the device through the intersection. Alternatively, only data relating to a manoeuvre of interest may be filtered out, e.g. by selecting data relating to the movement of devices following a route corresponding to the manoeuvre through the intersection. Suitable techniques may involve the use of an origin-destination analysis of the positional data, using appropriately selected origin and destination locations corresponding to different paths through the intersection.

Positional data may be selected as relating to movement through the intersection by defining a boundary of the intersection. Positional data lying within the boundary of the intersection may then be taken to be data relating to travel through the intersection. This may be done by defining one or more locations providing the boundary. The locations may be defined with respect to navigable segments around or forming part of the intersection. The locations may be considered to be points which will be entrance or exit points to the intersection depending upon direction of travel. One technique may involve applying a bounding box around the intersection, and considering positional data relating to movements within the bounding box as relating to travel through the intersection. The bounding box may be defined by reference to distance from a given reference location at the intersection or travel time to the reference location etc as described in WO 2010/063508. Determining whether positional data relates to a given manoeuvre through the intersection may be carried out by consideration of the entrance and exit locations of the device, e.g. by considering the positional trace of the route through the intersection.

The method of the present invention is carried out in relation to at least one manoeuvre at the intersection. In preferred embodiments a time delay is carried out for a plurality of manoeuvres, or each possible manoeuvre, at the intersection.

The method may comprise defining one or more manoeuvres which may be performed at the intersection .

In accordance with the invention, once the relevant positional data relating to a manoeuvre at an intersection has been filtered out, the data is used to obtain both a free flow time and a set of one or more time delays for performing the manoeuvre as defined herein. The step of filtering out the data may be carried out prior to or as part of the step of obtaining the free flow time or time delay, and data may or may not be filtered out separately for each determination. It will be appreciated that the free flow time and/or the or each time delay is obtained at least in part using the positional data. For example it is envisaged that additional sources of historical or "live" data regarding movements of vehicles or pedestrians at the intersection might be used, such as data derived from loop detection or road-side sensors. However, preferably the free flow time and/or the or each time delay is obtained only using the said positional data obtained from the devices. The free flow time for a manoeuvre is indicative of the time taken to perform the manoeuvre during a period of time in which there is no or substantially little traffic. This period may for example be one or more nighttime hours where the time taken to perform the manoeuvre may be less influenced by other users. Such freeflow times will still reflect the influence of speed limits, road layout and traffic management infrastructure for example. The step of obtaining the free-flow time for the manoeuvre may comprise analysing positional data relating to the movement of devices that performed the manoeuvre within a given predetermined time period. The relevant data may be obtained by suitable filtering of the positional data by reference to time. The time may be any reference time relating to a point at which a given position in the intersection is passed when performing the manoeuvre, for example. In order to be able to obtain a free flow time, the predetermined time period should be chosen appropriately so that it will include data relating to movements which are representative of movements made under free-flow conditions. Typically the time period will be relatively long, such as a 24 hour period, or longer. For example, a week long period, or even a month or longer period might be considered, if free flow conditions do not occur every day, or week, etc. The step of obtaining the free-flow time for the manoeuvre may comprise analysing positional data relating to the movement of devices that performed the manoeuvre within a given predetermined time period, preferably wherein the free-flow time obtained by averaging the times taken by different devices to perform the manoeuvre in the given time period.

Determining the free flow time using the positional data relating to the movement of devices performing the manoeuvre in the given predetermined time period will involve consideration of the times taken by the devices to perform the manoeuvre in the given time period used for determining free flow time. In other words a "transit" time for passing through the intersection along a path involving the manoeuvre is obtained. This may carried out using the positional data and associated time data relating to the movement of a device, e.g. a positional trace in any suitable manner. The method may comprise analysing the positional data relating to the movement of devices performing the manoeuvre in the given predetermined time period used in obtaining the free flow time to determine the time taken for the devices to perform the manoeuvre. The time taken to perform the manoeuvre may be any suitable time, and may be obtained by considering the time taken for the device to move between two reference points at or before the start of the manoeuvre and at or after the end thereof. The reference points may be any suitable points and may be upstream and downstream of the manoeuvre and indeed intersection. In embodiments the method comprises defining an entrance point and an exit point for the path through the intersection when performing the given manoeuvre, and analysing the positional data relating to the movement of devices performing the manoeuvre in the given predetermined time period used in obtaining the free flow time to determine the time taken for the devices to travel between the entrance point and the exit point. The method preferably comprises obtaining data representative of a profile indicative of the times taken by different devices to perform the manoeuvre in the given predetermined time period for obtaining the free flow time. The data may be the profile, or otherwise indicative thereof. The profile may be a time distribution profile. The free flow time may then be determined using the profile data, and preferably time distribution profile data.

The free flow time may be obtained solely by reference to the positional data obtained from the devices, or may involve the use of other positional data as described above.

In embodiments the free flow time is obtained using the positional data and a reference time indicative of a free flow time. The reference time is obtained from other source(s) than the positional data. For example, the reference time may be obtained using a theoretical calculation, or may be have been derived using road side sensor or fixed loop data, etc. It will be appreciated that as the free flow time is determined at least in part using the positional data relating to the movement of actual devices, it may automatically take into account factors influencing free flow travel time, such as layout and surroundings of the intersection, and provides more reliable and realistic timing than a value based solely on a theoretical calculation. The reference free flow time may be a predetermined reference free flow time. The reference free flow time may have been previously obtained for other purposes, rather than being determined specifically for the purposes of the present invention. In some preferred embodiments the reference free flow time is determined, e.g. calculated using (legal) speed limit value(s) governing the manoeuvre.

In some embodiments in which the free flow time is obtained using the time data obtained from the positional data, e.g. a time profile or time distribution profile data and a reference free flow time, the reference free flow time is used to select that data from the positional data which may be considered to relate to manoeuvres under free flow conditions. The free flow time may be obtained using data for manoeuvres performed in a time within a given range of the reference free flow time. This may be carried out by reference to time distribution profile data.

In other embodiments the method comprises using time distribution profile data to obtain a percentile time and basing the free flow time on the percentile time. The percentile time may be taken as the free flow time. In some embodiments therefore the free flow time is a percentile time obtained from said data indicative of the distribution profile of the times. The percentile time may be chosen as appropriate to be indicative of the free flow time, for example, taking into account the predetermined time period used in obtaining the time data. In one arrangement the percentile time may be a 10th or a 5th percentile time or lower. The free flow time obtained in this manner would be expected to be representative of a manoeuvre time that is not affected by signal controls where such controls are provided.

Regardless of how it is obtained from the positional data, the free flow time is preferably obtained by averaging the data considered to relate to manoeuvres under free flow conditions, e.g. by consideration of the reference free flow time. Any form of averaging may be used. Thus, the free flow time is preferably an average free flow time. Determining the set of one or more time delays for the given manoeuvre will involve determining a "transit" time for performing the manoeuvre in the time period to which the time delay is to relate. The time for performing the manoeuvre may be obtained in a similar manner to determining the free flow time for the manoeuvre, but instead by consideration of positional data relating to the movement of devices performing the manoeuvre in the given predetermined time period for which the time delay is to be by reference to. This data may be obtained by suitable filtering of the positional data relating to movements of devices performing the manoeuvre at the intersection by reference to the time data associated with the positional data. The method may comprise analysing the positional data relating to the movement of devices performing the manoeuvre in the given time period to determine the time taken for the devices to perform the manoeuvre. The or each time period to which the time delay relates is preferably a shorter time period than the predetermined time period used in determining the free flow travel time. The step of obtaining the free-flow time for the manoeuvre may comprise analysing positional data relating to the movement of devices that performed the manoeuvre within a given predetermined time period, and the step of obtaining the or each time delay for the manoeuvre may comprise analysing positional data relating to the movement of devices that performed the manoeuvre within a respective given predetermined time period that is shorter than the given predetermined time period used in obtaining the free flow time.

As described in relation to determining the free flow time, the time taken to perform the manoeuvre in the given time period for which the time delay is to be obtained may be any suitable time, and may be obtained by considering the time taken for the device to move between two reference points at or before the start of the manoeuvre and at or after the end thereof. The reference points may be any suitable points and may be upstream and downstream of the manoeuvre and indeed intersection. In embodiments the method comprises defining an entrance point and an exit point for the path through the intersection when performing the given manoeuvre, and analysing the positional data relating to the movement of devices performing the manoeuvre in the given predetermined time period to determine the time taken for the devices to travel between the entrance point and the exit point. The reference points used in the determination of the time when determining time delay should of course correspond to those used in determining free flow time for comparison purposes.

The time taken to perform the manoeuvre in the given time period is preferably obtained by averaging the times taken for different devices to perform the manoeuvre as indicated by the positional data for the relevant time period. Any form of averaging may be used.

The time delay data and/or the free flow time data determined, (or the transit times used to obtain the time delays) may be subject to appropriate further processing, e.g. filtering and/or smoothing.

The method may comprise obtaining data representative of a profile indicative of the times taken by the devices to perform the manoeuvre in the given predetermined time period for obtaining the time delay. The data may be the profile, or otherwise indicative thereof. The profile may be a time distribution profile. The time may then be determined using the profile data, and preferably time distribution profile data. The step of obtaining the time delay for a given time period may therefore comprise obtaining data indicative of a distribution profile of the times taken by different devices to perform the manoeuvre in the respective time period, and using the time distribution profile data to obtain the time delay.

The time delay for a given time period is indicative of the time delay relative to the free flow time for performing the manoeuvre as determined using the positional data. The time delay may be a difference between the free flow time and the time for performing the manoeuvre in the given period as determined using the positional data, or may be indicative of the relative delay in any other manner. The step of obtaining the time delay for a given time period may comprise obtaining data indicative of an average time taken by different devices to perform the manoeuvre in the respective time period, wherein the time delay is representative of the difference between the determined average time and the free flow time obtained.

In accordance with the invention, a set of one or more time delays is obtained for the given manoeuvre. An intersection may have a plurality of time delays for a given manoeuvre associated therewith, e.g. with each time delay being representative of the time delay with respect to the free flow time when performing the manoeuvre in a different given time period.

The time period(s) for which a time delay is obtained may be selected as desired. Time periods may correspond to a time of the year, day of the week and/or time of day. In some embodiments time delays are provided for performing a given manoeuvre at time intervals between 1 minute and 2 hours, between 5 minutes and 1 hour, between 10 minutes and 30 minutes or at time intervals of 15 minutes.

As will be appreciated the time delay is likely to vary depending on the time of day, the day of the week and even the time of year. Consequently the provision of multiple time delays is likely to give more accurate time delay prediction than a single time delay for a manoeuvre.

In some embodiments one or more alternative time delays are provided for a manoeuvre within corresponding time periods allowing selection of the most appropriate time delay at any given time based on one or more factors other than time dependent variation. Selection of an alternative time delay for use may be appropriate in particular situations, for example in different weather conditions, or where a particular event such as a football game is occurring. Such situations may be considered factors other than time dependent variation. Such situations may be considered atypical. As will be appreciated the provision of such alternative time delays may be dependent on the availability of sufficient historic positional data to create an accurate time delay.

In some embodiments alternative sets of time-dependent time delays are provided for the or each manoeuvre allowing selection of the most appropriate time delay based both on the time and on other factors. It may be for example that one set of time dependent time delays is used if the weather is dry and another set if there is rain.

In some embodiments time delays are determined for time periods according to or are at least influenced by the day of the week. This may serve to increase time delay accuracy as time delay may vary depending on day of the week dependent factors such as weekend shopping, Friday travel for a weekend away, haulage schedules and Monday long-distance commuting. In some embodiments time delays are obtained for time periods according to or are at least influenced by the time of day. This may serve to increase time delay accuracy as time delay may vary depending on "time of day"-dependent factors such as rush hours, school runs, opening and closing times (e.g. of bars, restaurants, theatres, concert venues, cinemas, clubs, etc), start and finish times (e.g. of festivals, shows and sporting events, etc), arrival and departure times (e.g. of trains, ships and aircraft) and widespread commonality of activity (e.g. eating or sleeping). In some embodiments there may for example be a single time delay for night. Night may be a predefined period between set times, e.g. between substantially 1 1 pm and 6am.

In some embodiments time delays are obtained for substantially fifteen minute time intervals.

However time intervals above or below this may be used, e.g. 5 minutes, 10 minutes, 15 minutes, 20 minutes, 30 minutes, 1 hour or longer periods such as the night. Further obtained time delays that are adjacent in time may be concatenated. This may be particularly useful where the time delays are similar (e.g. potentially night time hours).

In some embodiments time delays are calculated according to or are at least influenced by the occurrence of a particular event or situation. Such events or situations may for example include particular types of weather, events such as football matches or exhibitions and public holidays and the like.

In some of the embodiments, the time delays are obtained for time periods according to or at least influenced by more than one of the factors discussed above.

The time used for obtaining the time delay in a given time period may be an average of all, or substantially all or a selection of historic times for performing the manoeuvre based on the positional data. In other embodiments however the mode or a percentile of all or substantially all or a selection of historic times of travel across that segment may be used. Alternatively a time may be selected in another way.

In some embodiments the one or more intersections for which the methods of the present invention are implemented are a set of intersections that may comprise one or more of the following: intersections falling within a predetermined map area; intersections falling within a predetermined radius; intersections associated with likely routes into or out of an area; intersections within an area having predetermined travel directions and intersections selected as known bottle-necks; and intersections selected as containing a traffic hotspot. It may be, for example, that the set comprises intersections along what may be considered major routes out of a city. In these embodiments the present invention may be applied to providing time delay information at least for those more significant intersections, where time delays may be an issue.

In some embodiments the method further comprises using the time delay(s) in determination of a route across an area covered by the electronic map, and may comprise generating a navigable route taking into account the time delay or delays associated with performing manoeuvres at the intersection or intersections in the area. This system may allow routing based on likely time delays when performing manoeuvres at intersections that may form part of the route. The time delays may be for the time periods when the route is expected to be travelled or a current time period. The method may be carried out by a navigation device, such as a PND. The steps of the methods described herein may be performed exclusively on a server, or some on a server and the others on a navigation device in any combination, or exclusively on a navigation device. Performance of one or more of the steps on the server may be efficient and may reduce the computational burden placed on a navigation device. Alternatively if one or more steps are performed on the navigation device, this may reduce any bandwidth required for network communication.

For example, in some embodiments, the step of determining a route across an area covered by the electronic map is performed on a server. In other embodiments, the time delays associated with particular manoeuvres at intersections are sent to a navigation device (from a server) and the determination step is performed on the navigation device.

In some embodiments the time delay or delays are used by the server in generating a route. It may be for example that the server avoids generating a route incorporating a manoeuvre having a high delay time in a given period when the route is to be travelled. In some embodiments a generated time delay is sent from a server to one or more navigation devices. One or more of the navigation devices may in turn use the time delay to generate a route.

In accordance with the invention, data indicative of the or each time delay is stored in association with data indicative of the manoeuvre, the intersection and the time period to which it relates. The data indicative of the intersection is preferably location data. The data may be in any manner indicative of the relevant items The intersection data may be provided by the manoeuvre data, i.e. if the manoeuvre data uniquely identifies the manoeuvre among all manoeuvres at different intersections, or may be separate thereto if generic manoeuvre data is used e.g. describing the nature of the manoeuvre such as left or right turn etc. The manoeuvre data could be indicative of the general type of manoeuvre or could comprise location data indicating the change in location occurring when the manoeuvre is performed.

In some embodiments, the stored time delay data associated with a manoeuvre at an intersection could be transmitted upon request to a third party, e.g. for use in analysing the efficiency of traffic flow at the intersection. For example, the server may receive a request including an indication of one or more intersections, or one or more manoeuvres associated therewith, and the time or range of times of interest to the requester. The appropriate stored data will be identified and transmitted to the requester.

The present invention extends to a data product storing electronic map data indicative of the locations of one or more intersections in an area, the product further comprising data associated with the location data for the or each intersection being indicative of a particular manoeuvre which may be performed at the intersection, and data indicative of a time delay for performing the manoeuvre in a given respective time period with respect to a free flow time for performing the manoeuvre, wherein the time delay is obtained in accordance with the method of the present invention in any of its aspects or embodiments.

The data product in any of these further aspects or embodiments of the invention, may be of any suitable form. In some embodiments the data product may be stored on a computer readable medium. The computer readable medium may be, for example, a diskette, CD ROM, ROM, RAM, flash memory or hard disk. The present invention extends to a computer readable medium comprising the data product in accordance with the invention of any of its aspects or embodiments.

In accordance with a further aspect of the invention there is provided; a data product storing electronic map data indicative of the locations of one or more intersections in a geographic area, the product further comprising data associated with the location data for the or each intersection being indicative of a particular manoeuvre which may be performed at the intersection, and data indicative of a time delay for performing the manoeuvre in a given respective time period with respect to a free flow time for performing the manoeuvre, wherein the data product has been obtained according to a method comprising the steps of: obtaining positional data relating to the movement of a plurality of devices with respect to time in the area; and,

for one or more particular manoeuvres at the or each said intersection, filtering the positional data to obtain positional data relating to the movement of devices performing the particular manoeuvre at the intersection;

the method further comprising:

using the filtered positional data to obtain: a free flow time indicative of the time taken to perform the particular manoeuvre under free flow traffic conditions; and a set of one or more time delays for the particular manoeuvre, wherein the or each time delay is indicative of the time delay incurred when performing the manoeuvre in a given respective time period and is with respect to the free flow time; and

storing data indicative of the or each time delay in association with data indicative of the manoeuvre, the intersection and the time period to which it relates.

As will be appreciated by those skilled in the art, this further aspect of the present invention can and preferably does include any one or more or all of the preferred and optional features of the invention described herein in relation to any other aspects of the invention, as appropriate.

In accordance with a further aspect of the invention there is provided a system, optionally a server, arranged to process data relating to a geographic area including one or more intersections, the system being arranged to generate data in relation to the one or more intersections by:

obtaining positional data relating to the movement of a plurality of devices with respect to time in the area; and,

for one or more particular manoeuvres at the or each said intersection, filtering the positional data to obtain positional data relating to the movement of devices performing the particular manoeuvre at the intersection ;

using the filtered positional data to obtain: a free flow time indicative of the time taken to perform the particular manoeuvre under free flow traffic conditions; and a set of one or more time delays for the particular manoeuvre, wherein the or each time delay is indicative of the time delay incurred when performing the manoeuvre in a given respective time period and is with respect to the free flow time; and

storing data indicative of the or each time delay in association with data indicative of the manoeuvre, the intersection and the time period to which it relates. As will be appreciated by those skilled in the art, this further aspect of the present invention can and preferably does include any one or more or all of the preferred and optional features of the invention described herein in relation to any other aspects of the invention, as appropriate.

As will be appreciated the system and/or processor may be at least part of a server or a navigation device.

Accordingly the invention can encompass a server arranged to generate time delays for performing a manoeuvre or manoeuvres at intersection(s) in the area covered by an electronic map in accordance with the methods of the invention in any of its aspects or embodiments described herein. Similarly, the invention can encompass a navigation device arranged to generate time delays for performing a manoeuvre or manoeuvres at intersection(s) in the area covered by an electronic map in accordance with the methods of the invention in any of its aspects or embodiments described herein.

It should be noted that the phrase 'associated therewith' in relation to one or more segments should not be interpreted to require any particular restriction on data storage locations. The phrase only requires that the features are identifiably related to an intersection. Therefore association may for example be achieved by means of a reference to a side file, potentially located in a remote server.

Accordingly the invention can encompass a server arranged to process data relating to an electronic map and to generate time delay data. Similarly, the invention can encompass a navigation device arranged to process data relating to an electronic map and to generate time delay data.

As will be appreciated by those skilled in the art, any of the further aspects and embodiments of the present invention can and preferably do include any one or more or all of the preferred and optional features of the invention described herein in relation to any other aspect of the invention, as appropriate.

Any of the methods in accordance with the present invention may be implemented at least partially using software, e.g. computer programs. The present invention thus also extends to a computer program comprising computer readable instructions executable to perform a method according to any of the aspects or embodiments of the invention.

The invention correspondingly extends to a computer software carrier comprising such software which when used to operate a system or apparatus comprising data processing means causes in conjunction with said data processing means said apparatus or system to carry out the steps of the methods of the present invention. Such a computer software carrier could be a non-transitory physical storage medium such as a ROM chip, CD ROM or disk, or could be a signal such as an electronic signal over wires, an optical signal or a radio signal such as to a satellite or the like.

Where not explicitly stated, it will be appreciated that the invention in any of its aspects may include any or all of the features described in respect of other aspects or embodiments of the invention to the extent they are not mutually exclusive. In particular, while various embodiments of operations have been described which may be performed in the method and by the system or apparatus, it will be appreciated that any one or more or all of these operations may be performed in the method and by the system or apparatus, in any combination, as desired, and as appropriate. Advantages of these embodiments are set out hereafter, and further details and features of each of these embodiments are defined in the accompanying dependent claims and elsewhere in the following detailed description. Brief Description of the Drawings

Embodiments of the invention will now be described, by way of example only, with reference to the accompanying Figures, in which:

Figure 1 is a schematic illustration of an exemplary part of a Global Positioning System (GPS) usable by a navigation device;

Figure 2 is a schematic diagram of a communbations system for communication between a navigation device and a server;

Figure 3 is a schematic illustration of electronic components of the navigation device of Figure 2 or any other suitable navigation device;

Figure 4 is a schematic diagram of an arrangement of mounting and/or docking a navigation device; Figure 5 is a schematic representation of an architectural stack employed by the navigation device of

Figure 3;

Figure 6a illustrates the manoeuvres 1-12 possible at a first intersection by reference to which an embodiment of the invention is illustrated, and Figure 6b illustrates schematically the location of fixed loop traffic detectors at the intersection which are used in determining some comparative data;

Figure 6c illustrates the manoeuvres 1 -12 possible at a second intersection by reference to which an embodiment of the invention is illustrated, and Figure 6d illustrates schematically the location of fixed loop traffic detectors at the intersection which are used in determining some comparative data;

Figure 7 illustrates the average delay per 15-minute time period for left turning OD movement 3 at intersection 1 between 07:00 and 21 :00; and

Figure 8 shows the application of a moving average and a Savitzky-Golay filter to the average delay per 15-minute time period for left turning OD movement 3 at intersection 1 between 07:00 and 21 :00.

Detailed description of the Figures

Embodiments of the present invention will now be described with particular reference to a Portable Navigation Device (PND). It should be remembered, however, that the teachings of the present invention are not limited to PNDs but are instead universally applicable to any type of processing device that is configured to execute navigation software in a portable manner so as to provide route planning and navigation functionality. It follows therefore that in the context of the present application, a navigation 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 vehicle such as an automobile, or indeed a portable computing resource, for example a portable personal computer (PC), a mobile telephone or a Personal Digital Assistant (PDA) executing route planning and navigation software. Further, embodiments of the present invention are described with reference to road segments. It should be realised that the invention may also be applicable to other navigable segments, such as segments of a path, river, canal, cycle path, tow path, railway line, or the like. For ease of reference these are commonly referred to as a road segment.

It will also be apparent from the following that the teachings of the present invention even 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. In such circumstances the "destination" location selected by the user need not have a corresponding start location from which the user wishes to start navigating, and as a consequence references herein to the "destination" location or indeed to a "destination" view should not be interpreted to mean that the generation of a route is essential, that travelling to the "destination" must occur, or indeed that the presence of a destination requires the designation of a corresponding start location.

With the above provisos in mind, the Global Positioning System (GPS) of Figure 1 and the like are used for a variety of purposes. In general, the GPS is a satellite-radio based navigation system capable of determining continuous position, velocity, time, and in some instances direction information for an unlimited number of users. Formerly known as NAVSTAR, the GPS incorporates a plurality of satellites which orbit the earth in extremely precise orbits. Based on these precise orbits, GPS satellites can relay their location, as GPS data, to any number of receiving units. However, it will be understood that Global Positioning systems could be used, such as GLOSNASS, the European Galileo positioning system, COMPASS positioning system or IRNSS (Indian Regional Navigational Satellite System).

The GPS system is implemented when a device, specially equipped to receive GPS data, begins scanning radio frequencies for GPS satellite signals. Upon receiving a radio signal from a GPS satellite, the device determines the precise location of that satellite via one of a plurality of different conventional methods. The device will continue scanning, in most instances, for signals until it has acquired at least three different satellite signals (noting that position is not normally, but can be determined, with only two signals using other triangulation techniques). Implementing geometric triangulation, the receiver utilizes the three known positions to determine its own two-dimensional position relative to the satellites. This can be done in a known manner. Additionally, acquiring a fourth satellite signal allows the receiving device to calculate its three dimensional position by the same geometrical calculation in a known manner. The position and velocity data can be updated in real time on a continuous basis by an unlimited number of users.

As shown in Figure 1 , the GPS system 100 comprises a plurality of satellites 102 orbiting about the earth 104. A GPS receiver 106 receives GPS data as spread spectrum GPS satellite data signals 108 from a number of the plurality of satellites 102. The spread spectrum data signals 108 are continuously transmitted from each satellite 102, the spread spectrum data signals 108 transmitted each comprise a data stream including information identifying a particular satellite 102 from which the data stream originates. The GPS receiver 106 generally requires spread spectrum data signals 108 from at least three satellites 102 in order to be able to calculate a two-dimensional position. Receipt of a fourth spread spectrum data signal enables the GPS receiver 106 to calculate, using a known technique, a three-dimensional position.

Turning to Figure 2, a navigation device 200 (i.e. a PND) comprising or coupled to the GPS receiver device 106, is capable of establishing a data session, if required, with network hardware of a "mobile" or telecommunications network via a mobile device (not shown), for example a mobile telephone, PDA, and/or any device with mobile telephone technology, in order to establish a digital connection, for example a digital connection via known Bluetooth technology. Thereafter, through its network service provider, the mobile device can establish a network connection (through the Internet for example) with a server 150. As such, a "mobile" network connection can be established between the navigation device 200 (which can be, and often times is, mobile as it travels alone and/or in a vehicle) and the server 150 to provide a "real-time" or at least very "up to date" gateway for information.

The establishing of the network connection between the mobile device (via a service provider) and another device such as the server 150, using the Internet for example, can be done in a known manner. In this respect, any number of appropriate data communications protocols can be employed, for example the TCP/IP layered protocol. Furthermore, the mobile device can utilize any number of communication standards such as CDMA2000, GSM, IEEE 802.1 1 a/b/c/g/n, etc.

Hence, it can be seen that the Internet connection may be utilised, which can be achieved via data connection, via a mobile phone or mobile phone technology within the navigation device 200 for example.

Although not shown, the navigation device 200 may, of course, include its own mobile telephone technology within the navigation device 200 itself (including an antenna for example, or optionally using the internal antenna of the navigation device 200). The mobile phone technology within the navigation device 200 can include internal components, and/or can include an insertable card (e.g. Subscriber Identity Module (SIM) card), complete with necessary mobile phone technology and/or an antenna for example. As such, mobile phone technology within the navigation device 200 can similarly establish a network connection between the navigation device 200 and the server 150, via the Internet for example, in a manner similar to that of any mobile device.

For telephone settings, a Bluetooth enabled navigation device may be used to work correctly with the ever changing spectrum of mobile phone models, manufacturers, etc., model/manufacturer specific settings may be stored on the navigation device 200 for example. The data stored for this information can be updated.

In Figure 2, the navigation device 200 is depicted as being in communication with the server 150 via a generic communications channel 152 that can be implemented by any of a number of different arrangements. The communication channel 152 generically represents the propagating medium or path that connects the navigation device 200 and the server 150. The server 150 and the navigation device 200 can communicate when a connection via the communications channel 152 is established between the server 150 and the navigation device 200 (noting that such a connection can be a data connection via mobile device, a direct connection via personal computer via the Internet, etc.). The communbation channel 152 is not limited to a particular communication technology. Additionally, the communication channel 152 is not limited to a single communication technology; that is, the channel 152 may include several communication links that use a variety of technology. For example, the communication channel 152 can be adapted to provide a path for electrical, optical, and/or electromagnetic communications, etc. As such, the communication channel 152 includes, but is not limited to, one or a combination of the following: electric circuits, electrical conductors such as wires and coaxial cables, fibre optic cables, converters, radio-frequency (RF) waves, the atmosphere, free space, etc. Furthermore, the communication channel 152 can include intermediate devices such as routers, repeaters, buffers, transmitters, and receivers, for example.

In one illustrative arrangement, the communication channel 152 includes telephone and computer networks. Furthermore, the communication channel 152 may be capable of accommodating wireless communication, for example, infrared communications, radio frequency communications, such as microwave frequency communications, etc. Additionally, the communbation channel 152 can accommodate satellite communication.

The communbation signals transmitted through the communication channel 152 include, but are not limited to, signals as may be required or desired for given communication technology. For example, the signals may be adapted to be used in cellular communication technology such as Time Division Multiple Access (TDMA), Frequency Division Multiple Access (FDMA), Code Division Multiple Access (CDMA), Global System for Mobile Communications (GSM), General Packet Radio Service (GPRS), etc. Both digital and analogue signals can be transmitted through the communication channel 152. These signals may be modulated, encrypted and/or compressed signals as may be desirable for the communication technology.

The server 150 includes, in addition to other components which may not be illustrated, a processor 154 operatively connected to a memory 156 and further operatively connected, via a wired or wireless connection 158, to a mass data storage device 160. The mass storage device 160 contains a store of navigation data and map information, and can again be a separate device from the server 150 or can be incorporated into the server 150. The processor 154 is further operatively connected to transmitter 162 and receiver 164, to transmit and receive information to and from navigation device 200 via communications channel 152. The signals sent and received may include data, communication, and/or other propagated signals. The transmitter 162 and receiver 164 may be selected or designed according to the communications requirement and communication technology used in the communication design for the navigation system 200. Further, it should be noted that the functions of transmitter 162 and receiver 164 may be combined into a single transceiver.

As mentioned above, the navigation device 200 can be arranged to communbate with the server 150 through communications channel 152, using transmitter 166 and receiver 168 to send and receive signals and/or data through the communications channel 152, noting that these devices can further be used to communicate with devices other than server 150. Further, the transmitter 166 and receiver 168 are selected or designed according to communication requirements and communication technology used in the communication design for the navigation device 200 and the functions of the transmitter 166 and receiver 168 may be combined into a single transceiver as described above in relation to Figure 2. Of course, the navigation device 200 comprises other hardware and/or functional parts, which will be described later herein in further detail.

Software stored in server memory 156 provides instructions for the processor 154 and allows the server 150 to provide services to the navigation device 200. One service provided by the server 150 involves processing requests from the navigation device 200 and transmitting navigation data from the mass data storage 160 to the navigation device 200. Another service that can be provided by the server 150 includes processing the navigation data using various algorithms for a desired application and sending the results of these calculations to the navigation device 200.

The server 150 constitutes a remote source of data accessible by the navigation device 200 via a wireless channel. The server 150 may include a network server located on a local area network (LAN), wide area network (WAN), virtual private network (VPN), etc.

The server 150 may include a personal computer such as a desktop or laptop computer, and the communication channel 152 may be a cable connected between the personal computer and the navigation device 200. Alternatively, a personal computer may be connected between the navigation device 200 and the server 150 to establish an Internet connection between the server 150 and the navigation device 200. The navigation device 200 may be provided with information from the server 150 via information downloads which may be updated automatically, from time to time, or upon a user connecting the navigation device 200 to the server 150 and/or may be more dynamic upon a more constant or frequent connection being made between the server 150 and navigation device 200 via a wireless mobile connection device and TCP/IP connection for example. For many dynamic calculations, the processor 154 in the server 150 may be used to handle the bulk of processing needs, however, a processor (not shown in Figure 2) of the navigation device 200 can also handle much processing and calculation, oftentimes independent of a connection to a server 150.

Referring to Figure 3, it should be noted that the block diagram of the navigation device 200 is not inclusive of all components of the navigation device, but is only representative of many example components. The navigation device 200 is located within a housing (not shown). The navigation device 200 includes processing circuitry comprising, for example, the processor 202 mentioned above, the processor 202 being coupled to an input device 204 and a display device, for example a display screen 206. Although reference is made here to the input device 204 in the singular, the skilled person should appreciate that the input device 204 represents any number of input devices, including a keyboard device, voice input device, touch panel and/or any other known input device utilised to input information. Likewise, the display screen 206 can include any type of display screen such as a Liquid Crystal Display (LCD), for example.

In one arrangement, one aspect of the input device 204, the touch panel, and the display screen 206 are integrated so as to provide an integrated input and display device, including a touchpad or touchscreen input 250 (Figure 4) to enable both input of information (via direct input, menu selection, etc.) and display of information through the touch panel screen so that a user need only touch a portion of the display screen 206 to select one of a plurality of display choices or to activate one of a plurality of virtual or "soft" buttons. In this respect, the processor 202 supports a Graphical User Interface (GUI) that operates in conjunction with the touchscreen.

In the navigation device 200, the processor 202 is operatively connected to and capable of receiving input information from input device 204 via a connection 210, and operatively connected to at least one of the display screen 206 and the output device 208, via respective output connections 212, to output information thereto. The navigation device 200 may include an output device 208, for example an audible output device (e.g. a loudspeaker). As the output device 208 can produce audible information for a user of the navigation device 200, it should equally be understood that input device 204 can include a microphone and software for receiving input voice commands as well. Further, the navigation device 200 can also include any additional input device 204 and/or any additional output device, such as audio input/output devices for example.

The processor 202 is operatively connected to memory 214 via connection 216 and is further adapted to receive/send information from/to input/output (I/O) ports 218 via connection 220, wherein the I/O port 218 is connectible to an I/O device 222 external to the navigation device 200. The external I/O device 222 may include, but is not limited to an external listening device, such as an earpiece for example. The connection to I/O device 222 can further be a wired or wireless connection to any other external device such as a car stereo unit for hands-free operation and/or for voice activated operation for example, for connection to an earpiece or headphones, and/or for connection to a mobile telephone for example, wherein the mobile telephone connection can be used to establish a data connection between the navigation device 200 and the Internet or any other network for example, and/or to establish a connection to a server via the Internet or some other network for example.

The memory 214 of the navigation device 200 comprises a portion of non-volatile memory (for example to store program code) and a portion of volatile memory (for example to store data as the program code is executed). The navigation device also comprises a port 228, which communicates with the processor 202 via connection 230, to allow a removable memory card (commonly referred to as a card) to be added to the device 200. In the embodiment being described the port is arranged to allow an SD (Secure Digital) card to be added. In other embodiments, the port may allow other formats of memory to be connected (such as Compact Flash (CF) cards, Memory Sticks, xD memory cards, USB (Universal Serial Bus) Flash drives, MMC (MultiMedia) cards, SmartMedia cards, Microdrives, or the like).

Figure 3 further illustrates an operative connection between the processor 202 and an

antenna/receiver 224 via connection 226, wherein the antenna/receiver 224 can be a GPS antenna/receiver for example and as such would function as the GPS receiver 106 of Figure 1 . It should be understood that the antenna and receiver designated by reference numeral 224 are combined schematically for illustration, but that the antenna and receiver may be separately located components, and that the antenna may be a GPS patch antenna or helical antenna for example. It will, of course, be understood by one of ordinary skill in the art that the electronic components shown in Figure 3 are powered by one or more power sources (not shown) in a conventional manner. Such power sources may include an internal battery and/or a input for a low voltage DC supply or any other suitable arrangement. As will be understood by one of ordinary skill in the art, different configurations of the components shown in Figure 3 are contemplated. For example, the components shown in Figure 3 may be in communication with one another via wired and/or wireless connections and the like. Thus, the navigation device 200 described herein can be a portable or handheld navigation device 200.

In addition, the portable or handheld navigation device 200 of Figure 3 can be connected or "docked" in a known manner to a vehicle such as a bicycle, a motorbike, a car or a boat for example. Such a navigation device 200 is then removable from the docked location for portable or handheld navigation use. Indeed, in other embodiments, the device 200 may be arranged to be handheld to allow for navigation of a user.

Referring to Figure 4, the navigation device 200 may be a unit that includes the integrated input and display device 206 and the other components of Figure 2 (including, but not limited to, the internal GPS receiver 224, the processor 202, a power supply (not shown), memory systems 214, etc.).

The navigation device 200 may sit on an arm 252, which itself may be secured to a vehicle dashboard/window/etc. using a suction cup 254. This arm 252 is one example of a docking station to which the navigation device 200 can be docked. The navigation device 200 can be docked or otherwise connected to the arm 252 of the docking station by snap connecting the navigation device 200 to the arm 252 for example. The navigation device 200 may then be rotatable on the arm 252. To release the connection between the navigation device 200 and the docking station, a button (not shown) on the navigation device 200 may be pressed, for example. Other equally suitable arrangements for coupling and decoupling the navigation device 200 to a docking station are well known to persons of ordinary skill in the art.

Turning to Figure 5, the processor 202 and memory 214 cooperate to support a BIOS (Basic Input/Output System) 282 that functions as an interface between functional hardware components 280 of the navigation device 200 and the software executed by the device. The processor 202 then loads an operating system 284 from the memory 214, which provides an environment in which application software 286 (implementing some or all of the described route planning and navigation functionality) can run. The application software 286 provides an operational environment including the Graphical User Interface (GUI) that supports core functions of the navigation device, for example map viewing, route planning, navigation functions and any other functions associated therewith. In this respect, part of the application software 286 comprises a view generation module 288.

In the embodiment being described, the processor 202 of the navigation device is programmed to receive GPS data received by the antenna 224 and, from time to time, to store that GPS data, together with a time stamp of when the GPS data was received, within the memory 214 to build up a record of the location of the navigation device. Each data record so-stored may be thought of as a GPS fix; i.e. it is a fix of the location of the navigation device and comprises a latitude, a longitude, a time stamp and an accuracy report. In one embodiment the data is stored substantially on a periodic basis which is for example every 5 seconds. The skilled person will appreciate that other periods would be possible and that there is a balance between data resolution and memory capacity; i.e. as the resolution of the data is increased by taking more samples, more memory is required to hold the data. However, in other embodiments, the resolution might be substantially every: 1 second, 10 seconds, 15 seconds, 20 seconds, 30 seconds, 45 seconds, 1 minute, 2.5 minutes (or indeed, any period in between these periods). Thus, within the memory of the device there is built up a record of the whereabouts of the device 200 at points in time.

In some embodiments, it may be found that the quality of the captured data reduces as the period increases and whilst the degree of degradation will at least in part be dependent upon the speed at which the navigation device 200 was moving a period of roughly 15 seconds may provide a suitable upper limit.

Whilst the navigation device 200 is generally arranged to build up a record of its whereabouts, some embodiments, do not record data for a predetermined period and/or distance at the start or end of a journey. Such an arrangement helps to protect the privacy of the user of the navigation device 200 since it is likely to protect the location of his/her home and other frequented destinations. For example, the navigation device 200 may be arranged not to store data for roughly the first 5 minutes of a journey and/or for roughly the first mile of a journey.

In other embodiments, the GPS may not be stored on a periodic basis but may be stored within the memory when a predetermined event occurs. For example, the processor 202 may be programmed to store the GPS data when the device passes a road junction, a change of road segment, or other such event. Further, the processor 202 is arranged, from time to time, to upload the record of the whereabouts of the device 200 (i.e. the GPS data and the time stamp) to the server 150. In some embodiments in which the navigation device 200 has a permanent, or at least generally present, commun cation channel 152 connecting it to the server 150 the uploading of the data occurs on a periodic basis which may for example be once every 24 hours. The skilled person will appreciate that other periods are possible and may be substantially any of the following periods: 15 minutes, 30 minutes, hourly, every 2 hours, every 5 hours, every 12 hours, every 2 days, weekly, or any time in between these. Indeed, in such embodiments the

processor 202 may be arranged to upload the record of the whereabouts on a substantially real time basis, although this may inevitably mean that data is in fact transmitted from time to time with a relatively short period between the transmissions and as such may be more correctly thought of as being pseudo real time. In such pseudo real time embodiments, the navigation device may be arranged to buffer the GPS fixes within the memory 214 and/or on a card inserted in the port 228 and to transmit these when a predetermined number have been stored. This predetermined number may be on the order of 20, 36, 100, 200 or any number in between. The skilled person will appreciate that the predetermined number is in part governed by the size of the memory 214 or card within the port 228.

In other embodiments, which do not have a generally present communbation channel 152 the processor 202 may be arranged to upload the record to the server 152 when a communication channel 152 is created. This may for example, be when the navigation device 200 is connected to a user's computer. Again, in such embodiments, the navigation device may be arranged to buffer the GPS fixes within the memory 214 or on a card inserted in the port 228. Should the memory 214 or card inserted in the port 228 become full of GPS fixes the navigation device may be arranged to deleted the oldest GPS fixes and as such it may be thought of as a First in First Out (FIFO) buffer.

In the embodiment being described, the record of the whereabouts comprises one or more traces with each trace representing the movement of that navigation device 200 within a 24 hour period. Each 24 is arranged to coincide with a calendar day but in other embodiments, this need not be the case.

Generally, a user of a navigation device 200 gives his/her consent for the record of the devices whereabouts to be uploaded to the server 150. If no consent is given then no record is uploaded to the server 150. The navigation device itself, and/or a computer to which the navigation device is connected may be arranged to ask the user for his/her consent to such use of the record of whereabouts.

The server 150 is arranged to receive the record of the whereabouts of the device and to store this within the mass data storage 160 for processing. Thus, as time passes the mass data storage 160 accumulates a plurality of records of the whereabouts of navigation devices 200 which have uploaded data. As discussed above, the mass data storage 160 also contains map data. Such map data provides information about the location of road segments, points of interest and other such information that is generally found on map.

Some preferred embodiments of methods for generating intersection data in accordance with the invention will now be described.

The measurement of delay at intersections when performing given manoeuvres is needed for efficient intersection control. Optimization of road geometry, intersection control and dynamic traffic management requires up to date and accurate traffic information. Knowledge of such delays, and hence transit times at intersections is also important in the context of route planning, e.g. by PNDs and/or servers, allowing quickest route determinations and accurate ETAs to be provided.

Previous attempts to obtain delay information has focused on evaluation of measurements from roadside sensors and loop detection. Data collection from road-side sensors can directly be used to assess the performance of an intersection but it is expensive and requires high maintenance expenditures. Loop detection delivers accurate traffic intensities but can suffer from detection errors and missing data.

Continuous use of road-side sensors requires constant availability of detection equipment at the intersection, which is often not the case at uncontrolled intersections.

One prior art technique using fixed sensors for determining delays at an intersection using fixed loop detectors will be described by way of background.

Turning movements at intersections can be described by an Origin-Destination (OD) distribution or OD matrix which is derived from traffic counts for every OD combination. The OD distribution is presented as the absolute (traffic volume) or relative (percentage) distribution of turning movements at the intersection.

The time delay for a manoeuvre is defined as the difference between uninterrupted and interrupted travel times (transit times) through the intersection when taking a path involving the manoeuvre through the intersection. Measurement of travel time occurs by measuring the time difference between the arrival and the departure at the intersection. To ensure minimal influence of external factors and driving behaviour, the arrival and departure locations should be far enough from the intersection to include the braking and acceleration behaviour in the measurement of the travel time. Delay is calculated by comparison of the measured travel time and the free flow travel time (the travel time if there was no interference on the intersection):

T = (T - T )- T

Delay \ Departure Arrival / Free flow Eqn. 1

In the reference values determined herein, a steady-state approach is selected for the estimation of delay based on traffic counts from loop detectors and signal monitoring. The average delay at the intersections is calculated on a macroscopic level, to serve as input for Level of Service principle (LOS) assessments. The approximate value of the total delay (delay rate) for a movement at isolated fixed time signals (D in vehicles) is expressed as follows: qc< (l - u)

2(1 - y) Eqn. 2

Here qc is the average number of arrivals per cycle in vehicles, u is the green time ratio, y is the flow ratio and NO describes the overflow queue in vehicles. The flow ratio y is the ratio of the arrival flow and the saturation flow of the movement. Furthermore the average delay per vehicle d is derived (with q the flow of vehicles per second):

Eqn. 3 The described method is developed for isolated fixed-time signals but also provides delay calculation for vehicle actuated signals. Measurement of the green activation times, the length of the green phases, the signal sequence and the intensities for each separate cycle provides delay estimation for vehicle actuated signals. An exception for this model is the use of multiple green phases per signal sequence. This case can be included in the first term at Equation 2.

The present invention utilizes probe data to determine performance at intersections. As described above, probe data may be obtained from GPS navigation devices associated with vehicles, or indeed, any other type of mobile device passing through the intersection with positioning capability. For ease of reference, the embodiments of the invention are illustrated by reference to probe vehicle data obtained from vehicle navigation devices, e.g. PNDs located in vehicles or integrated systems. The use of GPS navigation devices is increasing rapidly providing the momentum needed for a network wide application of probe data in traffic studies.

Tom Tom International B.V. is one of the largest manufacturers of consumer GPS navigation devices in the world, and has been collecting probe data from GPS navigation equipment since 2007. The data comprises location measurements of navigational equipment delivering a probe dataset on a global scale. Privacy filtering ensures that drivers remain anonymous and guarantees the privacy of users. Map-matching algorithms are used to increase the accuracy of the measurements and link the GPS location of vehicles to the road network, producing a network-wide probe dataset. The probe data comprises GPS location measurements which are stored on the PND together with the time of the measurements. The GPS receiver stores the location of the device during every second of a trip.

The present invention uses such probe data to derive delay times for manoeuvres at intersections, and indeed to identify the manoeuvres themselves. The illustrated examples used probe data collected from consumer GPS navigation devices at two intersections in the Dutch city of Delft. As a reference the traffic volume is also measured with loop detection equipment at traffic signals at the intersections and the green phases are monitored at the traffic control device. This enables reference time delay values to be obtained using conventional techniques as discussed above. In this case, a steady-state approach described in Webster, F.V and B.M Cobbe, "Traffic Signals" London, UK, Road Research Lab, Technical paper no 56 HMSO, Editor 1966, and Akgelik, R " Traffic signals: Capacity and Timing Analysis", Research Report 123, Australian Road Research Board, Melbourne, Australia 1981 , was selected for the estimation of delay based on traffic counts from loop detectors and signal monitoring.

Figure 6a illustrates the manoeuvres 1-12 possible at the first intersection. Figure 6b illustrates schematically the location of fixed loop traffic detectors at the intersection which are used in determining some comparative data.

Figure 6c illustrates the manoeuvres 1 -12 possible at the second intersection. Figure 6d illustrates schematically the location of fixed loop traffic detectors at the intersection which are used in determining some comparative data.

The speed limits at the first intersection comprise 70km/h on the main stream (East link) and 50km/h on the secondary streams. At the second intersection the speed limits comprise 70km/h on all links. On average, intersection 1 handles a total traffic volume of 27000 vehicles per day and intersection 2 handles a total traffic volume of 17000 vehicles per day. At intersection 1 , loop detection is not placed at direction 7, 8 and 12. At intersection 2, loop detection is not available at directions 2 and 3.

The probe data relating to the travel of vehicles across each intersection was analysed, and probe traces combined and stored as manoeuvres in the form of turning movements at the test case intersections based on the time of crossing, the covered distance and GPS accuracy at the time of measurement. Using a multi-source multi-destination Dijkstra algorithm each individual measurement was analyzed and linked to the most probable location on the road based on the chosen route of the vehicle. The resulting dataset comprises for each turning movement the moment of arrival at the intersection, the moment of departure from the intersection and the Origin-Destination (OD) of the movement. The OD distribution defines the ratio of the total traffic volume at the intersection per turning movement within a specified time period. The OD distribution was calculated for both intersections. Probe counts were assessed per turning movement and the distribution calculated for the complete intersection.

The measurement of turning movements started with the selection of an appropriate probe data sample size, i.e. the number of measurements/traces. The sample size is determined by the number of probe measurements and increases with the length of the data collection period. The sample size chosen balanced using a large enough sample to obtain a smooth distribution, and avoiding excessively large sample sizes which require longer collection periods. This may lower the level of detail and enable seasonal changes to affect the distribution of turning movements. An optimal sample size may be obtained by considering the average absolute error of all individual movements. In the example, it was found that around 950 measurements gave rise to an appropriate dataset.

The measurement of time delay was carried out as follows using the probe data.

The probe data was used to directly measure the time taken by vehicles to perform particular manoeuvres at the intersections (the "transit time" for the intersection when performing the manoeuvre). By consideration of the resulting probe traces, for all probe vehicles that entered the study area, the manoeuvre, e.g. turning movement, was identified and the related transit time stored in respect of movements taking place within a given time period. The time was determined by reference to an arrival and departure location at the intersection, the transit time being the time taken to pass from the arrival to the departure location when performing the given manoeuvre therebetween. This was done by consideration of Tenure and T aiTiV ai. To minimise the influence of external factors and driving behaviour, the arrival and departure locations were taken to be sufficiently far from the intersection to include the braking and acceleration behaviour of vehicles in the transit time. This was repeated for all time periods of interest.

In accordance with the invention, the time delay obtained for a given manoeuvre is relative to a free flow time for performing the manoeuvre. Thus the time delay is obtained by comparison of the determined transit time and the free flow travel time when performing the same manoeuvre. The free flow travel time is the transit time under conditions where there is substantially no interference on movement of vehicles at the intersection .

The free flow time (T fre e fiow) was obtained as follows. Based on the local speed limits a reference free flow travel time was calculated. In an iterative process the lowest measured travel times according to probe data relating to movements across the intersection (in a given predetermined time period for obtaining free flow travel time) are identified as free flow movements within a 95% probability interval of the reference free flow travel time. This was an average of 2% of all intersection crossings in the test performed. The average transit time of the free flow turning movements is selected as the free flow travel time. Factors which influence the free flow travel time such as the layout and surroundings of the intersection are automatically taken into account as the free flow is determined based on probe data. The time period for determining free flow travel time was taken to be sufficiently large to include a meaningful proportion of probe data which related to free flow type movements.

Implementation of Equation 1 provides the delay per probe vehicle movement when performing the manoeuvre of interest for a given time period.

The individual probe vehicle delays from a complete three month period were combined to create the average delay distribution per day. The average delay was calculated for 15 minute aggregation intervals. This was done between 07:00 and 21 :00. For the analysis only working days are taken into account to create a clear picture of the differences between rush hour and off peak conditions.

In the test, 7262 observations were made over the 3 month period at intersection 1 and 12980 observations at intersection 2. This data is shown in Figure 7 which illustrates the average delay per 15- minute time period for left turning OD movement 3 at intersection 1 between 07:00 and 21 :00. For comparison reference results obtained using a conventional time-dependent stochastic delay model based on the fixed detector data are also included. The probe data gives rise to results showing more noise as the sample size in the test was not sufficient to create a smooth distribution. Nonetheless, the overall average delay shows a strong resemblance to the time-dependent stochastic delay model.

Methods may be used to reduce the amount of noise and locate trends in the distribution obtained using the probe data. By way of illustration, a moving average filter and a Savitzky-Golay filter are selected for the smoothing of the probe delay distribution. Figure 8 shows the application of a moving average and a Savitzky-Golay filter to the average delay per 15-minute time period for left turning OD movement 3 at intersection 1 between 07:00 and 21 :00. As shown in Figure 8, the smoothing process results in a reduction of noise and the probe distribution shows more resemblance to the results of the time-dependent stochastic delay model. The trends in the distribution are clearly visible and the variance is lowered. However the smoothing process also reduces peaks in the distribution resulting in data loss. In the example this results in a maximum peak reduction of 35% for the Savitzky-Golay filter and 60% for the moving average filter.

The calculated free flow travel time using probe data takes into account the delay caused by the signal control device. The results show the effect of this assumption. At periods with a very low traffic demand (night time) the delay distribution approaches zero seconds on some of the movements. The time-dependent stochastic delay model however indicates a delay of 10 to 15 seconds during these periods.

It will appreciated that whilst various aspects and embodiments of the present invention have heretofore been described, the scope of the present invention is limited to the particular arrangements set out herein and instead extends to encompass all arrangements, and modifications and alterations thereto. For example, whilst the embodiments described in the foregoing description refer to GPS, it should be noted that the devices may utilise any kind of position sensing technology as an alternative to, or indeed in addition to, GPS. For example, the devices may utilise other global navigation satellite systems, such as the European Galileo system. Equally, it is not limited to satellite-based systems, but could readily function using ground- based beacons or other kind of system that enables the device to determine its geographic location. It will also be understood by persons of ordinary skill in the art that whilst the preferred embodiment may implement certain functionality by means of software, that functionality could equally be implemented solely in hardware (for example by means of one or more SICs (application specific integrated circuit)) or indeed by a mix of hardware and software.

Lastly, it should be noted that whilst the accompanying claims set out particular combinations of features described herein, the scope of the present invention is not limited to the particular combinations hereafter claimed, but instead extends to encompass any combination of features or embodiments herein disclosed irrespective of whether or not that particular combination has been specifically enumerated in the accompanying claims at this time.