Method and apparatus for controlling the movement of a guided object

Claim 3

A method as claimed in Claim 1, characterized in that the cluster comprises a succession of levels of guard bubbles, in that each guard bubble of an innermost level contains a selection of the cluster bubbles such that the guard bubbles of the innermost level contain, between them, all the bubbles of the cluster and such that each bubble is assigned to only one innermost guard bubble, in that each guard bubble of a given level outside the innermost level encloses a selection of the guard bubbles of the adjacent inner level such that the guard bubbles of the given level contain, between them, all the guard bubbles of the adjacent inner level and such that a guard bubble of the adjacent inner level is assigned to only one guard bubble of the given level.

Claim 4

A method as claimed in Claim 1 or 2, characterized in that the collision calculation comprises calculating the trajectory of a bubble of the representation of the guided object relative to a bubble of a representation of another object for a limited period of time as a straight line approximation at constant velocity, deriving an equation giving the square of the separation of the bubbles as a function of time during the limited period, and calculating the time of a collision as an early approximate solution of the equation by applying Newton's method of successive approximations.

Claim 5

A method as claimed in Claim 3, characterized in that the time of a collision is calculated as the first approximate solution given by Newton's method.

Claim 6

Apparatus for controlling the movement of a guided object in an environment to avoid collision with another object, comprising movement means for guiding the guided object in the environment, means for measuring the position of the guided object relative to any other object, information storage means for storing the shape and size of the guided object and for storing the location, shape and size of any other object, and calculation means for taking the measured position of the guided object and the stored information on the guided object and on any other object, calculating a collision-free path for the guided object, and outputting control information to the movement means to realize said collision-free path wherein the stored information on each object comprises at least one spherical bubble of known radius and centre position which contains at least partially the geometrical outline of that object, at least one object being represented by a cluster of interpenetrating spherical bubbles of at least two different radii, the outermost surface of the cluster containing the outermost surface of the object in question, and wherein the collision between objects is predicted as the first estimated point of touch to occur between any bubble of the cluster representing one object with a bubble representing another object, characterized in that the cluster comprises at least one spherical guard bubble, any guard bubble containing a selection of the bubbles of that cluster, and in that any guard bubble from the cluster is examined for collision before further cluster bubbles are examined.

Claim 7

Apparatus for controlling the movement of a guided object in an environment to avoid collision with another object, comprising movement means for guiding the guided object in the environment, means for measuring the position of the guided object relative to any other object, information storage means for storing the shape and size of the guided object and for storing the location, shape and size of any other object, and calculation means for taking the measured position of the guided object and the stored information on the guided object and on any other object, calculating a collision-free path for the guided object, and outputting control information to the movement means to realize said collision-free path wherein the stored information on each object comprises at least one spherical bubble of known radius and centre position which contains at least partially the geometrical outline of that object, at least one object being represented by a cluster of interpenetrating spherical bubbles of at least two different radii, the outermost surface of the cluster containing the outermost surface of the object in question, and wherein the collision between objects is predicted as the first estimated point of touch to occur between any bubble of the cluster representing one object with a bubble representing another object, characterized in that the cluster comprises at least one spherical guard bubble, any guard bubble containing a selection of the bubbles of that cluster, and in that any guard bubble from the cluster is examined for collision before further cluster bubbles are examined.

Claim 8

Apparatus as claimed in Claim 5, characterized in that the collision calculation comprises calculating the trajectory of a bubble of the representation of the guided object relative to a bubble of a representation of another object for a limited period of time as a straight line approximation at constant velocity, deriving an equation giving the separation of the bubbles as a quadratic function of time during the limited period, and calculating the time of a collision as an early approximate solution of the equation by applying Newton's method of successive approximations.