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.
Towards a Framework for Comparing the Complexity of Robotic Tasks
Springer Proceedings in Advanced Robotics
International Workshop on the Algorithmic Foundations of Robotics ; 2022 ; , MD, USA June 22, 2022 - June 24, 2022
2022-12-15
21 pages
Aufsatz/Kapitel (Buch)
Elektronische Ressource
Englisch
Towards a Conceptual Framework for Comparing Perspective Flightpath Displays
British Library Conference Proceedings | 1996
|Architecture For Intelligent Control Of Robotic Tasks
NTRS | 1991
|Planning of Work Tasks for Robotic Excavation
British Library Conference Proceedings | 1997
|Execution Control of Robotic Tasks for UUVs
British Library Conference Proceedings | 2002
|