A Communication Consistent Approach to Signal Temporal Logic Task Decomposition in Multi-Agent Systems

We address the problem of decomposing a global task assigned to a multi-agent system, where the task is expressed using a fragment of Signal Temporal Logic (STL) and communication among agents is range-limited. The global task is expressed as the conjunction of local tasks over individual and relative agent's states, thus naturally inducing the definition of a task graph. Due to the limited communication range, inconsistencies among the edges of the communication and task graph prevent the application of previously derived state feedback control laws for the satisfaction of global STL tasks. To resolve this issue, we propose a task decomposition mechanism reassigning tasks between non-communicating agents to communicating ones, thus ensuring consistency between task and communication graphs. By assuming that the STL tasks are defined over concave predicate functions with polytopic super-level sets, the decomposition can be framed as a parameter optimization problem, solvable via decentralized convex optimization. To guarantee the soundness of our approach, we present various conditions under which the tasks defined in the applied STL fragment are unsatisfiable, and we derive sufficient conditions such that our decomposition approach yields satisfiable global tasks after decomposition.