Mikhail J. Atallah, S. Rao Kosaraju

techreport

We give efficient solutions to transportation problems motivated by the following robotics problem. A robot arm has the task of rearranging m objects between n stations in the plane. Each object is initially at one of these n stations and needs to be moved to another station. The robot arm consists of a single link that rotates about a fixed pivot. The link can extend in and out (like a telescope) so that its length is a variable. At the end of this "telescoping" link lies a gripper that is capable of grasping any one of the m objects (the gripper cannot be holding mre than one object at the same time). The robot arm must transport each of the m objects to its destination and come back to where it started. Since the problem of scheduling the motion of the gripper so as to minimize the total distance traveled in NP-hard, we focus on the problem of minimizing only the total angular motion (rotation of the link about the pivo), or only telescoping motion. We give algorithms for two different modes of operation: (i) No-drops. No object can be dropped before its destination is reached. (ii) With-drops. Any objectcan be dropped at any number of intermediate points. Our algorithm for case (i) runs in O(m + n log n) time for angular motion and in O(m + n alpha(n)) time for telescoping motion. Our algorithm for case (ii) runs in O(m + n) time for angular motion and with the same time bound for telescoping motion. The most interesting problem turns out to be that of minimizing angular motion for the with-drops mode of operation.

1988 – 10

SIAM J. COMPUT.

Atallah

5

Society for Industral and Applied Mathematics

17

Purdue University, Johns Hopkins University

1988-10-01

A hard-copy of this is in the Papers Cabinet