SMT-based Robot Transition Repair

Jarrett Holtz, Arjun Guha, Joydeep BiswasarXiv 2020 · OpenReview

Abstract: State machines are a common model for robot behaviors. Transition functions often rely on parameterized conditions to model preconditions for the controllers, where the correct values of the parameters depend on factors relating to the environment or the specific robot. In the absence of specific calibration procedures a roboticist must painstakingly adjust the parameters through a series of trial and error experiments. In this process, identifying when the robot has taken an incorrect action, and what should be done is straightforward, but finding the right parameter values can be difficult. We present an alternative approach that we call, interactive SMT-based Robot Transition Repair (SRTR). During execution we record an execution trace of the transition function, and we ask the roboticist to identify a few instances where the robot has transitioned incorrectly, and what the correct transition should have been. A user supplies these corrections based on the type of error to repair, and an automated analysis of the traces partially evaluates the transition function for each correction. This system of constraints is then formulated as a MaxSMT problem, where the solution is a minimal adjustment to the parameters that satisfies the maximum number of constraints. In order to identify a repair that accurately captures user intentions and generalizes to novel scenarios, solutions are explored by iteratively adding constraints to the MaxSMT problem to yield sets of alternative repairs. We test with state machines from multiple domains including robot soccer and autonomous driving, and we evaluate solver based repair with respect to solver choice and optimization hyperparameters. Our results demonstrate that SRTR can repair a variety of states machines and error types 1) quickly, 2) with small numbers of corrections, while 3) not overcorrecting state machines and harming generalized performance.

Introduction

Robots frequently utilize Finite State Machines (FSMs) to manage complex behaviors, such as switching from a "Go To" state to a "Kick" state in a soccer match. These transitions are governed by hard-coded parameters like distance thresholds or angle tolerances. However, the optimal values for these parameters are highly sensitive to specific robot hardware and environmental conditions, such as the friction of a playing surface.

Currently, roboticists often rely on manual trial-and-error to tune these values. While a human observer can easily identify when a robot makes a mistake (e.g., kicking too early), calculating the precise numerical adjustment required to fix that specific error without disrupting other behaviors is a significant challenge.

Methodology

The proposed Interactive SMT-based Robot Transition Repair (SRTR) framework automates this tuning process by treating behavior repair as a logic problem. The workflow consists of several key steps:

  1. Trace Recording: The robot logs sensor inputs, internal variables, and state transitions during operation.
  2. User Corrections: A human reviews the trace and provides corrections. These can be Immediate (specifying the correct state at a specific moment) or Continue (indicating the robot should have stayed in its current state longer).
  3. Partial Evaluation: The system simplifies the transition function's code by plugging in real sensor data from the trace, resulting in a set of mathematical constraints where the parameters are the only unknowns.
  4. MaxSMT Solving: The constraints are fed into an SMT solver (such as Z3). The solver identifies a minimal adjustment to the parameters that satisfies the user's corrections, preventing the model from overfitting to a single error.
The Attacker state machine and corresponding execution traces used for transition repair.

Evaluation and Results

SRTR was evaluated across four simulated domains (Robot Soccer Attacker, Deflector, Docking Robot, and Autonomous Driving) and one real-world scenario involving a physical robot soccer attacker.

Performance Metrics

  • Efficiency: For the soccer attacker domain, just two human corrections were sufficient to raise the success rate from 42% to 89%.
  • Speed: SRTR is significantly faster than exhaustive search methods. In comparative tests, SRTR found solutions in approximately 10 milliseconds, whereas exhaustive search required 1,300 CPU hours to reach the same success rate.
  • Real-World Validation: In physical tests on a carpeted field, a robot tuned with SRTR achieved an 85% success rate. This outperformed a "Competition Attacker" manually tuned by experts for the RoboCup world finals, which achieved a 75% success rate.
Real-world validation of SRTR on a physical robot soccer field, showing the robot's movement toward the ball.

Key Insights

  • Logic-Based Optimization: Unlike traditional optimization techniques (like least-squares), SMT solvers are uniquely suited to handle the "if-else" logic inherent in state machine transitions.
  • Minimalism and Generalization: By penalizing large parameter changes, the system preserves the original design intent. Repairs made at specific points on the field were found to generalize effectively across the entire environment.

Limitations and Future Work

While effective, SRTR currently struggles with non-linear functions (e.g., trigonometric functions) if parameters are nested within them. Additionally, the system can only repair parameter values, not the underlying structure of the state machine itself. Future research may extend this repair philosophy to motion planning and high-level task planners.

Summary updated

Abstract

State machines are a common model for robot behaviors. Transition functions often rely on parameterized conditions to model preconditions for the controllers, where the correct values of the parameters depend on factors relating to the environment or the specific robot. In the absence of specific calibration procedures a roboticist must painstakingly adjust the parameters through a series of trial and error experiments. In this process, identifying when the robot has taken an incorrect action, and what should be done is straightforward, but finding the right parameter values can be difficult. We present an alternative approach that we call, interactive SMT-based Robot Transition Repair. During execution we record an execution trace of the transition function, and we ask the roboticist to identify a few instances where the robot has transitioned incorrectly, and what the correct transition should have been. A user supplies these corrections based on the type of error to repair, and an automated analysis of the traces partially evaluates the transition function for each correction. This system of constraints is then formulated as a MaxSMT problem, where the solution is a minimal adjustment to the parameters that satisfies the maximum number of constraints. In order to identify a repair that accurately captures user intentions and generalizes to novel scenarios, solutions are explored by iteratively adding constraints to the MaxSMT problem to yield sets of alternative repairs. We test with state machines from multiple domains including robot soccer and autonomous driving, and we evaluate solver based repair with respect to solver choice and optimization hyperparameters. Our results demonstrate that SRTR can repair a variety of states machines and error types 1) quickly, 2) with small numbers of corrections, while 3) not overcorrecting state machines and harming generalized performance.
BibTeX
@misc{holtz2020smt,
  author = {Jarrett Holtz and Arjun Guha and Joydeep Biswas},
  title = {{SMT-based Robot Transition Repair}},
  year = {2020},
  eprint = {2001.04397},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2001.04397},
}
Figure