Introduction
In multi-agent systems, robots often share a workspace, necessitating coordination to prevent collisions and deadlocks. Social laws—sets of behavioral restrictions, such as "always drive on the right"—are a common solution to ensure agents can reach their goals independently. However, traditional verification of these laws has largely relied on "classical planning," which assumes instantaneous actions and sequential movement. This abstraction fails in real-world scenarios where robots move concurrently and actions have durations. In continuous-time settings, interference can occur mid-action; for example, one robot might inadvertently delete a condition that another robot is currently relying on to complete its move.
Defining Rational Robustness
This research introduces a formal definition of rational robustness tailored for continuous-time environments. A social law is considered robust if it guarantees that any valid individual plan an agent chooses will succeed, provided all other agents also adhere to the law. This ensures that agents acting rationally toward their own goals do not inadvertently interfere with one another.
Verification via Compilation
To automate the verification process, the authors developed a novel compilation technique. This method transforms the multi-agent verification problem into a single-agent temporal planning problem ($\Pi'$). Crucially, the "goal" of this new planning task is to find a failure scenario.
The compilation tracks two parallel versions of the world:
- Local State: What an individual agent expects to happen if it were acting in isolation.
- Global State: The actual state of the world when all agents act concurrently.
If these states diverge such that a robot's action fails—due to a violated condition or a deadlock—the social law is flagged as non-robust. To handle concurrent actions, the system uses numeric variables ($inv_f$) to track "invariants"—conditions that must remain true throughout the duration of an action. Furthermore, the authors formalize a "wait-for" mechanism at the start of actions, allowing robots to remain idle until specific conditions (like a square becoming vacant) are met, which is essential for decentralized coordination.
Experimental Evaluation
The approach was evaluated across several domains:
- Real-World Robotics: A system with two Turtlebots performing grid-cleaning tasks.
- Custom Benchmarks: "Intersection" (modeling cars at a four-way stop) and "Drink" (a coordination problem involving a shared resource).
- IPC Benchmarks: Standard International Planning Competition domains—Driverlog, Zenotravel, and Floortile—adapted for multi-agent temporal planning.
Key Results
The system demonstrates high efficiency in failure detection. In Turtlebot experiments, potential collisions were identified in under 3 seconds, and deadlocks in less than 1 second.
However, proving robustness (i.e., proving that no failure plan exists) remains a significant challenge. While the "Intersection" domain was verified in under a second, more complex domains like "Drink" or larger IPC instances often resulted in timeouts (TLE) due to the difficulty of proving unsolvability in temporal planning.
As shown in the table above, the compilation results in a polynomial increase in problem size, scaling reasonably well with the number of agents and facts. While many instances are solved quickly, the presence of reversible actions and complex state spaces leads to performance bottlenecks where current temporal planners struggle to prove unsolvability.
Limitations and Future Work
The primary bottleneck identified is not the compilation itself, but the limitations of current temporal planners, which are typically optimized for finding plans rather than proving their absence. Future improvements in proving unsolvability will directly enhance this verification tool. Additionally, the current model assumes agents only wait at the start of actions; extending this to "wait-for" conditions at the end of actions would introduce uncontrollable durations, a significant but necessary step for modeling more complex reactive behaviors.
Summary updated