Conditional timed partial orders speed up robot task planning
Conditional Timed Partial Orders: An Expressive and Interpretable Framework for Robot Task Specification and Planning
RoboticsFormal Languages and Automata Theory
Summary
Robot tasks often need clear instructions about the order and timing of actions. The authors extended an existing way to describe robot tasks, called Timed Partial Orders, by adding conditions and more detailed timing rules. This makes the task descriptions more flexible but also harder to solve computationally. To fix this, they broke down big problems into smaller pieces that are easier to handle, making planning much faster without losing accuracy. Their tests show this approach can speed up planning by thousands of times while keeping tasks understandable.
What this means in practice
- •For robot software developers: Create robot workflows with complex timing and conditions while enabling faster task plan computation.
- •For manufacturing automation engineers: Design and optimize robot assembly lines requiring conditional and tight timing constraints more efficiently.
Authors
Sebastian Escobar, Morteza Lahijanian
Abstract
Timed Partial Orders (TPOs), originally proposed for workflows, provide an interpretable framework for robot task specification with planning algorithms based on mixed-integer linear programming (MILP). However, TPOs are limited in expressivity, capturing only partial-order events with simple timing constraints. In this paper, we introduce Conditional TPOs (cTPOs), which extend TPOs with richer relative-timing constraints and conditional event activations based on environmental conditions. We show that planning for cTPOs also reduces to an MILP problem; however, the added expressivity results in significantly larger MILPs that can become computationally intractable. To address this challenge, we propose a decomposition algorithm that partitions a cTPO into smaller sub-TPOs, yielding a sequence of smaller MILP problems. We prove that this decomposition is complete and preserves plan optimality while improving the interpretability of complex tasks. Experimental results demonstrate the effectiveness of cTPOs as a task specification framework and the efficiency of our decomposition approach, achieving up to four orders of magnitude speedup over the monolithic MILP.