💻 computer science

Reactive Replanning Using a Target-State-Driven Strategy for Heterogeneous Multi-Robot Systems under Counting LTL Constraints

This paper proposes TRRS, a target-state-driven reactive replanning strategy that utilizes a receding-horizon mixed-integer linear programming formulation to dynamically handle position shifts and priority updates in heterogeneous multi-robot systems under counting LTL constraints, demonstrating superior performance over static and greedy baselines through simulations and physical experiments.

Original authors: Ting Jiao, Mengge Wang, Yuwei Wang, Rong Zhang, Huanrong Ren

Published 2026-09-23

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Ting Jiao, Mengge Wang, Yuwei Wang, Rong Zhang, Huanrong Ren

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a team of rescue robots sent into a disaster zone to find survivors. In a perfect world, the map would stay still, the survivors would stay put, and the robots would follow a single, pre-written script to the finish line. But the real world is messy. A survivor might crawl to a safer spot, or a new, more urgent call for help might come in from a different location. If the robots are stuck following their original script, they might waste precious time heading toward a person who has already moved, or they might ignore a critical new task because their list was written hours ago. This is the central challenge for teams of machines that must work together in changing environments: how do you keep a plan that was perfect a moment ago from becoming useless the next second?

The solution lies in a concept called reactive replanning. Instead of calculating one giant, unchangeable path at the start, the system constantly watches the world, detects changes, and recalculates the best course of action on the fly. This is especially difficult when the team is made of different types of robots, each with its own abilities, and when the mission has strict rules about what must happen and in what order. Researchers have long known that you cannot simply ignore these rules, but finding a way to update the plan quickly enough to be useful in real-time has been a major hurdle.

A team of researchers from Shanxi University has developed a new method to solve this problem, specifically for teams of mixed robots working under complex rules. They call their system TRRS, which stands for a Target-State-Driven Reactive Replanning Strategy. The core idea is to treat the robots' mission not as a fixed list of chores, but as a living situation that requires constant adjustment. The researchers built a mathematical framework that allows the robots to handle two specific types of changes: when a target moves to a new location, and when the urgency of a target changes.

In many previous systems, these two types of changes were treated the same way, or they were handled by separate, disconnected parts of the software. The new approach recognizes that they are fundamentally different. If a target moves, the robot's current path is physically broken; the robot must stop what it is doing and immediately head to the new spot. However, if only the priority of a target changes—meaning a task becomes more important but the location stays the same—the system acts more carefully. It allows the robot to finish its current job before switching to the new, urgent task. This distinction prevents the robots from wasting energy by constantly aborting tasks that are nearly complete, while still ensuring they react instantly when the physical world shifts beneath their wheels.

To make these decisions, the system uses a method called Mixed-Integer Linear Programming. In plain terms, this is a powerful way of solving puzzles with many variables and strict rules. The researchers set up the problem so that the computer has to find a path for every robot that satisfies the mission's rules, avoids collisions, and respects the different capabilities of each robot type. Because solving this puzzle for a whole day of work at once takes too long, the team uses a "receding horizon" approach. This means the computer only plans a short window of time ahead, solves the puzzle for that window, and then executes just the first step. As time passes and new information arrives, the window slides forward, and the computer solves a fresh, slightly updated puzzle. This keeps the thinking time short enough to happen while the robots are actually moving.

The researchers tested this system in two very different environments. First, they ran simulations in an open space where robots had to follow complex rules about visiting areas and returning to safety. Second, they tested them in a narrow corridor, a tight space where robots could easily get stuck or block each other. In both cases, they compared their new method against two older approaches: one where the robots stuck to a static plan no matter what happened, and another where robots simply grabbed the nearest available task without coordinating with the rest of the team.

The results were clear. The static plan failed completely in both scenarios because it could not adapt to the moving targets. The simple "grab the nearest task" method worked okay in the open space but fell apart in the narrow corridor, where the lack of coordination led to robots blocking each other and getting stuck. The new system, however, succeeded in every single test. It managed to complete all the tasks in the open space and the tight corridor, even as targets moved and priorities shifted. The system was also fast enough for real-world use; each time it had to recalculate the plan, it took less than a tenth of a second.

To prove the concept worked outside of a computer simulation, the team built a physical test with two small, wheeled robots. They set up a scenario where the robots had to pick up a backpack and a book and bring them to a storage box. Midway through the task, a human moved the book to a new spot and introduced a new, high-priority task: delivering water. The system detected both changes instantly. It paused the lower-priority book task, sent a robot to deliver the water first, and then resumed the book task, guiding the robot to the book's new location. The robots adapted seamlessly, proving that the logic holds up in the physical world.

This work shows that it is possible to give a team of diverse robots the ability to think on their feet without losing sight of the big picture. By distinguishing between a target that has moved and a task that has simply become more urgent, the system avoids unnecessary chaos. It ensures that the robots remain efficient and cooperative, even when the situation around them is unpredictable. While the current version of the system works best with a small number of robots, the researchers see this as a vital step toward deploying larger, more capable teams in real disaster zones, where the difference between a rigid plan and a flexible response can be the difference between success and failure.

Technical Summary: Reactive Replanning Using a Target-State-Driven Strategy for Heterogeneous Multi-Robot Systems under Counting LTL Constraints

1. Problem Statement

In dynamic heterogeneous multi-robot systems (HMRS), static plans often become obsolete due to unexpected changes in target attributes during execution. Specifically, targets may undergo position shifts (spatial coordinate changes) or priority updates (changes in urgency levels). Existing approaches typically treat these variations as independent factors or decouple replanning from task allocation and priority arbitration. Furthermore, standard Linear Temporal Logic (LTL) planning struggles with quantitative resource constraints required for heterogeneous teams (e.g., "at least $N$ robots of type $j$ must be in region $S$ ").

The core challenge addressed is how to jointly incorporate both position shifts and priority updates into a unified Mixed-Integer Linear Programming (MILP) framework for heterogeneous teams while maintaining online execution feasibility. The system must satisfy Counting LTL (cLTL) constraints, which enforce both temporal logic and type-specific quantitative resource limits, without violating mission constraints when targets change dynamically.

2. Methodology: TRRS Framework

The authors propose TRRS (Target-state-driven Reactive Replanning Strategy), a framework designed to reactively replan trajectories in response to target state variations. The methodology consists of three integrated components:

2.1 Unified MILP Encoding

The collaborative planning problem is formulated as an MILP that jointly optimizes task allocation and trajectory generation.

System Model: The workspace is a discrete grid graph $G=(V, E)$ . The robot team consists of heterogeneous types $j \in [m]$ , where each type $j$ has a set of robots $K_j$ . Targets $P(t)$ are time-varying, possessing spatial coordinates $\hat{p}_k(t)$ and priority levels $pri_k(t)$ .
Constraints:
- Kinematics & Collision: Robots move between adjacent vertices or stay stationary. Vertex mutual exclusion ensures no two robots occupy the same cell simultaneously.
- cLTL Specification: The mission is specified using cLTL, which extends standard LTL with counting predicates (e.g., $tp(S, N^j)$ ). These predicates are linearized using big-M reformulation techniques to enforce constraints like "at least $N$ robots of type $j$ in region $S$ ."
- Objective: Minimize total travel cost (Euclidean grid distance) subject to kinematic, collision, and cLTL constraints.

2.2 State-Aware Trigger Mechanism

TRRS employs a differentiated trigger mechanism that distinguishes between two types of target changes, applying specific preemption rules:

Position Shifts ( $E_{pos}$ ): If a target's location changes, the existing trajectory becomes physically obsolete. The system triggers an immediate preemption, aborting the current task and reassigning the robot to the new target immediately.
Priority Updates ( $E_{pri}$ ): If only the priority changes, the system does not necessarily abort current tasks. Instead, it reorders the task queue. Robots are instructed to complete their current task before switching to a newly assigned higher-priority target, unless the priority change is coupled with a position shift.
Coupled Events: If both occur, a full refresh is performed with immediate preemption.

2.3 Receding-Horizon Control

To ensure the MILP remains tractable for online execution, TRRS utilizes a receding-horizon (rolling window) approach:

The global horizon $T$ is divided into short, fixed-length windows of size $h$ (set to $h=7$ in experiments).
At each round, the MILP is solved only for the current window. The terminal state of the current window serves as the initial condition for the next.
Replanning is triggered either by the detection of target variations (via the trigger mechanism) or by the expiration of the current time window.

3. Key Contributions

Unified cLTL Framework for Heterogeneous Teams: The paper constructs a MILP formulation that captures both target position and priority variations within a single constraint framework, overcoming the decoupled treatment common in prior LTL-based planning.
Differentiated Preemption Logic: Unlike existing methods that treat all changes identically, TRRS distinguishes between position shifts and priority updates. It applies immediate preemption for spatial changes but allows task completion for priority-only changes, effectively reducing unnecessary online recomputation and task abandonment.
Online Tractability via Receding Horizon: By adopting a short rolling window, the framework ensures that MILP solutions are returned within bounded computation times suitable for real-time deployment.
Validation: The approach is validated through both Monte Carlo simulations and physical robot experiments, demonstrating superior performance over static and greedy baselines.

4. Experimental Results

The authors evaluated TRRS in two scenarios: an open-space environment and a narrow-corridor environment, comparing it against Static MILP (S-MILP) and Event-Triggered Greedy (ET-Greedy) reallocation.

Simulation Performance (30 Monte Carlo runs per scenario):
- Success Rate: S-MILP failed completely (0.0% success) in both scenarios due to its inability to adapt to changes. ET-Greedy achieved 99.3% success in open space but dropped to 29.3% in narrow corridors due to congestion and deadlocks. TRRS achieved 100% success in both scenarios.
- Task Completion: TRRS maintained 100% completion in both environments. ET-Greedy achieved 99.8% in open space but only 50.9% in narrow corridors.
- Efficiency: In open space, TRRS reduced average execution steps from 101.6 (ET-Greedy) to 94.6. In narrow corridors, TRRS required 59.4 steps compared to the truncated/failed runs of baselines.
Computational Overhead: The average time to solve the MILP for a triggered replanning round was 0.111 seconds. With approximately 9.8 replanning rounds per mission, the cumulative solving time was ~1.09 seconds, confirming suitability for online execution.
Physical Validation: A physical experiment with two differential-drive robots validated the strategy. When a target (a book) was manually moved and a new high-priority task (water delivery) was introduced, the system successfully reordered tasks, suspended the low-priority collection, executed the high-priority delivery, and then resumed the collection task.

5. Significance and Claims

The paper claims that TRRS addresses a critical gap in dynamic multi-robot coordination: the joint handling of position and priority variations under formal cLTL constraints. The authors assert that their differentiated trigger mechanism effectively balances responsiveness with computational efficiency, avoiding the "over-reaction" of treating all changes as immediate preemptions.

The significance of the work lies in its ability to maintain mission satisfaction (cLTL constraints) and high task completion rates in dynamic, constrained environments where static plans fail and greedy heuristics lead to deadlocks. The authors note that while the current centralized MILP formulation is effective for the tested fleet sizes, it does not scale to very large fleets. Consequently, they identify distributed MILP decomposition and learning-based heuristics as necessary future steps for scaling, alongside extending the grid-based representation to continuous workspaces and handling dynamic obstacles.