Motion planning for multi-robot assembly systems

The classical travelling salesperson problem (TSP) models the movements of a salesperson travelling through a number of cities. The optimization problem is to choose the sequence in which to visit the cities in order to minimize the total distance travelled. This paper presents a generalized point-to-point motion-planning technique for multi-robot assembly systems modelled as TSP-type optimization problems. However, in these augmented TSPs (TSP+), both the 'sales-person' (a robot with a tool) as well as the 'cities' (another robot with a workpiece) move. In addition to the sequencing of tasks, further planning is required to choose where the 'salesperson' (i.e., the tool) should rendezvous with each 'city' (i.e. the workpiece). The use of a genetic algorithm (GA) is chosen as the search engine for the solution of this TSP+ optimization problem. As an example area, the optimization of the electronic-component placement process is addressed. The simulation tools developed have been tested on five different component-placement system configurations. In the most generalized configuration, the placement robot meets the component delivery system at an optimal rendezvous location for the pick-up of the component and subsequently meets the printed-cirucit-board (on a mobile XY-table) at an optimal rendezvous location. In addition to the solution of the component-placement sequencing problem and the rendezvous-point planning problem, the collision-avoidance issue is addressed.