@inproceedings{37995782d2b54fbaadbc1365bf00993b,

title = "Towards a Framework for Comparing the Complexity of Robotic Tasks",

abstract = "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.",

keywords = "Complexity, Reduction, Reinforcement learning",

author = "Michelle Ho and Alec Farid and Anirudha Majumdar",

note = "Funding Information: Acknowledgements. The authors are grateful to the anonymous reviewers for their helpful feedback and suggestions on this work. Funding: NSF CAREER Award [#2044149] and Office of Naval Research [N00014-21-1-2803, N00014-18-1-2873]. Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 15th Workshop on the Algorithmic Foundations of Robotics, WAFR 2022 ; Conference date: 22-06-2022 Through 24-06-2022",

year = "2023",

doi = "10.1007/978-3-031-21090-7_17",

language = "English (US)",

isbn = "9783031210891",

series = "Springer Proceedings in Advanced Robotics",

publisher = "Springer Nature",

pages = "273--293",

editor = "LaValle, {Steven M.} and O{\textquoteright}Kane, {Jason M.} and Michael Otte and Dorsa Sadigh and Pratap Tokekar",

booktitle = "Algorithmic Foundations of Robotics XV - Proceedings of the Fifteenth Workshop on the Algorithmic Foundations of Robotics",

address = "United States",

}