碰撞问题中的量词消去算法的并行化研究

Research of the Quantifier Elimination Algorithm Parallelization on Collision Problems

机器人技术中的碰撞问题可以被表示成量词消去问题,但由于有些碰撞问题的复杂性使得这些问题在单个微机上求解需要花费的时间很长或者根本就解不出来。本文提出了基于分布Maple系统下量词消去算法的并行化,并针对分布Maple系统的特点以及算法的特点,通过实例分析,给出了两种并行策略,以达到在Maple软件环境下提高处理器利用率,提高量词消去算法的效率的目的。

In robotics we are often interested in whether two objects will collide with each other.the collision problems can be easily formulated as quantifier elimination problems. Some collision problems are still very time consuming and Some seems to be challenging problems. To raise efficiency of the quantifier elimination algorithm, parallelization of the quantifier elimination algorithm on the Distributed Maple environment is proposed and taking the characteristics of the Distributed Maple system and the algorithm ,and one example ,two kinds of parallel tactic are introduced in this paper. These parallel tactics are of advantage to raise rate of using processors