提出可条件触发的时序任务框架，让机器人更灵活地应对复杂环境。
Conditional Timed Partial Orders: An Expressive and Interpretable Framework for Robot Task Specification and Planning
- 用条件触发和复杂时序约束扩展传统时序规划框架
- 通过分解算法将大问题拆成小问题，速度提升达四数量级
- 适合需要高可解释性的复杂机器人任务设计
时序部分序（TPO）原本用于工作流，为机器人任务规划提供可解释的框架，基于混合整数线性规划（MILP）。但TPO表达能力有限，仅支持简单时序约束与事件顺序。本文提出条件时序部分序（cTPO），引入更丰富的相对时序约束和基于环境状态的事件激活机制。我们证明cTPO的规划仍可转化为MILP问题，但其规模显著增大，可能难以求解。为此，我们提出一种分解算法，将cTPO划分为多个子部分序，生成一系列更小的MILP问题。该方法在理论上保证完整性和最优性，同时提升复杂任务的可解释性。实验表明，新框架在任务表达上更有效，分解算法相比单体MILP实现最高达四数量级的速度提升。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。