Time-optimal task scheduling for articulated manipulators in environments cluttered with obstacles

Abstract

SUMMARY This paper proposes a new approach for solving a generalization of the task scheduling problem for articulated robots (either redundant or non-redundant), where the robot's 2D environment is cluttered with obstacles of arbitrary size, shape and location, while a set of task-points are located in the robot's free-space. The objective is to determine the optimum collision-free robot's tip tour through all task-points passing from each one exactly once and returning to the initial task-point. This scheduling problem combines two computationally NP-hard problems: the optimal scheduling of robot tasks and the collision-free motion planning between the task-points. The proposed approach employs the bump-surface (B-Surface) concept for the representation of the 2D robot's environment by a B-Spline surface embedded in 3D Euclidean space. The time-optimal task scheduling is being searched on the generated B-Surface using a genetic algorithm (GA) with a special encoding in order to take into consideration the infinite configurations corresponding to each task-point. The result of the GA's searching constitutes the solution to the task scheduling problem and satisfies optimally the task scheduling criteria and objectives. Extensive experimental results show the efficiency and the effectiveness of the proposed method to determine the collision-free motion among obstacles.