This paper introduces a partial satisfaction (PS) notion for Signal Temporal Logic (STL), finding solutions for specifications that might contain unfeasible or conflicting subformulae. We formulate the planning problem for teams of agents with robust PS of STL missions as a bi-level optimization problem. The goal is to maximize the number of subformulae satisfied with preference to larger ones that have lower depth in the syntax tree of the overall specification. The second objective is to maximize the smallest STL robustness of the feasible subformulae. First, we propose three Mixed Integer Linear Programming (MILP) methods to solve the inner level of the optimization problem, two exact and a relaxation. Then, the MILP solutions are used to find approximate solutions to the outer level optimization using a linear program. Finally, we show the performance of our methods in two multi-robot case studies: motion planning in continuous spaces, and routing for heterogeneous teams over finite graph abstractions.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Partial Satisfaction of Signal Temporal Logic Specifications for Coordination of Multi-robot Systems


    Additional title:

    Springer Proceedings in Advanced Robotics



    Conference:

    International Workshop on the Algorithmic Foundations of Robotics ; 2022 ; , MD, USA June 22, 2022 - June 24, 2022



    Publication date :

    2022-12-15


    Size :

    16 pages





    Type of media :

    Article/Chapter (Book)


    Type of material :

    Electronic Resource


    Language :

    English






    Satellite Mission Planning with Signal Temporal Logic Specifications

    Pantazides, Athanasios / Aksaray, Derya / Gebre-Egziabher, Demoz | TIBKAT | 2022


    Satellite Mission Planning with Signal Temporal Logic Specifications

    Pantazides, Athanasios / Aksaray, Derya / Gebre-egziabher, Demoz | AIAA | 2022


    DISTRIBUTED PLANNING OF MULTI-AGENT SYSTEMS WITH COUPLED TEMPORAL LOGIC SPECIFICATIONS

    Büyükkoçak, Ali Tevfik / Aksaray, Derya / Yazicioglu, Yasin | TIBKAT | 2021