MULTI-LEVEL PATH MAPPING FOR STREET GRID AND NON-STREET GRID ENTITIES

• US 20080183378A1
• Filed: 01/17/2008
• Published: 07/31/2008
• Est. Priority Date: 01/17/2007
• Status: Abandoned Application

• Current Assignee: David P. Weidner
• Original Assignee: David P. Weidner
• Inventors: Weidner, David P.
• Application Number:
  US12/016,159
• Publication Number:
  US 20080183378A1
• Time in Patent Office: Days
• US Class Current: 701/201
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence

Abstract

A method and system for path mapping through a multilevel path is disclosed. One embodiment is a process that compares a level of a start node with a level of a destination node; in response to the level of the start node being different from the level of the destination node, selects at least one preferred transition between the level of the start node and the level of the destination node; for a first plurality of nodes and respective edges on the level of the start node, determines a first best sub-path from the start node to the transition; for a second plurality of nodes and respective edges on the level of the destination node, determines a second best sub-path from the transition to the destination node; and defines a recommended path corresponding to the first best sub-path, the transition, and the second best preferred sub-path.

Claims

1. A method for determining a path through a multi-level architectural entity of interest, the method comprising:

comparing a level of a start node with a level of a destination node;

in response to the level of the start node being different from the level of the destination node, selecting at least one best match transition between the level of the start node and the level of the destination node, the best match transition including a transition start point on the level of the start node, a transition end point on the level of the destination, and a transition edge between the transition start point and the transition end point;

for a first plurality of nodes and respective edges on the level of the start node, determining a first sub-path from the start node to the transition start point;

for a second plurality of nodes and respective edges on the level of the destination node, determining a second sub-path from the transition end point to the destination node; and

determining a recommended path corresponding to the first sub-path, the second sub-path, and the best match transition.

2. The method of claim 1, wherein selecting the best match transition includes:

retrieving all transitions available for movement from the level of the start point to the level of the destination to form a transition set, each transition including a transition characteristic; and

selecting the best match transition from the transition set based upon the transition characteristic.

3. The method of claim 2, wherein selecting the best match transition further comprises:

comparing each recommended path according to a path characteristic;

determining at least one best match path based in response to the recommended path matching the characteristic; and

selecting a best match transition based upon inclusion in the best match path.

4. The method of claim 3, wherein the path characteristic in determining the best match path from the plurality of best matched paths is based on the shortest time required to traverse the best match path.

5. The method of claim 2, wherein selecting the best match transition includes:

eliminating at least one transition from the set based upon the transition characteristic.

6. The method of claim 2, wherein receiving all transitions includes:

defining as a combined transition a first transition in series with a second transition, the first transition having a first transition start point, a first transition end point and a first transition edge, and the second transition having a second transition start point, and a second transition edge, such that the combined transition start point is the first transition start point and the combined transition end point is the second transition end point, and such that an intermediate path edge is between the first transition end point and the second transition start point;

defining an intermediate path between the first transition end point and the second transition start point, the intermediate path having an intermediate path edge and that a combined transition edge includes characteristics from the first transition edge, the second transition edge and the intermediate path edge.

7. The method of claim 1, wherein selecting the best match transition further comprises:

identifying a first node of the best match transition that is on the same level as the start node such that the first best sub-path is determined from the start node to the first node of the transition; and

identifying a second node of the best match transition that is on the same level as the destination node such that the second best sub-path is determined from the second node of the transition to the destination node.

8. The method of claim 1, further comprising:

generating a map corresponding to a path of travel over of the recommended path.

9. The method of claim 1, further comprising:

generating a plurality of left turn and right turn directions corresponding to a path of travel over the recommended path.

11. The method of claim 1, further comprising:

receiving a request for path instructions, the request identifying the architectural entity of interest, identifying a start point in the architectural entity of interest, and identifying a destination in the architectural entity of interest;

defining the start node to correspond to the start point; and

defining the destination node to correspond to the destination.

12. The method of claim 1, further comprising:

receiving a request for special needs, the request identifying special needs of a person; and

identifying at least one special needs transition from a plurality of transitions such that the special needs transition is the best match transition.

13. The method of claim 1, further comprising:

receiving a request for special needs, the request identifying special needs of a person; and

identifying from a plurality of transitions at least one disqualified transition that is not compatible with the special needs such that the disqualified transition is not selectable as the best match transition.

14. The method of claim 1, wherein determining a first best sub-path from the start node to the best match transition comprises:

defining a node of the best match transition that is on the level of the start node as an end node for the first level; and

constructing a tree of vertices from the start node to the end node of the first level;

selecting at least one path on the tree of vertices between the start node and the end node of the first level as the first best sub-path.

15. The method of claim 1, further comprising:

performing reverse path construction for the first best sub-path.

16. A system operable to determine a path through a multi-level architectural entity of interest, the path having a start point and a destination, comprising:

a memory operable to store a map of the multi-level architectural entity of interest defined as a plurality of nodes, a plurality of edges, and at least one transition between a first level corresponding to the start point and a second level corresponding to the destination; and

a processing system operable to;

select at least one best match transition between the first level of the start node and the second level of the destination node;

for a first plurality of nodes and respective edges on the first level, determine a first best sub-path from the start node to the transition;

for a second plurality of nodes and respective edges on the second level of the destination node, determine a second best sub-path from the transition to the destination node; and

determining a recommended path corresponding to the first best sub-path, best match transition, and the second best preferred sub-path.

17. The system of claim 16, further comprising:

an input interface operable to receive a request for path instructions, the request identifying the multi-level architectural entity of interest, identifying the start point in the architectural entity of interest, and identifying the destination in the architectural entity of interest;

18. The system of claim 16, wherein the processing system is operable to generate at least one of a travel map and a set of directions corresponding to a path of travel over of the recommended path, further comprising:

an output interface operable to output at least one of the travel map and the set of directions determined by the processing system.

19. The system of claim 16, further comprising:

an input interface operable to receive the map of the multi-level architectural entity of interest from a database wherein a plurality of maps for different multi-level architectural entities of interest reside.

20. A method for determining a recommended path for traversing through a multi-level architectural entity of interest, the recommended path determined in part from a best sub-path on a first level that traverses from a start node on the first level to a transition start node of a transition on the first level, the transition connecting the first level with a second level, the method comprising:

for each node of the best sub-path on the first level, starting with the transition start node, adding the node and a respective incoming edge to a path list for the first level; and

in response to adding all nodes of the best sub-path to the path list for the first level, reverse ordering the nodes and edges of the path list for the first level.

21. The method of claim 20, further comprising:

signaling a last Vertex Path Event of the best sub-path for the first level in an event chain.

22. The method of claim 20, further comprising:

determining a route for the first level that traverses from the start node to the transition start node from the reverse ordered path list for the first level.

23. The method of claim 22, for a best sub-path on the second level that traverses from an end node of the transition to a destination node, further comprising:

for each node of the best sub-path on the second level, starting with the destination node, adding the node and its respective incoming edge to a path list for the second level; and

in response to adding all nodes of the best sub-path on the second level to the path list for the second level, reverse ordering the nodes and edges of the path list for the second level; and

determining a route on the second level that traverses from the end node of the transition to the destination node from the reverse ordered path list for the second level.

24. The method of claim 23, further comprising:

combining the determined rout for the first level, the transition, and the determined route for the second level such that a path for traversing from the start node to the destination node is determined.