A Theory for Comparing Robot Systems

O'Kane, Jason M.

Permalink

https://hdl.handle.net/2142/11357 Copy

Description

Title

A Theory for Comparing Robot Systems

Author(s)

O'Kane, Jason M.

Issue Date

2007-07

Doctoral Committee Chair(s)

LaValle, Steven M.

Committee Member(s)

• Erdmann, Michael
• Erickson, Jeff G.
• Forsyth, David A.
• Ghrist, Robert

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• theory
• robotics

Abstract

"As robots interact with the physical world, their usefulness depends directly on how effectively they can sense and move through their environments. Unfortunately, sensors provide only limited (and sometimes incorrect) information. In extreme cases, no sensors at all will be available. Therefore, for robots to be useful, they must act effectively in spite of uncertainty about the current state. This reality motivates a careful study of the information requirements of the problems we intend to solve. 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 thesis presents two related lines of research that make progress toward answering these questions. First, we introduce a new technique for comparing the power of robot systems based on how they progress through their information spaces, which encapsulate the robots' state uncertainty. The goal is to understand the relative power of different sets of sensors and actuators and to determine which of these sets enable the robot to complete its task. This line of research is inspired by the theory of computation, which has produced similar results for abstract computing machines. The central idea is a dominance relation over robot systems, formalizing the idea that some robots are more powerful than others. This comparison induces a partial order over the set of robot systems. We prove some basic properties of this partial order, show that it is directly related to the robots' ability to complete tasks, and give several examples. Second, we apply these ideas to the problem of active, global localization for mobile robots. Sensor systems of varying ability have been proposed and successfully used to complete this task. We probe the lower limits of this range by describing three extremely simple robot models and addressing the active localization problem for each. The robot, whose state includes its position and orientation, moves in a fully known, simply connected polygonal environment. We pose the localization task as a planning problem in the robot's information space. We consider robots equipped with (1) angular and linear odometers, (2) a compass and contact sensor, and (3) an angular odometer and contact sensor. We present localization algorithms for models 1 and 2 and show that no algorithm exists for model 3. An implementation with simulation examples is presented. These three results, combined with the comparison results mention above, allow us to fully classify a set of 15 robot models according to their ability to complete the localization task."

Graduation Semester

2007-5

Type of Resource

text

Permalink

http://hdl.handle.net/2142/11357

Copyright and License Information

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections