Signal Temporal Logic
- Aussi appelé: STL
- Catégorie: Planning & manipulation › Task-level
- Mots-clés: formal-methods, temporal-logic, task-specification, control, planning
Un langage formel pour écrire des exigences bornées dans le temps sur des signaux à valeurs réelles, comme des trajectoires de robot, avec un score de robustesse qui indique à quel point une trajectoire les satisfait.
Définition
La logique temporelle de signal (signal temporal logic, STL) est un langage de spécification formelle pour des propriétés de signaux continus à valeurs réelles au cours du temps. Elle a été introduite par Oded Maler et Dejan Nickovic en 2004 comme extension de la logique temporelle métrique à intervalles, dans le but de surveiller des signaux issus de systèmes continus et hybrides. En robotique, le signal est généralement une trajectoire d'états, et la STL permet à un ingénieur d'écrire des exigences telles que « atteindre la région A en moins de 10 secondes, y rester au moins 2 secondes, et ne jamais s'approcher à moins de 0,5 mètre de l'obstacle » sous la forme d'une seule formule précise.
Une formule STL est construite à partir de prédicats de la forme μ(x) ≥ 0, où μ est une fonction de l'état comme une distance à un but, combinés avec des opérateurs booléens (non, et, ou) et des opérateurs temporels munis d'intervalles de temps explicites : toujours (always) G[a,b] (la formule est vraie à chaque instant de l'intervalle), finalement (eventually) F[a,b] (elle est vraie à un instant de l'intervalle) et jusqu'à (until) U[a,b]. Comme les prédicats sont à valeurs réelles, la STL possède une sémantique quantitative en plus d'un sens vrai/faux. La robustesse (robustness) d'une trajectoire vis-à-vis d'une formule, telle que définie par Fainekos et Pappas et par Donzé et Maler, est un nombre signé : positive, elle signifie que la formule est satisfaite ; négative, qu'elle est violée ; et sa valeur absolue indique de combien le signal pourrait être perturbé avant que le verdict change.
La robustesse transforme la spécification en optimisation. Les planificateurs peuvent maximiser directement la robustesse, encoder la formule sous forme de contraintes dans un programme en nombres entiers mixtes, ou utiliser des approximations lisses des opérateurs min et max afin d'appliquer l'optimisation de trajectoire par gradient et des méthodes d'apprentissage. La STL sert aussi à l'exécution pour surveiller si un système respecte ses exigences, et pour falsifier des contrôleurs en cherchant des perturbations qui rendent la robustesse négative. Les principaux coûts pratiques sont calculatoires : des opérateurs temporels imbriqués et de longs horizons rendent les problèmes d'optimisation résultants volumineux, et la structure min/max non lisse complique les méthodes de gradient.
Pourquoi c'est important
Beaucoup de tâches robotiques comportent des échéances, des contraintes d'ordre et des exigences de sécurité qu'il est malcommode d'exprimer par une seule fonction de coût ou récompense. La STL donne à ces exigences un sens exact qui peut être vérifié, surveillé et optimisé, et son score de robustesse fournit aux contrôleurs une marge avec laquelle travailler plutôt qu'un succès ou un échec binaire.
Applications principales
- Spécification de tâches avec échéances et ordre pour robots mobiles et drones
- Commande prédictive qui maximise la robustesse de la spécification
- Surveillance à l'exécution des exigences de sécurité et de temps
- Falsification et test de contrôleurs, y compris de systèmes automobiles
- Façonnage de récompenses ou de contraintes pour des politiques apprises
- Coordination multirobot avec des objectifs communs bornés dans le temps
En pratique
Une équipe qui construit un robot d'entrepôt écrit la tâche sous forme de formule STL : finalement, en moins de 30 secondes, atteindre la zone de prise, puis, dans les 20 secondes suivantes, atteindre la zone de dépose, tout en restant toujours à au moins 0,3 mètre des étagères et des personnes. Elle modélise le robot comme un double intégrateur, encode la formule sur un horizon glissant sous forme de contraintes en nombres entiers mixtes et la résout dans une boucle de commande prédictive qui maximise la robustesse. Lorsqu'une personne entre dans l'allée, le prédicat d'obstacle change, le solveur replanifie, et la valeur de robustesse enregistrée montre à quel point le robot s'est approché d'une violation de l'exigence de dégagement. La même formule est exécutée comme moniteur hors ligne sur les trajectoires enregistrées pendant les essais.
Idées reçues
- La STL dont il est question ici est le format de fichier de modèles 3D STL — l'abréviation désigne aussi le format de maillage de stéréolithographie utilisé en CAO et en impression 3D, qui n'a aucun rapport avec la logique temporelle de signal
- La STL ne donne qu'une réponse oui/non — sa sémantique de robustesse quantitative fournit une marge de satisfaction signée que contrôleurs et optimiseurs peuvent exploiter
- Maximiser la robustesse produit toujours un comportement naturel — la robustesse standard ne dépend que de l'instant le plus défavorable, si bien que les optimiseurs peuvent produire des trajectoires qui respectent tout juste la marge à un instant et ignorent le reste
- La STL est la même chose que la logique temporelle linéaire (LTL) — la LTL raisonne sur des propositions discrètes sans bornes de temps explicites, tandis que la STL utilise des prédicats à valeurs réelles et des intervalles temporels
Qui devrait le savoir
- Ingénieurs en planification de mouvement et en commande qui travaillent avec des spécifications formelles de tâches
- Ingénieurs en vérification et en sécurité des systèmes autonomes
- Chercheurs qui combinent méthodes formelles et apprentissage
- Concepteurs de missions multirobots et de drones
Technologies associées
- Logique temporelle linéaire (Linear Temporal Logic)
- Logique temporelle métrique à intervalles (Metric Interval Temporal Logic)
- Solveurs de programmation en nombres entiers mixtes (Mixed-Integer Programming Solvers)
- Commande prédictive (Model Predictive Control)
- Fonctions barrières de contrôle (Control Barrier Functions)
- Vérification à l'exécution (Runtime Verification)
Termes associés
- Control Barrier Function
- Model Predictive Control
- Mixed-Integer Programming
- Task Planning
- Trajectory Planning
- Double Integrator
Projets associés
- Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design
- MuJoCo MPC: DeepMind's interactive real-time model predictive control framework for MuJoCo
- PyPose: PyTorch library for differentiable robotics with deep learning and Lie group optimization
- ros2_control: Hardware abstraction framework for ROS 2 enabling portable robot control code
- safe-control-gym: Benchmark suite for safe learning-based control: RL and MPC under one API
- OpEn (Optimization Engine): Embedded nonconvex optimization solver in Rust for real-time MPC on robots