ProSeqqo: A generic solver for process planning and sequencing in industrial robotics

Task sequencing problems arise in many different forms in various robotic applications. The task sequence can be subject to different constraints, and various cost functions can be used to assess the quality of a solution. Moreover, task sequencing is often closely coupled with other sub-problems of process planning, such as the selection of a robot joint configurations for each task originally defined in the task space, or the selection of cut directions in a cutting problem. This implies that these problems must be solved jointly, in an integrated way. This complexity results that almost all previous approaches to robotic task sequencing aim at solving the sequencing problem arising in a specific application, using a dedicated - typically, meta-heuristic - solution method. Despite this, such custom methods rely on similar mathematical models, namely, different extension of the well-known traveling salesman problem (TSP). In order to avoid such redundancies, this paper proposes a generic problem definition language for robotic task sequencing and process planning problems, as well as a solver called ProSeqqo to compute close-to-optimal solutions for those problems. ProSeqqo relies on the vehicle routing problem (VRP) library of Google OR-Tools, extended with custom algorithms to tackle conditional precedence constraints. It is demonstrated that the proposed language can capture the overwhelming majority of the robotic task sequencing problems investigated in the scientific literature, and the application of the modeling language and the solver is illustrated on five, seemingly very different use cases, including both real industrial applications and lab demonstrations. Results of thorough computational experiments are also presented. The ProSeqqo solver has been made available open source for the scientific community.

Automated summary

Task sequencing problems are common in robotic applications and can be solved by defining different constraints and cost functions. These problems are often closely related to other sub-problems in process planning and need to be solved jointly. Current methods are often developed for specific applications but rely on similar mathematical models. To avoid redundancies, this paper proposes a generic problem definition language and solver for robotic task sequencing problems. Experimental results show that the proposed language and solver can be applied to a variety of task sequencing problems in robotics.