Disclosure of Invention
According to a first aspect of the present invention there is provided a server arranged to process GPS data to generate map data, the map data comprising a plurality of navigable segments representing segments of a navigable route in an area covered by the map, the server being connected with a wireless telecommunications transceiver arranged to receive GPS fixes from a plurality of navigation devices by wireless telecommunications and to send the received GPS fixes to the server, the server comprising a processor arranged to generate at least one speed profile for each segment from GPS fixes from at least two of the plurality of navigation devices, each speed profile comprising an expected speed of travel through the segment, and the server being arranged to subsequently cause the transceiver to send the speed profiles to the navigation devices.
The server may be advantageous in that it allows wireless updating of the speed profile associated with each navigable segment in the area covered by the map data, in particular map data on the navigation device may be updated "in real time", i.e. when the navigation device provides instructions for a determined route. Real-time updates of the map data may provide the navigation device with a better indication of traffic flow along the road segment (as compared to old map data), which may well increase the accuracy with which routing algorithms determine journeys across the area represented by the map data.
The speed profile may be an average speed at which a navigation device comprising the plurality of navigation devices travels through the segment. The speed profile may be an average speed at which the navigation device has travelled through the segment over a predetermined period of time, for example during the last hour. In this way, the speed profile may provide an indication of current traffic behavior.
According to a second aspect of the invention there is provided a method of processing GPS data to generate map data comprising a plurality of navigable segments representing segments of a navigable route in the area covered by the map, the method comprising: transmitting GPS fixes from a plurality of navigation devices to a processor by wireless telecommunications causing the processor to generate at least one speed profile for each road segment from GPS fixes from at least two of the plurality of navigation devices, each speed profile including an expected speed of travel through the road segment; and sending the speed profile to the navigation device by wireless telecommunications.
According to a third aspect of the present invention there is provided a navigation device for determining a route across an area, the navigation device comprising: a wireless telecommunications transceiver; a memory having stored thereon map data including a plurality of navigable segments representing segments of a navigable route in an area covered by the map data, at least one of the navigable segments having a speed profile associated therewith; and a processor arranged to calculate a navigable route using the map data and to recalculate the navigable route using at least one updated speed profile in response to receiving the at least one updated speed profile via the transceiver and if the navigation device is providing routing instructions for the calculated navigable route.
The navigation device may be advantageous in that the determined navigable route is recalculated to account for any changes in the speed profile on which the route of segments of the map data is based. This may increase the accuracy with which the routing algorithm determines a journey across the area represented by the map data.
The navigation device may comprise a positioning device for determining a position fix for the navigation device, the processor being arranged to send the position fix to a server over a telecommunications network via the transceiver such that the server can identify a route that the navigation device has travelled. The positioning device may be a GPS device that generates a GPS fix. In this way, the navigation device can provide location data to the server on the move. This may allow the server to calculate a speed profile representative of the current traffic behavior.
The processor may be arranged to identify segments within a predetermined distance of a current location of the navigation device and to change a speed profile of the identified segments to the updated speed profile or one of the updated speed profiles. The predetermined distance may be a road segment within a particular area around the navigation device, for example a substantially rectangular or circular area around the navigation device. The distance between the navigation device and the edge of the area may be of the order of tens or hundreds of kilometres, preferably between 50 and 200 km. The processor may not change the speed profile of segments outside a predetermined distance of the current location of the navigation device to the updated speed profile. By the processor only changing the speed profile of road segments within a predetermined distance of the navigation device, the amount of processing required is reduced relative to changing all speed profiles. Changing only the speed profile of segments within a predetermined distance of the navigation device may not affect the accuracy of the determined route, as it is unlikely that the vehicle/person with which the navigation device is travelling will travel segments outside the predetermined distance during the time associated with the updated speed profile.
For example, the updated speed profile may be provided to account for dips in the average speed through segments due to accidents and if the navigation device is still travelling on those segments while it is affected by the accident, the navigation device need only change the speed profile of the affected segments. It may be the case that if the navigation device is in a vehicle (e.g. a car), the impact of an accident on road segments hundreds of kilometers from the current position of the vehicle will be clear before the vehicle reaches these road segments. Thus, if the route determined by the navigation device is for a motorised vehicle, the predetermined distance may be on the order of hundreds of kilometres, for example 100 to 200 km. The predetermined distance may be on the order of tens of kilometers if the route determined by the navigation device is for a non-motorized vehicle, such as a bicycle.
The processor may be arranged to determine the predetermined distance from a current speed at which the navigation device is travelling. For example, the predetermined distance may be a current speed of the navigation device multiplied by a preset time, for example one or more hours. The preset time may be a typical time for the traffic behavior to return to normal after an unusual event (e.g., a traffic accident). Alternatively, the preset time may be, for example, an estimated time for which the updated profile is applied, the estimated time being sent by the server to the navigation device.
In another embodiment, the predetermined distance is based on a bandwidth used for transmission of signals between the navigation device and a server providing the updated speed profile. In this way, a balance may be automatically determined between the accuracy of the speed profile of the map data and the amount of data sent to the navigation device. Thus, in one embodiment, the navigation device may only receive updated speed profiles for segments within a predetermined distance of the current location of the navigation device.
According to a fourth aspect of the present invention there is provided a navigation device for determining a route, the navigation device comprising: a wireless telecommunications transceiver; a memory having map data stored thereon; a GPS receiver; and a processor arranged to send a GPS fix obtained by the GPS receiver to a server via a wireless telecommunications transceiver and to calculate a navigable route using the map data upon request from a user.
In this way, the navigation device may provide GPS fixes to the server in real time, or at least pseudo-real time, so that the server may calculate speed profiles for map data and the device may calculate navigable routes.
According to a fifth aspect of the invention there is provided a data carrier containing instructions which, when read by a processor of a server comprising a wireless telecommunications transceiver and the processor, cause the processor to operate in accordance with the first aspect of the invention.
According to a sixth aspect of the invention there is provided a data carrier containing instructions which, when read by a processor of a navigation device, cause the navigation device to operate in accordance with the third or fourth aspects of the invention.
Navigable segments generally represent segments of a road, but may also represent segments of any other path, channel, etc. that may be traversed by a vehicle, person, etc. For example, a navigable segment may represent a segment of a route, river, canal, bicycle route, tow route, railroad line, and so forth.
Reference is made herein to speed data associated with a road segment. It will be appreciated by those skilled in the art that each road segment is represented by data within the map data that provides the map. In some embodiments, such data representative of a road segment may include an identifier that provides a reference to the speed data. For example, the reference may provide a reference to the generated speed profile. This reference may be provided in the form of a look-up table.
In any of the above aspects of the invention, the machine-readable medium may comprise any of the following: floppy disk, CD ROM, DVD ROM/RAM (including-R/-RW and + R/+ RW), hard disk drive, memory (including USB memory key, SD card, memoryTMCompressed flash cards, etc.), magnetic tape, any other form of magneto-optical storage device, transmitted signals (including internet downloads, FTP transfers, etc.), electrical wire, or any other suitable medium.
Detailed Description
Throughout the following description, like reference numerals will be used to identify similar components.
Embodiments of the present invention will now be described with particular reference to Portable Navigation Devices (PNDs). It should be kept in mind, however, that the teachings of the present invention are not limited to PNDs, but are generally applicable to any type of processing device configured to execute navigation software in a portable manner in order to provide route planning and navigation functionality. Thus, in the context of the present application below, a navigation device is intended to include, without limitation, any type of route planning and navigation device, whether embodied as a PND, a vehicle (e.g., an automobile), or indeed a portable computing resource, such as a portable Personal Computer (PC), mobile phone, or Personal Digital Assistant (PDA), that executes route planning and navigation software.
Further, embodiments of the present invention are described with reference to road segments. It should be recognized that the present invention is also applicable to other navigable segments, such as segments of a route, river, canal, bicycle path, tow path, railway line, and the like. For ease of reference, these are collectively referred to as road segments.
It should also be apparent from the following that the teachings of the present invention have utility even in the following situations: where the user is not seeking instructions on how to navigate from one point to another, but merely wishes to be provided with a view of the location. In such a situation, the "destination" location selected by the user need not have a corresponding start location from which the user wishes to start traffic, and thus references herein to a "destination" location or indeed to a "destination" view should not be interpreted to mean that a route must be generated, that travel to a "destination" must occur, or that the presence of a destination requires a corresponding start location to be specified.
With the above provisos in mind, the Global Positioning System (GPS) and the like of fig. 1 are used for various purposes. In general, the GPS is a satellite radio-based navigation system capable of determining continuous position, velocity, time, and in some examples, directional information for an unlimited number of users. Formerly known as NAVSTAR, the GPS incorporates a plurality of satellites that orbit the earth in extremely precise orbits. Based on these precise orbits, GPS satellites can relay their positions as GPS data to any number of receiving units. However, it should be understood that a global positioning system may be used, such as the GLOSNASS, European Galileo positioning system, COMPASS positioning system or IRNSS (India regional navigation 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 radio signals from GPS satellites, the device determines the precise location of the satellites by one of a number of different conventional methods. In most instances, the device will continue to scan for signals until it has acquired at least three different satellite signals (note that position is not normally determined but can be determined from only two signals using other triangulation techniques). After performing geometric triangulation, the receiver uses the three known positions to determine its own two-dimensional position relative to the satellites. This can be done in a known manner. In addition, acquiring a fourth satellite signal allows the receiving device to calculate its three-dimensional position in a known manner by the same geometric calculation. The position and velocity data may be updated in real-time on a continuous basis by an unlimited number of users.
As shown in fig. 1, the GPS system 100 includes a plurality of satellites 102 orbiting the earth 104. The GPS receiver 106 receives GPS data from a number of the plurality of satellites 102 as spread spectrum GPS satellite data signals 108. The spread spectrum data signals 108 are transmitted continuously from each satellite 102, with the transmitted spread spectrum data signals 108 each comprising a data stream that includes information identifying the particular satellite 102 from which the data stream originated. The GPS receiver 106 typically requires spread spectrum data signals 108 from at least three satellites 102 in order to be able to calculate a two dimensional position. Receiving the fourth spread spectrum data signal enables the GPS receiver 106 to calculate a three dimensional position using known techniques.
Turning to fig. 2a, a navigation device 200 (i.e., PND) including a positioning device (GPS receiver device 106 in this embodiment) and a wireless transceiver (which includes transmitter 165 and receiver 168) is capable of establishing a data session with the network hardware of a telecommunications network, such as a cellular network. The wireless communication may be infrared communication, radio frequency communication (e.g., microwave frequency communication), satellite communication, and the like.
Thereafter, via the telecommunications network, the device 200 can establish a communication channel 152 with the server 150 (which can also involve other networks besides the telecommunications network, such as the internet). Thus, a wireless network connection may be established between the navigation device 200 (which may be, and often 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 navigation device 200 may utilize "mobile phone technology" within the navigation device 200, such as an embedded GPRS modem, and may include internal components and/or an insertable card, such as a Subscriber Identity Module (SIM) card, equipped with the necessary mobile phone technology and/or antenna.
Establishing a network connection between the navigation device 200 and the server 150 using the internet, for example, can be done in a known manner. To this extent, any number of suitable data communication protocols can be employed, such as the TCP/IP layering protocol. Further, the navigation device may utilize any number of communication standards, such as CDMA2000, GSM, IEEE 802.11a/b/c/g/n, and so forth.
The communication channel 152 is not limited to a particular telecommunications communication technology. Additionally, the communication channel 152 is not limited to a single wireless communication technology; that is, channel 152 may include several communication links using a variety of techniques. For example, the communication channel 152 may be adapted to provide a path for electrical, optical, and/or electromagnetic communications, among others, as well as wireless communications. Further, the communication channel 152 may include intermediate devices such as routers, repeaters, buffers, transmitters, and receivers.
In one illustrative arrangement, the communication channel 152 includes telephone and computer networks.
The communication signals transmitted via the communication channel 152 include, but are not limited to, signals that may be required or desired for a given communication technology. For example, the signals may be adapted for use in cellular communication techniques 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), and so forth. Both digital and analog signals may be transmitted over the communication channel 152. These signals may be modulated, encrypted, and/or compressed signals as may be desired by the communication technology.
The server 150 includes, among other components that may not be illustrated, a processor 154, the processor 154 operatively connected to a memory 156 and further operatively connected to a mass data storage 160 via a wired or wireless connection 158. The mass storage device 160 contains storage of navigation data and map information, and may also be a separate device from the server 150 or may be incorporated into the server 150. The processor 154 is further operatively connected to a transmitter 162 and a receiver 164 to transmit information to the navigation device 200 or receive information from the navigation device 200 via the communication 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 communication needs and communication technology used in the communication design of the navigation system 200. Further, it should be noted that the functions of the transmitter 162 and receiver 164 may be combined into a single transceiver.
As mentioned above, the navigation device 200 may be arranged to communicate with the server 150 via the communication channel 152, using the transmitter 166 and receiver 168 to send and receive signals and/or data via the communication channel 152, it being noted that these devices may further be used to communicate with devices other than the server 150. Furthermore, the transmitter 166 and receiver 168 are selected or designed according to the communication needs and communication technology used in the communication design of the navigation device 200, and the functions of the transmitter 166 and receiver 168 may be combined into a single transceiver as described above with respect to fig. 2 a. Of course, the navigation device 200 includes other hardware and/or functional components, which will be described in further detail later herein.
Software stored in the 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 the server 150 may provide includes processing navigation data using various algorithms for the 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 comprise a network server located on a Local Area Network (LAN), Wide Area Network (WAN), Virtual Private Network (VPN), or the like.
The navigation device 200 may be provided with information from the server 150 via an information download, which may be automatically updated constantly or when the user connects the navigation device 200 to the server 150, and/or may be more dynamic when a more constant or frequent connection is made between the server 150 and the navigation device 200 via a wireless connection. For many dynamic calculations, the processor 154 in the server 150 may be used to handle batch processing needs, however the processor (not shown in fig. 2 a) of the navigation device 200 may also handle many processes and calculations, often independent of the connection to the server 150.
Referring to figure 2b, the server 150 is arranged to communicate with a plurality of navigation devices 200a to 200i (in this embodiment) over a cellular telecommunications network 300 and the internet 301. Each navigation device 200a to 200i corresponds to the navigation device 200 described with reference to fig. 2a and has a GPS receiver for obtaining a GPS position fix. In this embodiment, the navigation devices 200a to 200i communicate with base stations 300a to 300c of the telecommunications network 300 and these base stations 300a to 300c then pass signals received from the navigation servers 200a to 200i to the server 150 via the internet 301. Likewise, the server 150 is able to send signals to each of the navigation devices 200 a-200 i via the internet 301 and the appropriate base stations 300 a-300 c.
Referring to fig. 3, it should be noted that the block diagram of the navigation device 200 does not include all of the components of the navigation device, but is merely representative of many example components. The navigation device 200 is located within a housing (not shown). The navigation device 200 comprises a processing circuit including, for example, the processor 202 mentioned above, the processor 202 being coupled to an input device 204 and a display device, such as a display screen 206. Although the input device 204 is referred to herein in the singular, those skilled in the art will appreciate that the input device 204 represents any number of input devices, including keyboard devices, voice input devices, touch pads, and/or any other known input devices used to input information. Likewise, the display screen 206 may include any type of display screen, such as a Liquid Crystal Display (LCD).
In one arrangement, one aspect of the input device 204, the touch pad and display screen 206 are integrated so as to provide an integrated input and display device, including a touch pad or touch screen input 250 (fig. 4) to enable both information input (via direct input, menu selection, etc.) and information display (through the touch pad screen), such that a user need only touch a portion of the display screen 206 to select one of a plurality of display selections or activate one of a plurality of virtual or "soft" buttons. In this regard, the processor 202 supports a Graphical User Interface (GUI) that operates in conjunction with the touch screen.
In the navigation device 200, the processor 202 is operatively connected to the input device 204 via a connection 210 and is capable of receiving input information from the input device 204, and is operatively connected to at least one of the display screen 206 and the output device 208 via respective output connections 212 to output information therefrom. The navigation device 200 can include an output device 208, such as an audio output device (e.g., a speaker). While the output device 208 may generate audio information for a user of the navigation device 200, it should also be understood that the input device 204 may include a microphone and software for receiving input voice commands. Furthermore, the navigation device 200 may also include any additional input devices 204 and/or any additional output devices, such as audio input/output devices.
The processor 202 is operatively connected to the memory 214 via connection 216 and is further adapted to receive/send information from/to an input/output (I/O) port 218 via connection 220, wherein the I/O port 218 is connectable to an I/O device 222 external to the navigation device 200. External I/O device 222 may include, but is not limited to, an external listening device, such as an earbud. The connection to the I/O device 222 may 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 connecting to an ear bud or headset and/or for connecting to a mobile phone, for example, where the mobile phone connection may be used to establish a data connection, for example, between the navigation device 200 and the internet or any other network, and/or to a server via the internet or some other network, for example.
The memory 214 of the navigation device 200 includes a portion of non-volatile memory (for example, to store program code) and a portion of volatile memory (for example, to store data when the program code is executed). The navigation device also includes a port 228 in communication with the processor 202 via a 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 addition of an SD (secure digital) card. In other embodimentsThe port may allow connection of other formats of Memory (e.g., Compact Flash (CF) card, Memory Sticks)TMxD memory card, USB (universal serial bus) flash drive, MMC (multimedia) card, smart media card, microdrive, etc.).
Fig. 3 further illustrates an operative connection between the processor 202 and the antenna/receiver 224 via connection 226, wherein the antenna/receiver 224 may be a GPS antenna/receiver, for example, and thus will serve as the GPS receiver 106 of fig. 1. It should be understood that the antenna and receiver designated by reference numeral 224 are schematically combined for purposes of illustration, but may be separately located components, and may be, for example, a GPS panel antenna or a helical antenna.
Of course, it will be understood by those skilled in the art that the electronic components shown in FIG. 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 input for low voltage DC powering or any other suitable arrangement. Those skilled in the art will also appreciate that the present invention encompasses different configurations of the components shown in fig. 3. For example, the components shown in FIG. 3 may communicate with each other via wired and/or wireless connections and the like. Thus, the navigation device 200 described herein may be a portable or handheld navigation device 200.
In addition, the portable or handheld navigation device 200 of fig. 3 may be connected or "docked" in a known manner to a vehicle, such as a bicycle, motorcycle, car or boat. Such a navigation device 200 can therefore be removed from the engaged position for portable or handheld navigation use. Indeed, in other embodiments, the device 200 may be arranged so as to be hand-holdable to allow navigation by a user.
Referring to fig. 4, the navigation device 200 may be a unit that includes the integrated input and display device 206 and other components of fig. 2a, including but not limited to the internal GPS receiver 224, the processor 202, a power supply (not shown), the memory system 214, and the like.
The navigation device 200 may be located on an arm 252, which itself may be secured to a vehicle dashboard/window/etc. using suction cups 254. This arm 252 is one example of a docking station to which the navigation device 200 can dock. The navigation device 200 may be docked or otherwise connected to the arm 252 of the docking station by, for example, snapping the navigation device 200 to the arm 252. Thus, the navigation device 200 can rotate 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 with the docking station are well known to those skilled in the art.
Turning to FIG. 5, the processor 202 cooperates with the memory 214 to support a BIOS (basic input/output System) 282 that serves 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 the 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) may run. The application software 286 provides an operating environment that includes a Graphical User Interface (GUI) that supports core functions of the navigation device, such as map viewing, route planning, navigation functions, and any other functions associated therewith. In this regard, part of the application software 286 includes a view generation module 288.
The navigation device 200 is arranged so that a user can download map data into the memory 214 or into a memory card in the card port 228. The map data includes a plurality of navigable segments representing segments of a navigable route in the area covered by the map data, each of the navigable segments having a speed profile associated therewith. Each speed profile may include a plurality of average speeds through the road segment at different recurring weekly time periods. The processor 202 of the navigation device 200 is arranged to determine a navigable route requested by a user using the map data and such a navigable route may be based on the speed profile. For example, the processor 202 may use the speed profile to determine a fastest route and/or an estimate of travel time along the route.
In the embodiment being described, the processor 202 of the navigation device is programmed to receive GPS data received by the antenna 224 and to continually store the GPS data within the memory 214, along with a timestamp of when the GPS data was received, to construct a record of the location of the navigation device. Each data record so stored may be considered a GPS fix; i.e. it is a lock on the position of the navigation device and includes a latitude, longitude, timestamp and accuracy report.
In one embodiment, the data is stored on a substantially periodic basis, for example every 5 seconds. Those skilled in the art will appreciate that other cycles will be feasible and that there is a balance between data resolution and memory capacity; that is, when the resolution of the data is increased by taking more samples, more memory space is required to hold the data. However, in other embodiments, the resolution may be approximately 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, a record of the whereabouts of the device 200 at a point in time is constructed.
In some embodiments, it may be found that the quality of the captured data decreases as the period increases and although the extent of degradation will depend at least in part on the speed at which the navigation device 200 is moving, a period of approximately 15 seconds may provide a suitable upper limit.
Although the navigation device 200 is typically arranged to build 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, as it may protect the user's home and the location of other frequent destinations. For example, the navigation device 200 may be arranged to store no data for approximately the first 5 minutes of a journey and/or for approximately the first mile of a journey.
In other embodiments, the GPS may not be stored on a periodic basis, but rather may be stored in memory upon the occurrence of a predetermined event. For example, the processor 202 may be programmed to store GPS data as the device passes through a road intersection, a change in road segment, or other such event.
Further, the processor 202 is arranged to constantly upload a record of the whereabouts of the device 200 (i.e. GPS data and time stamps) to the server 150 via the communication channel 152, including the wireless cellular network 300. The processor 202 is arranged to upload a record of the whereabouts on a substantially real-time basis, but this may inevitably mean that the data is actually constantly transmitted (e.g. every 5, 10, 20, 30, 40, 50 seconds, minutes, etc. or any time in between these times), with relatively short periods in between the transmissions, and so can be more correctly considered pseudo-real-time. In such pseudo real time embodiments the navigation device may be arranged to buffer GPS fixes within the memory 214 and/or on the card inserted in the port 228 and transmit these GPS fixes when a predetermined number has been stored. This predetermined number may be about 20, 36, 100, 200, or any number therebetween. Those skilled in the art will appreciate that the predetermined number is governed in part by the size of the card within the memory 214/port 228.
In the embodiment being described, the record of whereabouts includes one or more trajectories, with each trajectory representing movement of the navigation device 200 over a 24-hour period. Each 24 hours is arranged to coincide with a day on the calendar, but need not be so in other embodiments.
Typically, the user of the navigation device 200 agrees to upload a record of the device whereabouts to the server 150. If not, 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 whether they agree to such use of a record of whereabouts.
The server 150 is arranged to receive a record of the whereabouts of the device and store this record within the mass storage device 160 for processing. Thus, as time passes, the mass storage device 160 accumulates a plurality of track records of the navigation devices 200a to 200i that have uploaded data. From these records, the server 150 is arranged to generate a speed profile, as now described.
As discussed above, the mass storage device 160 also contains map data. Such map data provides information about the location of road segments, points of interest, and other such information typically found on maps.
As a first process, the server 150 is arranged to perform a map matching function between map data and GPS fixes contained within records of whereabouts that have been received and such a process is described with respect to figure 6. Such map matching may be performed in a so-called real-time manner (i.e., when a record of the whereabouts is received) or at a later time after a record of the whereabouts has been recalled from the mass storage device 160.
To increase the accuracy of the map matching, the pre-processing of the records of the whereabouts is performed as follows. Each GPS track, i.e. a 24 hour period of GPS data, is divided into one or more journeys (600) with each journey representing a single journey of the navigation device 200, which is then stored for later processing.
Within each journey, a GPS fix received from the navigation device whose accuracy report is not high enough is rejected 602. Thus, in some embodiments, the GPS fix may be rejected if the accuracy report indicates that signals from less than three satellites 102 are being received by the navigation device 200 with respect to the lock. Further, each trip is pruned when the reported time between locks is above a threshold (604). Each trip through this preprocessing stage is passed for map matching.
In this context, a clipped trip is a trip in which there is a predetermined time period greater than a predetermined time between successive GPS fixes. Thus, it can be inferred that the vehicle has remained stationary and therefore should be considered that the first trip has ended and the second trip has started. Thus, the trimmed stroke becomes two separate strokes.
However, before dividing the trip, a check is made whether the position of the vehicle has changed between the last two fixes, since gaps above the predetermined time between GPS fixes may also result from the loss of GPS signals, and in such cases, the trip is not divided. In the embodiment being described, the predetermined time is about 3 minutes. However, it will be appreciated by those skilled in the art that the gap may be any other suitable time, such as substantially any of the following: 15 seconds, 30 seconds, 1 minute, 90 seconds, 2 minutes, 5 minutes, 10 minutes, or any time in between these times. As discussed below, if the average speed of the navigation device 200 from which a GPS fix is sent is below a predetermined threshold, the data may be rejected in later processing in some embodiments. Such an embodiment may be useful in that it may remove data relating to so-called stop-and-go traffic (which may occur after an accident such as a collision), which may leave residual data more representative of steady state traffic flow.
Each trip is then performed in turn and the lock within the trip is matched to a map from within the map data. Each map includes a plurality of road segments along which travel is possible, with each segment represented within the map as a straight vector.
Program code running on the processor 154 of the server 150 provides a map matcher arranged to step through the or each lock in the journey being processed until it finds a lock that is located within, or sufficiently close to, a road segment so as to assume that the lock has occurred on that road segment (i.e. it is within a distance threshold for that road segment). This threshold allows for less than 100% GPS accuracy and the compressive effect of splitting a road into a set of straight vectors.
Each trip has an initial lock that is more difficult to associate with a road segment than other locks within the trip (i.e., the first lock within the trip) because there are no road segments that have been identified as being available to define a selection of road segments. For this first lock, if multiple road segments are within a threshold (606), the algorithm proceeds to the next GPS lock within the trip (i.e., a second lock) and generates a set of roots from those multiple road segments based on the likely travel as a function of the distance between the 2 locks (i.e., between the first and second locks). If the second lock does not result in a unique candidate segment for the first lock, the algorithm moves to a third lock within the trip and again generates and compares possible routes to attempt to provide a unique candidate segment for the first lock (608). This process may continue until the remaining GPS fixes within the processed trip.
An advantage of such an embodiment is that although any one first lock in isolation may be close to multiple road segments and may not distinguish between those road segments in isolation, further travel (i.e., second and third locks) may be used to determine the identity of the road segment with which the first lock is associated. Thus, a first segment of the journey is determined by the map matcher.
Once the first road segment has been identified for the trip, other locks are processed to identify other road segments. Of course, the next lock of the stroke may be located in the same path as the first lock (612).
Thus, subsequent locks of the journey are processed (610) to determine whether they are within a distance threshold of a segment, and the map matcher is arranged to associate the segment with each of the locks that lie within the distance threshold. When the map matcher processes a lock outside the distance threshold, it is arranged to generate a new set of candidate segments for the lock. However, other definitions may now be added: the next segment is the one connected to the end of the one that has just been processed. These adjacent road segments are obtained from the base map data by a map matcher.
If the map matcher is not able to identify segments continuing from previous segment segments for a given lock at any point because no segments exist within a threshold or they are unable to uniquely identify a single segment, then the map matcher is arranged to step through subsequent locks (616) in order to further define the journey until it can identify a segment that is a unique match. That is, if the nth lock cannot be uniquely associated with a road segment, the identification of the road segment is further defined using the n +1 th road segment. If the n +1 th lock does not result in a unique road segment, then the n +2 th lock is used. In some embodiments, this process may continue until a unique road segment is identified or all GPS fixes for a trip have been processed.
The map matcher is arranged to attempt to uniquely identify a segment; in the embodiment being described, it does not attempt to form a continuous route, but only attempts to match the road segment with the lock. In other embodiments, it may be desirable to attempt to have the map matcher generate a continuous route.
Thus, at the end of the process that the map matcher is arranged to perform, a series of road segments along which the navigation device 200 has travelled in the journey being analysed is obtained. The map matcher then further processes these road segments and assigns the entry time and elapsed time for the segments from the GPS fix. These assigned times are stored within the mass storage device 160 for later processing. It is entirely possible to store multiple GPS fixes for each road segment. However, regardless of how many GPS fixes are associated with each road segment, the average speed for that road segment is calculated using the entry time, GPS fix, and length of the segment (which is stored in the map data in this embodiment). This average speed is then stored within the mass storage device 160 associated with the relevant assigned time and the segment. Information relating to the speed of traffic flow on a road segment and assigned to a road segment may be considered speed data for the road segment.
The server 150 is further arranged to run averaging program code on the processor 154 to provide an averager that processes the assigned times as described below to generate one or more averages therefrom. The averaging process used in this embodiment is now described.
In a first step of the process, an averager groups the average speeds for each road segment on the map based on the time at which the average speed occurred (e.g., the last 5 minutes, 10 minutes, 15 minutes, 30 minutes, or any time in between these times).
Before the average speed resulting from the trip is grouped into a predetermined time period, it is screened in an attempt to increase data quality. In this embodiment, the average speed is only added to a group of predetermined periods if the average speed falls within a predetermined range. In this embodiment, the method excludes speeds that exceed a maximum predetermined threshold (which may be about 180km/h) and furthermore, the method excludes speeds that fall below a predetermined amount of the average speed of the segment over the predetermined period of time (which may be 2km/h, for example). In other embodiments, the maximum permitted speed may be set as the speed limit for the road segment, but those skilled in the art will appreciate that such information may not be accurate in the map data being processed and also that the speed limit for a road segment may not actually give an accurate indication of traffic conditions.
At a predetermined time after the set time period has elapsed (for example, immediately after the set time period has elapsed), an average speed is calculated for each road segment for the set time period. There are several options for calculating the average speed: simple arithmetic or harmonic means or calculating median are used.
Thus, in the embodiment being described and for the map being processed, an average speed for a set period of time that has recently passed is generated for each road segment on the map. It should be further appreciated that, in practice, not necessarily all road segments will have an average speed assigned to them for each set time period, as frequent traversals are infrequent on some roads, particularly during abnormal working hours (e.g., early morning).
However, before the average speed of each road segment is used, quality check is performed. In some embodiments, if less than 5 values are used to compose the average, the average is rejected. Other embodiments may, of course, use different values, such as 2, 3, 4, 6, 7, 8, 10, 20, or more values or any value in between these values.
Also, a further check of the quality of the averages is performed and for each average the standard deviation of the average is divided by the square root of the number of data samples used to make up the average for the segment over the time period. If the result of this calculation is outside a predetermined threshold, the average is rejected again, leaving a gap for the segment for the time period.
Further quality checks may be implemented to reject averages according to any of the following: whether a deviation in the data exceeds a predetermined threshold; there are more than a predetermined number of outliers that exceed a predetermined threshold. Such statistical techniques to ensure the quality of the data should be understood by those skilled in the art.
The set of average values for any given road segment may be considered the measured speed profile for that road segment.
It will be appreciated by those skilled in the art that if a measured speed profile for a road segment has few missing speed values (i.e. all or at least a majority of the predetermined time period has a value), then the segment may be processed and the missing values masked accordingly.
Each average passing these quality checks is considered trustworthy and approved for use in map data. The server 150 then sends these updated speed profiles to the navigation devices 200 a-200 i via the communication channel 152.
Before sending the updated speed profile to the navigation devices 200a to 200i, the processor of the server 150 may check to see how the updated speed profile differs from the current speed profile of the map data being used by the navigation device 200. If the difference is above a predetermined threshold, the updated speed profile is sent to the navigation device, however, if not, the updated speed profile is not sent to the navigation device. This may help reduce unnecessary processing and utilization of available bandwidth.
In another embodiment, the speed profile is not the average speed of the road segment traversed during the most recent set period but a delay added to the current speed profile, for example, the average speed of the current speed profile minus the predicted speed differential, e.g., 5, 10, 15, 20km/h, etc. The predicted speed differential may be calculated using conventional algorithms known to those skilled in the art.
Upon receiving the updated speed profiles, the navigation device 200 changes at least some of the speed profiles of the map data stored in the memory 214 or memory card in the card port 228 to the updated speed profiles. In this way, the speed profile of the map data is updated in pseudo-real time so that the map data stored on the navigation device gives a more accurate reflection of current traffic conditions.
If the navigation device is providing routing instructions for a calculated navigable route, the processor 202 can recalculate the navigable route using the updated speed profile. In this way, the navigation device 200 may provide a route that automatically adapts to changes in average speed of segments traveling through the navigable route.
In one embodiment, the processor 202 of the navigation device 200 does not utilize all of the updated speed profiles received from the server 150, but only changes the speed profile of the road segments within a predetermined distance of the current location of the navigation device 200. For example, upon receiving an updated speed profile, the processor 202 may identify segments within a predetermined distance of the current location of the navigation device and change the speed profile for each of the identified segments to an updated speed profile (if an updated speed profile has been received for the segment). The speed profile of the road sections falling outside said predetermined distance remains unchanged. The predetermined distance may be a stretch of road within a particular area around the navigation device, and in the case of a navigation device for guiding a vehicle, the predetermined distance may be between 50 and 200 km.
For a navigation device that is commissioned to provide a traversable route for various forms of traffic (other than motor vehicles, such as walking, cycling, etc.), the processor 202 of the navigation device 200 can determine the predetermined distance from the current speed at which the navigation device is traveling. For example, the predetermined distance may be a current speed of the navigation device multiplied by a preset time, for example one or more hours.
In another embodiment, the predetermined distance is based on a bandwidth used for transmission of signals between the navigation device and a server providing the updated speed profile.
In this embodiment, the updated speed profile is temporarily maintained in the navigation device 200 for a predetermined length of time (e.g., 1 hour), after which the navigation device 200 changes the speed profile back to the original speed profile or other updated speed profile. An updated speed profile determined from the most recent set time period may provide a better representation of the current traffic conditions for a short period after the set time period, but it may be the case that unless other updated speed profiles are received, the original speed profile (which is based on the average speed calculated over several time periods rather than a single time period) will give a better representation of the traffic conditions at a fairly late time (e.g., 1, 2, or 3 hours after the set time period).
Those skilled in the art will appreciate that an apparatus provided to perform a method as described herein may comprise hardware, software, firmware, or any combination of two or more of these.
It will be appreciated by those skilled in the art that although the term GPS data has been used to refer to location data derived from a GPS global positioning system (as described, for example, with respect to fig. 1), other location data may be processed in a manner similar to the method as depicted herein. Thus, the term GPS data may be replaced by the phrase positioning data. For example, such location information may be derived from location information derived from mobile phone operation, data received at toll barriers, data obtained from induction coils embedded in roads, data obtained from license plate recognition systems, or any other suitable data.