Reports and Papers Archive
Predictive Battlespace Awareness to Improve Military Effectiveness
21st National Infrmation Systems Security Conference (Volume 2)
Information Hiding, Second International Workshop - Portland, Oregon
Information Hiding, Third International Workshop Dresden, Germany
Information Hiding, Third International Workshop Dresden, Germany
New Security Paradigms Workshop, 1997
Proceedings of the 2001 USENIX Annual Technical Conference
25th International Conference on Software Engineering
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 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.

