Method for providing a collision free path in a three-dimensional space

• US 4,862,373 A
• Filed: 05/13/1987
• Issued: 08/29/1989
• Est. Priority Date: 05/13/1987
• Status: Expired due to Term

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Meng, Alex C-C
• Primary Examiner(s): Karcza, Thomas H.
• Assistant Examiner(s): CAIN, DAVID C
• Application Number:
  US07/049,754
• Time in Patent Office: 839 Days
• Field of Search: 364/444, 364/443, 364/449, 364/460, 364/461
• US Class Current: 701/209
• CPC Class Codes: G01C 21/3878 Hierarchical structures, e.g. layering
• CPC Class Codes: G06T 19/003 Navigation within 3D models or images

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

8. 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.

9. 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.

10. 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.

11. 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.

12. The method of claim 11 wherein the spatial graphs are Voronoi graphs.

13. 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.

14. The method of claim 13 wherein the navigational limitations comprise information regarding the maximum proximity that can be safely navigated.

15. 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.

16. 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.

17. 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.

18. 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.

19. 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.

20. 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.

21. 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.

22. 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.

23. The method of claim 22 wherein the spacial graphs are Voronoi graphs.

24. 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.

25. The method of claim 24 wherein the predetermined motion constraints comprise a maximum turning angle.

26. 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.

27. 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.

28. 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.

29. The method of claim 28 wherein the spacial graphs are Voronoi graphs.