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.