Patent ID: 8423283

Claim:
A method for determining an overall driving route for a vehicle traveling between a starting location of the vehicle and a destination location of the vehicle in a geographical area, the geographical area comprising a plurality of geographical locations and a plurality of geographical roadways, wherein each geographical roadway connects two geographical locations in the geographical area, the method comprising: by a computer system comprising computer hardware: accessing a model from a computer accessible storage repository, the model representing the geographical area in which the vehicle is traveling, the model comprising a plurality of nodes representing the geographical locations in the geographical area and a plurality of edges representing the geographical roadways of the geographical area; accessing a start node of the plurality of nodes, the start node representing the starting location of the vehicle; accessing a destination node of the plurality of nodes, the destination node representing the destination location where the vehicle is to travel; searching successive nodes from the start node to identify a route from the start node to the destination node, the successive nodes being connected by successive edges of the plurality of edges; determining whether a selected edge of the successive edges is part of a multi-edge constraint that cannot be traversed by said searching; in response to determining that the selected edge is part of a multi-edge constraint, subdividing the model into two or more universes, wherein each of the universes comprises a subset of the plurality of nodes, wherein said subdividing the model into two or more universes comprises assigning a first one of the two or more universes to one of the successive nodes that is a start or continuation of the multi-edge constraint or that is a neighbor of a node at the start of the multi-edge constraint; separately identifying universe driving routes within the two or more universes, wherein the universe driving routes each comprise an ordered subset of the plurality of edges; and combining at least some of the universe driving routes to produce an overall driving route from the start node to the destination node.