Method of searching for points of closest approach, and preprocessing method therefor

A point-of-closest-approach search method for one of collision avoidance between two convex polyhedrons and path planning in operating a robot, said method searching for a point of closest approach from a coordinate origin to a figure, which is one of a polygon and polyhedron, formed by a subset whose elements are p-number of points on a difference convex polyhedron, which is formed by a set of position vectors obtained by vector subtraction of arbitrary position vectors of two convex polyhedrons, calculating an inner product between a position vector x of the point of closest approach and position vectors of the vertices of each convex polyhedron, calculating a sum of the inner product and .vertline.x.vertline..sup.2, judging, in a case where the sum is equal to 0, that the point of closest approach is a point of closest approach from the origin to the difference convex polyhedron and, in a case where the sum is not 0, altering the figure by changing a combination of said p-number of points, repeating previous steps until the sum equals 0, and finally obtaining the point of closest approach from the coordinate origin to the difference convex polyhedron to thereby find a point of closest approach of each convex polyhedron, said method comprising the steps of:

• partitioning each surface polygon of the convex polyhedrons into triangular polygons and expressing each convex polyhedron by directed-graph structure data which is obtained by arraying triangular polygons of the convex polyhedrons, arraying vertices and edges, which are elements of the triangular polygons, below the corresponding triangular polygon and arraying the triangular polygons, which form the vertices and edges, below respective ones of the vertices and edges;
• determining whether a point of closest approach on each convex polyhedron corresponding to the point of closest approach from the coordinate origin to the figure resides on one of the corresponding vertices, edges and triangular polygons;
• if the point of closest approach resides on one of the corresponding vertices, obtaining the triangular polygons forming this vertex from the directed-graph structure data and using the vertices of the obtained triangular polygons in the next calculation of said inner product;
• if the point of closest approach resides on one of the corresponding edges, obtaining the triangular polygons forming this edge from the directed-graph structure data and using position vectors of the vertices of the obtained triangular polygons in the next calculation of said inner product;
• if the point of closest approach resides on one of the corresponding triangular polygons, using position vectors of the vertices of this triangular polygon in the next calculation of said inner product, thereby obtaining the point of closest approach from the origin to the difference convex polyhedron and obtaining the point of closest approach on each convex polyhedron;
• and
• controlling operation of the robot based upon the points of closest approach.

A point-of-closest-approach search method for one of collision avoidance between two convex polyhedrons and path planning in operating a robot, said method continuously searching for a point of closest approach between two convex polyhedrons to check for interference between the two convex polyhedrons, said method comprising the steps of:

• inputting vertex coordinates of all polygons covering each convex polyhedron;
• creating for each convex polyhedron, a list which is referred to as a nearby-point linear list having a data structure obtained by arraying vertices of each polygon without repetition in a first direction so that the vertices connected by an edge of any polygon are arranged adjacently, and linking vertices, each of which is connected via an edge of any polygon to a vertex of interest arrayed in the first direction, to a vertex in a second direction, and linking in a similar way vertices to each vertex of the first direction in the second direction;
• obtaining vertices, which are adjacent to a point of closest approach obtained most recently on each convex polyhedron, from the nearby-point linear list of each convex polyhedron;
• performing an interference check by searching for a point of closest approach on each convex polyhedron at a next moment in time from among said obtained vertices of each convex polyhedron;
• controlling operation of the robot based upon the points of closest approach.

A point-of-closest-approach search method for one of collision avoidance between two non-convex polyhedrons and path planning in operating a robot, said method decomposing first and second non-convex polyhedrons into respective ones of convex polyhedrons and continuously searching for points of closest approach between the convex polyhedrons, thereby checking for interference between the non-convex polyhedrons, said method comprising the steps of:

• creating, for each convex polyhedron, a list referred to as a nearby-point linear list having a data structure obtained by arraying vertices of each polygon without repetition in a first direction so that the vertices connected by a an edge of any polygon are arrayed adjacently, and linking vertices, each of which is connected via an edge of any polygon to a vertex of interest arrayed in the first direction, to a vertex in a second direction, and linking in a similar way vertices to each vertex of the first direction in the second direction;
• obtaining, for each non-convex polyhedron, a maximum coordinate value V.sub.max and a minimum coordinate value V.sub.min, along each axis, from among coordinate value of vertices of the non-convex polyhedron, and generating an envelope sphere, having a diameter equal to a value .vertline.V.sub.max -V.sub.min .vertline., to be able to cover the non-convex polyhedron;
• checking whether envelope spheres of the first and second non-convex polyhedrons interfere with each other;
• searching for a point of closest approach between two arbitrary convex polyhedrons obtained by decomposing the non-convex polyhedrons after the envelope spheres of the first and second non-convex polyhedrons have interfered with each other;
• obtaining vertices which are adjacent to the point of closest approach obtained most recently on each convex polyhedron, from the nearby-point linear list of each convex polyhedron, and searching for a point of closest approach at a next moment in time from among these vertices;
• performing an interference check using whichever distance between points of closest approach between the convex polyhedrons is shortest;
• and
• controlling operation of the robot based upon the points of closest approach.

A point-of-closest-approach search method for one of collision avoidance between two non-convex polyhedrons and path planning in operating a robot, said method decomposing first and second non-convex polyhedrons into respective ones of convex polyhedrons and continuously searching for points of closest approach between the convex polyhedrons, thereby checking for interference between the non-convex polyhedrons, said method comprising the steps of:

• creating for each convex polyhedron, a list referred to as a nearby-point linear list having a data structure obtained by arraying vertices of each polygon without repetition in a first direction so that the vertices connected by an edge of any polygon are arrayed adjacently, and linking vertices, each of which is connected via an edge of any polygon to a vertex of interest arrayed in the first direction, to a vertex in a second direction, and linking in a similar way vertices to each vertex of the first direction in the second direction;
• generating convex hulls which are the smallest convex polyhedrons which cover the respective non-convex polyhedrons;
• checking whether the convex hulls of the first and second convex polyhedrons interfere;
• searching for a point of closest approach between two arbitrary convex polyhedrons after the convex hulls have interfered with each other;
• obtaining vertices which are adjacent to the point of closest approach obtained most recently on each convex polyhedron, from the nearby-point linear list of each convex polyhedron, and searching for a point of closest approach at a next moment in time from among these vertices;
• performing an interference check using whichever distance between points of closest approach between the convex polyhedrons is shortest;
• and
• controlling operation of the robot based upon the points of closest approach.

A point-of-closest-approach search method for one of collision avoidance between two convex polyhedrons and path planning in operating a robot, said method searching for a point of closest approach from a coordinate origin to a figure which is one of a polygon and a polyhedron formed by a subset whose elements are p-number of points on a difference convex polyhedron, which is formed by a set of position vectors obtained by vector subtraction of arbitrary position vectors of two convex polyhedrons, calculating an inner product between a position vector x of the point of closest approach and position vectors of the vertices of each convex polyhedron, calculating a sum of the inner product and .vertline.x.vertline..sup.2, judging, in a case where the sum is equal to 0, that the point of closest approach is a point of closest approach from the coordinate origin to the difference convex polyhedron and, in a case where the sum is not 0, altering the figure by changing a combination of said p-number of points, repeating the previous steps until the sum becomes 0, and finally obtaining the point of closest approach from the coordinate origin to the difference convex polyhedron to thereby find a point of closest approach of each convex polyhedron, said method comprising the steps of:

• inputting vertex coordinates of all polygons covering each convex polyhedron;
• creating for each convex polyhedron, a list referred to as a nearby-point linear list having a data structure obtained by arraying vertices of each polygon without repetition in a first direction so that the vertices connected by an edge of any polygon are arrayed adjacently, and linking vertices, each of which is connected via an edge of any polygon to a vertex of interest arrayed in the first direction, to a vertex in a second direction, and linking in a similar way vertices to each vertex of the first direction in the second direction;
• obtaining vertices from the nearby-point linear list of each convex polyhedron which are adjacent to a point of closest approach on each convex polyhedron corresponding to the point of the closest approach from the coordinate origin to the figure;
• using position vectors of the obtained vertices in the next calculation of said inner product, thereby obtaining the point of closest approach from the origin to the difference convex polyhedron and obtaining the point of closest approach of each convex polyhedron;
• and
• controlling operation of the robot based upon the points of closest approach.