Abstract
Robot manipulators are highly nonlinear systems and their motion control requires the computation of generalized forces/torques to drive all the joint motors at an adequate rate. This paper presents efficient scheduling algorithms for computing the robot inverse dynamics on a multiprocessor system. The problem of scheduling the inverse dynamics computation consisting of m computational modules to be executed on a multiprocessor system consisting of p identical homogeneous processors to achieve a minimum-scheduled length is known to be NP-complete. In order to achieve the minimum computation time, the Newton-Euler equations of motion are expressed in the homogeneous linear recurrence form which results in achieving maximum parallelism. To speed up the searching for a solution, a heuristic search algorithm called Dynamical Highest Level First/Most Immediate Successors First (DHLF /MISF) is first proposed to find a fast but suboptimal schedule. For an optimal schedule, the minimum-scheduled-length problem can be solved by a state- space search method — the A* algorithm coupled with an efficient heuristic function derived from the Fernandez and Bussell bound. The state-space search method is a classical minimum cost graph search algorithm, which is guaranteed to find the optimal solution if the evaluation function is properly defined. An objective function is defined in terms of the task execution time and the optimization of the objective function is based on the minimax of the execution time. The proposed optimization algorithm solves the minimum-scheduled-length problem in pseudo-polynominal time and can be used to solve various large-scale problems in a reasonable time. An illustrative example of computing the inverse dynamics of an n-link manipulator based on the Newton-Euler dynamic equations is performed to show the effectiveness of the A algorithm and the heuristic algorithm DHLF /MISF.
Date of this Version
7-1-1987