High-Level Multi-Robot Trajectory Planning And Spurious Behavior Detection

1. Problem Statement

Multi-robot systems (MRS) are increasingly used for complex missions (surveillance, rescue, coverage) due to their efficiency and fault tolerance. However, coordinating heterogeneous agents introduces significant challenges in ensuring that the collective team behavior adheres to high-level mission specifications.

The core problem addressed is the detection of spurious behaviors—executions that appear locally correct for individual agents but violate global mission constraints. These deviations can manifest as:

• Incorrect task sequences: Violating the logical order of tasks.
• Spatial constraint violations: Entering forbidden zones or failing mutual exclusion constraints.
• Timing inconsistencies: Failing to meet simultaneity requirements or low-level execution delays.
• Semantic deviations: Violating conditional access rules or mission semantics defined by Linear Temporal Logic (LTL).

Existing methods often focus on low-level faults or single-agent anomalies, lacking the capability to analyze entire team trajectories against high-level formal specifications.

2. Methodology

The authors propose a structured pipeline integrating formal methods for data generation and deep learning for anomaly detection. The methodology consists of five phases:

A. Formal Specification via Nets-within-Nets (NWN)

To generate ground-truth data, the authors utilize the Nets-within-Nets (NWN) paradigm, a hierarchical Petri Net formalism.

• Specification Net: Represents the global mission as a co-safe LTL formula (e.g., $\diamond(y_1 \land \diamond(y_2 \land \diamond y_3))$).
• Robot Nets: Individual Petri Nets modeling each robot's discrete environment and movement capabilities.
• System Net: Synchronizes the evolution of robot nets with the mission specification using a Global Enabling Function (GEF).
• Utility: This framework allows for the systematic generation of both valid trajectories and controlled "spurious" trajectories by modifying the nets to introduce specific violations.

B. Dataset Generation (Renew Simulator)

Using the Renew simulator, the NWN model generates symbolic trajectory logs.

• Process: The system iterates through enabled transitions, selecting macro-transitions (combinations of robot moves) via a random policy to ensure diversity.
• Output: Trajectories are recorded as text files where each line represents a timestep with tuples containing: Robot ID, duration, start/end places, and atomic proposition labels.
• Anomaly Injection: Spurious datasets are created by altering robot nets (to simulate timing mismatches or capacity violations) or modifying the specification net (to induce logical deviations).

C. Low-Level Simulation (VMAS)

To bridge the gap between symbolic logic and physical reality, the authors use VMAS (a low-level multi-robot simulator with continuous dynamics).

• Purpose: To extract realistic transition times ($t_i$) between regions of interest, which high-level symbolic models cannot accurately predict.
• Mechanism: Simulates holonomic robots using RRT* for path planning and potential fields for collision avoidance, providing empirical duration data for the symbolic logs.

D. Trajectory Encoding

Symbolic logs are converted into fixed-size numerical tensors for machine learning using a custom Action-Token Encoding:

• Robot ID & Places: Mapped to trainable embedding matrices ($W_{ID}, W_{place}$).
• Duration ($t_i$): Encoded using a 2D angle embedding after logarithmic normalization to handle variable time scales: $V_t = [\sin \theta, \cos \theta]^T$.
• Labels: Encoded as vectors indicating origin (-1), destination (1), or neutral (0) for atomic propositions.
• Positional Encoding: Uses fixed sinusoidal embeddings (similar to Transformers) to capture the step index $k$ without learnable parameters.
• Result: Each action becomes a dense vector (e.g., 140-dimensional) representing the full context of the robot's move.

E. Machine Learning Architecture

A Transformer-based neural network is employed for classification:

1. Linear Projection: Maps input tokens to a 256-dimensional latent space.
2. Transformer Encoder: Stacked self-attention layers (4 heads) with Feed-Forward Networks (GELU activation) to capture intra- and inter-robot dependencies.
3. Max Pooling: Aggregates the sequential output into a fixed-size vector.
4. Classifier Head: A Multi-Layer Perceptron (MLP) with a sigmoid activation to output the probability of a trajectory being spurious.

3. Key Contributions

1. Structured Data Generation Framework: A novel approach using NWN and Renew to generate diverse, labeled datasets of multi-robot trajectories with inherent ground truth for both normal and various types of spurious behaviors.
2. Learning-Based Anomaly Detection Pipeline: A system that classifies entire team trajectories as normal or anomalous, capable of detecting subtle inconsistencies across low-level (timing, collisions) and high-level (LTL semantics) constraints.
3. Novel Embedding Strategy: A specialized encoding scheme that effectively translates symbolic, variable-length multi-robot logs into dense, fixed-size representations suitable for Transformer architectures.
4. Comprehensive Evaluation: Extensive experiments demonstrating the model's ability to detect specific mission violations (e.g., forbidden zones, sequentiality errors) and low-level execution inefficiencies.

4. Experimental Results

The model was evaluated on seven distinct anomaly cases using 2,000 trajectories per case (80/10/10 split).

• Overall Performance: The system achieved high accuracy in identifying execution inefficiencies (91.3%) and core mission violations (88.3%).
• Specific Case Results:
  • Forbidden Zone Breaching: Near-perfect detection (Accuracy: 0.996, F1: 0.994).
  • Sequentiality Violation: High performance (F1: 0.906), indicating strong temporal reasoning.
  • Simultaneity & Recurrency: Robust detection (F1 > 0.82).
  • Conditional Access & Mutual Exclusion: Lower performance (F1: 0.647 and 0.815 respectively), attributed to the complexity of causal relationships and path dependencies.
  • Low-Level Execution: High accuracy (F1: 0.923) in detecting timing and capacity anomalies.
• Ablation Study:
  • Replacing the proposed complex embeddings with simple One-Hot encoding caused a significant performance drop (F1 from 0.829 to 0.593).
  • Feeding raw data directly into the Transformer resulted in the worst performance, highlighting the necessity of the encoding pipeline.
  • Reducing attention heads lowered recall, while excessive heads hurt performance, confirming the need for balanced architecture design.

5. Significance and Limitations

Significance:
This work bridges the gap between formal verification (LTL/Petri Nets) and data-driven anomaly detection. By generating synthetic data with formal guarantees and using a Transformer to learn complex spatiotemporal patterns, the system offers a robust solution for ensuring mission integrity in multi-robot teams, moving beyond simple local fault detection to holistic team behavior analysis.

Limitations & Future Work:

• Generalization: The current model requires retraining for each specific anomaly type and does not generalize across all LTL specifications. Future work aims to condition the model on the LTL specification itself.
• Localization: The system classifies the entire trajectory as spurious but cannot yet pinpoint the exact temporal segment or specific robot responsible for the failure. Future research plans to incorporate fine-grained supervision to localize anomalies.