Conditional timed partial orders improve robot task planning and speed
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 to be planned with timing and order rules, but existing tools could handle only simple timing and event sequences. The authors introduce conditional timed partial orders (cTPOs) that add more detailed timing rules and conditional steps triggered by the environment. Planning with cTPOs involves solving complex math problems, which can get very slow, so the authors created a method to break tasks into smaller parts. This makes planning much faster while keeping the quality of the plan and also helps people understand complex robot tasks better.
Timed Partial OrdersRobot task planningMixed Integer Linear ProgrammingConditional eventsRelative timing constraintsTask decompositionOptimizationWorkflow modelingComputational efficiencyPlan interpretability
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.