EP0335314A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Method and apparatus of free space enumeration for collision avoidance
Assignee: Toshiba Corp
•
Filing: 1989-03-28
•
Granted: —
•
Expires: 2009-03-28
Abstract
Abstract A method and an apparatus of 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 plurality of strategies for selecting the cells simultanuously, 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 the collision, or modifying the collision-free path. The apparatus for performing the method is also disclosed.
Inventors
- 👤 Koichi Kondo
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-03 22:20
CPC Classifications
B; B25; B25J; B25J9/00; B25J9/16; B25J9/1656; B25J9/1664; B25J9/1666
Claims Analysis
Total Claims: 112
Claim 1
Independent Claim
150 words
An apparatus for enumerating a free space in a configuration space representing configurations of an object and surrounding obstacles in terms of degrees of freedom of the object, the configuration space being divided up into multiplicity of cells defined in terms of intervals in the degrees of freedom, the free space being continuously connecting a given initial point in the configuration space from which a motion of the object starts and a given final point in the configuration space at which the motion ends, the apparatus comprising: means for selecting(22) cells; means for detecting(25) a collision between the object and the surrounding obstacles in the selected cells; and means for memorizing(21) positions in the configuration space of free space cells which are the selected cells for which the collision cannot be detected; characterized in that the selecting means(22) selects only those cells between the initial point and the final point.
Claim 2
Independent Claim
150 words
An apparatus for enumerating a free space in a configuration space representing configurations of an object and surrounding obstacles in terms of degrees of freedom of the object, the configuration space being divided up into multiplicity of cells defined in terms of intervals in the degrees of freedom, the free space being continuously connecting a given initial point in the configuration space from which a motion of the object starts and a given final point in the configuration space at which the motion ends, the apparatus comprising: means for selecting(22) cells; means for detecting(25) a collision between the object and the surrounding obstacles in the selected cells; and means for memorizing(21) positions in the configuration space of free space cells which are the selected cells for which the collision cannot be detected; characterized in that the selecting means(22) selects only those cells between the initial point and the final point.
Claim 3
Dependent Claim
31 words
The apparatus of claim 1, wherein the memorizing means(21) also memorizes positions in the configuration space of collision cells which are the selected cells for which the collision can be detected.
Claim 4
Dependent Claim
53 words
The apparatus of claim 1, wherein the configuration space is divided into blocks, each block containing plurality of the cells, and wherein the memorizing means(21) memorizes positions in the configuration space of the blocks containing at least one of the free space cells, and positions in the blocks of the free space cells.
Claim 5
Dependent Claim
47 words
The apparatus of claim 3, wherein the memorizing means(21) also memorizes positions in the configuration space of the blocks containing at least one of collision cells which are the selected cells for which the collision can be detected and positions in the blocks of the collision cells.
Claim 6
Dependent Claim
12 words
The apparatus of claim 1, wherein the selecting means(22) utilizes cell expansions.
Claim 7
Dependent Claim
62 words
The apparatus of claim 1, wherein the selecting means(22) selects cells according to a heuristic function defined for each cell as f = c + h, where c is a number of cells from the initial point and h is an estimated number of cells to the final point, such that the cell which minimize the heuristic function is selected in succession.
Claim 8
Dependent Claim
76 words
The apparatus of claim 6, wherein the estimated number of cells h at a particular cell is obtained as: h = G x √ Σa(i) x [c(i) - Fc(i)]² where G is an overall coefficient, each a (i) is a coefficient for each degree of freedom of the object, c(i) is a value of i-th degree of freedom at the particular cell, and Fc(i) is a value of i-th degree of freedom at the final point.
Claim 9
Dependent Claim
28 words
The apparatus of claim 7, wherein at least one of the overall coefficient G and coefficients a(i) are determined within a prescribed range of values given for each.
Claim 10
Dependent Claim
38 words
The apparatus of claim 8, wherein those of the overall coefficient G and coefficients a(i) which are to be determined within a prescribed range of values given for each, are determined as a random number within the range.
Claim 11
Dependent Claim
26 words
The apparatus of claim 8, wherein the range is narrower for a coefficient which has a smaller difference between the initial point and the final point.
Claim 12
Independent Claim
131 words
An apparatus for enumerating a free space in a configuration space representing configurations of an object and surrounding obstacles in terms of degrees of freedom of the object, the configuration space being divided up into multiplicity of cells defined in terms of intervals in the degrees of freedom, the free space being continuously connecting a given initial point in the configuration space from which a motion of the object starts and a given final point in the configuration space at which the motion ends, the apparatus comprising: means for selecting(22) cells between the initial point and the final point; and means for detecting(25) a collision between the object and the surrounding obstacles in the selected cells; characterized in that the selecting means(22) uses plurality of strategies for selecting the cells simultaneously.
Claim 13
Independent Claim
131 words
An apparatus for enumerating a free space in a configuration space representing configurations of an object and surrounding obstacles in terms of degrees of freedom of the object, the configuration space being divided up into multiplicity of cells defined in terms of intervals in the degrees of freedom, the free space being continuously connecting a given initial point in the configuration space from which a motion of the object starts and a given final point in the configuration space at which the motion ends, the apparatus comprising: means for selecting(22) cells between the initial point and the final point; and means for detecting(25) a collision between the object and the surrounding obstacles in the selected cells; characterized in that the selecting means(22) uses plurality of strategies for selecting the cells simultaneously.
Claim 14
Dependent Claim
35 words
The apparatus of claim 11, wherein all the selections by the plurality of strategies discontinues when the cells selected by one of the strategies succeed to connect the initial point and the final point continuously.
Claim 15
Dependent Claim
62 words
The apparatus of claim 11, wherein the selecting means(22) further including: means for inspecting progress of the selection by each of the plurality of strategies at intermediate points between the initial point and the final point; and means for deterring the selections by those strategies found by the inspections to be slower in progress than at least one of the other strategies.
Claim 16
Dependent Claim
60 words
The apparatus of claim 13, wherein the inspecting means utilizes a quantity P defined for a point in the configuration space by: P = C N /F where C is a number of cells from the initial point, N is a dimensionality of the configuration space, and F is a total number of cells in the free space already enumerated.
Claim 17
Dependent Claim
78 words
The apparatus of claim 11, wherein the selecting means(22) selects cells according to a heuristic function defined for each cell as f = c + h, where C is a number of cells from the initial point and h is an estimated number of cells to the final point, such that the cell which minimize the heuristic function is selected in succession, and wherein the different strategies being given by the estimated number of cells h estimated differently.
Claim 18
Dependent Claim
98 words
The apparatus of claim 15, wherein the estimated number of cells h at a particular cell is obtained as: h = G x √ Σa(i) x [c(i) - Fc(i)]² where G is an overall coefficient, each a(i) is a coefficient for each degree of freedom of the object, c(i) is a value of i-th degree of freedom at the particular cell, and Fc(i) is a value of i-th degree of freedom at the final point, and wherein the different strategies being given by at least one of the overall coefficient G and coefficient a(i) different from each other.
Claim 19
Dependent Claim
28 words
The apparatus of claim 16, wherein at least one of the overall coefficient G and coefficients a(i) are determined within a prescribed range of values given for each.
Claim 20
Dependent Claim
38 words
The apparatus of claim 17, wherein those of the overall coefficient G and coefficients a(i) which are to be determined within a prescribed range of values given for each, are determined as a random number within the range.
Claim 21
Dependent Claim
26 words
The apparatus of claim 17, wherein the range is narrower for a coefficient which has a smaller difference between the initial point and the final point.
Claim 22
Independent Claim
193 words
An apparatus for enumerating a free space in a configuration space representing configurations of an object and surrounding obstacles in terms of degrees of freedom of the object, the free space being continuously connecting a given initial point in the configuration space from which a motion of the object starts and a given final point in the configuration space at which the motion ends, the apparatus comprising: means for selecting(22) cells between the initial point and the final point; and means for detecting(25) a collision between the object and the surrounding obstacles in the selected cells; characterized by further comprising: means for dividing(26) the configuration space into multiplicity of cells defined in terms of intervals in the degrees of freedom, including: means for partitioning(261) a physical space into multiplicity of sub-regions; means for calculating(262) 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 provisional unit of intervals; and means for determining(263) the intervals for the degrees of freedom defining the cells in the configuration space in accordance with the calculated change.
Claim 23
Independent Claim
193 words
An apparatus for enumerating a free space in a configuration space representing configurations of an object and surrounding obstacles in terms of degrees of freedom of the object, the free space being continuously connecting a given initial point in the configuration space from which a motion of the object starts and a given final point in the configuration space at which the motion ends, the apparatus comprising: means for selecting(22) cells between the initial point and the final point; and means for detecting(25) a collision between the object and the surrounding obstacles in the selected cells; characterized by further comprising: means for dividing(26) the configuration space into multiplicity of cells defined in terms of intervals in the degrees of freedom, including: means for partitioning(261) a physical space into multiplicity of sub-regions; means for calculating(262) 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 provisional unit of intervals; and means for determining(263) the intervals for the degrees of freedom defining the cells in the configuration space in accordance with the calculated change.
Claim 24
Dependent Claim
15 words
The apparatus of claim 20, wherein all the sub-regions are identical in shape and volume.
Claim 25
Dependent Claim
33 words
The apparatus of claim 20, wherein the partitioning means(261) uses a quad-tree when the physical space is considered to be 2-dimensional, and an oct-tree when the physical space is considered to be 3-dimensional.
Claim 26
Dependent Claim
26 words
The apparatus of claim 20, wherein the determining means(263) determines the intervals on a basis of comparison between the calculated change and a prescribed reference value.
Claim 27
Dependent Claim
49 words
The apparatus of claim 23, wherein the determining means(263) determines the intervals such that, when the calculated change is greater than the prescribed reference value, the provisional unit of the intervals is reduced in proportion to a ratio of the prescribed reference value with respect to the calculated change.
Claim 28
Independent Claim
205 words
An apparatus for motion planning using free space enumeration, in which configurations of an object and surrounding obstacles are represented by a configuration space defined in terms of degrees of freedom of the object, the configuration space being divided up into multiplicity of cells defined in terms of intervals in the degrees of freedom, in which a motion 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 motion ends is to be planned, the apparatus comprising: means for enumerating(21, 22, 25) a continuous free space between the initial point and the final point, in which the motion is possible, including: means for selecting(22) cells; means for detecting(25) a collision between the object and the surrounding obstacles in the selected cells; and means for memorizing(21) positions in the configuration space of free space cells which are the selected cells for which the collision cannot be detected; and means for determining(27) a collision-free path in the free space joining the initial point and the final point without the collision: characterized in that the selecting means(22) selects only those cells between the initial point and the final point.
Claim 29
Independent Claim
205 words
An apparatus for motion planning using free space enumeration, in which configurations of an object and surrounding obstacles are represented by a configuration space defined in terms of degrees of freedom of the object, the configuration space being divided up into multiplicity of cells defined in terms of intervals in the degrees of freedom, in which a motion 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 motion ends is to be planned, the apparatus comprising: means for enumerating(21, 22, 25) a continuous free space between the initial point and the final point, in which the motion is possible, including: means for selecting(22) cells; means for detecting(25) a collision between the object and the surrounding obstacles in the selected cells; and means for memorizing(21) positions in the configuration space of free space cells which are the selected cells for which the collision cannot be detected; and means for determining(27) a collision-free path in the free space joining the initial point and the final point without the collision: characterized in that the selecting means(22) selects only those cells between the initial point and the final point.
Claim 30
Dependent Claim
31 words
The apparatus of claim 25, wherein the memorizing means(21) also memorizes positions in the configuration space of collision cells which are the selected cells for which the collision can be detected.
Claim 31
Dependent Claim
54 words
The apparatus of claim 25, wherein the configuration spce is partitioned into blocks, each block containing plurality of the cells, and wherein the memorizing means(21) memorizes the positions in the configuration space of the blocks containing at least one of the free space cells, and positions in the blocks of the free space cells.
Claim 32
Dependent Claim
47 words
The apparatus of claim 27, wherein the memorizing means(21) also memorizes positions in the configuration space of the blocks containing at least one of collision cells which are the selected cells for which the collision can be detected and positions in the blocks of the collision cells.
Claim 33
Dependent Claim
12 words
The apparatus of claim 25, wherein the selecting means(22) utilizes cell expansions.
Claim 34
Dependent Claim
62 words
The apparatus of claim 25, wherein the selecting means(22) selects cells according to a heuristic function defined for each cell as f = c + h, where c is a number of cells from the initial point and h is an estimated number of cells to the final point, such that the cell which minimize the heuristic function is selected in succession.
Claim 35
Dependent Claim
75 words
The apparatus of claim 30, wherein the estimated number of cells h at a particular cell is obtained as: h = G x √ Σa(i) x [c(i) - Fc(i)]² where G is an overall coefficient, each a(i) is a coefficient for each degree of freedom of the object, c(i) is a value of i-th degree of freedom at the particular cell, and Fc(i) is a value of i-th degree of freedom at the final point.
Claim 36
Dependent Claim
28 words
The apparatus of claim 31, wherein at least one of the overall coefficient G and coefficients a(i) are determined within a prescribed range of values given for each.
Claim 37
Dependent Claim
38 words
The apparatus of claim 32, wherein those of the overall coefficient G and coefficient a(i) which are to be determined within a prescribed range of values given for each, are determined as a random number within the range.
Claim 38
Dependent Claim
26 words
The apparatus of claim 32, wherein the range is narrower for a coefficient which has a smaller difference between the initial point and the final point.
Claim 39
Independent Claim
151 words
An apparatus for motion planning using free space enumeration, in which configurations of an object and surrounding obstacles are represented by a configuration space defined in terms of degrees of freedom of the object, the configuration space being divided up into multiplicity of cells defined in terms of intervals in the degrees of freedom, in which a motion 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 motion ends is to be planned, the apparatus comprising: means for enumerating(21, 22, 25) a continuous free space between the initial point and the final point, in which the motion is possible; and means for determining(27) a collision-free path in the free space joining the initial point and the final point without the collision; characterized by further comprising: means for modifying(28) the collision-free path.
Claim 40
Independent Claim
151 words
An apparatus for motion planning using free space enumeration, in which configurations of an object and surrounding obstacles are represented by a configuration space defined in terms of degrees of freedom of the object, the configuration space being divided up into multiplicity of cells defined in terms of intervals in the degrees of freedom, in which a motion 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 motion ends is to be planned, the apparatus comprising: means for enumerating(21, 22, 25) a continuous free space between the initial point and the final point, in which the motion is possible; and means for determining(27) a collision-free path in the free space joining the initial point and the final point without the collision; characterized by further comprising: means for modifying(28) the collision-free path.
Claim 41
Dependent Claim
66 words
The apparatus of claim 35, wherein the enumerating means(21, 22, 25) includes: means for selecting(22) cells only between the initial point and the final point; means for detecting(25) a collision between the object and the surrounding obstacles in the selected cells; and means for memorizing(21) positions in the configuration space of free space cells which are the selected cells for which the collision cannot be detected.
Claim 42
Dependent Claim
31 words
The apparatus of claim 36, wherein the memorizing means(21) also memorizes positions in the configuration space of collision cells which are the selected cells for which the collision can be detected.
Claim 43
Dependent Claim
41 words
The apparatus of claim 35, wherein the modifying means(28) includes: means for deciding a part of the free space as dangerous part; and means for adjusting the collision-free path such that the dangerous part do not overlap with the collision-free path.
Claim 44
Dependent Claim
20 words
The apparatus of claim 38, wherein the deciding means utilizes wavefront expansions from the cells not in the free space.
Claim 45
Dependent Claim
18 words
The apparatus of claim 38, wherein the modifying means(28) further includes means for expanding the free space further.
Claim 46
Dependent Claim
12 words
The apparatus of claim 40, wherein the expanding means utilizes wavefront expansion.
Claim 47
Dependent Claim
17 words
The apparatus of claim 41, wherein the expanding means utilizes a scanning window for the wavefront expansion.
Claim 48
Independent Claim
117 words
An apparatus for collision avoidance using free space enumeration, in which configurations of an object and surrounding obstacles are represented by a configuration space defined in terms of 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 planned, the apparatus comprising: means for enumerating(21, 22, 25) a continuous free space between the initial point and the final point, in which the object can be located; and means for determining(27) a collision-free area in the free space joining the initial point and the final point without the collision; characterized by further comprising: means for modifying(28) the collision-free area.
Claim 49
Independent Claim
117 words
An apparatus for collision avoidance using free space enumeration, in which configurations of an object and surrounding obstacles are represented by a configuration space defined in terms of 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 planned, the apparatus comprising: means for enumerating(21, 22, 25) a continuous free space between the initial point and the final point, in which the object can be located; and means for determining(27) a collision-free area in the free space joining the initial point and the final point without the collision; characterized by further comprising: means for modifying(28) the collision-free area.
Claim 50
Dependent Claim
86 words
The apparatus of claim 43, wherein the configuration space being divided up into multiplicity of cells defined in terms of intervals in the coordinates, and wherein the enumerating means(21, 22, 25) includes: means for selecting(22) cells only between the initial point and the final point; means for detecting(25) a collision between the object and the surrounding obstacles in the selected cells; and means for memorizing(21) positions in the configuration space of free space cells which are the selected cells for which the collision cannot be detected.
Claim 51
Dependent Claim
31 words
The apparatus of claim 44, wherein the memorizing means(21) also memorizes positions in the configuration space of collision cells which are the selected cells for which the collision can be detected.
Claim 52
Dependent Claim
41 words
The apparatus of claim 43, wherein the modifying means(28) includes: means for deciding a part of the free space as dangerous part; and means for adjusting the collision-free area such that the dangerous part do not overlap with the collision-free area.
Claim 53
Dependent Claim
20 words
The apparatus of claim 45, wherein the deciding means utilizes wavefront expansions from the cells not in the free space.
Claim 54
Dependent Claim
18 words
The apparatus of claim 45, wherein the modifying means(28) further includes means for expanding the free space further.
Claim 55
Dependent Claim
12 words
The apparatus of claim 47, wherein the expanding means utilizes wavefront expansion.
Claim 56
Dependent Claim
17 words
The apparatus of claim 48, wherein the expanding means utilizes a scanning window for the wavefront expansion.
Claim 57
Independent Claim
151 words
A method for enumerating a free space in a configuration space representing configurations of an object and surrounding obstacles in terms of degrees of freedom of the object, the configuration space being divided up into multiplicity of cells defined in terms of intervals in the degrees of freedom, the free space being continuously connecting a given initial point in the configuration space from which a motion of the object starts and a given final point in the configuration space at which the motion ends, the method comprising the steps of: selecting(102, 103) cells; detecting(104) a collision between the object and the surrounding obstacles in the selected cells; and memorizing(105) positions in the configuration space of free space cells which are the selected cells for which the collision cannot be detected; characterized in that at the selecting step(102, 103) only those cells between the initial point and the final point are selected.
Claim 58
Independent Claim
151 words
A method for enumerating a free space in a configuration space representing configurations of an object and surrounding obstacles in terms of degrees of freedom of the object, the configuration space being divided up into multiplicity of cells defined in terms of intervals in the degrees of freedom, the free space being continuously connecting a given initial point in the configuration space from which a motion of the object starts and a given final point in the configuration space at which the motion ends, the method comprising the steps of: selecting(102, 103) cells; detecting(104) a collision between the object and the surrounding obstacles in the selected cells; and memorizing(105) positions in the configuration space of free space cells which are the selected cells for which the collision cannot be detected; characterized in that at the selecting step(102, 103) only those cells between the initial point and the final point are selected.
Claim 59
Dependent Claim
33 words
The method of claim 51, wherein at the memorizing step(105) positions in the configuration space of collision cells which are the selected cells for which the collision can be detected are also memorized.
Claim 60
Dependent Claim
55 words
The method of claim 51, wherein the configuration space is divided into blocks, each block containing plurality of the cells, and wherein at the memorizing step(105) positions in the configuration space of the blocks containing at least one of the free space cells, and positions in the blocks of the free space cells are memorized.
Claim 61
Dependent Claim
40 words
The method of claim 53, wherein at the memorizing step(105) positions in the configuration space of the blocks containing at least one of collision cells which are the selected cells for which the collision can be detected are also memorized.
Claim 62
Dependent Claim
15 words
The method of claim 51, wherein at the selecting step(102, 103) cell expansions are utilized.
Claim 63
Dependent Claim
66 words
The method of claim 51, wherein at the selecting step(102, 103) the cells are selected according to a heuristic function defined for each cell as f = c + h, where c is a number of cells from the initial point and h is an estimated number of cells to the final point, such that the cell which minimize the heuristic function is selected in succession.
Claim 64
Dependent Claim
75 words
The method of claim 56, wherein the estimated number of cells h at a particular cell is obtained as: h = G x √ Σa(i) x [c(i) - Fc(i)]² where G is an overall coefficient, each a(i) is a coefficient for each degree of freedom of the object, c(i) is a value of i-th degree of freedom at the particular cell, and Fc(i) is a value of i-th degree of freedom at the final point.
Claim 65
Dependent Claim
28 words
The method of claim 57, wherein at least one of the overall coefficient G and coefficients a(i) are determined within a prescribed range of values given for each.
Claim 66
Dependent Claim
38 words
The method of claim 58, wherein those of the overall coefficient G and coefficients a(i) which are to be determined within a prescribed range of values given for each, are determined as a random number within the range.
Claim 67
Dependent Claim
26 words
The method of claim 58, wherein the range is narrower for a coefficient which has a smaller difference between the initial point and the final point.
Claim 68
Independent Claim
134 words
A method for enumerating a free space in a configuration space representing configurations of an object and surrounding obstacles in terms of degrees of freedom of the object, the configuration space being divided up into multiplicity of cells defined in terms of intervals in the degrees of freedom, the free space being continuously connecting a given initial point in the configuration space from which a motion of the object starts and a given final point in the configuration space at which the motion ends, the method comprising the steps of: selecting cells(102, 103) between the initial point and the final point; and detecting(104) a collision between the object and the surrounding obstacles in the selected cells; characterized in that at the selecting step(102, 103) plurality of strategies for selecting the cells simultaneously are used.
Claim 69
Independent Claim
134 words
A method for enumerating a free space in a configuration space representing configurations of an object and surrounding obstacles in terms of degrees of freedom of the object, the configuration space being divided up into multiplicity of cells defined in terms of intervals in the degrees of freedom, the free space being continuously connecting a given initial point in the configuration space from which a motion of the object starts and a given final point in the configuration space at which the motion ends, the method comprising the steps of: selecting cells(102, 103) between the initial point and the final point; and detecting(104) a collision between the object and the surrounding obstacles in the selected cells; characterized in that at the selecting step(102, 103) plurality of strategies for selecting the cells simultaneously are used.
Claim 70
Dependent Claim
35 words
The method of claim 61, wherein all the selections by the plurality of strategies discontinues when the cells selected by one of the strategies succeed to connect the initial point and the final point continuously.
Claim 71
Dependent Claim
62 words
The method of claim 61, wherein the selecting step(102, 103) further including the steps of: inspecting progress of the selection by each of the plurality of strategies at intermediate points between the initial point and the final point; and deterring the selections by those strategies found by the inspections to be slower in progress than at least one of the other strategies.
Claim 72
Dependent Claim
62 words
The method of claim 63, wherein at the inspecting step a quantity P defined for a point in the configuration space by: P = C N /F where C is a number of cells from the initial point, N is a dimensionality of the configuration space, and F is a total number of cells in the free space already enumerated, is utilized.
Claim 73
Dependent Claim
82 words
The method of claim 61, wherein at the selecting step(102, 103) the cells are selected according to a heuristic function defined for each cell as f = c + h, where c is a number of cells from the initial point and h is an estimated number of cells to the final point, such that the cell which minimize the heuristic function is selected in succession, and wherein the different strategies being given by the estimated number of cells h estimated differently.
Claim 74
Dependent Claim
98 words
The method of claim 65, wherein the estimated number of cells h at a particular cell is obtained as: h = G x √ Σa(i) x [c(i) - Fc(i)]² where G is an overall coefficient, each a(i) is a coefficient for each degree of freedom of the object, c(i) is a value of i-th degree of freedom at the particular cell, and Fc(i) is a value of i-th degree of freedom at the final point, and wherein the different strategies being given by at least one of the overall coefficient G and coefficients a(i) different from each other.
Claim 75
Dependent Claim
28 words
The method of claim 66, wherein at least one of the overall coefficient G and coefficients a(i) are determined within a prescribed range of values given for each.
Claim 76
Dependent Claim
38 words
The method of claim 67, wherein those of the overall coefficient G and coefficients a(i) which are to be determined within a prescribed range of values given for each, are determined as a random number with the range.
Claim 77
Dependent Claim
26 words
The method of claim 67, wherein the range is narrower for a coefficient which has a smaller difference between the initial point and the final point.
Claim 78
Independent Claim
192 words
A method for enumerating a free space in a configuration space representing configurations of an object and surrounding obstacles in terms of degrees of freedom of the object, the free space being continuously connecting a given initial point in the configuration space from which a motion of the object starts and a given final point in the configuration space at which the motion ends, the method comprising the steps of: selecting (102, 103) cells between the initial point and the final point; and detecting(104) a collision between the object and the surrounding obstacles in the selected cells; characterized by further comprising 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 provisional 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.
Claim 79
Independent Claim
192 words
A method for enumerating a free space in a configuration space representing configurations of an object and surrounding obstacles in terms of degrees of freedom of the object, the free space being continuously connecting a given initial point in the configuration space from which a motion of the object starts and a given final point in the configuration space at which the motion ends, the method comprising the steps of: selecting (102, 103) cells between the initial point and the final point; and detecting(104) a collision between the object and the surrounding obstacles in the selected cells; characterized by further comprising 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 provisional 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.
Claim 80
Dependent Claim
15 words
The method of claim 70, wherein all the sub-regions are identical in shape and volume.
Claim 81
Dependent Claim
38 words
The method of claim 70, wherein at the partitioning step a use is made of a quad-tree when the physical space is considered to be 2-dimensional, and an oct-tree when the physical space is considered to be 3-dimensional.
Claim 82
Dependent Claim
28 words
The method of claim 70, wherein at the determining step the intervals are determined on a basis of comparison between the calculated change and a prescribed reference value.
Claim 83
Dependent Claim
51 words
The method of claim 73, wherein at the determining step the intervals are determined such that, when the calculated change is greater than the prescribed reference value, the provisional unit of the intervals is reduced in proportion to a ratio of the prescribed reference value with respect to the calculated change.
Claim 84
Independent Claim
203 words
A method for motion planning using free space enumeration, in which configurations of an object and surrounding obstacles are represented by a configuration space defined in terms of degrees of freedom of the object, the configuration space being divided up into multiplicity of cells defined in terms of intervals in the degrees of freedom, in which a motion 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 motion ends is to be planned, the method comprising the steps of: enumerating(101-105) a continuous free space between the initial point and the final point, in which the motion is possible, including the steps of: selecting(102, 103) cells; detecting(104) a collision between the object and the surrounding obstacles in the selected cells; and memorizing(105) positions in the configuration space of free space cells which are the selected cells for which the collision cannot be detected; and determining a collision-free path in the free space joining the initial point and the final point without the collision; characterized in that at the selecting step(102, 103) only those cells between the initial point and the final point are selected.
Claim 85
Independent Claim
203 words
A method for motion planning using free space enumeration, in which configurations of an object and surrounding obstacles are represented by a configuration space defined in terms of degrees of freedom of the object, the configuration space being divided up into multiplicity of cells defined in terms of intervals in the degrees of freedom, in which a motion 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 motion ends is to be planned, the method comprising the steps of: enumerating(101-105) a continuous free space between the initial point and the final point, in which the motion is possible, including the steps of: selecting(102, 103) cells; detecting(104) a collision between the object and the surrounding obstacles in the selected cells; and memorizing(105) positions in the configuration space of free space cells which are the selected cells for which the collision cannot be detected; and determining a collision-free path in the free space joining the initial point and the final point without the collision; characterized in that at the selecting step(102, 103) only those cells between the initial point and the final point are selected.
Claim 86
Dependent Claim
33 words
The method of claim 75, wherein at the memorizing step(105) positions in the configuration space of collision cells which are the selected cells for which the collision can be detected are also memorized.
Claim 87
Dependent Claim
56 words
The method of claim 75, wherein the configuration space is partitioned into blocks, each block containing plurality of the cells, and wherein at the memorizing step(105) the positions in the configuration space of the blocks containing at least one of the free space cells, and positions in the blocks of the free space cells are memorized.
Claim 88
Dependent Claim
40 words
The method of claim 77, wherein at the memorizing step(105) positions in the configuration space of the blocks containing at least one of collision cells which are the selected cells for which the collision can be detected are also memorized.
Claim 89
Dependent Claim
15 words
The method of claim 75, wherein at the selecting step(102, 103) cell expansions are utilized.
Claim 90
Dependent Claim
66 words
The method of claim 75, wherein at the selecting step(102, 103) the cells are selected according to a heuristic function defined for each cell as f = c + h, where c is a number of cells from the initial point and h is an estimated number of cells to the final point, such that the cell which minimize the heuristic function is selected in succession.
Claim 91
Dependent Claim
75 words
The method of claim 80, wherein the estimated number of cells h at a particular cell is obtained as: h = G x √ Σa(i) x [c(i) - Fc(i)]² where G is an overall coefficient, each a(i) is a coefficient for each degree of freedom of the object, c(i) is a value of i-th degree of freedom at the particular cell, and Fc(i) is a value of i-th degree of freedom at the final point.
Claim 92
Dependent Claim
28 words
The method of claim 81, wherein at least one of the overall coefficient G and coefficients a(i) are determined within a prescribed range of values given for each.
Claim 93
Dependent Claim
38 words
The method of claim 82, wherein those of the overall coefficient G and coefficients a(i) which are to be determined within a prescribed range of values given for each, are determined as a random number within the range.
Claim 94
Dependent Claim
26 words
The method of claim 82, wherein the range is narrower for a coefficient which has a smaller difference between the initial point and the final point.
Claim 95
Independent Claim
149 words
A method for motion planning using free space enumeration, in which configurations of an object and surrounding obstacles are represented by a configuration space defined in terms of degrees of freedom of the object, the configuration space being divided up into multiplicity of cells defined in terms of intervals in the degrees of freedom, in which a motion 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 motion ends is to be planned, the method comprising the steps of: enumerating(101-105) a continuous free space between the initial point and the final point, in which the motion is possible; and determining(201) a collision-free path in the free space joining the initial point and the final point without the collision; characterized by further comprising the step of: modifying(202-205) the collision-free path.
Claim 96
Independent Claim
149 words
A method for motion planning using free space enumeration, in which configurations of an object and surrounding obstacles are represented by a configuration space defined in terms of degrees of freedom of the object, the configuration space being divided up into multiplicity of cells defined in terms of intervals in the degrees of freedom, in which a motion 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 motion ends is to be planned, the method comprising the steps of: enumerating(101-105) a continuous free space between the initial point and the final point, in which the motion is possible; and determining(201) a collision-free path in the free space joining the initial point and the final point without the collision; characterized by further comprising the step of: modifying(202-205) the collision-free path.
Claim 97
Dependent Claim
62 words
The method of claim 85, wherein the enumerating step(101-105) includes the steps of: selecting(102, 103) cells only between the initial point and the final point; detecting(104) a collision between the object and the surrounding obstacles in the selected cells; and memorizing(105) positions in the configuration space of free space cells which are the selected cells for which the collision cannot be detected.
Claim 98
Dependent Claim
33 words
The method of claim 86, wherein at the memorizing step(105) positions in the configuration space of collision cells which are the selected cells for which the collision can be detected are also memorized.
Claim 99
Dependent Claim
41 words
The method of claim 85, wherein the modifying step(202-205) includes the steps of: deciding(203) a part of the free space as dangerous part; and adjusting(204, 205) the collision-free path such that the dangerous part do not overlap with the collision-free path.
Claim 100
Dependent Claim
22 words
The method of claim 88, wherein at the deciding step(203) wavefront expansion from the cells not in the free space is utilized.
Claim 101
Dependent Claim
19 words
The method of claim 88, wherein the modifying step(202-205) further includes the step of expanding(202) the free space further.
Claim 102
Dependent Claim
14 words
The method of claim 90, wherein at the expanding step(202) wavefront expansion is utilized.
Claim 103
Dependent Claim
19 words
The method of claim 91, wherein at the expanding step(202) a scanning window is utilized for the wavefront expansion.
Claim 104
Independent Claim
115 words
A method for collision avoidance using free space enumeration, in which configurations of an object and surrounding obstacles are represented by a configuration space defined in terms of 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 planned, the method comprising the steps of: enumerating(101-105) a continuous free space between the initial point and the final point, in which the object can be located; and determining(201) a collision-free area in the free space joining the initial point and the final point without the collision; characterized by further comprising the step of: modifying(202-205) the collision-free area.
Claim 105
Independent Claim
115 words
A method for collision avoidance using free space enumeration, in which configurations of an object and surrounding obstacles are represented by a configuration space defined in terms of 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 planned, the method comprising the steps of: enumerating(101-105) a continuous free space between the initial point and the final point, in which the object can be located; and determining(201) a collision-free area in the free space joining the initial point and the final point without the collision; characterized by further comprising the step of: modifying(202-205) the collision-free area.
Claim 106
Dependent Claim
82 words
The method of claim 93, wherein the configuration space being divided up into multiplicity of cells defined in terms of intervals in the coordinates, and wherein the enumerating step(101-105) includes the steps of: selecting(102, 103) cells only between the initial point and the final point; detecting(104) a collision between the object and the surrounding obstacles in the selected cells; and memorizing(105) positions in the configuration space of free space cells which are the selected cells for which the collision cannot be detected.
Claim 107
Dependent Claim
33 words
The method of claim 94, wherein at the memorizing step(105) positions in the configuration space of collision cells which are the selected cells for which the collision can be detected are also memorized.
Claim 108
Dependent Claim
41 words
The method of claim 93, wherein the modifying step(202-205) includes the steps of: deciding(203) a part of the free space as dangerous part; and adjusting(204, 205) the collision-free path such that the dangerous part do not overlap with the collision-free path.
Claim 109
Dependent Claim
22 words
The method of claim 95, wherein at the deciding step(203) wavefront expansion from the cells not in the free space is utilized.
Claim 110
Dependent Claim
19 words
The method of claim 95, wherein the modifying step(202-205) further includes the step of expanding(202) the free space further.
Claim 111
Dependent Claim
14 words
The method of claim 97, wherein at the expanding step(202) wavefront expansion is utilized.
Claim 112
Dependent Claim
19 words
The method of claim 98, wherein at the expanding step(202) a scanning window is utilized for the wavefront expansion.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.