Efficient scheduling algorithms for robot inverse dynamics computation on a multiprocessor system

Abstract

The problem of scheduling the robot 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-schedule length is examined. This scheduling problem is known to be NP-complete. To achieve the minimum computation time, the Newton-Euler equations of motion are expressed in the homogeneous linear recurrence form that 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 proposed to find a fast but suboptimal schedule. For an optimal schedule the minimum-schedule-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.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>