On comparing the power of robots

Jason M. O'Kane, Steven M. LaValle
International Journal of Robotics Research
January 2008


Robots must complete their tasks in spite of unreliable actuators and limited, noisy sensing. In this paper, we consider the information requirements of such tasks. What sensing and actuation abilities are needed to complete a given task? Are some robot systems provably "more powerful," in terms of the tasks they can complete, than others? Can we find meaningful equivalence classes of robot systems? This line of research is inspired by the theory of computation, which has produced similar results for abstract computing machines. The basic idea is a dominance relation over robot systems that formalizes the idea that some robots are stronger than others. This comparison, which is based on the how the robots progress through their information spaces, induces a partial order over the set of robot systems. We prove some basic properties of robots' ability to complete tasks. We give examples to demonstrate the theory, including a detailed analysis of a limited-sensing global localization problem.


  author       = {Jason M. O'Kane and Steven M. LaValle},
  title        = {On comparing the power of robots},
  journal      = {International Journal of Robotics Research},
  volume       = {27},
  number       = {1},
  pages        = {5--23},
  month        = {January},
  year	       = {2008}

O'Kane's home page
O'Kane's publication list

Wed Mar 4 12:52:19 EST 2020