Automated Planning of Motion Tasks for Multi-Robot Systems

In this paper we present an automated task planning methodology to automatically compose multi-robot motion tasks. A motion task is defined as an input-output module. Primitive motion tasks represented as modules (called primitive modules) are defined based on Linear Temporal Logic specifications. The task planning is then considered as a composition over compatible primitive modules in such a way that the inverted motion task module and the primitive modules form a closed chain. The problem is posed as an integer programming problem and is reduced to the combinatorial optimization problem of shortest dipath which can be solved in polynomial time. The basic safety and liveness specifications of the primitive task controllers are inherited by the resulting composed system and the requested task specifications are satisfied by construction, ensuring a correct design. The effectiveness of the proposed methodology is shown through computer simulation.