WO2021242416A1

WO2021242416A1 - Systems and methods of translating routing constraints to a map

Info

Publication number: WO2021242416A1
Application number: PCT/US2021/026172
Authority: WO
Inventors: Brett BAVAR; Patrick Niklaus
Original assignee: Rideos Inc
Current assignee: Rideos Inc
Priority date: 2020-05-28
Filing date: 2021-04-07
Publication date: 2021-12-02
Anticipated expiration: 2022-11-28

Abstract

Systems and methods for routing one or more vehicles are provided. In one aspect, a method of routing a vehicle includes receiving a geographic constraint for routing vehicles. The geographic constraint includes a plurality of points on a geographic path and a restriction applied to the plurality of points. The method also includes mapping each point on the geographic path onto a routing map, including transferring the restriction to a corresponding set of one or more edges on the routing map. The method further includes receiving a request to route a vehicle and routing the vehicle using the routing map using the geographic constraint.

Description

SYSTEMS AND METHODS OF TRANSLATING ROUTING

CONSTRAINTS TO A MAP

TECHNICAL FIELD

[0001] The disclosed embodiments relate generally to systems and methods for generating a routing map based on routing constraints.

BACKGROUND

[0002] In the coming years, autonomous vehicle (AV) technology will overcome the present challenges in motion planning and control. For example, autonomous vehicles will be able to stay in lanes, follow cars, avoid pedestrians, and drive as well as or better than a taxi driver. Autonomous vehicles will need only to be instructed where to go and how to get there, making route planning critical in the AV world.

[0003] As developers build core autonomy technology and start to scale their fleets of self-driving or autonomous vehicles, whether for sale to individual consumers or operating their own ride-sharing fleets, these developers will need effective routing technology. The winners and losers in this race will be determined by which companies operate the most efficient networks with the highest vehicle utilization.

SUMMARY

[0004] Autonomous vehicles (AVs) are routed using routing maps that include information that is relevant to autonomous operation of AVs. For example, routing maps used in AV routing may have extremely high precision accuracy (e.g., at the centimeter-level) and include detailed information, such as lane information, traffic-light information, etc. Additionally, routing maps may include information regarding routing constraints, including but not limited to geographic constraints and/or rule-based constraints (such as maneuver-based constraints or speed-based constraints).

[0005] Routing constraints may be determined using any map. For example, routing constraints may be defined on a map that is different from a routing map (e.g., having different map standards, being a different map type from a routing map). Alternatively, a user may define routing constraints based on a routing map. For example, speed-based constraints may be defined on a map (e.g., a road map) that includes traffic speed information. In another example, a user that defines one or more routing constraints may use a map that is available to the user (such as an open source map), rather than defining the one or more constraints on a routing map, which may not be as easily accessible to the user (e.g., because the routing map is proprietary to another party, distinct from the user). In a third example, a user may wish to use routing constraints that are defined on a pre-existing map. In yet another example, a user may define routing constraints on a routing map. In these cases, the routing constraints must be translated or matched to edges (e.g., road edges) in a routing map in order for a routing engine to take the routing constraints into consideration when routing one or more vehicles.

[0006] Routing constraints are used to improve safe and consistent operation of vehicles, especially AVs, and routing maps allow vehicles to operate within the confines of the defined routing constraints. Routing constraints can be displayed as imprecise geometry representing travel along roads. In such cases, translating routing constraints to a routing map includes identifying a most likely sequence of roads or road edges that correspond to the routing constraints. However, translating the routing constraints from a first map to a routing map can be challenging since, in addition to routing constraints being presented in the form of imprecise geometries and topologies, the two maps do not always line up with one another. Methods of map matching that rely on physical (e.g., as-the-crow-flies) distance alone are likely to map, for example, a highway onto a frontage road. Thus, there is a need for techniques that allow routing constraints to be efficiently and accurately translated (e.g., added, updated, matched, mapped) to a routing map. To address the problem with existing techniques, the present disclosure provides systems and methods for mapping routing constraints to a routing map for routing AVs. Some embodiments of the systems and methods described herein consider both physical proximity and a transition probability between adjacent points on the mapped path (e.g., based on routing distance). These systems and methods thus result in more accurate mapping of maps and application of user-defined constraints to routing maps.

[0007] In accordance with some embodiments, a method of routing vehicles includes receiving a geographic constraint for routing vehicles. The geographic constraint includes a plurality of points on a geographic path and a property applied to the plurality of points. The method also includes mapping each point on the geographic path onto a routing map, including transferring the property to a corresponding set of one or more edges (e.g., paths, roads) on the routing map. The method further includes receiving a request to route a vehicle and routing the vehicle using the routing map with the geographic constraint.

[0008] Some embodiments of the present disclosure provide a computer system (e.g., a server system), comprising one or more processors and memory storing one or more programs. The one or more programs store instructions that, when executed by the one or more processors, cause the computer system to perform any of the methods described herein.

[0009] Some embodiments of the present disclosure provide a non-transitory computer readable storage medium storing instructions that, when executed by a computer system having one or more processors, cause the computer system to perform any of the methods described herein.

[0010] These embodiments improve operation of autonomous vehicles by allowing autonomous vehicles to be safely routed on a routing map that includes routing constraints. Thus, such embodiments improve the safety, utility, and energy efficiency of autonomous vehicles by enabling more efficient routing (e.g., by allowing for a safer route).

BRIEF DESCRIPTION OF THE DRAWINGS

[0011] The embodiments disclosed herein are illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings. Like reference numerals refer to corresponding parts throughout the drawings.

[0012] Figure 1A illustrates geographic constraints and a routing map, in accordance with some embodiments.

[0013] Figure IB illustrates geographic constraints superimposed on the routing map shown in Figure 1 A, in accordance with some embodiments.

[0014] Figure 1C illustrates identifying candidate edges on the routing map shown in

Figure IB, in accordance with some embodiments.

[0015] Figures ID - IE illustrate determining candidate probabilities, in accordance with some embodiments.

[0016] Figure IF illustrates determining transition probabilities between candidate edges on a routing map, in accordance with some embodiments.

[0017] Figure 1G illustrates mapping a geographic constraint to edges on a routing map, in accordance with some embodiments.

[0018] Figures 2A - 2F illustrate an example of mapping a geographic constraint to a routing map, in accordance with some embodiments.

[0019] Figures 3A - 3B are block diagrams illustrating an architecture of an autonomous vehicle routing engine, in accordance with some embodiments. [0020] Figure 4 is a block diagram illustrating a client-server environment, in accordance with some embodiments.

[0021] Figure 5A illustrates an example of a user interface for providing geographic constraints, in accordance with some embodiments.

[0022] Figures 5B - 5F illustrate examples of geographic constraints on a routing map, in accordance with some embodiments.

[0023] Figure 5G illustrates an example of a user interface for providing rule-based constraints, in accordance with some embodiments.

[0024] Figures 6A - 6F illustrate a flowchart of a method for generating a routing map with routing constraints, in accordance with some embodiments.

DETAILED DESCRIPTION

[0025] The systems and methods described herein improve routing for vehicles

(including AVs) by allowing routing constraints to be accurately mapped onto a routing map. Thus, such embodiments improve the safety, utility, and efficiency of vehicle routing for on- demand transportation services.

[0026] Figure 1A illustrates geographic constraints and a routing map, in accordance with some embodiments.

[0027] Figure 1A illustrates geographic constraints 110 to 118 and a routing map 104 that includes the geographic constraints 110 to 118 in accordance with some embodiments. In some embodiments, geographic constraints 110 to 118 are provided by a user (e.g., a client or fleet manager). For example, the user may provide the geographic constraints 110 to 118 via a user interface or an application programming interface (API). The geographic constraints 110 to 118 may be formed in response to a user indication on a map (e.g., a user-provided map). For example, a user may draw one or more lines on a map that correspond to roads that the user does not want their fleet to be routed on. In order to implement the geographic constraints 110 to 118 in routing vehicles of a fleet, the geographic constraints 110 to 118 need to be mapped onto a routing map 104 for the fleet. As shown in Figure 1A, routing map 104 includes a plurality of edges 102 that represent roads. The geographic constraints 110 to 118 are overlaid on top of routing map 104 to illustrate how the geographic constraints 110 to 118 could potentially be mapped onto routing map 104. [0028] Figure IB illustrates an enlarged version of routing map 104, as shown in Figure

1 A, that includes the geographic constraints 110 to 118 superimposed on the routing map 104 shown in Figure 1A. A geographic constraint includes a plurality of points on a geographic path and a restriction (or other property) applied to the plurality of points and geographic path. A restriction may be a restriction that disallows a maneuver. In other circumstances, another property, such as allowance of a particular maneuver, may be applied to the plurality of points. For example, a geographic constraint may include a property that allows routing along geographic path of the geographic constraint (e.g., “route only on defined geographic constraints or allow only maneuvers that correspond to defined geographic constraints”). Conversely, another geographic constraint may include a restriction that does not allow routing along the geographic path of the geographic constraint (e.g., “do not route on defined geographic constraints” or “do not allow maneuvers that correspond to defined geographic constraints”). For ease of explanation, the embodiments are described below in terms of “restrictions”. A routing map 104 may include a combination of geographic constraints that correspond to allowed roads and/or allowed maneuvers and geographic constraints that correspond to roads and maneuvers that are not allowed. Examples of geographic constraints for routing a vehicle include different maneuvers such as “do not turn left at this intersection”, “no U-turns”, “do not drive on this road”, “drive only on the indicated roads”, and “no un protected left turns”.

[0029] For example, geographic constraint 110 includes points 103 and 132 that are located on a geographic path 190 (represented by a dashed line), and a restriction applied to the points 130 and 132 and the geographic path 190. In another example, geographic constraint 112 includes three points that are located on a geographic path 192 and a restriction to not allow the left turn maneuver corresponding to the geographic constraint 112. Note that the points corresponding to geographic constraint 116 are not shown in Figure IB for ease of illustration.

[0030] Routing map 104 includes a plurality of edges 102, with each edge corresponding to a road. For example, edge 122 corresponds to a real and physical road or path (e.g., Commonwealth Avenue). Edge 122 is emphasized as a bolded solid line to aid comprehension.

[0031] Mapping a geographic constraint to routing map 104 includes mapping each point of the geographic constraint onto a respective edge of routing map 104. Two different points may be mapped to a same edge and thus, even though each geographic constraint includes two or more points, each geographic constraint is mapped onto one or more edges of routing map 104. Mapping the geographic constraint to routing map 104 also includes transferring the restriction to the one or more edges that correspond to the points of the geographic constraint. A first example of how geographic constraint 110 is mapped to routing map 104 is shown below with respect to Figures 1C - 1G. A second example of how geographic constraint 112 is mapped to routing map 104 is shown below with respect to Figures 2A - 2F.

[0032] Figures 1C - 1G show the steps of mapping geographic constraint 110 to one or more edges 102 of routing map 104 in accordance with some embodiments.

[0033] Referring to Figure 1C, routing map 104 shows a plurality of edges

(e.g., edges 160 to 178) and each edge corresponds to a respective physical road or path, represented as a pair of solid lines. For example, a pair of solid lines represent road 154 and edges 174 and 175 both correspond to road 154 (e.g., a same road). In this example, edge 174 corresponds to a path along road 154 that travels from right to left and edge 175 corresponds to a path along road 154 that travels from left to right. In some embodiments, an edge 102 is directional such that an edge has a start portion and an end portion with the direction of the edge being in a direction pointing from the start portion to the end portion, represented by an arrow. As shown, point 132 is closer to an end portion of edge 174 than a start portion of edge 174.

[0034] Geographic constraint 110 is represented in Figure 1C by points 130 and 132 on geographic path 190 (shown as a dashed line). In order to map point 130 to an edge of routing map 104, a first set of candidate edges on the routing map 104 are identified. In this example, edges 160 - 168 are identified as being proximate to (e.g., near, in the vicinity of) point 130. In some embodiments, as shown, only edges that are located within a predetermined distance from point 130 are included as a candidate edge. For example, dashed circle 140 illustrates an area within a predetermined distance from point 130 (e.g., if the predetermined distance is 500 meters, circle 140 has a radius of 500 meters and point 130 is disposed at a center of circle 140). Edges 161 and 167 are outside the area (e.g., are not within the predetermined distance from point 130) and thus, are not included considered candidate edges for point 130. In this example, edges 160 - 168 are candidate edges for point 130. Note that only a portion (e.g., at least a portion) of an edge has to be located within circle 140 to be considered a candidate edge. Similarly, in order to map point 132 to an edge of routing map 104, a second set of candidate edges on the routing map 104 are identified. In this example, edges 170 - 178 are identified as being proximate to (e.g., near, in the vicinity of) point 132 and thus, are considered candidate edges for point 132. Once a set of candidate edges have been identified for each of the points 130 and 132, each candidate edge is evaluated based on candidate probabilities, described below with respect to Figures ID and IE, and transition probabilities, described below with respect to Figure IF. A candidate probability of a candidate edge is reflective of a proximity of the candidate edge to the corresponding point and a transition probability of a candidate edge is determined by trying to find a most probable path between points of the geographic constraint.

[0035] Referring to Figure ID, the candidate probabilities for each of the identified candidate edges corresponding to point 130 (e.g., edges 160 - 168) are determined based at least in part on a proximity of the candidate edge to point 130. Thus, candidate edges that are located closer to point 130 have a higher candidate probability compared to candidate edges that are located further away from point 130. For example, candidate edge 163 is located close to point 130 and thus, has a high candidate probability of 0.97. In contrast, candidate edge 168 is located far from point 130 and thus, has a low candidate probability of 0.48. In some embodiments, the candidate probability for each candidate edge is calculated based on a mathematical relationship between the proximity of the candidate edge to the point (in this case, point 130). For example, the mathematical relationship may be a predetermined mathematical relationship, such as an inverse logarithmic relationship. Figure ID shows a plot representing a mathematical relationship between the candidate probability and a proximity of the candidate edge to the corresponding point. As shown, the closer the candidate edge is to the corresponding point, the higher the candidate probability. In contrast, the candidate probability goes to zero as the distance between the candidate edge and the corresponding point goes to infinity. In some embodiments, such as when the candidate edges must be within a predetermined distance from the corresponding point, the mathematical relationship may show that the candidate probability is zero for edges that are further from the corresponding point than the predetermined distance.

[0036] In some embodiments, the candidate probability for a candidate edge is based at least in part on which portion of the candidate edge is close to the corresponding point. For example, while candidate edges 164 and 165 are both within the predetermined distance from point 130, a start portion of candidate edge 164 overlaps with the area defined by circle 140 and an end portion of candidate edge 165 overlaps with the area defined by circle 140. Thus, despite candidate edges 164 and 165 being equidistant from point 130, candidate edge 164 has a higher candidate probability than candidate edge 165 (e.g., 0.82 versus 0.78). In some embodiments, as shown in the example above, the candidate probability is higher for candidate edges that correspond to a start portion of the candidate edge compared to candidate edges that correspond to an end portion of the candidate edge.

[0037] Referring to Figure IE, the candidate probabilities for each of the identified candidate edges corresponding to point 132 (e.g., edges 170 - 178) are determined in the same fashion as described above with respect to candidate edges for point 130 (e.g., edges 160 - 168).

[0038] In some embodiments, there is a threshold number of candidate edges for a given point (e.g., point 130, 132). For example, if a maximum number of candidate edges is 5, then the edges having the top 5 candidate probabilities (e.g., the top five highest candidate probabilities) are selected as candidate edges for the corresponding point. For example, if a maximum number of candidate edges for points 130 and 132 is 3, then edges 160, 162, and 163 are candidate edges for point 130 and edges 164, 165, and 168 are not considered to be candidate edges for point 130. Similarly, edges 174, 175, and 176 are candidate edges for point 132 and edges 170, 174, and 178 are not considered to be candidate edges for point 132.

[0039] In some embodiments, there is a threshold candidate probability for a given point (e.g., point 130, 132). For example, if a threshold candidate probability is 0.5 for points 130 and 132 (e.g., a candidate edge must have a candidate probability score that is at least 0.5 or greater), then edge 168 is not a candidate edge for point 130 and edge 178 is not candidate edge for point 132 since edges 168 and 178 each have candidate probabilities that are below 0.5.

[0040] In some embodiments, the candidate probability for a candidate edge is determined based at least in part on a comparison between the direction (e.g., heading of an edge) and a direction (e.g., heading) of the path of the geographic constraint. For example, a heading of geographic path 190 is compared to a direction of candidate edge 163 and the candidate probability of candidate edge 163 is determined based at least in part on whether the direction of candidate edge 163 is the same as the heading of geographic path 190. When the direction of candidate edge 163 is the same as (e.g., in the same direction as) the heading of geographic path 190, the candidate probability for candidate edge 163 is higher than if the direction of candidate edge 163 is the not the same as (e.g., in a different direction from) the heading of geographic path 190.

[0041] Additional details regarding edges of a routing map are provided in PCT

Application PCT/US 18/056740, filed October 19, 2018, entitled “Autonomous Vehicle Routing,” which is incorporated herein by reference in its entirety. [0042] Referring to Figure IF, a transition probability is determined for each possible candidate edge pair (or at least a subset of possible candidate edge pairs), where each candidate edge pair includes one candidate edge for point 130 and one candidate edge for point 132. For ease of illustration, the transition probabilities between the top three candidate edges for point 130 and the top three candidate edges for point 132 are shown in Figure IF. Dashed lines between two candidate edges represent a routing distance (e.g., as opposed to an “as-the-crow- flies” distance) between two candidate edges of a candidate edge pair. Figure IF shows three candidate edges corresponding to point 130 and three candidate edges corresponding to point 132. Thus, there are nine possible candidate edge pairs and each candidate edge pair has a corresponding transition probability that is determined based at least in part on a routing distance between the candidate edges of the candidate edge pair. In the case where point 130 has six candidate edges (e.g., edges 160 - 168) and point 132 has six candidate edges (e.g., edges 170 - 178), there are 36 unique candidate edge pairs and a transition probability is determined (e.g., calculated) for each candidate edge pair.

[0043] Following the example shown in Figure IF, dashed lines 180 to 188 represent routing (e.g., a routing path, a route) between a candidate edge of point 130 and a candidate edge of point 132. The transition probability for routing between two candidate edges is shown. For example, the transition probability for routing between candidate edges 160 and 174 is 0.21. Since each edge is directional (e.g., has a start portion and an end portion, has a heading, has a direction), a transition probability for routing from a first edge to a second edge is not the same as a transition probability for routing from a second edge to a first edge. For example, while the transition probability for routing from candidate edge 163 to candidate edge 175 is high (e.g., 0.96), the transition probability for routing from candidate edge 175 to candidate edge 163 would be lower (e.g., 0.61) since a routing distance from candidate edge 175 to candidate edge 163 would be longer than a routing distance from candidate edge 163 to candidate edge 175 due to the directionality of candidate edges 163 and 175.

[0044] In some embodiments, the transition probability for routing between a candidate edge pair is determined based at least in part on a routing distance between the candidate edges of the candidate edge pair. Thus, candidate edges of a candidate edge pair that have a short routing distance (e.g., 20 meter) will have a higher transition probability compared to candidate edges of a different candidate edge pair that have a longer routing distance (e.g., 500 meters).

[0045] In some embodiments, the transition probability for a candidate edge pair is determined based at least in part on a road type of at least one of the candidate edges of the candidate edge pair. For example, for a geographic constraint that includes a restriction to route only on identified (e.g., marked) roads, if a first candidate edge corresponding to a first point is a small alleyway, the transition probabilities for candidate edge pairs that include the first point have relatively low transition probabilities since it is unlikely that a vehicle can be or will be routed to a small or narrow alleyway. In a second example, if a first candidate edge corresponding to a first point is a street and a second candidate edge corresponding to a second point is an expressway, the transition probability for the candidate edge pair is lower compared to another candidate edge pair that has a same routing distance and has candidate edges that have a same road type.

[0046] Referring to Figure 1G, candidate edges 163 and 175 have been selected so that point 130 is mapped onto edge 163 and point 132 is mapped onto edge 175 of routing map 104. Thus, the geographic path 190 of geographic constraint 110 corresponds to route 187 from candidate edge 163 to candidate edge 175. Candidate edges 163 and 175 and route 187 (e.g., a route from edge 163 to edge 175) are selected as corresponding to geographic constraint 110 and are shown in Figure 1G as thick solid lines for emphasis and ease of comprehension.

[0047] In some embodiments, a total probability is determined for each candidate edge.

The total probability is determined using a hidden Markov model and is based on both the candidate probability and the transition probability (e.g., a weighted average of the candidate probability and the transition probability). In some embodiments, the candidate probability and the transition probability for each candidate edge are modeled as cost-probability curves and the curves are weighted using a hidden Markov model in the determination of the total probability. A respective candidate edge corresponding to a respective point is determined (e.g., selected) based on the total probability of the candidate edge. For example, a total probability is determined for each of the candidate edges corresponding to point 130 and each of the candidate edges corresponding to point 132. Following the example described in Figures 1C - IF, candidate edge 163 has the highest candidate probability (0.97) and the highest transition probability (0.96) compared to other candidate edges for point 130. Similarly, candidate edge 175 had a high candidate probability (0.94) and the highest transition probability 0.96 compared to other candidate edges for point 132. Note that candidate edge 175 was selected despite not having the highest candidate probability (see candidate edge 174, which has a candidate probability of 0.97, shown in Figure IE).

[0048] Figures 2 A - 2F illustrate an example of mapping a geographic constraint 112 to routing map 104, in accordance with some embodiments. [0049] Referring to Figure 2A, geographic constraint 112 is represented by points 230,

232, and 234 on geographic path 290 (shown as a dashed line). As shown, point 232 is disposed between points 230 and 234 such that point 232 is adjacent to each of point 230 and 234 but points 230 and 234 are not adjacent to each other.

[0050] In order to map point 230 to an edge of routing map 104, a first set of candidate edges on the routing map 104 are identified. In this example, edges 220 and 221 are identified as being proximate to (e.g., near, in the vicinity of) point 230. In some embodiments, as shown, only edges that are located within a predetermined distance from point 230 are included as a candidate edge. For example, dashed circle 240 illustrates an area within a predetermined distance from point 230 (e.g., if the predetermined distance is 100 meters, circle 240 has a radius of 100 meters and point 230 is located at a center of circle 240).

[0051] Similarly, in order to map point 232 to an edge of routing map 104, a second set of candidate edges on the routing map 104 are identified. In this example, edges 220 - 225 are identified as being proximate (e.g., near, in the vicinity of) point 232 and thus, are considered candidate edges for point 232. The process of identifying candidate edges that potentially correspond to point 234 is the same as described above with respect to points 230 and 232. As shown in Figure 2A, edges 224 - 227 are identified as being proximate (e.g., near, in the vicinity of) to point 232 and thus, are considered candidate edges for point 234.

[0052] Once a set of candidate edges have been identified for point 230, a candidate probability is determined (e.g., assigned, calculated) for each candidate edge. As shown in Figure 2B, point 230 has two candidate edges, 220 and 221. In this example, both candidate edges 220 and 221 are equidistant from point 230. Additionally, a middle portion (e.g., not a start portion or an end portion) of each of the candidate edges 220 and 221 are near point 230. Thus, both candidate edges 220 and 221 have a same candidate probability of 0.96.

[0053] Figures 2C and 2D illustrate determining candidate probabilities for candidate edges for points 242 and 244, respectively. The methods used to determine (e.g., calculate, assign) a candidate probability to a candidate edge are described above with respect to Figures IE, ID, and 2B and thus, are not repeated here for brevity. Figure 2C shows that six candidate edges (e.g., edges 220 - 225) are found to potentially correspond to point 232 and Figure 2D shows that 4 candidate edges (e.g., edges 224 - 226) are found to potentially correspond to point 234.

[0054] Figure 2E illustrates determining transition probabilities for each possible candidate edge pair, where each candidate edge pair includes a first candidate edge that potentially corresponds to a first point of the geographic constraint and a second candidate edge that potentially corresponds to second point of the geographic constraint that is adjacent to the first point. For example, a first candidate edge pair includes candidate edge 220 that potentially corresponds to point 230 and candidate edge 222 that potentially corresponds to point 232. In a second example, another candidate edge pair includes candidate edge 221 that potentially corresponds to point 232 and candidate edge 224 that potentially corresponds to point 234. Note that in this example, there are no candidate edge pairs that include a candidate edge that potentially corresponds to point 230 and a candidate edge that potentially corresponds to point 234 since points 230 and 234 are not adjacent to one another.

[0055] For example, the routing distance for routing between candidate edges 220 (for point 230) and 221 (for point 231) is 0.5, the routing distance for routing between candidate edges 221 (for point 230) and 220 (for point 231) is 0.1, and the routing distance for routing between candidate edges 221 (for point 230) and 221 (for point 231) is 0.98. A transition probability is also determined for each candidate edge pair that includes a candidate edge for point 232 and a candidate edge for point 234.

[0056] Figure 2F illustrates that candidate edges 221 and 224 have been selected so that point 230 is mapped onto candidate edge 221, point 232 is mapped to candidate edge 221, and point 234 is mapped to candidate edge 224. Thus, the geographic path of geographic constraint 112 corresponds to the route (shown as a thick solid line) between candidate edge 221 (for point 230) and candidate edge 221 (for point 232) and the route (shown as a thick solid line) between candidate edge 221 (for point 232) and candidate edge 224 (for point 234). The selected candidate edges (e.g., 221, 221, and 224) and the corresponding route between the selected edges are shown in Figure 2F with thick solid lines for emphasis and ease of comprehension.

[0057] In some embodiments, a total probability is determined for each candidate edge and the candidate edges are selected based on the total probability. Details regarding how the total probability is determined are described above with respect to Figure 1G and are not repeated here for brevity.

[0058] Figures 3A - 3B are block diagrams illustrating an architecture of an autonomous vehicle routing engine, in accordance with some embodiments.

[0059] Figure 3A is an example of an architecture of an autonomous-vehicle routing engine, in accordance with some embodiments. For example, the client 310 is the autonomous vehicle to be routed or an electronic device associated with the autonomous vehicle. [0060] Real-time data updates 330 include a server system that receives and/or tracks real-time traffic 332, historical traffic 334, and AV Events 336 and processes and forwards the traffic and events to AV Routing Engine 324, such that AV Routing Engine 324 can create and/or update a route for client 310. The AV Routing Engine 324 also uses information received from routing map 322, which includes routing constraints 320, to create/update the route for client 310.

[0061] Figure 3B illustrates another exemplary architecture (e.g., a so-called “stack”) for a fleet of vehicles. The features of the exemplary architecture shown in Figure 3B may optionally complement, replace, or be combined with the features of the architecture described with respect to Figure 3A. In some embodiments, the fleet of vehicles is a mixed fleet of vehicles including autonomous vehicles (e.g., autonomous vehicles 342) and non-autonomous vehicles (e.g., non-autonomous vehicles 340). In some circumstances, a fleet includes a mix of different vehicle types (e.g., automobiles, bicycles, scooters, and/or delivery robots). In some circumstances, the fleet provides services to riders (e.g., riders/consumers 344) by transporting riders from a first location to a second location. In some circumstances, the fleet provides services to other consumers, e.g., by delivering items to the consumers (e.g., delivering meals from restaurants, delivering packages from retail stores).

[0062] To facilitate the provision of these services using a mixed fleet of vehicles, the stack includes a first server system 350 that provides fleet management services and routing information. The first server system 350 includes one or more processors (e.g., CPUs) and memory storing instructions for the modules described with reference to the first server system (e.g., the map matching/positioning module 358, the routing engine 352, the geospatial siloed databases 354, and the normalizing data schema 356). The first server system 350 interfaces with a fleet manager 362 on a second server system 360. In the exemplary architecture shown in the figure, the second server system 360 acts as a client of the first server system 350, while riders, consumers (e.g., riders/consumers 344), and vehicles (e.g., non-autonomous vehicles 340 and/or autonomous vehicles 342) act as clients of the second server system 360.

[0063] In some embodiments, the second server system 360 is a separate and distinct server system from the first server system 350. The second server system 360 includes one or more processors (e.g., CPUs) and memory storing instructions for the modules described with reference to the second server system 360 (e.g., the fleet manager 362). The instructions are executed by the one or more processors. In some circumstances, the fleet manager 362 is one of a plurality of fleet managers serviced by the first server system 350. For example, the fleet manager 362 may be a fleet manager for a specific company’s fleet, and the first server system 350 may provide services to multiple companies’ fleets.

[0064] The first server system 350 includes a routing engine 352 that provides routes, distances, and estimated times of arrival for autonomous vehicles 342 and non-autonomous vehicles 340. In some embodiments, a different instance of the routing engine is instantiated for each fleet.

[0065] The first server system includes one or more geospatial siloed databases 354 storing geospatial data (e.g., data stored with a corresponding geographical location, such as latitude and longitude). The geospatial siloed databases 354 include “standard definition” (SD) map data received from SD map data providers 370 (e.g., data such as streets locations/geometries, street names). An example of an SD Map Data Provider is OpenStreetMap. In some embodiments, the geospatial data further includes “high definition” data such as lane-level data (e.g., lane locations/geometries, information about which maneuvers are permitted from which lanes) received from HD map data providers. The geospatial data further includes data from other data providers, such as information received from municipalities about construction and road closures, real-time data, traffic data and other data. In addition, the geospatial siloed databases 354 store locations (e.g., map matched locations) of the vehicles in the various fleets.

[0066] In some embodiments, the geospatial siloed databases 354 store a plurality of distinct instances of data covering the same geographical region. For example, the geospatial siloed databases 354 store multiple maps (e.g., with geospatial data overlaid on those maps) covering the same region. In some circumstances, the different maps will include data appropriate to a specific fleet’s vehicles (e.g., a fleet will include autonomous vehicles and delivery bots, and the geospatial siloed databases will store one or more maps with information appropriate to the fleet’s vehicle types). Some instances of the map may be public to any client (e.g., any fleet manager), while other versions of the map may be private to certain clients (e.g., certain fleet managers). For example, a respective fleet may license data from a respective HD map data provider. The data provided by the respective HD map data provider are thus siloed and private to the respective fleet’s fleet manager (e.g., fleet manager 362).

[0067] The first server system 350 further includes a map matching/positioning module

358 that matches location data received from vehicles to a map location (e.g., a location of a map stored in the geospatial siloed databases 354). For example, some vehicles generate location data (e.g., GPS data or data from another positioning system, such as GLONASS, Galileo, or BeiDou). In some circumstances, this data is noisy and may place the vehicle away from its actual location, e.g., on a sidewalk or in a building. The map matching/positioning module 358 receives the location data from a respective vehicle (e.g., through the fleet manager 362, which interfaces with the first server system 350), matches the noisy location data to a probable road location and/or lane location and updates the “map matched” location of the vehicle in the geospatial siloed databases 354 (e.g., updates the matched position). In addition, the map matched position is provided to the fleet manager 362 for various purposes (e.g., monitoring the fleet).

[0068] As noted above, the stack includes a second server system 360, optionally distinct and separate from the first server system 350. The second server system 360 includes the fleet manager3, which acts as a client of the first server system 350 (e.g., a client of the routing engine). The fleet manager 362 dispatches vehicles (e.g., non-autonomous vehicles 340 and/or autonomous vehicles 342), assigns routes to vehicles, and assigns staging locations to vehicles within its corresponding fleet (e.g., using information and routes provided by the routing engine). In addition, the fleet manager 362 interfaces with riders/consumers 344 (e.g., via a mobile application on the rider’s smartphone or other device). The fleet manager 362 provides information such as estimated times of arrival (ETAs) and trip costs to the riders/consumers 344 via their mobile devices. In some embodiments, the fleet manager 362 also receives data such as vehicle positions (e.g., location, including optionally lane-specific location and orientation (e.g., which way the vehicle is pointing)) from the individual vehicles.

[0069] In some embodiments, an autonomous vehicle includes an AV platform which serves as an operating system and framework for the autonomous functionality of the autonomous vehicle. The autonomous vehicle includes one or more processors (e.g., CPUs) and memory storing instructions for the modules described with reference to the autonomous vehicle (e.g., the interface module, the AV platform, drivers for the sensors/controls). The instructions are executed by the one or more processors. An example of an AV platform is the open source Robotics Operating System. The fleet manager (e.g., fleet manager 362) interacts with the autonomous vehicles (e.g., autonomous vehicles 342) through an interface module, which is a module that runs on the AV platform to provide routes to the AV platform and receive data from the autonomous vehicle’s sensors. For example, in some circumstances, the interface module is provided by the developer of the routing engine to act as a liaison between the first server system and the robotics of the autonomous vehicle. The AV platform receives sensor data from the autonomous vehicles sensor’s and, in some circumstances, makes the sensor data available to the fleet manager, which can make the sensor data available further down the stack, for example, to the map matching/position module. In some embodiments, the AV platform sends commands to the autonomous vehicle’s controls (e.g., acceleration commands, breaking commands, turning commands, etc.) through a drive-by-wire system.

[0070] Figure 4 is block diagram illustrating a client-server environment 400 in accordance with some embodiments. The client-server environment 400 includes vehicles 410 (e.g., 410-1, 410-2, ... , 410-n) that are connected to a vehicle routing server 420 through one or more networks 414. In some embodiments, vehicles 410 are or are analogous to vehicles 340 or 342 (shown in Figure 3B). In some circumstances, the vehicles 410 operate as clients of vehicle routing server 420. The one or more networks 414 can be any network (or combination of networks) such as the Internet, other Wide Area Networks, Local Area Networks, metropolitan area networks, VPNs, peer-to-peer, ad-hoc connections, and so on.

[0071] The non-autonomous vehicle 410-1 is a representative human-driven vehicle

(e.g., a car, truck, or motorcycle). In some embodiments, non-autonomous vehicle 410-1 is or is analogous to non-autonomous vehicle 340 (Figure 3B) In some embodiments, non- autonomous vehicle 410 includes a dashcam 412 that acquires and sends camera images to vehicle routing server 420, which can automatically identify road conditions from the dashcam images (as well as from autonomous vehicle camera sensor data from autonomous vehicles, such as from sensors 402 in an autonomous vehicle).

[0072] The autonomous vehicle 410-2 (e.g., a car, truck, or motorcycle) includes non- transitory memory 404 (e.g., non-volatile memory) that stores instructions for one or more client routing applications 406. In some embodiments, autonomous vehicle 410-2 is or is analogous to autonomous vehicle 342 (Figure 3B) Client routing applications 406 are executed by one or more processors (e.g., CPUs) 408 on the autonomous vehicle 410-2. In some embodiments, the client routing applications 406 send requests for routes to the vehicle routing server 420 and receive selected routes from the vehicle routing server 420. In some embodiments, the client routing applications 306 direct the autonomous vehicles 410-2 along the selected routes. Client routing applications 306 may be embodied as any appropriate combination of programs, firmware, operating systems, or other logical or physical aspects of the autonomous vehicle 410-2. Autonomous vehicle 410-2 also optionally includes one or more network interfaces and one or more communication buses for interconnecting these components. Autonomous vehicle 410-2 further includes vehicle components, such as an engine/motor, a steering mechanism, lights, signaling mechanisms, etc., some or all of which may be under the control of programs (e.g., a client routing application 406) stored in memory 404.

[0073] In some circumstances, a fleet of vehicles e.g., up to vehicle 410-n) is in communication with vehicle routing server 420. The fleet may be a mix of autonomous and human driven vehicles or may be entirely autonomous.

[0074] Vehicle routing server 420 includes non-transitory memory 416 (e.g., non volatile memory) that stores instructions for one or more server routing applications 418 (sometimes referred to as “routing engines”). Vehicle routing server 420 further includes one or more processors (e.g., CPUs) 422 for executing server routing applications 418. Server routing applications 418 may be embodied as any appropriate combination of programs, firmware, operating systems, or other logical or physical aspects of the autonomous vehicle 410-2. Vehicle routing server 420 also optionally includes one or more network interfaces and one or more communication buses for interconnecting these components.

[0075] The above-identified applications correspond to sets of instructions for performing functions described herein. The applications need not be implemented as separate software programs, procedures, or modules, and thus various subsets of these instructions may be combined or otherwise re-arranged in various embodiments.

[0076] Figure 5A illustrates an example of a user interface 500 for providing geographic constraints, in accordance with some embodiments. User interface 500 may be presented to a user as part of a computer program (e.g., application) or via a web browser. For example, a fleet manager may interact with user interface 500 to add routing constraints (such as geographic constraints 110 to 118 shown in Figures 1A and IB) for routing a fleet of vehicles.

[0077] In some embodiments, user interface 500 includes a field corresponding to a client identification (ID) field 512 that shows which profile (e.g., client profile, user profile, company profile) is currently active in the user interface 500. The user interface 500 may also include a fleet identification (ID) field 514 that shows which fleet is currently active in the user interface 500. In some embodiments, user interface 500 also includes one or more user affordances to add routing constraints 520, remove routing constraints 522, reset routing constraints 524 (e.g., remove all routing constraints), preview routing constraints on a map 526, or update routing constraints 528 for the fleet.

[0078] In some embodiments, user interface 500 may include a map 510 that allows a user to draw or indicate routing constraints directly on the map. The map may include navigational affordances 518, such as affordances corresponding to zoom-in, zoom-out, and pan (left, right, up, down) functions. The user interface 500 may also include an address bar 516 that allows a user to type in an address (such as a zip code, country, street address, state, etc.) in order to move an area shown in the map 510. For example, when a user types in a street address (such as “1234 Lombard Street, San Francisco, CA), the map 510 automatically updates to show a region that includes the entered street address.

[0079] For example, Company A (client ID 12345), which manages four different fleets, may access user interface 500 to add routing constraints for one of its fleets (e.g., fleet 56789). This information is reflected in the client ID field 512 and fleet ID field 514. In some embodiments, fleet ID field 514 may be a text field or a drop down menu that allows the user to search or switch between different fleets that are associated with a same client ID. In this example, the map 510 shows a region that includes streets as well as an overpass 530. As shown in Figure 5 A, the user has added three constraints 532 on map 510. Each of the constraints is a routing constraint and includes a restriction, such as a restriction to route only on indicated path or to not allow routing on the indicated paths. In this example, the user has indicated that vehicles belonging to fleet 56789 are not allowed to be routed along the indicated paths (e.g., not allowed to conduct the left turns that are indicated on map 510). Additional examples of geographic constraints (e.g., different types of geographic constraints) are provided below with respect to Figures 5B - 5F.

[0080] Figure 5B illustrates a white-listed area in San Francisco (an example of a polygonal constraint). In this example, a user has identified a region 550 (represented by the highlighted polygon) in which vehicles of a fleet are allowed to operate. The shaded region 552 represents a black-listed area.

[0081] Figure 5C illustrates black-listed roads 564 in a white-listed area 560 (examples of path constraints). In this example, a user has identified a region 560 in which vehicles of a fleet are allowed to operate as well as roads that vehicles of the fleet are not allowed to traverse (e.g., roads 564). When these routing constraints are translated onto a routing map for the fleet, a routing engine can take these constraints into consideration when routing vehicles of the fleet. The shaded region 562 represents a restricted area.

[0082] Figure 5D illustrates examples of restricted maneuvers 574 (e.g., maneuver constraints). In this example, a user has identified three separate maneuvers (one of which is a left turn) that are not allowed to be performed by vehicles of a fleet. Such constraints can be taken into consideration when a routing engine routs one or more vehicles of the fleet. As shown, the restricted maneuvers 574 are in a white-listed area 570 and the shaded region 572 corresponds to a restricted area (e.g., a black-listed area).

[0083] Figure 5E illustrates an example of a simulated fleet that serves riders within the San Francisco area. In this example, user constraints 584 (e.g., path constraints) have been translated to a routing map for the fleet and the simulation shows a simulated route 586 determined (e.g., assigned, routed) for a requested trip. As shown, the routing engine takes the user-defined constraints into consideration and the simulated route does not traverse any roads that are not allowed and does not perform any maneuvers that are not allowed. As shown, the user constraints 584 are in a white-listed area 580 and the shaded region 582 corresponds to a restricted area (e.g., a black-listed area).

[0084] Figure 5F illustrates an example of a simulated fleet that serves riders within the San Francisco area. In this example, user constraints have been applied to multiple white listed areas 590 and shaded area 592 corresponds to restricted (e.g., black-listed) areas.

[0085] Figure 5G illustrates an example of a user interface 502 for providing rule-based constraints, in accordance with some embodiments. User interface 502 corresponds to user interface 501 and includes the many of the same features and affordances described above with respect to Figure 5A, and such details are not repeated here for brevity. User interface 502 allows a user to define rule-based constraints for routing vehicles. In contrast, user interface 500 allows a user to define geographic constraints (e.g., by drawing on a map) for routing vehicles.

[0086] In some embodiments, as shown, when a user selects a user affordance to add routing constraints 520, a drop down menu or a set of predefined (e.g., curated) rules are provided. The user may select rules to be applied to routing a vehicle. Each rule includes a restriction to either allow or not allow a specific maneuver or travel along a road that matches the rule. For example, a rule may not allow travel on roads that have a speed limit above 50 miles per hour (mph). Alternatively, a rule may allow travel only on roads that have a speed limit below 35 mph. Figure 5G shows an example where a user has selected a rule to not allow any left turns. Thus, map 510 reflects the implementation of the selected rule and maneuvers 542 (e.g., paths) are shown on map 510 as being restricted.

[0087] Figures 6A - 6F show a flow chart of a method 600 for generating a routing

(e.g., routing map 104) map with routing constraints, in accordance with some embodiments. The method 600 includes receiving (operation 602) a geographic constraint (e.g., geographic constraints 110 - 118) for routing vehicles. The geographic constraint includes a plurality of points on a geographic path and a restriction applied to the plurality of points (e.g., geographic constraint 110 includes points 130 and 132 on geographic path 190). In some embodiments, the geographic path is not a boundary (e.g., is not closed and does not define a polygon). In some embodiments, the geographic constraint does not define a geographic region. In some embodiments, the geographic path is a two-dimensional path on a user-provided map, that is not the same as the routing map described below. In some embodiments, the geographic path corresponds to a route along which the geographic constraint is applied. The method 600 also includes mapping (operation 604) each point on the geographic path onto a routing map 104, including transferring the restriction to a corresponding set of one or more edges 102 on the routing map 104. The method 600 further includes receiving (operation 606) a request to route a vehicle and routing (608) the vehicle using the routing map using the geographic constraint.

[0088] In some embodiments, (operation 610) the geographic constraint corresponds to a restricted path. For example, geographic constraint 112 corresponds to a path that a vehicle of a fleet is not allowed to traverse (e.g., a vehicle of the fleet is not allowed to take the left turn corresponding to geographic constraint 112).

[0089] In some embodiments, (operation 612) the geographic constraint corresponds to an allowed path. For example, geographic constraint 110 may correspond to a path that a vehicle of a fleet is allowed to traverse. In some embodiments, vehicles of a fleet are allowed to drive only on indicated constraints and perform only indicated maneuvers.

[0090] In some embodiments, (operation 614) user input indicating the geographic constraint is received via a provided user interface (e.g., a graphical user interface). Figure 5A illustrates an example of constraints 532 that are provided by a user via user interface 500.

[0091] In some embodiments, (operation 616) the user input includes an indication to either allow or restrict a maneuver.

[0092] In some embodiments, the method 600 further includes identifying

(operation 620) a first plurality of candidate edges on the routing map for a first point on the geographic path and identifying (operation 630) a second plurality of candidate edges on the routing map for a second point on the geographic path. For example, Figure ID shows identifying a first plurality of candidate edges 160, 162 - 166, and 168 for point 130 and Figure IE shows identifying a second plurality of candidate edges 170, 172 - 176, and 178 for point 132.

[0093] The method 600 also includes determining (operation 640) a transition probability between each of the first candidate edges and each of the second candidate edges. For example, Figure IF shows determining a transition probability of 0.21 between candidate edge 160 and candidate edge 174.

[0094] The method 600 also includes selecting (650) a particular first candidate edge as a first edge on the routing map based on the transition probabilities, including determining that the first point on the geographic path is located along the first edge on the routing map. The method 600 also includes selecting (654) a particular second candidate edge as a second edge on the routing map based on the transition probabilities, including determining that the second point on the geographic path is located along the second edge on the routing map. The set of one or more edges corresponding to the geographic path includes the first edge and the second edge.

[0095] In some embodiments, (operation 622) the first plurality of candidate edges are located within a predetermined distance of the first point on the geographic path. Figures 1C - IE show that the candidate edges for each of point 130 and 132 are located within a predetermined distance from the respective point. The predetermined distance around point 130 and point 132 are represented for by dashed circles 140 and 142, respectively.

[0096] In some embodiments, (operation 624) the predetermined distance is customizable based on a user preference. For example, a user (e.g., a client, a fleet manager, a fleet operator, an operator of the routing service provider) may set the predetermined distance. In some embodiments, the predetermined distance may be a default setting that can be adjusted by a user.

[0097] In some embodiments, (operation 632) the first point and the second point are adjacent to one another relative to other points on the geographic path. For example, Figure 1C shows that points 130 and 132 of geographic constraint 110 are adjacent to one another. In another example, Figure 2A shows that points 230 and 232 of geographic constraint 112 are adjacent to one another and that points 232 and 234 of geographic constraint 112 are adjacent to one another.

[0098] In some embodiments, (operation 634) at least one of the first plurality of candidate edges differs from at least one of the second plurality of candidate edges.

[0099] In some embodiments, (operation 652) the particular first candidate edge is not the closest candidate edge, of the first plurality of candidate edges, to the first point of the geographic path. [00100] In some embodiments, the method 600 further includes determining

(operation 660) a candidate probability for each of the first candidate edges based on at least a proximity of the first candidate edge to the first point and (operation 662) determining a candidate probability for each of the second candidate edges based on at least a proximity of the second candidate edge to the second point. The method 600 further includes selecting (operation 664) the particular first candidate edge and the particular second candidate edge as the first and the second edge on the routing map based at least in part on the candidate probabilities. The method 600 also includes determining (operation 666) a total probability using a hidden Markov model. The total probability is based on the candidate probability and the transition probability.

[00101] In some embodiments, the method 600 further includes identifying

(operation 670) a third plurality of candidate edges on the routing map for a third point on the geographic path and determining (operation 672) a transition probability between each of the second candidate edges and each of the third candidate edges. The method 600 also includes selecting (674) the particular first candidate edge and the particular second candidate edge as the first and the second edge on the routing map based at least in part on the transition probability between each of the second candidate edges and each of the third candidate edges. The method 600 also includes selecting (operation 676) a particular third candidate edge as the third edge on the routing map that corresponds to the third point on the geographic path. The particular third candidate is selected based on the transition probabilities between each of the second candidate edges and each of the third candidate edges.

[00102] In some embodiments, the method 600 further includes determining

(operation 680) a routing distance between the particular first candidate edge and the particular second candidate edge. The transition probability between the particular first candidate edge and the particular second candidate edge corresponds to the routing distance. The method 600 also includes comparing (operation 682) the routing distance between the particular first candidate edge and the particular second candidate edge to an expected path distance between the first point and the second point of the geographic path. The transition probability between the particular first candidate edge and the particular second candidate edge corresponds to a difference between the routing distance and the expected path distance.

[00103] It will also be understood that, although the terms “first,” “second,” etc. are, in some circumstances, used herein to describe various elements, these elements should not be limited by these terms. These terms are only used to distinguish one element from another. For example, a first vehicle could be termed a second vehicle, and, similarly, a second vehicle could be termed a first vehicle, which changing the meaning of the description, so long as all occurrences of the “first vehicle” are renamed consistently and all occurrences of the second vehicle are renamed consistently. The first vehicle and the second vehicle are both vehicles, but they are not the same vehicle (e.g., the second vehicle is an additional vehicle).

[00104] The terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of the claims. As used in the description of the embodiments and the appended claims, the singular forms “a”, “an” and “the” are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will also be understood that the term “and/or” as used herein refers to and encompasses any and all possible combinations of one or more of the associated listed items. It will be further understood that the terms “comprises” and/or “comprising,” when used in this specification, specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, and/or groups thereof.

[00105] As used herein, the term “if’ is, optionally, construed to mean “when” or “upon” or “in response to determining” or “in accordance with a determination” or “in response to detecting,” that a stated condition precedent is true, depending on the context. Similarly, the phrase “if it is determined (that a stated condition precedent is true)” or “if (a stated condition precedent is true)” or “when (a stated condition precedent is true)” is, optionally, construed to mean “upon determining” or “in response to determining” or “in accordance with a determination” or “upon detecting” or “in response to detecting” that the stated condition precedent is true, depending on the context.

[00106] The foregoing description included example systems, methods, techniques, instruction sequences, and computing machine program products that embody illustrative embodiments. For purposes of explanation, numerous specific details were set forth in order to provide an understanding of various embodiments of the inventive subject matter. It will be evident, however, to those skilled in the art that embodiments of the subject matter are, optionally, practiced without these specific details. In general, well-known instruction instances, protocols, structures and techniques have not been shown in detail.

[00107] The foregoing description, for purpose of explanation, has been described with reference to specific embodiments. However, the illustrative discussions above are not intended to be exhaustive or to limit the embodiments to the precise forms disclosed. Many modifications and variations are possible in view of the above teachings. The embodiments were chosen and described in order to best explain the principles and their practical applications, to thereby enable others skilled in the art to best use the embodiments and various embodiments with various modifications as are suited to the particular use contemplated.

Claims

WHAT IS CLAIMED IS:

1. A method of routing vehicles, the method comprising: receiving a geographic constraint for routing vehicles, the geographic constraint comprising a plurality of points on a geographic path and a property applied to the plurality of points; mapping each point on the geographic path onto a routing map, including transferring the property to a corresponding set of one or more edges on the routing map; receiving a request to route a vehicle; and routing the vehicle using the routing map with the geographic constraint.

2. The method of claim 1, wherein mapping each point on the geographic path onto the routing map comprises: identifying, for a first point on the geographic path, a first plurality of candidate edges on the routing map; identifying, for a second point on the geographic path, a second plurality of candidate edges on the routing map; determining a transition probability between each of the first candidate edges and each of the second candidate edges; selecting a particular first candidate edge as a first edge on the routing map based on the transition probabilities, including determining that the first point on the geographic path is located along the first edge on the routing map; and selecting a particular second candidate edge as a second edge on the routing map based on the transition probabilities, including determining that the second point on the geographic path is located along the second edge on the routing map, wherein the set of one or more edges corresponding to the geographic path comprises the first edge and the second edge.

3. The method of claim 2, wherein mapping each point on the geographic path onto the routing map comprises: determining a candidate probability for each of the first candidate edges based on at least a proximity of the first candidate edge to the first point; and determining a candidate probability for each of the second candidate edges based on at least a proximity of the second candidate edge to the second point; and the particular first candidate edge and the particular second candidate edge are selected as the first edge and second edge on the routing map based at least in part on the candidate probabilities.

4. The method of claim 3, further comprising: determining a total probability using a hidden Markov model, wherein the total probability is based on the candidate probability and the transition probability.

5. The method of claim 2, further comprising: identifying, for a third point on the geographic path, a third plurality of candidate edges on the routing map; and determining a transition probability between each of the second candidate edges and each of the third candidate edges, wherein selecting the particular first candidate edge and the particular second candidate edges is further based on the transition probability between each of the second candidate edges and each of the third candidate edges.

6. The method of claim 5, further comprising: selecting, based on the transition probabilities between each of the second candidate edges and each of the third candidate edges, a particular third candidate edge as a third edge on the routing map that corresponds to the third point on the geographic path.

7. The method of claim 2, further comprising: determining a routing distance between the particular first candidate edge and the particular second candidate edge, wherein the transition probability between the particular first candidate edge and the particular second candidate edge corresponds to the routing distance.

8. The method of claim 7, further comprising: comparing the routing distance between the particular first candidate edge and the particular second candidate edge to an expected path distance between the first point and the second point of the geographic path, wherein the transition probability between the particular first candidate edge and the particular second candidate edge corresponds to a difference between the routing distance and the expected path distance.

9. The method of claim 2, wherein the first plurality of candidate edges are located within a predetermined distance of the first point on the geographic path.

10. The method of claim 9, wherein the predetermined distance is customizable based on a user preference.

11. The method of claim 9, wherein the particular first candidate edge is not the closest candidate edge, of the first plurality of candidate edges, to the first point of the geographic path.

12. The method of claim 2 wherein a transition probability from the particular first candidate edge to the particular second candidate edge is not the same as a transition probability from the particular second candidate edge to the particular first candidate edge.

13. The method of claim 2, wherein the first point and the second point are adjacent to one another relative to other points on the geographic path.

14. The method of claim 2, wherein at least one of the first plurality of candidate edges differs from at least one of the second plurality of candidate edges.

15. The method of claim 2, wherein: the routing map is used by a routing service for routing vehicles; and the geographic path is provided by a user of the routing service using a first map that is distinct from the routing map.

16. The method of claim 1, wherein the geographic constraint corresponds to a restricted path.

17. The method of claim 1, wherein the geographic constraint corresponds to an allowed path.

18. The method of claim 1, further comprising: providing a user interface; and receiving, via the user interface, a user input indicating the geographic constraint.

19. The method of claim 18, wherein the user input includes an indication to either allow or restrict a maneuver.

20. A computer system, comprising: one or more processors; and memory storing one or more programs, the one or more programs comprising instructions for: receiving a geographic constraint for routing vehicles, the geographic constraint comprising a plurality of points on a geographic path and a property applied to the plurality of points; mapping each point on the geographic path onto a routing map, including transferring the property to a corresponding set of one or more edges on the routing map; receiving a request to route a vehicle; and routing the vehicle using the routing map with the geographic constraint.

21. A computer system, comprising: one or more processors; and memory storing one or more programs, the one or more programs comprising instructions for performing the method of any of claims 2-19.

22. A non-transitory computer-readable storage medium storing one or more programs, which, when executed by an electronic device with one or more processors, cause the electronic device to perform a set of operations, including: receiving a geographic constraint for routing vehicles, the geographic constraint comprising a plurality of points on a geographic path and a property applied to the plurality of points; mapping each point on the geographic path onto a routing map, including transferring the property to a corresponding set of one or more edges on the routing map; receiving a request to route a vehicle; and routing the vehicle using the routing map with the geographic constraint.

23. A non-transitory computer-readable storage medium storing one or more programs, which, when executed by an electronic device with one or more processors, cause the electronic device to perform the method of any of claims 2-19.