Identifying and resolving prohibited maneuvers in routes generated by a routing system

Patent metadata

Field	Value
Publication number	US-12467757-B2
Application number	US-202318369346-A
Country	US
Kind code	B2
Filing date	Sep 18, 2023
Priority date	Sep 18, 2023
Publication date	Nov 11, 2025
Grant date	Nov 11, 2025

Abstract

A technique automatically identifies and resolves prohibited maneuvers in candidate routes generated by a routing system. Examples of prohibited maneuvers include traveling over a non-navigable path, traveling in an incorrect direction over a roadway, and an improper turn. The technique determines whether the candidate routes contain prohibited maneuvers by comparing the candidate routes with plural types of route-related validation data in plural respective validation processes. For example, a first validation process compares the candidate routes with a collection of GPS traces. A second validation process compares the candidate routes with map reference data. The technique further includes provisions for correcting the causes of identified prohibited maneuvers. Overall, the technique reduces the amount of manual effort involved in verifying the accuracy of routes produced by the routing system, and improves the accuracy, reliability, and safety of the routing system.

First claim

What is claimed is:

1 . A method for identifying and resolving prohibited maneuvers in routes generated by a computer-implemented routing system, comprising:
receiving a set of candidate routes sampled from a collection of routes generated by the routing system based on routing-engine network data in response to submitted requests, the set of candidate routes having different starting and ending locations, the routing-engine network data being provided in a data store of the routing system and describing a physical roadway network; receiving first route-related validation data from a first source, wherein the first route-related validation data is a collection of Global Positioning System (GPS) traces measured by position-determining devices at respective sampling rates as the position-determining devices traverse actual routes; receiving second route-related validation data from a second source, wherein the second route-related validation data is reference map data produced by another computer-implemented system that describes a same roadway network as the routing-engine network data used by the routing system; producing first validation results by comparing the set of candidate routes with the first route-related validation data; producing second validation results by comparing the set of candidate routes with the second route-related validation data, the producing second validation results being performed independently of the first validation results; identifying prohibited maneuvers in the set of candidate routes that are independently confirmed by both the first validation results and the second validation results; revising the routing system using a correction system to eliminate or reduce at least one factor that is causing generation of routes containing the prohibited maneuvers identified in the identifying, to provide a revised routing system, the correction system including functions for correcting one or more data errors in the routing-engine network data in the data store, and modifying logic used by the routing system to generate routes, the logic being at least one of machine-trained instructions that execute a routing algorithm or a machine-trained model; receiving requests by the revised routing system, each request that is received specifying a starting and ending location; and generating and providing routes using the revised routing system in response to the requests, the routes providing guidance on how to navigate over a physical roadway network.

2 . The method of claim 1 , wherein the prohibited maneuvers that are determined include any of:
navigation over a non-navigable route portion; and/or a prohibited turn; and/or navigation over a route portion in a direction that is prohibited.

3 . The method of claim 1 , further comprising snapping at least the first route-related validation data to a road network described by a common base map data.

4 . The method of claim 3 , wherein the common base map data is the routing-engine network data used by the routing system.

5 . The method of claim 1 , further comprising receiving third route-related validation data and producing third validation results by comparing the set of candidate routes with the third route-related validation data, wherein the identifying is also based on the third validation results.

6 . The method of claim 1 , wherein the producing first validation results comprises:
identifying a group of GPS traces within a prescribed geographic proximity to a particular candidate route; determining whether a particular segment of the particular candidate route is found in at least a first prescribed number of GPS traces in the group of GPS traces, at a same time at which the particular segment occurs; identifying a pair of segments in the candidate route that is joined at a maneuver point associated with a maneuver; and determining whether the pair of segments in the particular candidate route is found in at least a second prescribed number of GPS traces in the group of GPS traces, at a same time at which the pair of segments occurs.

7 . The method of claim 6 , wherein the producing first validation results further comprises:
designated the particular segment as matched, even though the particular segment does not match the first prescribed number of GPS traces, based on a consideration of a profile of the particular segment, and a consideration of a profile of a preceding group of one or more neighboring segments that precede the particular segment, and a profile of a following group of one or more neighboring segments that follow the particular segment; and designating the pair of segments as matched, even though the pair of segments does not match the second prescribed number of GPS traces, based on a consideration of the profile of the particular segment, and a consideration of a profile of a preceding group of one or more neighboring segments that precede the pair of segments, and a profile of a following group of one or more neighboring segments that follow the pair of segments, the profile of a particular group specifying at least whether each neighboring segment in the particular group is matched or unmatched.

8 . The method of claim 1 , wherein the producing second validation results comprises:
identifying a set of route entities in the routing-engine network data or the reference map data, each route entity describing a route portion having common properties; based at least in part on the set of route entities that are identified, identifying a pair of neighboring route entities in a particular candidate route that are joined at a maneuver point associated with a maneuver, the two neighboring route entities having a first neighboring route entity and a second neighboring route entity; identifying a first mini-route, using the routing-engine network data, between a beginning point of the first neighboring route entity and an ending point in the second neighboring route entity; identifying a second mini-route, based on the map reference data, between the beginning point of the first neighboring route entity and the ending point of the second neighboring route entity; and determining whether the first mini-route matches the second mini-route.

9 . The method of claim 8 , wherein the determining whether the first mini-route matches the second mini-route comprises determining whether bounding shapes associated with the first mini-route and the second mini-route, respectively, overlap by a prescribed amount.

10 . The method of claim 1 , wherein the first validation results and the second validation results are binary results, a binary result having two values, a first indicating that a particular conclusion applies, and a second indicating that the particular conclusion does not apply.

11 . The method of claim 1 , wherein the first validation results and the second validation results are probabilistic results, a probabilistic result indicating a likelihood of a particular conclusion that is a capable of ranging over plural values, including values between zero percent and 100 percent.

12 . The method of claim 1 , further comprising:
generating a presentation for a particular prohibited maneuver that has been identified; and receiving manually-specified classification information that specifies a cause of the particular prohibited maneuver.

13 . The method of claim 12 , wherein the presentation includes an aerial-captured image and/or a satellite-captured image of a map region associated with the prohibited maneuver.

14 . A computing system for identifying and resolving prohibited maneuvers in routes generat

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Karatzoglou Antonios
• Bekic Tijana
• Agrawal Vashutosh
• Khanna Mohit
• Kakkar Varun
• Evans Michael Robert
• Whitbeck Jacob Nicholas
• Yankov Dragomir Dimitrov
• Perin Nikola
• Todic Nikola
• Predovic Goran
• Samardzija Aleksandar

Classifications

• G01C21/38

  Electronic maps specially adapted for navigation; Updating thereof · CPC title

• G01C21/3415

  Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents · CPC title

• G01C21/3461 Primary

  Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types or segments such as motorways, toll roads or ferries · CPC title