Learning GR(1) Specifications from Traces

Imagine you are trying to teach a robot how to behave, but you can't write down the rules because you don't know what they are. Instead, you have a video camera recording the robot. You show the camera a bunch of clips where the robot did a great job (the "good" traces) and a bunch of clips where it crashed or acted weirdly (the "bad" traces). Your goal is to write a rulebook that perfectly separates the good clips from the bad ones. This is the world of specification mining: digging through data to find the hidden laws that govern a system.

But there's a catch. In the real world, systems like self-driving cars or factory robots don't just follow rules; they react to their environment. If the environment (like a rainy road or a human pushing a button) does something, the system must respond. This is called a reactive system. To make these systems safe, computer scientists use a special kind of logic called GR(1). Think of GR(1) as a strict contract: "If the environment promises to behave nicely (assumptions), then the system promises to do its job (guarantees)." If you get this contract right, you can automatically build a robot that is mathematically guaranteed to work. If you get it wrong, the robot might fail, or worse, the math might say the robot is impossible to build when it actually could be.

The problem is that finding the right contract is hard. Existing tools often try to guess the rules by looking at every possible sentence in the language of logic. This is like trying to find a specific needle in a haystack by checking every single piece of straw in the universe. It takes forever, and often the tools give you a rule that looks okay but is actually a trap—it separates the good clips from the bad, but it's a rule that no robot could ever actually follow.

This is where the paper comes in. The researchers, led by Sam Nicholas Kouteili and his team, built a new tool called GR1MINE. Instead of guessing randomly, GR1MINE knows the shape of the contract beforehand. It knows the skeleton of the GR(1) rule: "If the environment does X, then the system must do Y." It only has to figure out what X and Y actually are.

To do this, they used a clever trick involving a "SAT solver," which is like a super-fast puzzle solver. Imagine you are trying to build a LEGO castle, but you don't know which bricks to use. Instead of building a whole castle, testing it, and then tearing it down to try again, GR1MINE builds the frame of the castle once. Then, it tries different combinations of bricks inside that frame. If a combination fails, the solver remembers why it failed and uses that memory to skip over thousands of other bad combinations instantly. This is called "incremental solving."

The team tested their tool on 120 different puzzles (benchmarks) taken from real-world hardware and robotics challenges. The results were striking. When the puzzles were made of standard GR(1) rules, GR1MINE solved all 60 of them. In contrast, the previous best tools only solved about half or a third of them. Even more impressively, GR1MINE was over 30 times faster than the generic tools on these specific puzzles.

But the real magic happened when they tested it on puzzles that weren't perfect GR(1) rules. Even when the original rules were messy and didn't fit the neat template, GR1MINE still managed to find a working, realizable rule for 38 out of 60 of those messy cases. The other tools struggled, finding very few working rules, and the ones they did find were often "unrealizable"—meaning they were mathematically impossible for a robot to follow.

In short, GR1MINE doesn't just find a rule that separates good from bad; it finds a rule that a robot can actually live by. By sticking to the known structure of GR(1) and using smart memory tricks to avoid re-doing work, the team showed that we can automatically discover complex, safe contracts for robots much faster and more reliably than before. They didn't just find a needle in the haystack; they built a magnet that only attracts the right kind of needles.