Transforming Robotic Plans with Timed Automata to Solve Temporal Platform Constraints

Tarik Viehmann, Till Hofmann, Gerhard LakemeyerIJCAI 2021 · DOI

TL;DR

This paper tackles the challenge of executing abstract robot plans on real-world platforms by introducing a novel plan transformation technique. It leverages timed automata and Metric Temporal Logic to automatically incorporate low-level platform constraints into high-level plans, ensuring executable and safe robot behavior. This approach decouples platform specifics from the core planning problem, leading to more efficient and modular robotic systems.

What Problem Does This Paper Address?

Robotic task planning often operates at a high level, abstracting away crucial low-level details of the robot's hardware and its operational constraints. For instance, a plan might simply state "pick up object," but in reality, this requires enabling a perception unit, which itself has a warm-up time and consumes resources if left on unnecessarily. Directly incorporating these low-level details into the high-level planner significantly increases complexity and hinders performance. This paper addresses the gap between abstract, high-level plans and concrete, executable robot actions by proposing a method to automatically transform abstract plans to satisfy temporal platform constraints.

Methods

The core of the paper is a plan transformation procedure that leverages timed automata (TAs) and Metric Temporal Logic (MTL). The process involves:

  1. Modeling Platform Constraints: Each robot platform component with temporal constraints is modeled as a TA. These constraints are expressed using a subset of MTL.
  2. Constructing a Plan TA: The abstract plan is first encoded into a TA, where plan actions become states. Temporal constraints on plan actions (like durations or relative timing) are incorporated using clocks and guards.
  3. Integrating Platform TAs: Copies of the platform TAs are then integrated into the plan TA. Transitions in the plan TA are augmented to include transitions into and out of these platform TA copies.
  4. Enforcing Temporal Constraints: Specific MTL constraints (like "action A must happen X seconds before action B" or "platform must be in state S for duration D during action A") are enforced by restricting the states and transitions within the combined TA. This is achieved by creating sub-automata and carefully combining them.
  5. Reachability Analysis: The final, combined TA is analyzed using reachability analysis. A successful path from a start state to a designated goal state in this TA corresponds to an executable plan with grounded execution times that satisfies all abstract plan actions and platform constraints.

The key novelty lies in the systematic construction of this combined TA and the use of reachability analysis to derive executable timed traces, effectively "filling in the gaps" left by the abstract planner.

Datasets

The paper evaluates its approach on two scenarios:

  1. RoboCup Logistics League (RCLL): A simplified setting of the RCLL where robots move workpieces and instruct machines. The domain includes actions like goto, pick, get-from-shelf, put, and pay. The robot platform is modeled using three TAs: perc (perception), calib (calibration), and comm (communication with machines).
  2. Domestic Service Robot: A scenario involving a robot cleaning a table, placing clean cups on a shelf and dirty ones in a dishwasher. This scenario uses a simplified domain without specific alignment or scanning requirements, decoupling these into a separate platform TA.

No new benchmarks were introduced; instead, existing robotics domains were adapted to fit the temporal planning framework.

Key Insights and Ideas

  • Decoupling is Key: Separating high-level task planning from low-level platform specifics significantly simplifies the planning problem and improves overall system modularity.
  • Timed Automata as a Unifying Framework: TAs provide a powerful formalism to model both abstract plan execution and complex temporal platform behaviors, allowing them to be combined into a single, verifiable system.
  • MTL for Expressive Constraints: Metric Temporal Logic offers a concise and expressive way to define temporal relationships between abstract actions and platform states, bridging the gap between the two.
  • Reachability Analysis for Executable Plans: Transforming the problem into a reachability question on a combined TA elegantly solves for executable plans with precise timing, rather than just abstract sequences.
  • Platform Constraints as "Gaps" to Fill: The approach views platform constraints not as limitations to the abstract plan, but as temporal "gaps" that need to be filled with appropriate low-level actions.

Key Results

The paper demonstrates the effectiveness of its approach through evaluations on the RCLL and domestic service robot scenarios.

  • Scalability: The transformation procedure scales reasonably well, handling plans with up to 150 domain actions within practical time limits.
  • Performance Improvement: For complex scenarios, decoupling platform constraints and using the transformation approach significantly reduced overall planning time compared to encoding all details directly into the planning problem.
  • Computational Overhead: While the transformation introduces some computational overhead, it is minor for small tasks and justified by the gains in complex scenarios.
  • Qualitative Success: The approach successfully generates executable plans that satisfy all specified temporal constraints for both evaluated scenarios.

Limitations and Future Work

  • Single TA Assumption: The current approach assumes the robot platform can be modeled by a single TA. The paper notes that multiple TAs can be combined via a product construction, but this can lead to state-space explosion.
  • Symbolic Traces: The UPPAAL model checker, used in the evaluation, returns symbolic traces. Retrieving concrete timed traces requires an additional step, which the authors implemented.
  • Future Work: The authors suggest exploring more complex platform models and investigating optimizations for the TA construction and reachability analysis to handle larger state spaces. Further research could also focus on automating the TA modeling process for platform components.

Summary updated

BibTeX
@inproceedings{viehmann2021transforming,
  author = {Tarik Viehmann and Till Hofmann and Gerhard Lakemeyer},
  title = {{Transforming Robotic Plans with Timed Automata to Solve Temporal Platform Constraints}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/287},
}
Figure