We are motivated by the problem of comparing the complexity of one robotic task relative to another. To this end, we define a notion of reduction that formalizes the following intuition: Task 1 reduces to Task 2 if we can efficiently transform any policy that solves Task 2 into a policy that solves Task 1. We further define a quantitative measure of the relative complexity between any two tasks for a given robot. We prove useful properties of our notion of reduction (e.g., reflexivity, transitivity, and antisymmetry) and relative complexity measure (e.g., nonnegativity and monotonicity). In addition, we propose practical algorithms for estimating the relative complexity measure. We illustrate our framework for comparing robotic tasks using (i) examples where one can analytically establish reductions, and (ii) reinforcement learning examples where the proposed algorithm can estimate the relative complexity between tasks.
翻译:我们的动机是比较一个机器人任务的复杂性和另一个机器人任务的复杂性。为此,我们定义了一个削减概念,将以下直觉正式化:任务1减少为任务2,如果我们能够有效地将解决任务2的任何政策转化为解决任务1的政策,我们进一步界定了对给定机器人的任何两个任务之间相对复杂性的定量衡量标准。我们证明了我们减排概念(如反应性、过渡性和反对称性)和相对复杂性计量(如非惯性和单一性)的有用属性。此外,我们提出了估算相对复杂性计量的实用算法。我们用(一)实例来比较机器人任务的比较框架,用实例来分析确定减排,以及(二)加强学习范例,以便拟议的算法能够估计任务之间的相对复杂性。