Towards a Framework for Comparing the Complexity of Robotic Tasks

Michelle Ho, Alec Farid, Anirudha Majumdar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationAlgorithmic Foundations of Robotics XV - Proceedings of the Fifteenth Workshop on the Algorithmic Foundations of Robotics
EditorsSteven M. LaValle, Jason M. O’Kane, Michael Otte, Dorsa Sadigh, Pratap Tokekar
PublisherSpringer Nature
Number of pages21
ISBN (Print)9783031210891
StatePublished - 2023
Event15th Workshop on the Algorithmic Foundations of Robotics, WAFR 2022 - College Park, United States
Duration: Jun 22 2022Jun 24 2022

Publication series

NameSpringer Proceedings in Advanced Robotics
Volume25 SPAR
ISSN (Print)2511-1256
ISSN (Electronic)2511-1264


Conference15th Workshop on the Algorithmic Foundations of Robotics, WAFR 2022
Country/TerritoryUnited States
CityCollege Park

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Electrical and Electronic Engineering
  • Mechanical Engineering
  • Engineering (miscellaneous)
  • Artificial Intelligence
  • Computer Science Applications
  • Applied Mathematics


  • Complexity
  • Reduction
  • Reinforcement learning


Dive into the research topics of 'Towards a Framework for Comparing the Complexity of Robotic Tasks'. Together they form a unique fingerprint.

Cite this