US4862373A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for providing a collision free path in a three-dimensional space
Assignee: Texas Instruments Inc
•
Filing: 1987-05-13
•
Granted: 1989-08-29
•
Expires: 2007-05-13
Abstract
Abstract A method for providing a collision free safe path includes storing predetermined spatial graphs representing the set of points defining the collision free paths within that region and calculating the shortest path over the region. Each of the points in the graph have associated therewith predetermined constraints which, where compared to real world navigational limitations, determine if the path is navigable. A collision free path is generated by first examining the set of points defining the path and comparing them with the real world limitations. If all of the available paths are not collision free on the prestored spatial graph, a modified spatial graph, at a different altitude if necessary, is defined with collision free paths and then the shortest path between two points on this graph determined and output to a navigation system. In the event that the initial navigational limitations are altered during traversing of the shortest path, the same process will be repeated, i.e., a new spatial graph can be generated defining the collision free paths and the shortest path determined along this new shortest path from the point at which the navigational limitations changed.
Inventors
- 👤 Alex C-C Meng
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 14:14
CPC Classifications
G; G06; G06T; G06T19/00; G06T19/003; G01; G01C; G01C21/00; G01C21/38; G01C21/3863; G01C21/387; G01C21/3878
Claims Analysis
Total Claims: 33
Claim 1
Independent Claim
143 words
A method for collision free navigation in a predefined region comprising: storing a predetermined set of points defining the available paths through navigable free space in the region, each of the points having associated therewith predetermined navigational constraints; receiving externally generated position coordinates; receiving externally generated navigational limitations; comparing the received navigational limitations with the navigational constraints associated with the stored predetermined set of points to determine the ones of a predetermined set of points that can be safely navigated; generating a collision free set of points that is comprised of the ones of the predetermined set of points that can be safely navigated through the free space in the region; calculating the shortest path through the collison free set of points that can be navigated from the received position coordinates to a predetermined goal; and outputting coordinates defining the calculated shortest path.
Claim 2
Independent Claim
143 words
A method for collision free navigation in a predefined region comprising: storing a predetermined set of points defining the available paths through navigable free space in the region, each of the points having associated therewith predetermined navigational constraints; receiving externally generated position coordinates; receiving externally generated navigational limitations; comparing the received navigational limitations with the navigational constraints associated with the stored predetermined set of points to determine the ones of a predetermined set of points that can be safely navigated; generating a collision free set of points that is comprised of the ones of the predetermined set of points that can be safely navigated through the free space in the region; calculating the shortest path through the collison free set of points that can be navigated from the received position coordinates to a predetermined goal; and outputting coordinates defining the calculated shortest path.
Claim 3
Dependent Claim
40 words
The method of claim 1 wherein the navigational constraints associated with each one of the predetermined set of points is comprised of the proximity of each of the points to the nearest boundary of the free space in the region.
Claim 4
Dependent Claim
52 words
The method of claim 1 wherein the region is three-dimensional and is divided into discrete two-dimensional levels, each level represented by a set of points defining it out of the available paths through the free space in the associated two-dimensional level, each of the points having associated therewith the predetermined navigational constraints.
Claim 5
Dependent Claim
48 words
The method the claim 3 wherein the predetermined set of points for each two-dimensional level is comprised of a plurality of nodes in the free space of the two-dimensional level interconnected by discrete paths, each path defining a navigable set of points through the free space between nodes.
Claim 6
Dependent Claim
35 words
The method of claim 3 wherein the navigational constraints are comprised of proximity information associated with each point, the proximity information defining the proximity of the associated point with the nearest two-dimensional free space boundary.
Claim 7
Dependent Claim
29 words
The method of claim 5 wherein each point is disposed equi-distant between the closest points on the two nearest boundaries in the free space in the associated two-dimensional level.
Claim 8
Dependent Claim
79 words
The method of claim 3 wherein the levels are arranged in an ascending order and the step of calculating the safest path comprises: determining the lowest level in which there exists a set of points defining at least one collision free path between the received position coordinates and the goal; and calculating the shortest path through the collision free set of points in the determined lowest level that can be navigated from the received position coordinates to the goal.
Claim 9
Dependent Claim
44 words
The method of claim 1 wherein the step of generating the collision free set of points comprises the step of removing ones of the predetermined set of points that cannot be safely navigated, with the remaining points defining the collision free set of points.
Claim 10
Independent Claim
210 words
A method for providing a collision free path to a navigation system to allow collision free navigation through navigable free space in a three-dimensional space, comprising: storing a plurality of predetermined spacial graphs each associated with a two-dimensional level in the three-dimensional space, each of the predetermined spacial graphs representing all available discrete paths through the associated two-dimensional level with all available paths interconnected and each path having associated therewith predetermined navigational constraints; receiving externally generated position coordinates to define the present position of the navigation system in the three-dimensional space; receiving externally generated navigational limitations from the navigation system; comparing the received navigational limitations with the predetermined navigational constraints for each of the available paths on each of the levels to determine for each of the levels ones on the available paths that can be safely navigated; generating a collision-free spacial graph for each two-dimensional level, each collision free spacial graph comprised of the available safe paths of the corresponding predetermined spacial graph that can be safely navigated collision free; calculating the shortest path along the collision free available paths between the present position and a predetermined goal and in accordance with a predetermined shortest path algorithim; and outputting coordinates defining the calculated shortest path to the navigation system.
Claim 11
Independent Claim
210 words
A method for providing a collision free path to a navigation system to allow collision free navigation through navigable free space in a three-dimensional space, comprising: storing a plurality of predetermined spacial graphs each associated with a two-dimensional level in the three-dimensional space, each of the predetermined spacial graphs representing all available discrete paths through the associated two-dimensional level with all available paths interconnected and each path having associated therewith predetermined navigational constraints; receiving externally generated position coordinates to define the present position of the navigation system in the three-dimensional space; receiving externally generated navigational limitations from the navigation system; comparing the received navigational limitations with the predetermined navigational constraints for each of the available paths on each of the levels to determine for each of the levels ones on the available paths that can be safely navigated; generating a collision-free spacial graph for each two-dimensional level, each collision free spacial graph comprised of the available safe paths of the corresponding predetermined spacial graph that can be safely navigated collision free; calculating the shortest path along the collision free available paths between the present position and a predetermined goal and in accordance with a predetermined shortest path algorithim; and outputting coordinates defining the calculated shortest path to the navigation system.
Claim 12
Dependent Claim
67 words
The method of claim 9 wherein each of the predetermined spacial graphs is comprised of a plurality of nodes disposed in the free space in each of the associated two-dimensional levels with each of the discrete paths connected between two of the nodes, with each of the paths comprising a set of discrete points which define coordinates for traversing the associated discrete path between the two nodes.
Claim 13
Dependent Claim
35 words
The method of claim 10 wherein each of the points on each of the discrete paths is equi-distant from the two nearest boundaries of the free space in the associated one of the two-dimensional levels.
Claim 14
Dependent Claim
12 words
The method of claim 11 wherein the spatial graphs are Voronoi graphs.
Claim 15
Dependent Claim
36 words
The method of claim 10 wherein the navigational constraints associated with each of the points on the associated paths is comprised of proximity information regarding the distance to the nearest point on the free space boundary.
Claim 16
Dependent Claim
20 words
The method of claim 13 wherein the navigational limitations comprise information regarding the maximum proximity that can be safely navigated.
Claim 17
Dependent Claim
40 words
The method of claim 13 wherein the step of receiving the navigational limitations comprises: receiving the coordinates of an unexpected obstacle blocking one of the collision free available paths; and inhibiting use of this path in calculating the shortest path.
Claim 18
Dependent Claim
56 words
The method of claim 9 wherein the two-dimensional levels are arranged in ascending order with the lowest level having highest priority and the highest level having lowest priority such that the lowest two-dimensional level having a collision free available path is selected for calculation of the shortest path between the present invention and the predetermined goal.
Claim 19
Dependent Claim
39 words
The method of claim 9 wherein the navigational constraints comprise information regarding proximity of the path to the free space boundary and the navigational limitations comprise uncertain, information to define the minimum proximity that can be navigated collision free.
Claim 20
Dependent Claim
51 words
The method of claim 9 and further comprising calculating the shortest collision free path from the present position to the closest point on the closest one of the available paths in accordance with a second predetermined shortest path algorithm when the present position is not on one of the available paths.
Claim 21
Dependent Claim
49 words
The method of claim 18 and further comprising calculating the shortest collision free path from the goal to the closest point on the closest one of the available paths in accordance with a second predetermined shortest path algorithm when the goal is not on one of the available paths.
Claim 22
Independent Claim
246 words
A method for providing a collision free path for a navigation system to allow collision free navigation through navigable free space between obstacles in a three-dimensional space, comprising: storing a plurality of predetermined spacial graphs each associated with a two-dimensional level in the three-dimensional space, each of the spacial graphs representing all available discrete paths through the free space in the associated two-dimensional level with all available paths interconnected and each path having associated therewith proximity information defining the proximity of the path to the obstacle closest thereto; receiving externally generated position coordinates to define the position of the navigational system in the three-dimensional space; receiving externally generated uncertainty information from the navigation system as to location; determining the maximum proximity of a path that can be navigated collision free within the constraints of the received location uncertainty; selecting the lowest level spacial graph having a path with a proximity that allows collision free navigation in accordance with the location uncertainty constraints, the spacial graphs arranged in an ascending order from the lowest level to the highest level; generating a collision free spacial graph comprised of paths of the selected predetermined spacial graphs that can be safely navigated collision free in accordance with the location uncertainty constraints; calculating the shortest path along the collision free available paths between the present position and a predetermined goal and in accordance with a predetermined shortest path algorithm; and outputting coordinates defining the calculated shortest path to the navigation system.
Claim 23
Independent Claim
246 words
A method for providing a collision free path for a navigation system to allow collision free navigation through navigable free space between obstacles in a three-dimensional space, comprising: storing a plurality of predetermined spacial graphs each associated with a two-dimensional level in the three-dimensional space, each of the spacial graphs representing all available discrete paths through the free space in the associated two-dimensional level with all available paths interconnected and each path having associated therewith proximity information defining the proximity of the path to the obstacle closest thereto; receiving externally generated position coordinates to define the position of the navigational system in the three-dimensional space; receiving externally generated uncertainty information from the navigation system as to location; determining the maximum proximity of a path that can be navigated collision free within the constraints of the received location uncertainty; selecting the lowest level spacial graph having a path with a proximity that allows collision free navigation in accordance with the location uncertainty constraints, the spacial graphs arranged in an ascending order from the lowest level to the highest level; generating a collision free spacial graph comprised of paths of the selected predetermined spacial graphs that can be safely navigated collision free in accordance with the location uncertainty constraints; calculating the shortest path along the collision free available paths between the present position and a predetermined goal and in accordance with a predetermined shortest path algorithm; and outputting coordinates defining the calculated shortest path to the navigation system.
Claim 24
Dependent Claim
66 words
The method of claim 20 wherein each of the predetermined spacial graphs is comprised of a plurality of nodes disposed in the free space in each of the associated two-dimensional levels with each of the discrete paths connected between two of the nodes, each of the paths comprising a set of discrete points which define coordinates for traversing the associated discrete path between the two nodes.
Claim 25
Dependent Claim
35 words
The method of claim 21 wherein each of the points on each of the discrete paths is equi-distant from the boundary of the two nearest adjacent obstacles in the associated one of the two-dimensional levels.
Claim 26
Dependent Claim
12 words
The method of claim 22 wherein the spacial graphs are Voronoi graphs.
Claim 27
Independent Claim
223 words
A method for providing a collision free path for a navigation system to allow collision free navigation between obstacles in a three-dimensional space, comprising: storing a plurality of predetermined spacial graphs each associated with a two-dimensional level in the three-dimensional space, each of the predetermined spacial graphs representing all available discrete paths through the associated two-dimensional level between known obstacles; receiving externally generated coordinates of an unexpected obstacle when the unexpected obstacle is detected; receiving externally generated position coordinates to define the present position of the navigation system in the three-dimensional space when the unexpected obstacle is detected; modifying the predetermined spacial graphs to remove any of the available paths in any of the two-dimensional levels that are blocked by the obstacle; determining the shortest collision free straight line path from the point of detection of the unexpected obstacle to the closest point on the modified spacial graph in accordance with predetermined motion constraints to define a new starting coordinate; selecting the lowest level of the modified spacial graphs having an available path between the new starting coordinates and a predetermined goal; calculating the shortest path along the available path in the selected level between the new starting coordinates and the predetermined goal and in accordance with a shortest path algorithm; outputting the coordinates of the calculated shortest path through the navigational system.
Claim 28
Independent Claim
223 words
A method for providing a collision free path for a navigation system to allow collision free navigation between obstacles in a three-dimensional space, comprising: storing a plurality of predetermined spacial graphs each associated with a two-dimensional level in the three-dimensional space, each of the predetermined spacial graphs representing all available discrete paths through the associated two-dimensional level between known obstacles; receiving externally generated coordinates of an unexpected obstacle when the unexpected obstacle is detected; receiving externally generated position coordinates to define the present position of the navigation system in the three-dimensional space when the unexpected obstacle is detected; modifying the predetermined spacial graphs to remove any of the available paths in any of the two-dimensional levels that are blocked by the obstacle; determining the shortest collision free straight line path from the point of detection of the unexpected obstacle to the closest point on the modified spacial graph in accordance with predetermined motion constraints to define a new starting coordinate; selecting the lowest level of the modified spacial graphs having an available path between the new starting coordinates and a predetermined goal; calculating the shortest path along the available path in the selected level between the new starting coordinates and the predetermined goal and in accordance with a shortest path algorithm; outputting the coordinates of the calculated shortest path through the navigational system.
Claim 29
Dependent Claim
15 words
The method of claim 24 wherein the predetermined motion constraints comprise a maximum turning angle.
Claim 30
Dependent Claim
67 words
The method of claim 24 wherein each of the predetermined spacial graphs is comprised of a plurality of nodes disposed in the free space in each of the associated two-dimensional levels with each of the discrete paths connected between two of the nodes, with each of the paths comprising a set of discrete points which define coordinates for traversing the associated discrete path between the two nodes.
Claim 31
Dependent Claim
64 words
The method of claim 26 wherein the step of determining the shortest straight path from the point of detection of the unexpected obstacle to the closest point on the available path comprises determining the shortest straight line path from the point of detection to the closest node, which shortest path does not intersect with an obstacle, with the node defining the new start coordinates.
Claim 32
Dependent Claim
34 words
The method of claim 26 wherein each of the points in each of the discrete paths are equi-distant from the boundaries of the two nearest obstacles in the associated one of the two-dimensional levels.
Claim 33
Dependent Claim
12 words
The method of claim 28 wherein the spacial graphs are Voronoi graphs.
References Cited (Backward Citations)
US3784800A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1992-08-28 | 1993-02-27 | 1993-08-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1996-08-28 | 1997-02-27 | 1997-08-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2000-08-28 | 2001-02-27 | 2001-08-29 | $7700.00 | Window Closed / Lapsed |