Abstract:
A route guidance system, for providing individualized route guidance to from at least one and up to each one of a plurality of selected individual vehicles, which are system participants, and which are moving in at least one traffic stream of a plurality of vehicles is disclosed. Various embodiments of the system commonly include a digital cellular operator, a route guidance web server, and a central traffic light computer. In addition, each vehicle that is a system participant, is provided with means, such as a cellular phone, for transmitting and receiving information, such as vehicle position, destination, and route information, as well as with means for displaying information, such as a recommended route of travel from the vehicle&#39;s current location to its destination. Certain embodiments of the system utilize satellite-provided photographic data showing traffic density. A method of providing rout guidance to vehicles is also disclosed.

Description:
FIELD OF THE INVENTION 
     The present invention relates to apparatus and methods for providing route guidance to vehicles. 
     BACKGROUND OF THE INVENTION 
     Navigation systems which compute a route for a vehicle designed to bring the vehicle from its current location to a desired location are known. 
     A document entitled “DynaMIT:Task C Report”, describes a traffic assignment system and notes, inter alia, that “In an (ideal) system . . . where there is two-way communication between the traffic control center and every vehicle in the network, perfect information about the vehicle location and possibly its origin and destination, can be obtained. While such perfect systems are possible in the future, most existing surveillance systems are limited to vehicle detectors located at critical points in the network. The information provided by these traffic sensors therefore, must be used to infer traffic flows, queue lengths, incidents, etc., at all locations of the network.” 
     Another document discussing pertinent technology is entitled “DynaMIT:DYnamic network assignment for the management of information to travellers.” 
     The disclosures of all publications mentioned in the specification and of the publications cited therein are hereby incorporated by reference. 
     SUMMARY OF THE INVENTION 
     The present invention seeks to provide an improved route guidance system. 
     There is thus provided, in accordance with a preferred embodiment of the present invention, a route guidance system including a traffic velocity computer operative to receive the following information: a plurality of locations, separated by a known time interval, of at least one vehicle within traffic separating a moving vehicle&#39;s current location from the selected destination, and a route assigned to at least one vehicle within the traffic, and to compute at least one velocity characteristic of the traffic, and a route selecting computer operative to receive a selected destination of the moving vehicle and a current location of the moving vehicle, and to compute a route from the moving vehicle&#39;s current location to the moving vehicle&#39;s selected destination, at least partly as a function of the at least one velocity characteristic. 
     Also provided, in accordance with another preferred embodiment of the present invention, is a traffic velocity monitoring system including a representation of an area in which traffic travels, a vehicle location monitor operative to receive vehicle location information, from a multiplicity of moving vehicles, as to their current location, and a per-vehicle velocity computer operative to derive, from the vehicle location information and the representation, an average velocity of at least one individual moving vehicle from among the multiplicity of moving vehicles. 
     Further in accordance with a preferred embodiment of the present invention, the system also includes a global velocity computer operative to receive average velocities of each of a plurality of vehicles from the per-vehicle velocity computer and to compute therefrom an average velocity of traffic including the plurality of vehicles. 
     Additionally provided, in accordance with another preferred embodiment of the present invention, is a route guidance system including a traffic information accumulator operative to accumulate up-to-date information characterizing traffic including a route assigned to at least one vehicle within the traffic, and a route selecting computer operative to compute a route from a moving vehicle&#39;s current location to the moving vehicle&#39;s selected destination, at least partly as a function of the traffic characterizing information. 
     Further in accordance with a preferred embodiment of the present invention, the route computed by the route selecting computer is fed back to the traffic information accumulator and is employed by the accumulator to generate anticipated traffic information estimating characteristics of traffic separating a future location of the moving vehicle from the moving vehicle&#39;s selected destination. 
     Still further in accordance with a preferred embodiment of the present invention, the route selecting computer includes a dynamic route selecting computer operative to provide the moving vehicle with ongoing modifications of the route at least partly as a function of the anticipated traffic information. 
     Additionally in accordance with a preferred embodiment of the present invention, the route selecting computer randomly selects at least a portion of at least one vehicle&#39;s route from among several candidate route portions for that vehicle, the random selection being biased by the relative merits of the candidate route portions for the vehicle. 
     Further in accordance with a preferred embodiment of the present invention, the traffic information accumulator is also operative to receive up-to-date information characterizing permanent and/or transient road conditions in road segments separating the vehicle&#39;s current location from the vehicle&#39;s selected destination. 
     Further in accordance with a preferred embodiment of the present invention, the transient road conditions include states of multi-state traffic governing elements. 
     Still further in accordance with a preferred embodiment of the present invention, the multi-state traffic governing elements include at least one of the following: a traffic light having more than one possible schedule, and a digital sign displaying any of a plurality of route-guiding messages. 
     Further in accordance with a preferred embodiment of the present invention, the traffic information accumulator is operative to provide information to the multi-state traffic governing elements and the multi-state traffic governing elements are operative to select a state at least partly in response to the information. 
     Still further in accordance with a preferred embodiment of the present invention, the accumulator includes a traffic flow simulator operative to generate at least some of the anticipated traffic information. 
     Further in accordance with a preferred embodiment of the present invention, the information characterizing traffic includes quantitative information. 
     Still further in accordance with a preferred embodiment of the present invention, the route selecting computer includes a multiplicity of independent route selecting units located within each of a multiplicity of vehicles respectively. 
     Additionally in accordance with a preferred embodiment of the present invention, the route selecting computer includes a central unit operative to compute a route for each of a multiplicity of vehicles and to transmit each vehicle&#39;s route to that vehicle. 
     Also provided, in accordance with another preferred embodiment of the present invention, is a route guidance system including a traffic velocity computer operative to accept a plurality of locations, separated by a known time interval, of at least one vehicle within traffic separating the moving vehicle&#39;s current location from the selected destination, and to compute at least one velocity characteristic of the traffic, and a route selecting computer operative to receive a selected destination of a moving vehicle and a current location of the moving vehicle, and to compute a route from the moving vehicle&#39;s current location to the moving vehicle&#39;s selected destination, at least partly as a function of the at least one velocity characteristic. 
     Further in accordance with a preferred embodiment of the present invention, the route selecting computer is operative to compute and display an estimated arrival time for the moving vehicle. 
     Still further in accordance with a preferred embodiment of the present invention, the system also includes a route display unit operative to display to a driver of the moving vehicle, at least one driver direction derived from the route. 
     Also provided, in accordance with another preferred embodiment of the present invention, is a route guidance method including receiving the following information: a selected destination of a moving vehicle, a current location of the moving vehicle, and a plurality of locations, separated by a known time interval, of at least one vehicle within traffic separating the moving vehicle&#39;s current location from the selected destination, and a route assigned to at least one vehicle within the traffic, computing at least one velocity characteristic of the traffic, and computing a route from the moving vehicle&#39;s current location to the moving vehicle&#39;s selected destination, at least partly as a function of the at least one velocity characteristic. 
     Also provided, in accordance with another preferred embodiment of the present invention, is a traffic velocity monitoring method including providing a representation of an area in which traffic travels, receiving vehicle location information, from a multiplicity of moving vehicles, as to their current location, and deriving, from the vehicle location information and the representation, an average velocity of at least one individual moving vehicle from among the multiplicity of moving vehicles. 
     Also provided, in accordance with another preferred embodiment of the present invention, is a route guidance method including accumulating up-to-date information characterizing traffic including a route assigned to at least one vehicle within the traffic, and computing a route from a moving vehicle&#39;s current location to the moving vehicle&#39;s selected destination, at least partly as a function of the traffic characterizing information. 
     Further provided, in accordance with another preferred embodiment of the present invention, is a route guidance method including providing the following information: a selected destination of a moving vehicle, a current location of the moving vehicle, and a plurality of locations, separated by a known time interval, of at least one vehicle within traffic separating the moving vehicle&#39;s current location from the selected destination, computing at least one velocity characteristic of the traffic, and computing a route from the moving vehicle&#39;s current location to the moving vehicle&#39;s selected destination, at least partly as a function of the at least one velocity characteristic. 
     Also provided, in accordance with still another preferred embodiment of the present invention, is a route guidance system including a traffic quantifier operative to receive the following information: traffic location information describing a location of at least one vehicle within traffic separating a moving vehicle&#39;s current location from the selected destination, and a route assigned to at least one vehicle within the traffic, and to compute at least one quantitative characteristic of the traffic, and a route selecting computer operative to receive a selected destination of the moving vehicle and a current location of the moving vehicle, and to compute a route from the moving vehicle&#39;s current location to the moving vehicle&#39;s selected destination, at least partly as a function of the at least one quantitative characteristic. 
     Also provided, in accordance with another preferred embodiment of the present invention, is a route guidance method including receiving the following information: a selected destination of a moving vehicle, a current location of the moving vehicle, and a route assigned to at least one vehicle within the traffic, computing at least one quantitative characteristic of the traffic, and computing a route from the moving vehicle&#39;s current location to the moving vehicle&#39;s selected destination, at least partly as a function of the at least one quantitative characteristic. 
     Further provided, in accordance with yet another preferred embodiment of the present invention, is a route guidance system including a traffic quantification computer operative to provide a quantitative characterization of traffic separating the moving vehicle&#39;s current location from the selected destination, and a route selecting computer operative to receive a selected destination of a moving vehicle and a current location of the moving vehicle, and to compute a route from the moving vehicle&#39;s current location to the moving vehicle&#39;s selected destination, at least partly as a function of the quantitative characterization. 
     Further in accordance with a preferred embodiment of the present invention, the method also includes employing a global average velocity of a sample of moving vehicles to estimate average velocity of traffic. 
     Still further in accordance with a preferred embodiment of the present invention, the traffic characterizing information employed by the route selecting computer includes information regarding anticipated traffic. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The present invention will be understood and appreciated from the following detailed description, taken in conjunction with the drawings in which: 
     FIG. 1 is a data flow diagram of a driving route guidance system constructed and operative in accordance with a preferred embodiment of the present invention; 
     FIG. 2 is a semi-pictorial semi-block diagram illustration of a driving route guidance system implementing the data flow of FIG.  1  and constructed and operative in accordance with a first preferred embodiment of the present invention; 
     FIG. 3 is a diagrammatic illustration of a preferred implementation of the average traffic speed table+map of FIG. 2; 
     FIG. 4 is a semi-pictorial semi-block diagram illustration of a driving route guidance system implementing the data flow of FIG.  1  and constructed and operative in accordance with a second preferred embodiment of the present invention; 
     FIG. 5 is a simplified flowchart illustration of an individual driver&#39;s interaction with the route guidance system of FIG. 2; 
     FIG. 6 is a simplified flowchart illustration of an individual driver&#39;s interaction with the route guidance system of FIG. 4; 
     FIG. 7 is a simplified flowchart illustration of an individual traffic light control computer&#39;s interaction with the route guidance system of the present invention; 
     FIG. 8 is a simplified semi-pictorial semi-block diagram illustration of a route guidance system constructed and operative in accordance with a preferred embodiment of the present invention which employs aerial photographs to derive traffic information such as traffic density information, the system communicating with vehicles via satellite; and 
     FIG. 9 is a simplified functional block diagram illustration of the route guidance server of FIG. 4, constructed and operative in accordance with a preferred embodiment of the present invention. 
    
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS 
     Reference is now made to FIG. 1 which is a data flow diagram of a driving route guidance system constructed and operative in accordance with a preferred embodiment of the present invention. 
     Data elements are represented as ellipses and arrows, marked by letters A-J, indicate the flow of data. 
     Arrow A indicates a typically periodic probe of vehicle locations, for all vehicles being served by the system or more typically, for only a sample of the vehicles being served by the system. 
     As each sample of vehicles is selected, the location of all vehicles in the sample is computed (e.g. by a digital cellular operator or by any other vehicle location source) at the beginning as well as at the end of some specified time period (e.g. one minute). In the case of digital cellular location vehicle location computation can be performed as a response to messages sent out by these vehicles&#39; mobile phones at the beginning and at the end of this time period. Based on each car&#39;s locations at the beginning and at the end of the specified time period, provided to the system by a digital cellular operator or by any other vehicle location source, the system computes the average velocity of each car belonging to the sample during this time period. For each road segment and each time period the system derives, from the per-car velocity information, the approximate average velocity of all vehicles driving along the road segment during that time period. 
     As shown in FIGS. 5-6, periodic computations of anticipated average traffic velocity in each road segment are preferably performed by simulating traffic through the road network, based on selected routes, and periodically “freezing” the traffic picture, typically at two instances in time which are, say, one minute apart, and computing average velocities in each road segment by comparing the locations of the vehicles at the two instances in time. 
     The size of sample, i.e. proportion of vehicles which are sampled, should be as large as possible, typically restricted only by the digital cellular operator&#39;s limitations. For example, in order to carry out a cellular-based computation of a vehicle&#39;s location, a signal or a message output by the vehicle&#39;s mobile phone is typically provided and thus the limitations of simultaneous message capacity of the actual digital cellular operator are relevant. Similarly, other limitations may exist in embodiments which employ other systems as sources for vehicle location information. 
     The sampling frequency typically depends on the digital cellular operator&#39;s limitations and on the estimated error of vehicles&#39; location. Estimated error depends on the reliability of the source of vehicle location information. This source may, for example, comprise a digital cellular operator, GPS (global positioning system) or any other suitable source. Sampling frequency is typically higher if the vehicle is travelling in the city, relative to a situation in which the vehicle is driving along a freeway. 
     Any suitable source for vehicle location information may be employed, such as GPS information. In the illustrated embodiment, vehicle location is derived by a digital mobile communication network operator, also termed herein “digital cellular operator”, based on messages or signals which are sent by mobile communication devices, such as mobile telephones, mounted on the vehicles. 
     Typically, messages triggering vehicle location computation, which may even be empty messages, are automatically and repeatedly sent out from any mobile phone served by the system once every time slot. Mobile phones located within vehicles falling within the sample send such automatic cellular messages at least one more time during the time slot in which they were selected for the sample. 
     Optionally, different subsets of sampled vehicles are more or less frequently sampled. For example, vehicles travelling in town (rather than between towns or cities) may be more frequently sampled because many detour options are available in town such that the vehicle&#39;s actual trajectory can only be tracked by frequently sampling the vehicle&#39;s location. 
     Arrow B: Destination is typically input by the user, e.g. by voice or by means of a suitable key-in device on the user&#39;s in-car computer. In case the route is not in-car computed, the destination may be sent by the in-car computer to the entity in charge of route computation. 
     Arrows C and D: An individual driver&#39;s route may be selected to minimize the driver&#39;s driving time, based on current and anticipated average traffic speeds on candidate roads and road segments. Alternatively, all drivers&#39; routes may be selected to minimize the total drivers&#39; driving time, again based on current and anticipated average traffic speeds on candidate roads and road segments. 
     Optionally, if two candidate routes are substantially equivalent as to travel time, then route selection involves an unbiased random choice between these two routes. 
     Optionally, if there is only a slight difference between anticipated travel times over two candidate routes, route selection involves a biased random choice between these two routes, where the weighting of the biased random choice depends on the relationship between the average traffic speeds on the two candidate routes, on the relative lengths of the two candidate routes and also optionally on the absolute lengths of the candidate routes and the rate of flow of traffic speed information to users of the system (which is affected inter alia by the sampling frequency or frequencies employed by the system) and/or the time which elapses until new traffic affects average traffic speed. 
     More generally, optionally, road characteristics such as width, number of lanes, length, topography, surface quality, traffic regulations and aesthetics are taken into account when determining anticipated average traffic speeds and/or selected routes. Typically, permanent and time-dependent road characteristics are taken into account. Time-dependent road characteristics include, for example, rainy or snowy conditions which affect effective quality of the road and hence average traffic speed. Another example of a time-dependent road characteristic is an accident, construction project or other road obstructing occurrence which is going to affect the traffic for some time. One way to handle time-dependent road characteristics is to define an “anticipated number of lanes” variable which defines as lanes only those lanes which are not blocked by road-obstructing occurrences. 
     Arrow E: To select a route, the current location of a car is an important input. 
     Arrow F: Selected routes are preferably sent to the system in order to update anticipated average traffic velocity along each road segment. 
     Arrow G: The current average traffic velocity in a specific road segment affects the anticipated average traffic velocity in other roads (or road segments) that the specific road segment leads into, directly or ultimately. 
     Arrows H, I and J: Typically, the route guidance system of the present invention exchanges data with existing traffic light control systems as shown in FIG.  7 . Similarly, the route guidance system of the present invention may exchange data with other computer-controlled systems affecting traffic flow such as ramp traffic control or digital roadside route guidance signs or traffic information signs directing traffic to or away from a certain route, or providing information regarding one or more routes. 
     Reference is now made to FIG. 2 which is a semi-pictorial semi-block diagram illustration of a driving route guidance system implementing the data flow of FIG.  1  and constructed and operative in accordance with a first preferred embodiment of the present invention. In FIG. 2, each vehicle computes its own route as well as, preferably, its own estimated arrival time. It is appreciated that the route guidance web server need not necessarily be a web server and may alternatively comprise a non-web server. 
     Reference is now made to FIG. 3 which is a diagrammatic illustration of a preferred implementation of the average traffic speed table+map of FIG.  2 . The map of FIG. 3 may be stored in any suitable format or representation such as a graph representation or such as a bitmap. The map preferably includes detailed information regarding each road and each segment of each road typically including some or all of the following information: road width, length, number of lanes, topography, surface quality. 
     The traffic flow simulator of FIG. 9 employs the map of FIG. 3 when computing the anticipated average traffic velocity in each road and each segment of each road. 
     Any desired regional traffic speed table may be sent to a vehicle from the average traffic speed table by selecting the contents of the table which pertain to a particular region in which the vehicle is travelling, the region comprising certain roads each of which includes one or more segments. 
     If communication with vehicles is cellular and if the cellular communication system provides a cell-based message broadcasting capability, supported e.g. by a short message system (SMS)), then the network of roads, and hence the table, are preferably divided into regions which correspond to the cells. Thereby, the same regional table or tables may be broadcast to all vehicles within a particular cell, which reduces the communication burden. Typically, more than one regional table is broadcast to vehicles within a particular cell. Specifically, the regional tables of that cell and all its cell neighbors may be broadcast to the vehicles within the cell, in order to anticipate a situation in which a vehicle crosses from cell to cell. 
     Reference is now made to FIG. 4 which is a semi-pictorial semi-block diagram illustration of a driving route guidance system implementing the data flow of FIG.  1  and constructed and operative in accordance with a second preferred embodiment of the present invention. In FIG. 4, the server computes routes and, optionally, estimated arrival times, rather than each vehicle doing so as in FIG.  2 . 
     Reference is now made to FIG. 5 which is a self-explanatory simplified flowchart illustration of an individual driver&#39;s interaction with the route guidance system of FIG.  2 . As shown, the in-car computer typically does not receive the entire average traffic speed table but only a subset thereof pertaining to territory which the vehicle may wish to traverse. The size of the region is typically selected to be large enough such that all information pertaining to the contemplated trip is transmitted to the in-car computer by the route guidance server. 
     FIG. 6 is a simplified flowchart illustration of an individual driver&#39;s interaction with the route guidance system of FIG.  4 . 
     Reference is now made to FIG. 7 which is a self-explanatory simplified flowchart illustration of an individual traffic light control computer&#39;s interaction with the route guidance system of the present invention. 
     FIG. 8 is a simplified semi-pictorial semi-block diagram illustration of a route guidance system constructed and operative in accordance with a preferred embodiment of the present invention which employs aerial photographs to derive traffic information such as traffic density information, the system communicating with vehicles via satellite. 
     The embodiment of FIG. 8 differs from the embodiment of FIGS. 2 and 4 in that: 
     a. The source of traffic information is aerial photographs rather than or in addition to ground-based and/or vehicle originated sources; 
     b. The type of traffic information comprises traffic density information rather than or in addition to velocity information, and 
     c. Communication of the central system with the vehicles is via satellite rather than or in addition to cellular communication. 
     It is appreciated that any of the features of FIG. 8 may be incorporated in isolation or in combination with any other feature into the embodiments of either FIG. 2 or FIG.  4 . 
     FIG. 9 is a simplified functional block diagram illustration of the route guidance server of FIG. 4, constructed and operative in accordance with a preferred embodiment of the present invention. The route guidance server of FIG. 2 may be similar except that the route selection unit is eliminated since route selection is performed by the in-car computer of the individual vehicles. 
     Another application of the present invention pertains to tollway systems. Based on the locations of all vehicles for which localization is possible (e.g. digital cellular operator&#39;s users, vehicles equipped with GPS (global positioning system) etc.) a tollway system may be provided with all necessary information regarding the tollway segments travelled by each car. Therefore all existing toll debit means (e.g. toll gates, tollcards, electronic toll wallet etc.) may be replaced by a system that periodically, e.g. monthly, computes an exact total debit for each vehicle, based upon information listing all toll way segments that the vehicle has passed during the time period in question. 
     Still another application of the present invention pertains to fleet management systems. Based on the location, provided by any suitable vehicle location source, of all vehicles belonging to a fleet, a fleet management system is able to compute the individual average velocity of any car that belongs to the fleet during any time period. Also, the system of the present invention is capable of providing traffic information which would allow a fleet manager to select a vehicle, from among several vacant vehicles in the fleet, which can most quickly arrive at a particular destination, such as the current location of a passenger who has ordered a taxi. Typically, the vacant vehicle to send to a particular destination is selected by selecting, from among the vacant vehicles in the fleet, the one having the shortest estimated arrival time to the destination in question. 
     It is appreciated that the software components of the present invention may, if desired, be implemented in ROM (readonly memory) form. The software components may, generally, be implemented in hardware, if desired, using conventional techniques. 
     It is appreciated that various features of the invention which are, for clarity, described in the contexts of separate embodiments may also be provided in combination in a single embodiment. Conversely, various features of the invention which are, for brevity, described in the context of a single embodiment may also be provided separately or in any suitable subcombination. 
     It will be appreciated by persons skilled in the art that the present invention is not limited to what has been particularly shown and described hereinabove. Rather, the scope of the present invention is defined only by the claims that follow: