Safety based road map navigation

• US 8,626,444 B2
• Filed: 03/10/2010
• Issued: 01/07/2014
• Est. Priority Date: 03/16/2009
• Status: Expired due to Fees

• Current Assignee: Hong Kong University of Science and Technology
• Original Assignee: Hong Kong University of Science and Technology
• Inventors: Li, Mo, Liu, Yunhao, Wang, Jiliang, Zhou, Xi, Han, Jinsong
• Primary Examiner(s): Trammell, James
• Assistant Examiner(s): Do, Truc M
• Application Number:
  US12/720,889
• Publication Number:
  US 20100235088A1
• Time in Patent Office: 1,399 Days
• Field of Search: 701/23, 701/532, 701/533, 370/238, 370/392
• US Class Current: 701/533
• CPC Class Codes: G05D 1/0214 in accordance with safety or protection criteria, e.g. avoiding hazardous areas monitoring the location of vehicles within a certain area, e.g. forbidden or allowed areas, in traffic control systems for road vehicles G08G1/13
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30

Abstract

The disclosed subject matter relates to an architecture that can facilitate safety-oriented navigation through a local environment that presents emergency dynamics. The architecture can facilitate monitoring of deployed sensors constituting a sensor network, even for cases in which sensor locations are not known in advance such as for rapid or random deployment.

Claims

1. A computer implemented system that determines safety-oriented navigation paths, comprising:

a monitor component configured to receive a hazard signal from at least one alarming sensor included in a sensor array distributed in a local environment bounded by a detection radius of the sensor array, wherein the hazard signal indicates a detected presence of danger proximal to the at least one alarming sensor, and wherein a sensor from the sensor array is not required to maintain location information relating to a location within the local environment; and

a mapping component configured to construct a road map scaled to dimensions of the local environment, wherein the road map includes a route backbone that depicts one or more recommended paths through the local environment selected based on a distance that satisfies a defined condition with respect to reduction of distance from the detected presence of danger.

2. The system of claim 1, wherein the route backbone comprises a set of edges that join a sequence of adjacent nodes that correspond to respective locations within the local environment of nominal sensors included in the sensor array.

3. The system of claim 1, wherein at least one of:

the mapping component further identifies at least one safe area within the local environment and plots an exit point on the road map that corresponds with the at least one safe area;

the mapping component further identifies at least one mobile entity extant in the local environment and plots at least one evacuating entity that corresponds to the at least one mobile entity on the road map connected to a proximal point of the route backbone;

or

the mapping component connects at least one exit point to the route backbone with an edge that intersects a proximal point, denoted a gateway, on the route backbone and depicts a recommended path through the local environment.

4. The system of claim 3, wherein the mapping component connects the at least one exit point to the gateway of the route backbone based upon a concatenation of a medial axis of the exit point.

5. The system of claim 4, wherein the medial axis includes a set of points, wherein a point from the set of points is a minimum distance from at least two danger regions.

6. The system of claim 1, wherein the mapping component includes in the road map at least one danger region that encompasses a contiguous set of alarming sensors and that corresponds to a danger area in the local environment.

7. The system of claim 6, wherein the mapping component treats regions beyond the local environment that correspond to areas outside the detection radius of the sensor array as one or more of the at least one danger region or the mapping component treats at least one region beyond the local environment that corresponds to areas outside the detection radius of the sensor array as a safe region and plots an exit point to correspond to the safe region.

8. The system of claim 1, wherein the mapping component assigns a potential value to a node included in the road map based at least in part upon data received from a corresponding sensor, wherein the potential value is inversely proportional to a distance between the corresponding sensor and a nearest danger area.

9. The system of claim 8, wherein at least one of:

the mapping component maximizes a minimum distance from all or a portion of danger regions included in the road map to construct the route backbone and further assigns a direction to one or more segment of the route backbone based upon descending potential values for nodes included in the one or more segment;

the mapping component connects an exit point or an evacuation entity to the route backbone based upon descending potential values for connected nodes extending from the exit point or the evacuation entity to the route backbone;

or

the potential value of the node is determined based at least in part upon information that propagates from a gateway sensor that corresponds to a gateway for the road map.

10. The system of claim 9, wherein information propagates from the gateway sensor to other sensors in the sensor array that correspond to nodes included in the road map, wherein the information includes an indication of distance to a nearest danger area, denoted d_c, an indication of a distance to the gateway sensor that increases as the information propagates to subsequent other sensors, denoted d_r, and a direction for the route backbone for nodes along the route backbone, denoted D.

11. The system of claim 10, wherein the mapping component constructs the route backbone based upon a comparison between multiple nodes included in the road map, wherein the comparison selects nodes associated with a larger d_c, or a smaller d_r when d_c are equal for compared nodes.

12. The system of claim 1, wherein the road map includes multiple danger regions and the mapping component divides the road map into multiple cells with each cell including exactly one danger region and at least one exit point that represents a boundary along the route backbone between at least two adjacent cells or a final destination for an evacuating entity.

13. The system of claim 1, further comprising a navigation component that configures a set of instructions to guide the mobile entity along at least a portion of the recommended path to at least one safe area.

14. The system of claim 1, further comprising an update component configured to continuously monitor data received from the sensor array and that facilitates at least one real time update to the road map upon detection of a variation of one or more danger area in the local environment that corresponds to one or more danger region in the road map.

15. The system of claim 14, wherein at least one of:

the update component categorizes the variation as one of (1) an expanding variation identified based upon an indication of a nominal sensor that is adjacent to an alarming sensor transitioning from nominal mode to alarming mode, (2) a shrinking variation identified based upon an indication of an alarming sensor that is adjacent to at least one other alarming sensor transitioning from alarming mode to nominal mode, (3) an emerging variation identified based upon an indication of a nominal sensor that is adjacent to no alarming sensors transitioning from nominal mode to alarming mode, or (4) a diminishing variation identified based upon an indication of an alarming sensor that is adjacent to no other alarming sensors transitioning from alarming mode to nominal mode;

the update component includes in the road map an expanding node in connection with the expanding variation and increases dimensions of an adjacent danger region to include the expanding node;

includes in the road map a shrinking node in connection with the shrinking variation and decreases dimension of an adjacent danger region to exclude the shrinking node;

includes in the road map an emerging node in connection with the emerging variation and adds a new danger region to the road map;

or includes in the road map a diminishing node in connection with the diminishing variation and removes an associated danger region from the road map;

or

the update component modifies a d_c value only for nodes that are nearer to the emerging node or the expanding node than to any other node extant in a danger region, or the update component modifies a d_c value only for nodes that are nearer to the shrinking node or the diminishing node than to any other node extant in a danger region, wherein a modification to a d_c value facilitates re-construction of the route backbone.

16. The system of claim 1, further comprising a shortcut component that identifies one or more shortcut path between two inscribed points extant on the route backbone, wherein the shortcut path differs from the route backbone and represents a shortest distance between the two inscribed points while maintaining a minimum distance from a nearest danger region, and wherein at least one of:

the shortcut component facilitates inclusion of the one or more shortcut path to the road map;

the shortcut component initiates identification of the one or more shortcut path when the road map is divided into multiple cells;

or

the shortcut component establishes a direction for the one or more shortcut path consistent with an associated route backbone portion direction upon inclusion of the one or more shortcut path to the road map or upon an event signaled when an evacuating entity encounters one of the two inscribed points.