Method and apparatus of free space enumeration for collision avoidance
First Claim
1. An apparatus for collision-free path determination using free space enumeration, in which configurations of a physical object and surrounding physical obstacles are represented by a configuration space defined in terms of degrees of freedom of the object, the configuration space being divided up into a multiplicity of cells defined in terms of intervals in the degrees of freedom, in which a path of the object between a given initial point in the configuration space from which the path starts and a given final point in the configuration space at which the path ends is to be determined, the apparatus comprising:
- means for enumerating a continuous free space between the initial point and the final point in which the path can be located, including;
means for selecting cells which satisfy a prescribed condition, between the initial point and the final point, by simultaneously using a plurality of strategies for selecting the cells; and
means for checking an occurrence of a collision between the object and the surrounding obstacles in the selected cells;
means for determining a collision-free path in the free space joining the initial point and the final point; and
means for controlling a position of the physical object with respect to the physical obstacle according to the determined collision-free path.
1 Assignment
0 Petitions
Accused Products
Abstract
A method and an apparatus for free space enumeration for motion planning, having general applicability while reducing amounts of information and calculations involved, capable of modifying a path, capable of setting up appropriate configuration space quantization, and capable of adopting appropriate strategy for free space enumeration. The method may include the step of selecting cells only between the initial point and the final point, or selecting cells between the initial point and the final point, using a plurality of strategies for selecting the cells simultaneously, or dividing the configuration space into multiplicity of cells defined in terms of intervals in the degrees of freedom, or determining a collision-free path in the free space joining the initial point and the final point without collision, or modifying the collision-free path.
48 Citations
80 Claims
-
1. An apparatus for collision-free path determination using free space enumeration, in which configurations of a physical object and surrounding physical obstacles are represented by a configuration space defined in terms of degrees of freedom of the object, the configuration space being divided up into a multiplicity of cells defined in terms of intervals in the degrees of freedom, in which a path of the object between a given initial point in the configuration space from which the path starts and a given final point in the configuration space at which the path ends is to be determined, the apparatus comprising:
-
means for enumerating a continuous free space between the initial point and the final point in which the path can be located, including; means for selecting cells which satisfy a prescribed condition, between the initial point and the final point, by simultaneously using a plurality of strategies for selecting the cells; and means for checking an occurrence of a collision between the object and the surrounding obstacles in the selected cells; means for determining a collision-free path in the free space joining the initial point and the final point; and means for controlling a position of the physical object with respect to the physical obstacle according to the determined collision-free path. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. An apparatus for collision-free path determination using free space enumeration, in which configurations of a physical object and surrounding physical obstacles are represented by a configuration space defined in terms of degrees of freedom of the object, the configuration space being divided up into a multiplicity of cells defined in terms of intervals in the degrees of freedom, in which a path of the object between a given initial point in the configuration space from which the path starts and a given final point in the configuration space at which the path ends is to be determined, the apparatus comprising:
-
means for enumerating a continuous free space between the initial point and the final point in which the path can be located, including; means for dividing the configuration space into multiplicity of cells defined in terms of intervals in the degrees of freedom, including; means for partitioning a physical space into a multiplicity of sub-regions; means for calculating a change in a total volume of the sub-regions which contains at least a portion of the object when each one of the degrees of freedom is varied separately by one provisionally adapted unit of intervals; and means for determining the intervals for the degrees of freedom defining the cells in the configuration space in accordance with the calculated change; means for selecting cells which satisfy a prescribed condition, between the initial point and the final point; and means for checking an occurrence of a collision between the object and the surrounding obstacles in the selected cells; means for determining a collision-free path in the free space joining the initial point and the final point without the collision; and means for controlling a position of the physical object with respect to the physical obstacle according to the determined collision-free path. - View Dependent Claims (11, 12, 13, 14)
-
-
15. An apparatus for collision-free path determination using free space enumeration, in which configurations of a physical object and surrounding physical obstacles are represented by a configuration space defined in terms of degrees of freedom of the object, the configuration space being divided up into a multiplicity of cells defined in terms of intervals in the degrees of freedom, in which a path of the object between a given initial point in the configuration space from which the motion starts and a given final point in the configuration space at which the path ends is to be determined, the apparatus comprising:
-
means for enumerating a continuous free space between the initial point and the final point in which the path can be located, including; means for selecting cells which satisfy a prescribed condition, only between the initial point and the final point; means for checking an occurrence of a collision between the object and the surrounding obstacles in the selected cells; and means for memorizing positions in the configuration space of free space cells which are the selected cells for which the collision cannot be detected; means for determining a collision-free path in the free space joining the initial point and the final point without the collision; and means for controlling a position of the physical object with respect to the physical obstacle according to the determined collision-free path. - View Dependent Claims (16, 17, 18, 19, 20, 21, 22, 23, 24)
-
-
25. An apparatus for collision-free path determination using free space enumeration, in which configurations of a physical object and surrounding physical obstacles are represented by a configuration space defined in terms of their coordinates, in which a path of the object between a given initial point in the configuration space and a given final point in the configuration space is to be determined, the apparatus comprising:
-
means for enumerating a continuous free space between the initial point and the final point in which the collision between the object and the surrounding obstacles is not possible; means for determining a collision-free path in the free space joining the initial point and the final point without the collision; means for modifying the collision-free path; and means for controlling a position of the physical object with respect to the physical obstacle according to the modified collision-free path. - View Dependent Claims (26, 27, 28, 29, 30, 31, 32)
-
-
33. An apparatus for collision-free area determination using free space enumeration, in which configurations of a physical object and surrounding physical obstacles are represented by a configuration space defined in terms of their coordinates, in which a location of the object between a given initial point in the configuration space and a given final point in the configuration space is to be determined, the apparatus comprising:
-
means for enumerating a continuous free space between the initial point and the final point in which the object can be located; means for determining a collision-free area in the free space joining the initial point and the final point without the collision; means for modifying the collision-free area; and means for controlling a position of the physical object with respect to the physical obstacle according to the modified collision-free path. - View Dependent Claims (34, 35, 36, 37, 38, 39, 40)
-
-
41. A method of collision-free path determination using free space enumeration, in which configurations of a physical object and surrounding physical obstacles are represented by a configuration space defined in terms of degrees of freedom of the object, the configuration space being divided up into a multiplicity of cells defined in terms of intervals in the degrees of freedom, in which a path of the object between a given initial point in the configuration space from which the path starts and a given final point in the configuration space at which the path ends is to be determined, the method comprising the steps of:
-
enumerating a continuous free space between the initial point and the final point in which the path can be located, including the steps of; selecting cells which satisfy a prescribed condition, between the initial point and the final point, by simultaneously using a plurality of strategies for selecting the cells; and checking an occurrence of a collision between the object and the surrounding obstacles in the selected cells; determining a collision-free path in the free space joining the initial point and the final point without the collision; and controlling a position of the physical object with respect to the physical obstacle according to the determined collision-free path. - View Dependent Claims (42, 43, 44, 45, 46, 47, 48, 49)
-
-
50. A method of collision-free path determination using free space enumeration, in which configurations of a physical object and surrounding physical obstacles are represented by a configuration space defined in terms of degrees of freedom of the object, the configuration space being divided up into a multiplicity of cells defined in terms of intervals in the degrees of freedom, in which a path of the object between a given initial point in the configuration space from which the path starts and a given final point in the configuration space at which the path ends is to be determined, the method comprising the steps of:
-
enumerating a continuous free space between the initial point and the final point in which the path can be located, including the steps of; dividing the configuration space into multiplicity of cells defined in terms of intervals in the degrees of freedom, including the steps of; partitioning a physical space into multiplicity of sub-regions; calculating a change in a total volume of the sub-regions which contains at least a portion of the object when each one of the degrees of freedom is varied separately by one provisionally adapted unit of intervals; and determining the intervals for the degrees of freedom defining the cells in the configuration space in accordance with the calculated change; selecting cells which satisfy a prescribed condition, between the initial point and the final point; and checking an occurrence of a collision between the object and the surrounding obstacles in the selected cells; determining a collision-free path in the free space joining the initial point and the final point without the collision; and controlling a position of the physical object with respect to the physical obstacle according to the determined collision-free path. - View Dependent Claims (51, 52, 53, 54)
-
-
55. A method of collision-free path determination using free space enumeration, in which configurations of a physical object and surrounding physical obstacles are represented by a configuration space defined in terms of degrees of freedom of the object, the configuration space being divided up into a multiplicity of cells defined in terms of intervals in the degrees of freedom, in which a path of the object between a given initial point in the configuration space from which the path starts and a given final point in the configuration space at which the path ends is to be determined, the method comprising the steps of:
-
enumerating a continuous free space between the initial point and the final point in which the path can be located, including the steps of; selecting cells which satisfy a prescribed condition, only between the initial point and the final point; checking an occurrence of a collision between the object and the surrounding obstacles in the selected cells; and memorizing positions in the configuration space of free space cells which are the selected cells for which the collision cannot be detected; determining a collision-free path in the free space joining the initial point and the final point without the collision; and controlling a position of the physical object with respect to the physical obstacle according to the determined collision-free path. - View Dependent Claims (56, 57, 58, 59, 60, 61, 62, 63, 64)
-
-
65. A method of collision-free path determination using free space enumeration, in which configurations of a physical object and surrounding physical obstacles are represented by a configuration space defined in terms of degrees of freedom of the object, the configuration space being divided up into a multiplicity of cells defined in terms of intervals in the degrees of freedom, in which a path of the object between a given initial point in the configuration space from which the path starts and a given final point in the configuration space at which the path ends is to be planned, the method comprising the steps of:
-
enumerating a continuous free space between the initial point and the final point in which the motion is possible; determining a collision-free path in the free space joining the initial point and the final point without the collision; modifying the collision-free path; and controlling a position of the physical object with respect to the physical obstacle according to the modified collision-free path. - View Dependent Claims (66, 67, 68, 69, 70, 71, 72)
-
-
73. A method of collision-free area determination using free space enumeration, in which configurations of a physical object and surrounding physical obstacles are represented by a configuration space defined in terms of their coordinates, and in which a location of the object between a given initial point in the configuration space and a given final point in the configuration space is to be determined, the method comprising the steps of:
-
enumerating a continuous free space between the initial point and the final point in which the object can be located; determining a collision-free area in the free space joining the initial point and the final point without the collision; modifying the collision-free area; and controlling a position of the physical object with respect to the physical obstacle according to the modified collision-free area. - View Dependent Claims (74, 75, 76, 77, 78, 79, 80)
-
Specification