An Approximation Algorithm with Factor Two for a Repetitive Routing Problem of Grasp-and-Delivery Robots

摘要

In this paper, we consider a routing problem for a single grasp-and-delivery robot used on a printed circuit (PC) board assembly line. The robot arranges n identical pins from their current configuration to the next required configuration by transferring them one by one in a transition. The n pins support a PC board from underneath to prevent it from overbending as an automated manipulator embeds electronic parts in the PC board from above. Each PC board has its own circuit pattern, and required configurations for PC boards all differ. Given an initial configuration of n pins and a sequence of m required configurations, the problem asks to find a transfer route of the robot that minimizes the route length over all m transitions. By applying a weighted matroid intersection algorithm, we show the repetitive routing problem to be 2-approximable in polynomial time.