SAFETY-BASED ROAD MAP NAVIGATION

• US 20100235088A1
• Filed: 03/10/2010
• Published: 09/16/2010
• Est. Priority Date: 03/16/2009
• Status: Active Grant

• Current Assignee: Hong Kong University of Science and Technology
• Original Assignee: Hong Kong University of Science and Technology
• Inventors: Zhou, Xi, Li, Mo, Wang, Jiliang, Han, Jinsong, Liu, Yunhao
• Granted Patent: US 8,626,444 B2
• Time in Patent Office: Days
• US Class Current: 701/201
• 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

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 upon a 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 the at least one evacuating 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 (1) intersects a proximal point, denoted a gateway, on the route backbone and (2) 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, each of which 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 (1) an indication of distance to a nearest danger area, denoted d_c, (2) an indication of a distance to the gateway sensor that increases as the information propagates to subsequent other sensors, denoted d_r, and (3) 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;

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.

17. A computer implemented method for facilitating safety-based navigational guidance, comprising:

generating a road map to represent a model of a local environment;

assigning nodes of the road map to correspond to respective locations within the local environment of a set of networked sensors whose sensor detection radii define boundaries for the local environment;

electronically receiving by way of a receiver a notification from at least one alarming sensor indicating a presence of danger in an area surrounding the at least one alarming sensor;

determining at least one safe path for navigating the local environment based upon a distance of nominal sensors from the at least one alarming sensor; and

representing the at least one safe path in the road map as a route backbone that intersects nodes that correspond to the nominal sensors included in the at least one safe path.

18. The method of claim 17, further comprising at least one of:

including in the road map at least one exit point corresponding to a target destination for a mobile entity in the local environment;

including in the road map at least one evacuation entity that corresponds to the mobile entity;

including in the road map a gateway node extant on both the route backbone and a medial axis for the exit point;

determining the at least one safe path for navigating the local environment further based upon distances from a nearest danger area and from the gateway node acquired by the set of sensors by way of message flooding propagating to successive sensors and origination from a sensor corresponding to the gateway node;

determining a direction for at least one segment of the route backbone based upon the information retained or propagated from the set of sensors;

or

providing instructions for directing the evacuating entity to the exit point while maximizing a minimum distance from a danger area based upon the route backbone.

19. The method of claim 17, further comprising at least one of:

receiving a transition notification from at one sensor in the set of sensors indicating the at least one sensor has switched from a nominal mode to an alarming mode or switched from an alarming mode to a nominal mode;

characterizing the at least one sensor as one of an expanding node, a shrinking mode, an emerging node, or a diminishing node based upon the transition notification and whether any node adjacent to the at least one node corresponds to an alarming sensor;

updating dimensions of a danger region to include or exclude the at least one sensor based upon the characterizing;

updating nodes of the route backbone by modifying distance data retained by corresponding sensors by way of message flooding only for sensors in which the at least one sensor newly represents a nearest danger region or was previously designated as the nearest danger region;

separating the road map into distinct cells with each cell comprising a single danger region and at least one exit point representing a boundary along the route backbone between at least two adjacent cells or an original exit point;

or

including in the road map at least one shortcut between two inscribed points existing 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.

20. A computer implemented system for facilitating safety-based navigational guidance, comprising:

means for modeling a local environment as a road map with sensors distributed throughout the local environment serving as nodes of the road map;

means for electronically receiving a notification from at least one alarming sensor indicating a presence of danger in an area surrounding the at least one alarming sensor;

means for adding a danger region to the road map corresponding to the area surrounding the at least one alarming sensor; and

means for determining at least one safe path for navigating the local environment while maximizing a minimum distance of nominal sensors that constitute the at least one safe path from the area surrounding the at least one alarming sensor.

21. The system of claim 20, further comprising means for updating the at least one safe path dynamically due to changes to the presence of danger detected by the sensors.

22. The system of claim 20, further comprising means for minimizing a distance between two points on the route backbone while maintaining a minimum distance from a nearest danger region.