Publications of Jason M. O'Kane

Journal articles
[1]Jason M. O'Kane, Steven M. LaValle. On comparing the power of robots. International Journal of Robotics Research, 27(1):5--23, January 2008.

[2]Jason M. O'Kane, Steven M. LaValle. Localization with limited sensing. IEEE Transactions on Robotics, 23:704--716, August 2007.

[3]Robert Ghrist, Jason M. O'Kane, Steven M. LaValle. Computing pareto optimal coordinations on roadmaps. International Journal of Robotics Research, 24(11):997-1010, November 2005.

 
Refereed conference papers
[4]Hamid Chitsaz, Steven M. LaValle, Jason M. O'Kane. Exact Pareto-optimal coordination for two translating polygonal robots on a cyclic roadmap. In Candadian Conference on Computational Geometry, 2008.

[5]Lawrence Erickson, Joseph Knuth, Jason M. O'Kane, Steven M. LaValle. Probabilistic localization with a blind robot. In Proc. IEEE International Conference on Robotics and Automation, 2008.

[6]Jason M. O'Kane, Steven M. LaValle. Sloppy motors, flaky sensors, and virtual dirt: Comparing imperfect ill-informed robots. In Proc. IEEE International Conference on Robotics and Automation, 2007.

[7]Jason M. O'Kane, Steven M. LaValle. Dominance and equivalence for sensor-based agents. In Proc. AAAI Conference on Artificial Intelligence (NECTAR track), 2007.

[8]Jason M. O'Kane, Steven M. LaValle. On comparing the power of mobile robots. In Proc. Robotics: Science and Systems, 2006.

[9]Jason M. O'Kane. Global localization using odometry. In Proc. IEEE International Conference on Robotics and Automation, 2006.

[10]Jason M. O'Kane, Steven M. LaValle. Almost-sensorless localization. In Proc. IEEE International Conference on Robotics and Automation, 2005.

[11]Robert Ghrist, Jason M. O'Kane, Steven M. LaValle. Pareto optimal coordination on roadmaps. In Proc. Workshop on the Algorithmic Foundations of Robotics, 2004.

[12]Hamid Chitsaz, Jason M. O'Kane, Steven M. LaValle. Exact Pareto-optimal coordination for two translating polygonal robots on an acyclic roadmap. In Proc. IEEE International Conference on Robotics and Automation, 2004.

 
Conference paper under review
[13]Jason M. O'Kane. On the value of ignorance: Balancing tracking and privacy using a two-bit sensor. In Proc. Workshop on the Algorithmic Foundations of Robotics, 2008. Under review.

 
Book chapter
[14]Jason M. O'Kane, Benjamin Tovar, Peng Cheng, Steven M. LaValle. Algorithms for Planning Under Uncertainty in Prediction and Sensing. In S. S. Ge and F. L. Lewis, editors, Autonomous Mobile Robots: Sensing, Control, Decision-Making, and Applications, Series in Control Engineering, chapter 13, pages 501--547. Marcel Dekker, 2006.

 
Other publications
[15]Jason M. O'Kane. Book Review: Maja J. Matari\'c, The Robotics Primer. Autonomous Agents and Multi-Agent Systems, To appear.

[16]Benjamin Tovar, Anna Yershova, Jason M. O'Kane, Steven M. LaValle. Information Spaces for Mobile Robots. In Proc. International Workshop on Robot Motion and Control, 2005.

[17]Jason M. O'Kane, Steven M. LaValle. Sampling-based methods for discrete planning. In Doctoral Consortium of the International Conference on Automated Planning and Scheduling, 2004.

 
 
 
 

On comparing the power of robots

 Jason M. O'Kane, Steven M. LaValle

International Journal of Robotics Research
January 2008
Volume 27, Number 1
Pages 5--23

Note

These results originally appeared here and here.

Abstract

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.

Download

BibTeX

@article{OKaLav06c,
  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},
}

Localization with limited sensing

 Jason M. O'Kane, Steven M. LaValle

IEEE Transactions on Robotics
August 2007
Volume 23Pages 704--716

Note

Preliminary versions of this work appeared in this paper and this paper.

Abstract

Localization is a fundamental problem for many kinds of mobile robots. Sensor systems of varying ability have been proposed and successfully used to solve the problem. This paper probes the lower limits of this range by describing three extremely simple robot models and addressing the localization problem for each. The robot, whose configuration is composed of 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, which encapsulates the uncertainty in the robot's configuration. 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 such algorithm exists for model 3. An implementation with simulation examples is presented.

Download

BibTeX

@article{OKaLav06b,
  author       = {Jason M. O'Kane and Steven M. LaValle},
  title        = {Localization with limited sensing},
  journal      = {IEEE Transactions on Robotics},
  month        = {August},
  year	       = {2007},
  volume       = {23},
  issue        = {4},
  pages        = {704--716},
}

Computing pareto optimal coordinations on roadmaps

 Robert Ghrist, Jason M. O'Kane, Steven M. LaValle

International Journal of Robotics Research
November 2005
Volume 24, Number 11
Pages 997-1010

Note

A preliminary version of this work appeared at WAFR 2004.

Abstract

We consider coordination of multiple robots in a common environment, each robot having its own (distinct) roadmap. Our primary contribution is a classification of and exact algorithm for computing vector-valued -- or Pareto -- optima for collision-free coordination. We indicate the utility of new geometric techniques from CAT(0) geometry and give an argument that curvature bounds are the key distinguishing feature between systems for which the classification is finite and for those in which it is not.

Download

BibTeX

@article{GhrOKaLav05,
  author       = {Robert Ghrist and Jason M. O'Kane and Steven M. LaValle},
  title        = {{Computing pareto optimal coordinations on roadmaps}},
  journal      = {International Journal of Robotics Research},
  volume       = {24},
  month        = {November},
  number       = {11},
  pages        = {997-1010},
  year	       = {2005},
}

Exact Pareto-optimal coordination for two translating polygonal robots on a cyclic roadmap

 Hamid Chitsaz, Steven M. LaValle, Jason M. O'Kane

Candadian Conference on Computational Geometry, 2008

BibTeX

@inproceedings{ChiOKaLav08,
  author       = {Hamid Chitsaz and Steven M. LaValle and Jason M. O'Kane},
  title        = {Exact {P}areto-optimal coordination for two translating
		 polygonal robots on a cyclic roadmap},
  booktitle    = {Candadian Conference on Computational Geometry},
  year	       = {2008},
}

Probabilistic localization with a blind robot

 Lawrence Erickson, Joseph Knuth, Jason M. O'Kane, Steven M. LaValle

Proc. IEEE International Conference on Robotics and Automation, 2008

Abstract

Researchers have addressed the localization problem for mobile robots using many different kinds of sensors, including rangefinders, cameras, and odometers. In this paper, we consider localization using a robot that is virtually ``blind'', having only a clock and contact sensor at its disposal. This represents a drastic reduction in sensing requirements, even in light of existing work that considers localization with limited sensing. We present probabilistic techniques that represent and update the robot's position uncertainty and algorithms to reduce this uncertainty. We demonstrate the experimental effectiveness of these methods using a Roomba autonomous vacuum cleaner robot in laboratory environments.

Download

BibTeX

@inproceedings{EriKnu+08,
  title        = {Probabilistic localization with a blind robot},
  author       = {Lawrence Erickson and Joseph Knuth and Jason M. O'Kane
		 and Steven M. LaValle},
  booktitle    = {Proc. IEEE International Conference on Robotics and
		 Automation},
  year	       = {2008},
  acceptance   = {43\% (641/1476)}
}

Sloppy motors, flaky sensors, and virtual dirt: Comparing imperfect ill-informed robots

 Jason M. O'Kane, Steven M. LaValle

Proc. IEEE International Conference on Robotics and Automation, 2007

Note

Although this is a companion paper to our earlier RSS 2006 paper, the journal version is the most authoritative presentation of this work.

Abstract

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'' 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. We show that this definition is directly related to the robots' ability to complete tasks. Our prior work in this area assumes perfect control and sensing, requires that the robot begin with a single fixed initial condition within a known environment, and models of time as a sequence of variable-length discrete stages, rather than as a continuum. In this paper, we substantially improve upon that earlier work by addressing these problems.

Download

BibTeX

@inproceedings{OKaLav07,
  author       = {Jason M. O'Kane and Steven M. LaValle},
  title        = {Sloppy motors, flaky sensors, and virtual dirt: Comparing
		 imperfect ill-informed robots},
  booktitle    = {Proc. IEEE International Conference on Robotics and
		 Automation},
  year	       = {2007},
  acceptance   = {44\% (787/1800)},
}

Dominance and equivalence for sensor-based agents

 Jason M. O'Kane, Steven M. LaValle

Proc. AAAI Conference on Artificial Intelligence (NECTAR track), 2007

Note

This a short survey paper that introduces results from previous work to the AI community.

Abstract

This paper describes recent results from the robotics community that develop a theory, similar in spirit to the theory of computation, for analyzing sensor-based agent systems. The central element to this work is a notion of dominance of one such system over another. This relation is formally based on the agents' progression through a derived information space, but may informally be understood as describing one agent's ability to ``simulate'' another. We present some basic properties of this dominance relation and demonstrate its usefulness by applying it to a basic problem in robotics. We argue that this work is of interest to a broad audience of artificial intelligence researchers for two main reasons. First, it calls attention to the possibility of studying belief spaces in way that generalizes both probabilistic and nondeterministic uncertainty models. Second, it provides a means for evaluating the information that an agent is able to acquire (via its sensors and via conformant actions), independent of any optimality criterion and of the task to be completed.

Download

BibTeX

@inproceedings{OKaLav07b,
  author       = {Jason M. O'Kane and Steven M. LaValle},
  title        = {Dominance and equivalence for sensor-based agents},
  booktitle    = {Proc. AAAI Conference on Artificial Intelligence (NECTAR
		 track)},
  year	       = {2007},
  acceptance   = {37\% (18/48)}
}

On comparing the power of mobile robots

 Jason M. O'Kane, Steven M. LaValle

Proc. Robotics: Science and Systems, 2006

Note

There is a more complete journal version of this work.

Abstract

Minimalist models have been studied for a broad array of tasks in robotics. In this paper, we consider the task-completing power of robots in terms of the sensors and actuators with which the robot is equipped. Our 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. We define robots as collections of robotic primitives and provide a formal method for comparing the sensing and actuation power of robots constructed from these primitives. 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 this partial order and then apply it to a limited-sensing version of the global localization problem.

Download

BibTeX

@inproceedings{OKaLav06,
  author       = {Jason M. O'Kane and Steven M. LaValle},
  title        = {On comparing the power of mobile robots},
  booktitle    = {Proc. Robotics: Science and Systems},
  year	       = {2006},
}

Global localization using odometry

 Jason M. O'Kane

Proc. IEEE International Conference on Robotics and Automation, 2006

Note

An extended journal version of this work is here.

Abstract

This paper presents a global localization technique for a robot with only linear and angular odometers. The robot, whose configuration is composed of its position and orientation, moves in a fully-known environment by alternating rotations and forward translations. We pose the problem as a discrete-time planning problem in the robot's information space, which encapsulates the uncertainty in the robot's configuration. Our contribution is to show that in any simply-connected, bounded polygonal environment, localization by odometry alone is possible, but only up to the symmetries in the environment.

Download

BibTeX

@inproceedings{OKa06,
  author       = {Jason M. O'Kane},
  title        = {Global localization using odometry},
  booktitle    = {Proc. IEEE International Conference on Robotics and
		 Automation},
  year	       = {2006},
  acceptance   = {38\% (680/1756)}
}

Almost-sensorless localization

 Jason M. O'Kane, Steven M. LaValle

Proc. IEEE International Conference on Robotics and Automation, 2005

Note

There is also a journal version. My master's thesis is an extended version of this work with many examples.

Abstract

We present a localization method for robots equipped with only a compass, a contact sensor and a map of the environment. In this framework, a localization strategy can be described as a sequence of directions in which the robot moves maximally. We show that a localizing sequence exists for any simply connected polygonal environment by presenting an algorithm for computing such a sequence. We have implemented the algorithm and we present several computed examples. We also show that the sensing model is minimal by showing that replacement of the compass by an angular odometer precludes the possibility of performing localization.

Download

BibTeX

@inproceedings{OKaLav05,
  author       = {Jason M. O'Kane and Steven M. LaValle},
  title        = {Almost-sensorless localization},
  booktitle    = {Proc. IEEE International Conference on Robotics and
		 Automation},
  year	       = {2005},
  acceptance   = {45\% (771/1700)}
}

Pareto optimal coordination on roadmaps

 Robert Ghrist, Jason M. O'Kane, Steven M. LaValle

Proc. Workshop on the Algorithmic Foundations of Robotics, 2004

Note

The journal version supercedes this paper.

Abstract

Given a collection of robots sharing a common environment, assume that each possesses an individual roadmap for its C-space and a cost function for attaining a goal. Vector-valued (or Pareto) optima for collision-free coordination are by no means unique: in fact, continua of optimal coordinations are possible. However, for cylindrical obstacles (those defined by pairwise interactions), we prove a finite bound on the number of optimal coordinations. For such systems, we present an exact subquadratic algorithm for reducing a coordination scheme to its Pareto optimal representative.

Download

BibTeX

@inproceedings{GhrOKaLav04,
  author       = {Robert Ghrist and Jason M. O'Kane and Steven M. LaValle},
  title        = {{P}areto optimal coordination on roadmaps},
  booktitle    = {Proc. Workshop on the Algorithmic Foundations of
		 Robotics},
  pages        = {185--200},
  year	       = {2004},
}

Exact Pareto-optimal coordination for two translating polygonal robots on an acyclic roadmap

 Hamid Chitsaz, Jason M. O'Kane, Steven M. LaValle

Proc. IEEE International Conference on Robotics and Automation, 2004

Abstract

We present an algorithm that computes the complete set of Pareto-optimal coordination strategies for two translating polygonal robots in the plane. A collision-free acyclic roadmap of piecewise-linear paths is given on which the two robots move. The robots have a maximum speed and are capable of instantly switching between any two arbitrary speeds. Each robot would like to minimize its travel time independently. The Pareto-optimal solutions are the ones for which there exist no solutions that are better for both robots. The algorithm computes exact solutions in time O(mn2 log n), in which m is the number of paths in the roadmap, n is the number of coordination space vertices. An implementation is presented.

Download

BibTeX

@inproceedings{ChiOKaLav04,
  author       = {Hamid Chitsaz and Jason M. O'Kane and Steven M. LaValle},
  title        = {Exact {P}areto-optimal coordination for two translating
		 polygonal robots on an acyclic roadmap},
  booktitle    = {Proc. IEEE International Conference on Robotics and
		 Automation},
  _pages       = {3981--3986},
  year	       = {2004},
  acceptance   = {59\% (858/1459)}
}

On the value of ignorance: Balancing tracking and privacy using a two-bit sensor

 Jason M. O'Kane

Proc. Workshop on the Algorithmic Foundations of Robotics, 2008
Under review

BibTeX

@inproceedings{OKa08b,
  author       = {Jason M. O'Kane},
  title        = {On the value of ignorance: Balancing tracking and privacy
		 using a two-bit sensor},
  booktitle    = {Proc. Workshop on the Algorithmic Foundations of
		 Robotics},
  note	       = {Under review},
  year	       = {2008},
}

Algorithms for Planning Under Uncertainty in Prediction and Sensing

 Jason M. O'Kane, Benjamin Tovar, Peng Cheng, Steven M. LaValle

In Autonomous Mobile Robots: Sensing, Control, Decision-Making, and Applications
Marcel Dekker, Series in Control Engineering
Chapter 13
Pages 501--547
2006

BibTeX

@incollection{OKaTovCheLav06,
  author       = {Jason M. O'Kane and Benjamin Tovar and Peng Cheng and
		 Steven M. LaValle},
  title        = {Algorithms for Planning Under Uncertainty in Prediction
		 and Sensing},
  booktitle    = {Autonomous Mobile Robots: Sensing, Control,
		 Decision-Making, and Applications},
  editor       = {S. S. Ge and F. L. Lewis},
  series       = {Series in Control Engineering},
  publisher    = {Marcel Dekker},
  year	       = {2006},
  chapter      = {13},
  pages        = {501--547},
}

Book Review: Maja J. Matari\'c, The Robotics Primer

 Jason M. O'Kane

Autonomous Agents and Multi-Agent Systems

To appear

BibTeX

@article{OKa08,
  title        = {Book Review: Maja {J}. {M}atari\'{c}, {T}he {R}obotics
		 {P}rimer},
  author       = {Jason M. O'Kane},
  journal      = {Autonomous Agents and Multi-Agent Systems},
  note	       = {To appear},
}

Information Spaces for Mobile Robots

 Benjamin Tovar, Anna Yershova, Jason M. O'Kane, Steven M. LaValle

Proc. International Workshop on Robot Motion and Control, 2005

Abstract

Planning with sensing uncertainty is central to robotics. Often, sensor limitations prevent accurate state estimation of the robot. To solve robotics tasks given such sensing uncertainty two general approaches are usually taken. The first approach is to estimate the state first and to solve the given task next using the estimated state information. Hovewer, estimation of the state may sometimes be harder than solving the original task. The other approach is to avoid estimating of the state, solving the task based only on sensor information that comes to robot. These approaches can be further generalized, by defining the information space, the space of all the histories of actions and sensors of the robot. All possible solutions to the given task lie in this space, including the solutions given by the above two approaches. Considering information spaces brings better understanding of the problems involving uncertainty, and also allows finding better solutions to such problems.

Download

BibTeX

@inproceedings{TovYerOKaLav05,
  title        = {Information Spaces for Mobile Robots},
  author       = {Benjamin Tovar and Anna Yershova and Jason M. O'Kane and
		 Steven M. LaValle},
  booktitle    = {Proc. International Workshop on Robot Motion and Control},
  year	       = {2005},
}

Sampling-based methods for discrete planning

 Jason M. O'Kane, Steven M. LaValle

Doctoral Consortium of the International Conference on Automated Planning and Scheduling, 2004

Download

BibTeX

@inproceedings{OKaLav04,
  author       = {Jason M. O'Kane and Steven M. LaValle},
  title        = {Sampling-based methods for discrete planning},
  booktitle    = {Doctoral Consortium of the International Conference on
		 Automated Planning and Scheduling},
  year	       = {2004},
}
Fri Aug 22 14:40:08 EDT 2008