TY - GEN

T1 - Spatial planning and geometric optimization

T2 - 5th International Workshop on Automated Deduction in Geometry, ADG 2004

AU - Chibisov, Dmytro

AU - Mayr, Ernst W.

AU - Pankratov, Sergey

PY - 2006

Y1 - 2006

N2 - In this paper, we propose a symbolic-numerical algorithm for collision-free placement and motion of an object avoiding collisions with obstacles. The algorithm is based on the combination of configuration space and energy approaches. According to the configuration space approach, the position and orientation of the geometric object to be moved or placed is represented as an individual point in a configuration space, in which each coordinate represents a degree of freedom in the position or orientation of this object. The configurations which, due to the presence of obstacles, are forbidden to the object, can be characterized as regions in this configuration space called configuration space obstacles. As will be demonstrated, configuration space obstacles can be computed symbolically using quantifier elimination over the reals and represented by polynomial inequalities. We propose to use the functional representation of semi-algebraic point sets defined by such inequalities, so-called R-functions, to describe nonlinear geometric objects in the configuration space. The potential field defined by R-functions can be used to "move" objects in such a way as to avoid collisions. Introducing the additional function, which forces the object towards the goal position, we reduce the problem of finding collision free path to a solution of the Newton's equations, which describes the motion of a body in the field produced by the superposition of "attractive" and "repulsive" forces. These equations can be solved iteratively in a computationally efficient manner. Furthermore, we investigate the differential properties of R-functions in order to construct a suitable superposition of attractive and repulsive potentials.

AB - In this paper, we propose a symbolic-numerical algorithm for collision-free placement and motion of an object avoiding collisions with obstacles. The algorithm is based on the combination of configuration space and energy approaches. According to the configuration space approach, the position and orientation of the geometric object to be moved or placed is represented as an individual point in a configuration space, in which each coordinate represents a degree of freedom in the position or orientation of this object. The configurations which, due to the presence of obstacles, are forbidden to the object, can be characterized as regions in this configuration space called configuration space obstacles. As will be demonstrated, configuration space obstacles can be computed symbolically using quantifier elimination over the reals and represented by polynomial inequalities. We propose to use the functional representation of semi-algebraic point sets defined by such inequalities, so-called R-functions, to describe nonlinear geometric objects in the configuration space. The potential field defined by R-functions can be used to "move" objects in such a way as to avoid collisions. Introducing the additional function, which forces the object towards the goal position, we reduce the problem of finding collision free path to a solution of the Newton's equations, which describes the motion of a body in the field produced by the superposition of "attractive" and "repulsive" forces. These equations can be solved iteratively in a computationally efficient manner. Furthermore, we investigate the differential properties of R-functions in order to construct a suitable superposition of attractive and repulsive potentials.

UR - http://www.scopus.com/inward/record.url?scp=33745289416&partnerID=8YFLogxK

U2 - 10.1007/11615798_10

DO - 10.1007/11615798_10

M3 - Conference contribution

AN - SCOPUS:33745289416

SN - 354031332X

SN - 9783540313328

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 156

EP - 168

BT - Automated Deduction in Geometry - 5th International Workshop, ADG 2004, Revised Papers

Y2 - 16 September 2004 through 18 September 2004

ER -