STL-GO: A Formal Language for Agent Planning with Topology and Time

When there are more than two agents, planning ceases to be a routing problem and becomes a constrained satisfaction problem. Where each agent should be, when, and with whom it should interact—these are three independent dimensions that conflict with one another in real-world systems (firefighting drones, facility inspections, search and rescue).

STL-GO (Spatio-Temporal Logic with Graph Operators) is an attempt to unify all three dimensions into a single formal language. Graph operators describe topologies: who communicates with whom, who sees whom, and to whom a task is assigned. Spatio-temporal logic defines “when” and “where.” Together, this provides a specification that can be passed to a solver rather than relying on heuristics.

The main engineering value of this work lies not in the language itself, but in the two representations of the same problem. The first is based on mixed-integer programming (MIP), and the second on satisfiability modulo theory (SMT). Both come with correctness guarantees, and both operate through a unified interface: you specify the agent constraints, graph topologies, and the STL-GO specification—and you get a plan.

Why two implementations? Because MIP and SMT react differently to scale. MIP is strong when the objective function and continuous variables dominate; SMT is strong when the Boolean structure of the constraints is more complex than a linear one. Having a unified interface allows us to compare them on a single benchmark rather than on different problem settings, which is itself a rarity in multi-agent research.

The evaluation was conducted on a search-and-rescue benchmark using a group of UAVs, with ablation experiments varying the team size and graph complexity. This is a deliberate choice: dynamic multigraph interactions are the weak point of most existing frameworks, which either ignore changing topology or can handle only static graphs.

The limitations are evident from the problem statement. Encoding multiple time-varying graphs using STL-GO graph operators is a computationally expensive operation. The work focuses on expressiveness and correctness, rather than real-time performance. For production environments, where drones fly for seconds while the solver runs for minutes, this means that STL-GO is suitable for offline planning or as a high-level layer, but tactical decisions will still have to be left to lighter-weight methods.

The next question the authors leave open is: how do STL-GO plans fit into online replanning when the topology changes faster than the solver can reach the optimum? This is the point where formal methods meet reality, and it is precisely where an engineer who has decided to apply this approach should focus their attention.

Source: cs.AI updates on arXiv.org