Abstract
Designing a robot line includes the critical decision about the number of robots needed to carry out all the tasks in the stations and their placement. Similarly, having a robot manipulator mounted on a mobile base, such as an Automated Guided Vehicle (AGV), needs a careful choice of the base positions to minimize cycle time for the operations. In this paper, we solve both the robot placement and the AGV positioning problems by relating them to feature coverage applications, where the challenge is to place cameras (or other sensors) to inspect all points on a workpiece for metrology tasks. These similarities allow us to design an efficient divide&conquer-based algorithm which can be adapted to solve all three problems above, where finding the minimum number of positions for sensors, AGVs and robots is crucial to reduce cycle time and costs. The algorithm is divided in two parts: the first one is responsible for identifying candidate positions, whereas the second solves a set covering problem. We show that these two parts can even be interlaced to obtain high-quality solutions in short time. A successful computational study has been carried out with both artificial instances and three industrial scenarios, ranging from laser sensor inspection cells in the aerospace industry, to an automated cleaning room, and ending with a stud welding station for automotive applications. The results show that geometric and industrial tests, even accounting for kinematics and distance queries, can be handled with high accuracy in reasonable computing time.