STL-GO: формальный язык для планирования агентов с топологией и временем

Когда агентов больше двух, планирование перестаёт быть задачей маршрутизации и становится задачей约束ного удовлетворения. Где каждый агент должен находиться, когда и с кем взаимодействовать — это три независимых измерения, которые в реальных системах (пожарные дроны, инспекция предприятий, поиск и спасение) конфликтуют друг с другом.

STL-GO (Spatio-Temporal Logic with Graph Operators) — попытка свести все три измерения в один формальный язык. Графовые операторы описывают топологии: кто с кем связывается, кто кого видит, кому передаёт задачу. Пространственно-временная логика задаёт «когда» и «где». Вместе это даёт спецификацию, которую можно передать решателю, а не оставлять на эвристики.

Главная инженерная ценность работы — не сам язык, а две кодировки одной и той же задачи. Первая на основе mixed-integer programming (MIP), вторая — satisfiability modulo theory (SMT). Обе с гарантиями корректности, обе работают через унифицированный интерфейс: задаёшь ограничения агентов, топологии графов и STL-GO-спецификацию — получаешь план.

Зачем две кодировки? Потому что MIP и SMT по-разному реагируют на масштаб. MIP силён, когда целевая функция и непрерывные переменные доминируют; SMT — когда булева структура ограничений сложнее, чем линейная. Наличие единого интерфейса позволяет сравнивать их на одном бенчмарке, а не на разных постановках, что само по себе редкость в многоагентных работах.

Оценка проведена на бенчмарке поиска и спасения с помощью группы БПЛА, с абляцией по размеру команды и сложности графа. Это честный выбор: именно динамические мультиграфовые взаимодействия — слабое место большинства существующих фреймворков, которые либо игнорируют меняющуюся топологию, либо справляются только со статическими графами.

Ограничения видны из постановки. Кодировка нескольких изменяющихся во времени графов через графовые операторы STL-GO — вычислительно дорогая операция. Работа фокусируется на выразительности и корректности, а не на реальном времени. Для продакшна, где дроны летают секунды, а решатель считает минуты, это означает: STL-GO подходит для офлайн-планирования или как верхнеуровневый слой, а тактические решения всё равно придётся отдавать более лёгким методам.

Следующий вопрос, который авторы не закрывают: как STL-GO-планы встраиваются в online replanning, когда топология меняется быстрее, чем решатель доходит до оптимума. Это та точка, где формальные методы встречаются с реальностью, и именно туда стоит смотреть инженеру, решившему применить этот подход.

Источник: cs.AI updates on arXiv.org