Efficient Solutions to Some Transportation Problems with Applications to Minimizing Robot Arm Travel

摘要

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 given objects (the gripper cannot be holding more 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 is NP-hard, we focus on the problem of minimizing only the total angular motion (rotation of the link about the pivot), or only the 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 object can 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.