Optimal robot task scheduling based on genetic algorithms

Industrial robots should perform complex tasks in the minimum possible cycle time in order to obtain high productivity. The problem of determining the optimum route of a manipulator's end effector visiting a number of task points is similar but not identical to the well-known travelling salesman problem (TSP). Adapting TSP to Robotics, the measure to be optimized is the time instead of the distance. In addition, the travel time between any two points is significantly affected by the choice of the manipulator's configuration. Therefore, the multiple solutions of the inverse kinematics problem should be taken into consideration. In this paper, a method is introduced to determine the Optimum sequence of task points visited by the tip of the end effector of an articulated robot and it can be applied to any non-redundant manipulator. This method is based on genetic algorithms and an innovative encoding is introduced to take into account the multiple solutions of the inverse kinematic problem. The results show that the method can determine the optimum sequence of a considerable number of task points for robots up to six-degrees of freedom. (C) 2004 Elsevier Ltd. All rights reserved.