Method of route retrieval

• US 8,346,474 B2
• Filed: 08/28/2008
• Issued: 01/01/2013
• Est. Priority Date: 08/28/2008
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Chen, Henry, Plocher, Tom, Beaulieu, Conrad Bruce, Li, Cheng Jun
• Primary Examiner(s): Tran, Khoi
• Assistant Examiner(s): Nguyen, Kira
• Application Number:
  US12/200,158
• Publication Number:
  US 20100057354A1
• Time in Patent Office: 1,587 Days
• Field of Search: 701/411
• US Class Current: 701/411
• CPC Class Codes: G01C 21/12 executed aboard the object being navigated; Dead reckoning
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G08B 7/066 guiding along a path, e.g. evacuation path lighting strip

Abstract

A method of route retrieval is provided comprising initializing a first weighted graph, converting a blueprint of an area into a weighted graph, updating the weighted graph in real time, and calculating an optimal route in the area.

Claims

1. A method of route retrieval comprising:

a programmed processor initializing a first weighted graph;

a programmed processor converting a blueprint of an area into a weighted graph where the weighted graph is a set of nodes connected to one another by a set of edges, the nodes of the weighted graph are at least one of a starting point, a way point or destination within the area and where weights assigned to each edge describes the relative cost to travel across that particular edge between a starting or way point and a destination within the area;

a programmed processor updating the weighted graph in real time where at least some of the weights of the weighted graph are defined as the product of distance and one of smoke density and temperature;

a programmed processor calculating a plurality of optimal routes in the area using the weights of the weighted graph; and

displaying the optimal routes wherein said plurality of optimal routes includes at least some partially overlapping routes and wherein upon detection that one or more of the plurality of optimal routes is blocked, the step of updating includes dividing the blocked route into two or more parts and calculating a new plurality of optimal routes based upon the one or more blocked routes.

2. The method of claim 1 wherein converting a blueprint of an area into a weighted graph comprises:

a programmed processor recognizing and assessing the area;

recognizing and assessing any compartments in the area;

calculating an area of a hallway located within the area;

converting the hallway area into a single pixel width connected curve;

splitting the curve into segmented lines;

adding the segmented lines to the first weighted graph representative of edges;

adding nodes to the first weighted graph representative of the compartments in the area; and

calculating the distance of each edge.

3. The method of claim 2 further including a programmed processor adding additional edges to the first weighted graph representative of portals between adjacent floors of a building.

4. The method of claim 2 further including a programmed processor assigning one or more weights to each edge.

5. The method of claim 4 further including a programmed processor retrieving the one or more weights from at least one sensor in the area.

6. The method of claim 4 further comprising a programmed processor retrieving the one or more weights from predictive data.

7. The method of claim 1 further comprising a programmed processor converting a blueprint of a sub-area into a sub-weighted graph and adding the sub-weighted graph to the first weighted graph.

8. The method of claim 1 wherein updating the weighted graph in real time comprises:

a programmed processor retrieving current environmental information;

determining any nodes or edges influenced by the current environmental information;

determining how the current environmental information influences the nodes or edges influenced by the current environmental information; and

adjusting a weight of the nodes or edges influenced by the current environmental information.

9. The method of claim 8 wherein retrieving current environmental information comprises a programmed processor retrieving data from a sensor in the area or retrieving predictive data.

10. The method of claim 8 wherein adjusting a weight of the nodes or edges influenced by the current environmental information further comprises a programmed processor adjusting the weight of an edge when a whole edge is influenced by the current environmental information.

11. The method of claim 8 wherein adjusting a weight of the nodes or edges influenced by the current environmental information further comprises a programmed processor dividing an edge into multiple edges when only a part of an edge is influenced by current environmental information and assigning new weights to the multiple edges.

12. The method of claim 1 wherein calculating an optimal route in the area comprises:

a programmed processor determining all weights associated with all edges in the area;

computing the final weight of the each edge in the area; and

running a shortest path algorithm using the final weights of the edges in the area as input for the algorithm.

13. The method of claim 1 further comprising a programmed processor drawing edges of the optimal route in a three-dimensional scene.

14. Software stored in a computer-readable medium for retrieving an optimal route in an area comprising:

instructions for initializing a first weighted graph;

instructions for converting a blueprint of the area into a weighted graph where the weighted graph is a set of nodes connected to one another by a set of edges, the nodes of the weighted graph are at least one of a starting point, a way point or destination within the area and where weights assigned to each edge describes the relative cost to travel across that particular edge between a starting or way point and a destination within the area;

instructions for updating the weighted graph in real time where at least some of the weights of the weighted graph are defined as the product of distance and one of smoke density and temperature; and

instructions for calculating a plurality of optimal routes in the area using the weights of the weighted graph wherein said plurality of optimal routes includes at least some partially overlapping routes and wherein upon detection that one or more of the plurality of optimal routes is blocked, the instructions for updating divides the blocked route into two or more parts and calculates a new plurality of optimal routes based upon the one or more blocked routes.