Control of noisy differential-drive vehicles from time-bounded temporal logic specifications

Igor Cizelj, Călin Belta

TL;DR

This paper presents a framework for controlling noisy differential-drive robots to satisfy complex, time-sensitive tasks (like "pick up a load within 14 seconds and stay in the test area for at least 1 second") expressed in Bounded Linear Temporal Logic (BLTL). By mapping noisy sensor data to a Markov Decision Process (MDP) and using Statistical Model Checking, the authors generate a control policy that guarantees the robot's real-world success probability is at least as high as the model's estimate.

What Problem Does This Paper Address?

In "classical" robotics, motion planning usually involves simple primitives: "Go from A to B while avoiding obstacles." However, real-world missions are often more nuanced, involving sequences, timing constraints, and conditional goals. While Temporal Logic (like LTL) provides a rich language for these missions, applying it to physical robots is difficult because:

  1. Noise: Actuators (motors) are never perfect, and sensors (encoders) have limited resolution.
  2. Continuous vs. Discrete: Logic is discrete, but robot dynamics are continuous.
  3. State-Space Explosion: Modeling every possible noisy outcome in a complex environment leads to massive mathematical models that are computationally impossible to solve exactly.

The authors bridge the gap between low-level noisy sensory inputs and high-level temporal logic specifications, providing a way to maximize the probability of mission success despite hardware imperfections.

Methods

The authors propose a three-step suboptimal solution:

  1. MDP Modeling: They discretize the robot's motion and sensor readings into a Markov Decision Process (MDP). Each state in the MDP represents a sequence of measured wheel rotations from incremental encoders.
  2. Statistical Model Checking (SMC): Because the MDP is too large to solve using traditional exact methods, they use SMC. Specifically, they employ a Control Policy Optimization algorithm that samples paths to incrementally improve the control strategy.
  3. Bayesian Interval Estimation (BIE): To verify the policy, they use a BIE algorithm to estimate the probability of satisfying the BLTL formula. This provides a "confidence interval" for success.
  4. Conservative Uncertainty Bounds: To ensure the discrete model reflects the continuous world, they model the robot's position as a "disc" of uncertainty that grows over time. They define "conservative rules" for trace generation: a mission requirement is only considered "satisfied" if the entire uncertainty disc meets the criteria.

Datasets

The paper does not use a standard public dataset. Instead, the authors generated a custom dataset through experimental trials using a Dr. Robot x80Pro mobile robot.

  • They measured actual angular wheel velocities against commanded inputs to build a continuous probability density function for actuator noise.
  • They used an OptiTrack motion capture system (8 cameras) to reconstruct the ground-truth trajectories for experimental validation.

Key Insights and Ideas

  • The Lower Bound Guarantee: The most critical insight is that by being "conservative" in the model (requiring the whole uncertainty region to satisfy a property), the probability of success calculated on the MDP acts as a mathematical lower bound. If the model says you have a 66% chance of success, your real-world chance is likely much higher.
  • Trading Correctness for Scalability: The authors acknowledge that finding an exact optimal solution is "prohibitively expensive." By using sampling-based SMC instead of exhaustive state-space analysis, they make the problem tractable for robotic applications.
  • Logic as a Language: The use of BLTL allows for "time-bounded" operators, which are more practical for robotics than standard LTL (which often deals with infinite time horizons).

Key Results

The framework was tested in two simulated environments (A and B) with complex "pick-up, test, and drop-off" missions:

  • Environment A: The MDP estimated a success probability ($\hat{p}^*_M$) of 0.664. In actual simulations, the robot succeeded with a probability of roughly 0.835 across multiple runs.
  • Environment B: The MDP estimated a success probability of 0.719, while simulations showed an actual success rate of roughly 0.889.
  • Validation: These results confirm the "lower bound" theory—the robot performed significantly better in practice than the conservative model predicted.
  • Computation: The Matlab implementation took approximately 2.2 hours to generate the control strategy on a 2.5GHz dual-processor machine.

Limitations and Future Work

  • Computation Time: While 2.2 hours is better than "infinite," it is still too slow for real-time re-planning if the environment changes. The authors suggest moving to a fully parallel implementation to speed this up.
  • Conservatism Gap: The gap between the predicted 66% and actual 83% success suggests the uncertainty model might be too conservative. Future work involves developing a "less conservative" uncertainty model to get a tighter bound.
  • Static Environments: The current approach assumes a known, static map. Incorporating dynamic obstacles or unknown environments would be a significant next step.

Summary updated

Abstract

We address the problem of controlling a noisy differential drive mobile robot such that the probability of satisfying a specification given as a bounded linear temporal logic formula over a set of properties at the regions in the environment is maximized. We assume that the vehicle can determine its precise initial position in a known map of the environment. However, motivated by practical limitations, we assume that the vehicle is equipped with noisy actuators and, during its motion in the environment, it can only measure the angular velocity of its wheels using limited accuracy incremental encoders. Assuming the duration of the motion is finite, we map the measurements to a Markov decision process (MDP). We use recent results in statistical model checking to obtain an MDP control policy that maximizes the probability of satisfaction. We translate this policy to a vehicle feedback control strategy and show that the probability that the vehicle satisfies the specification in the environment is bounded from below by the probability of satisfying the specification on the MDP. We illustrate our method with simulations and experimental results.
BibTeX
@article{cizelj2014control,
  author = {Igor Cizelj and Călin Belta},
  title = {{Control of noisy differential-drive vehicles from time-bounded temporal logic specifications}},
  journal = {The International Journal of Robotics Research},
  year = {2014},
  doi = {10.1177/0278364914522312},
}
Figure