SYSTEM AND METHOD FOR ROUTING AUTONOMOUS VEHICLES

A system for routing a vehicle includes a prediction module configured to receive traffic data in which the traffic data is communicated to the system via a wireless communication link. An information design engine is configured to receive a current traffic volume and a traffic prediction based on the traffic data from the prediction module and generate one or more route selection decisions for the vehicle in response to the traffic prediction. The one or more route selection decisions are provided to a vehicle control computer configured to control a vehicle steering system and a vehicle motion and braking system.

BACKGROUND

Many automobile drivers today rely on a crowdsourced traffic information service, such as WAZE®, to assist them in making routing decisions as they progress from their departure location to their destination location. These traffic information services provide near real-time information to the drivers with respect to traffic conditions on the roadways that link the driver's point of departure and destination. The information that these services provide is obtained by feedback from the vehicles pertaining to driving times as well as reports from the drivers. Drivers may then make informed decisions with respect to alternative route choices. With progress in autonomous vehicles is advancing rapidly the rapid appearance of such vehicles can be expected. Autonomous vehicles are already deployed as research vehicles and semi-autonomous vehicles with varying degrees of driver assistance are already commercially deployed. Fully autonomous vehicles in which the driver assumes a passive role, assuming control in emergency situations, are expected in the near future. Ultimately, autonomous vehicles without human drivers will appear. Autonomous vehicles relying on GPS and fixed waypoints between departure and destination will be subject to the same dynamic traffic conditions that human drivers try to mitigate by using crowdsourced traffic information services. Consequently, there is a need in the art for systems that leverage crowdsourced traffic information to provide dynamically adjusted routing decisions to the vehicle.

NOTATION AND NOMENCLATURE

“Exemplary” as used herein means “serving as an example, instance, or illustration.” An embodiment described herein as “exemplary” is not necessarily to be construed as preferred or advantageous over other embodiments.

DETAILED DESCRIPTION

FIG. 1shows a data flow block diagram of a vehicle routing system100in accordance with an exemplary embodiment. System100includes a server102that provides route selection decisions to a plurality of vehicles104. Three vehicles104are shown for the purpose of illustration. It would be appreciated by those skilled in the art that a server102would be providing route selection decisions to perhaps several tens of vehicles104. Further, a system100would comprise a farm of servers102. Each vehicle104includes a vehicle control computer106coupled to a steering system108and a motion and brake system110. Steering system108and motion and brake system110operate the steering, power and brake mechanisms of the vehicle (not shown inFIG. 1) as commanded by vehicle control computer106. Thus, in this example embodiment, route selection decisions, as described further below, would be received by vehicle control computer106, and along with position data from a vehicle Global Positioning System (not shown inFIG. 1) mapped into commands to steering system108.

Server102includes a database management system (DBMS)112and a database (DB)114. DB114holds both historic traffic data and real-time traffic data which may include crowdsourced traffic data116. DBMS112manages DB114and provides traffic data, as described further below, to a prediction module118and to an information design engine120. Additionally, DBMS112may receive weather data113from an external source which may also be provided to prediction module118. An example of sources of weather data include GroundTruth® from WeatherCloud, Inc., Boulder, Colo. As described further below, prediction module118makes statistical predictions of the traffic on possible routes between a departure location and destination location of a vehicle104. The predictions are based on both the real-time traffic data119, e.g. current traffic volume, and historic traffic data and weather data121maintained in DB114. The predictions are provided to information design engine120. Further, in at least some embodiments, information design engine120may receive vehicle data124from vehicles104. As described further below, such data may include vehicle type and toll budget information. As described further below, information design engine120generates route selection decisions122for each vehicle104and conveys them to the vehicles as vehicles104as they progress from their respective departure locations to destination locations. Stated otherwise, prediction module118is configured to receive traffic data which is communicated to system via a wireless communication link. Information design engine120is configured to receive current traffic volume and a traffic prediction based on the traffic data from the prediction module. Information design module120generates one or more route selection decisions for a vehicle104in response to the traffic prediction. The one or more route selection decisions are then provided to vehicle control computer106that is configured to control a vehicle steering system108and a vehicle motion and braking system110. Because of workload demands in generating routing decisions, particularly in what amounts to substantially real time, information design engine120is instantiated in hardware, that is, as a hardware device. For example, in at least some embodiments, information design engine may be an application-specific integrated circuit (ASIC). Other instantiations may include a field-programmable gate array (FPGA), or similar devices. It would be understood by those skilled in the art that a server102includes other, conventional components such as central processing units (CPUs), memory, communication and network interfaces and the like that have not been shown inFIG. 1so an not to obscure the descriptions in unnecessary detail inasmuch as such details are not necessary to obtain a complete understanding of the present invention and are within the skills of persons of ordinary skill in the relevant art. Likewise, it would be understood that interconnections between components in server102, and between server102and vehicles104reflect logical interconnections and data transfer paths rather than a particular network or physical link architecture. Thus, interconnections may be instantiated by wired connections, wireless connections or combinations thereof. For example, routing selection decisions122may, in at least some embodiments be conveyed to vehicles104over a wireless communication link that is part of a cellular communication network. Likewise, vehicle data124may be sent to server102via a similar wireless link. However, it would be understood by those skilled in the art, that the principles disclosed herein do not depend on a particular wireless communication architecture or the particular data transport protocols employed thereon.

FIG. 2shows a data flow block diagram of a vehicle routing system200in accordance with another exemplary embodiment. Similar to system100,FIG. 1, system200includes a server202that provides route selection decisions to a plurality of vehicles204. Three vehicles204are again shown for the purpose of illustration. Further, a system200would similarly comprise a farm of servers202. Each vehicle204includes a vehicle control computer106coupled to a steering system108and a motion and brake system110. Steering system108and motion and brake system110operate the steering, power and brake mechanisms of the vehicle (not shown inFIG. 2) as commanded by vehicle control computer106. In system200, each vehicle204includes an information design engine220coupled to a respective vehicle control computer106. Server202does not include an information design engine. In this example embodiment, the determination of route selection decisions by an information design engine220are thus distributed among the vehicles204themselves, thereby reducing the workload imposed on an information design engine220. Similar to information design engine120,FIG. 1, information design engine220is instantiated in hardware, For example, in at least some embodiments, information design engine may be an application-specific integrated circuit (ASIC). Other instantiations may include a field-programmable gate array (FPGA), or similar devices. Further, in at least some embodiments, the ASIC or FPGA as the case may be may be integrated with vehicle control computer106on a single chip constituting a so-called System on a Chip (SOC) In an embodiment in which information design engine220and vehicle control computer106are discrete devices, route selection decisions226may be communicated to vehicle control computer106via a wired data link or bus. Route selection decisions226along with position data from a vehicle Global Positioning System (not shown inFIG. 2) would be mapped into commands to steering system108by vehicle control computer106, similar to system100,FIG. 1.

Similar to server102,FIG. 1, server202includes a database management system (DBMS)112and a database (DB)114. DB114holds both historic traffic data and real-time traffic data which may include crowdsourced traffic data116. DBMS112manages DB114and provides traffic data, as described further below, to a prediction module118and to an information design engine220. Similar to system100,FIG. 1, DBMS112may receive weather data113from an external source which may also be provided to prediction module118. As described above, prediction module118makes statistical predictions of the traffic on possible routes between a departure location and destination location of a vehicle104. The traffic predictions are based on both the real-time traffic data119, e.g. current traffic volume, and historic traffic data and weather data121maintained in DB114. Traffic predictions228are provided to information design engine220via a wireless link, similar to the route selection decisions122,FIG. 1. Further information design engine220road information230, such as tolls and road capacities, from server202via a wireless link. In system200, vehicle data may be loaded into each information design engine220. The operation of information design engines220is otherwise the same as information design engines120,FIG. 1, and it would be understood by those skilled in the art that the description hereinabove with respect to such operation also pertains to information design engines220. It would also be understood by those skilled in the art that a server202includes other, conventional components such as central processing units (CPUs), memory, communication and network interfaces and the like that have not been shown inFIG. 2so an not to obscure the descriptions in unnecessary detail inasmuch as such details are not necessary to obtain a complete understanding of the present invention and are within the skills of persons of ordinary skill in the relevant art. Likewise, as in system100,FIG. 1, it would be understood that interconnections between components in server202, and between server202and vehicles204reflect logical interconnections and data transfer paths rather than a particular network or physical link architecture. Thus, interconnections may be instantiated by wired connections, wireless connections or combinations thereof.

To further appreciate the principles of the disclosure,FIG. 3shows a schematic representation of a route decision task300in accordance with an exemplary embodiment. In route decision task300, a vehicle302has a choice between two routes: route304and route306. Each route may have a different capacity to handle traffic which is accounted for by capacity s1on one of routes304,306and a capacity s2on the other. With Each route may experience congestion308A and308B. Further, there is a possibility of merging traffic310entering one of the routes, in this example route304, via an intersecting road312. The state of merging traffic may be a random variable, θ, with a probability distribution of a number, θ=λ, of merging traffic310being ψ(λ). In at least some embodiments, the probability distribution ψ(λ) may be determined based on the real-time and historic traffic data by a prediction module118as described above in conjunction withFIGS. 1, 2. Note that the probability of no merging traffic310is 1−ψ. The congestion308A on the route304is characterized by a queue length D1and the congestion308B on route306by a queue length D2. The values of D1and D2may be obtained from real-time crowdsourced traffic data as described above in conjunction withFIGS. 1, 2. An information design engine, e.g.120,FIG. 1 or 220,FIG. 2, then determines a stochastic route selection decision by the minimization of the expected waiting time of vehicle302:

where p(θ) is the probability that the routing decision is route304, conditioned on the true state of the merging traffic310being θ Eθis the expectation operator over the ensemble of merging traffic and minp(θ)denotes minimum of the expected value. The probability that the routing decision is route306is 1−p(θ).

FIG. 4shows a schematic representation of a route decision task400in accordance with another exemplary embodiment. In this embodiment, a vehicle402confronts a routing choice between a first route404and a second route406. Further, one of the routes, say406, is tolled, measured by the quantity, τ. The case of both routes being free in accounted for in the decision task as described further below by setting τ=0. Both routes are subject to congestion408A,408B represented by queue lengths D0and D1, respectively. Again, there is a possibility of merging traffic410entering, in this example, the free route404, via an intersecting road412. Again, the state of merging traffic is a discrete random variable, θ, having a probability mass function (PMF) ƒ(θ). The PMF may, be determined based on historical traffic data by a prediction module118as previously described. As before, each route has a capacity, here denoted by capacity s0on free road404and a capacity s1on toll road406. Further, in this exemplary embodiment, a vehicle402can have a private type, denoted by the quantity c, which is a measure of the disutility per unit time of delay. The higher the value of c, the tighter the schedule a vehicle402may have. In a system exemplified by system100,FIG. 1, a vehicle402's private type may be communicated to an information design engine120in vehicle data124. A vehicle may choose to cheat and report a vehicle type c′ different from its true type. Because a vehicle may report a type other than its true type, from the perspective of the information design engine, the type, c is treated as a random variable with PMF g(c). The PMF g(c) is assigned by the vehicle owner or operator. With b, denoting the objective function of a vehicle402arriving at its destination, the utility function of a vehicle402is given in Equation (2):

The utility function is also referred to as the payoff function. The quantity b is set by a vehicle owner or operator as a measure of the value it assigns to the trip from a starting point to a destination point. Thus the utility function or, equivalently the payoff function, is a measure of the value assigned to the trip diminished by the disutility arising from the delay, or waiting time, on a route, and further diminished by the toll on the toll road. Here t0(θ) denotes the waiting time of a vehicle402if it travels on toll road406and t1denotes the waiting time if it travels on free road404. Note that t0depends on the state of merging traffic inasmuch as the delay time would be expected to increase in the presence of merging traffic. Thus, the type, c weights the waiting time giving it more or less effect as the case may be in accordance with the tightness of the vehicle's schedule. With the probability of a toll road406routing decision denoted by τ(θ, c′) and a free road404routing decision given by 1−π(θ, c′). To optimize a route selection decision from the perspective of a vehicle402, an information design engine minimized the total disutility from waiting times, as described further below, based on the ex post probability of taking toll road406: a0(1−π(θ, c′))+a1π(θ, c′). Here a0and a1 represent vehicle actions with each taking values in {0,1}, where, if the vehicle takes follows the route selection decision to take toll road406, a0=0 and a1=1, and vice versa if the vehicle does not follow the route selection decision. In other words, by basing the minimization on the aforesaid ex post probability, a vehicle has no incentive to ignore the route selection decision provided by the information design engine. Then, a vehicle402's expected utility is, Equation (3):

If a vehicle reports its true type and obeys the route selection decision, then c′=c, and a0=0 and a1=1. The utility is then Uπ(c,c, 0, 1) which is hereinafter simply denoted by Uπ(c). An information design engine, e.g.120,FIG. 1 or 220,FIG. 2, then determines a stochastic route selection decision by the minimization of the expected disutility of vehicle402:

For example, an information design engine120(FIG. 1) or220(FIG. 2) may, in at least some embodiments, use a simplex method, or, alternatively, an interior point method in implementing this minimization.

FIG. 5shows a schematic representation of a route decision task500in accordance with yet another exemplary embodiment. In task500, a vehicle502travels from a starting point504to a destination point506via a road network508. A path from starting point504to destination point506comprises a set of road segments, defined by edges510and intersections512therebetween. An exemplary path514comprises edges, e1, e2, e3, e4, e5, e6, e7, e8, e9, e10, e11and e12. Each edge510has a predetermined capacity, sei, where the index i runs from 1 to n, with n representing the total number of edges510in road network508connecting a starting point504to a destination point506. Further, some edges510may experience congestion516of varying degrees (denoted by cross-hatching). A vehicle502departing from starting point504at a time, t, is informed of a queue length, denoted De(t) on each edge510. As previously described, the queue lengths may comprise crowdsourced traffic data (e.g. crowdsourced traffic data116,FIG. 1) and communicated to a vehicle502via a wireless link. However, beyond some boundary518, accurate data may not be available and therefore in determining a route selection decision an information design engine regards the queue length as a random variable {tilde over (D)}E=({tilde over (D)}e)eϵEhaving a cumulative distribution function (CDF) {tilde over (F)} where E denotes the set of all edges510connecting starting point504and destination point506. The travel time on the first edge, e1is given by Equation (5):

Then, the travel time in the ithedge, eiwhere the index I runs from 2 to n is, Equation (6):

And, the total travel time along a path, p, from starting point504to destination point506, such as exemplary path514is thus, Equation (7):

Further, at least some segments, i.e. edges, of a path may be tolled. Allowing for tolls to be dynamic, that is dependent on the level of congestion on the tolled segment, the total toll along path, p is given by Equation (8):

The utility function of a vehicle502is then, Equation (9):

Here b is the utility of a vehicle502arriving at destination point506and where ap=1 if route p is chosen; otherwise ap=0. To further define the route selection decision mechanism of an information design engine, e.g. information design engine120,FIG. 1 or 220FIG. 2, the information design engine receives accurate traffic forecasts on the first Ĵ segments of route p. In other words, the information design engine receives a traffic prediction in the form of traffic forecasts on at least a portion of each path between a starting point504and destination point506. For example, the information design engine may receive such traffic forecasts may be received from a prediction module118,FIGS. 1, 2. With the realization of {tilde over (D)}Edenoted {circumflex over (D)}ejthe expected utility is, Equation (10):

where, as in task400,FIG. 4, a vehicle502's reported type is c′ which can be different that its true type, c, and

is the probability that route p is selected given the accurate traffic flow forecast on the set of edges510given by {ej}1≤j≤J, vehicle502's reported type, c. Similar to route selection task400,FIG. 4, if a vehicle502reports its true type and obeys the route selection decision, the utility reduces to Uπ(c, c, {p}pϵP) which is simply denoted Uπ(c). Similar to route selection task400,FIG. 4, an information design engine, e.g.120,FIG. 1 or 220,FIG. 2, determines a stochastic route selection decision by the minimization of the expected disutility of vehicle502:

Further, as a trip may pass several toll segments, an owner or occupant of an autonomous vehicle may, in at least some embodiments, want to specify a toll budget for the trip. In such an embodiment the individual rationality constraint is replaced by a budget constraint:

Here B denotes the budget set by the owner or occupant. In such an embodiment, an information design engine determines the route selection decision in accordance with the following constrained disutility minimization:

In this way, route selection decisions are constrained to keep the total toll expense under the set budget, B. Although the foregoing example is described in terms of a route selection between a particular starting point504and destination point506, it would be appreciated by those skilled in the art having the benefit of the disclosure that an intermediate intersection, e.g. intersection520, may itself be treated as a destination point, and the route selection decision refined by an information design engine by re-optimizing the selection by treating the intermediate intersection, e.g.520, as a new starting point with updated traffic data forecasts on the segments connecting the intermediate intersection520and the destination point506. It would be further appreciated that such re-optimization could be repeated as updated traffic forecasts were provided to the information deign engine by a prediction module, for example.

FIG. 6is a flowchart of a method600for providing routing decisions to a vehicle. Method600starts at block602. In block604, an optimized route decision for a first vehicle between a first route and a second route is determined. The route decision is based on real-time traffic data for the first route and the second route. The route decision is also based on a predetermined probability of a vehicle joining a queue on the first route, input at block606, and a predetermined capacity of each of the first and second routes, input at blocks608,610, respectively. Real-time traffic data comprising a number of vehicles in the queue on the first route is input at block612. Real-time traffic data comprising a number of vehicles in a queue on the second route is input at block614. The optimized route decision minimizes an expected waiting time of the first vehicle. In block616, the optimized route decision is provided to a vehicle control computer in the first vehicle. Method600ends at block618. In at least some embodiments, the predetermined probability of a second vehicle joining the queue is determined by a prediction module based on historic traffic data. Further, in at least some embodiments, the predetermined probability is sent to an information design engine in the first vehicle via a wireless communication link.

TABLE ITable I summarizes the symbols used hereinabove.τThe fee paid to use the toll roads0The capacity of the free roads1The capacity of the toll roadA = {0, 1}The action set. 0 denotes taking the free road; 1 denoted taking the tollroadαAn action in the action setD0The number of vehicles on the free road when the vehicle departsD1The number of vehicles on the toll road when the vehicle departsΘThe set of possible number of merging vehiclesθA possible number of merging vehiclesf (θ)The probability that a number of θ vehicles merging into the free roadt0The vehicle's waiting time if it travels on the toll roadt1The vehicle's waiting time if it travels on the free roaduThe utility function of the vehiclebThe utility of arriving at the destination from the starting pointcThe disutility from per unit time of waiting (delay)g (c)The probability that a vehicle has disutility cπ (θ, c)The probability that the information designer recommends the toll roadunder θ and vehicle's reported cUπThe expected utility of a vehicle under the recommendation πp = (e1, . . . , en)A path p that goes through roads e1, . . . , enDe(t)The current traffic volume (queue length) on the road eδeThe travel time on the road eδpThe travel time on the path pθThe operator of taking expectationThe set of all real numbersBBudgets.t.Such that∀For all∈Element ofminMinimizemaxMaximizeinfInfimum or greatest lower bound

The above discussion is meant to be illustrative of the principles and various embodiments of the present invention. Numerous variations and modifications will become apparent to those skilled in the art once the above disclosure is fully appreciated. For example, an information design engine may base a route selection decision on the departure of multiple vehicles from a starting point. In other embodiments, an information design engine may base a route selection decision on the departure of multiple vehicles at different starting times. It is intended that the following claims be interpreted to embrace all such variations and modifications.