Temporal Logic Planning

How can robots plan to accomplish complex tasks?

Roboticists and control theorists have a few favorite problems: Reach a goal while avoiding obstacles. Stabilize a fixed-point. Find a minimum-cost control action. But many of the tasks that we want robots to do in the real world don’t fit neatly into any of these formulations.

An example of a more complex task: starting from the "x", a robot must reach the goal (blue), but before passing through each door (red) it must first pick up a corresponding key (green).

Temporal logic is one way to specify a wide array of desired behaviors. Given a logical formula that defines the task, how can we generate a trajectory that satisfies the specification? Can we guarantee that our algorithm will find a solution if one exists?

Temporal logic planning is NP-hard, so there is a significant tradeoff between completeness and computational efficiency.

Related Publications

2023

  1. atlas_cover_pic.png
    Temporal Logic Motion Planning with Convex Optimization via Graphs of Convex Sets
    Vince Kurtz, and Hai Lin
    IEEE Transactions on Robotics (T-RO), 2023
    PDF Video Code

2022

  1. multitarget.png
    Mixed-Integer Programming for Signal Temporal Logic with Fewer Binary Variables
    Vince Kurtz, and Hai Lin
    IEEE Control Systems Letters (L-CSS), 2022
    PDF Code

2021

  1. large_scale_gridworld_example.png
    A More Scalable Mixed-Integer Encoding for Metric Temporal Logic
    Vince Kurtz, and Hai Lin
    IEEE Control Systems Letters (L-CSS), 2021
    PDF

2020

  1. talos.png
    Trajectory Optimization for High-Dimensional Nonlinear Systems Under STL Specifications
    Vince Kurtz, and Hai Lin
    IEEE Control Systems Letters (L-CSS), 2020
    PDF
  2. medium_smoothing.png
    A Smooth Robustness Measure of Signal Temporal Logic for Symbolic Control
    Yann Gilpin, Vince Kurtz, and Hai Lin
    IEEE Control Systems Letters (L-CSS), 2020
    PDF Code