Devika Subramanian

ICRA Conference 2001 Conference Paper

Robust Localization Algorithms for an Autonomous Campus Tour Guide

• Richard Thrapp
• Christian Westbrook
• Devika Subramanian

This paper describes a robust localization method for an outdoor robot that gives tours of the Rice University campus. The robot fuses odometry and GPS data using extended Kalman filtering. We propose and experimentally test a technique for handling two types of nonstationarity in GPS data quality: abrupt changes in GPS position readings caused by sudden obstructions to line of sight access to satellites, and more gradual changes caused by disparities in atmospheric conditions. We construct measurement error covariance matrices indexed by number of visible satellites and switch them into the localization computation automatically. The matrices are built by sampling GPS data repeatedly along the route and are updated continuously to handle drift in GPS data quality. We demonstrate that our approach performs better than extended Kalman filters that use only a single error covariance matrix. With a GPS receiver that delivers 1 meter accuracy, we have been able to localize to 40 cm through a challenging route in the Engineering Quadrangle of Rice University.

IJCAI Conference 1997 Conference Paper

Ants and Reinforcement Learning: A Case Study in Routing in Dynamic Networks

• Devika Subramanian
• Peter Druschel
• Johnny Chen

We investigate two new distributed routing algorithms for data networks based on simple biological "ants" that explore the network and rapidly learn good routes, using a novel variation of reinforcement learning. These two algorithms are fully adaptive to topology changes and changes in link costs in the network, and have space and computational overheads that are competitive with traditional packet routing algorithms: although they can generate more routing traffic when the rate of failures in a network is low, they perform much better under higher failure rates. Both algorithms are more resilient than traditional algorithms, in the sense that random corruption of routing state has limited impact on the computation of paths. We present convergence theorems for both of our algorithms drawing on the theory of non-stationary and stationary discrete-time Markov chains over the reals. We present an extensive empirical evaluation of our algorithms on a simulator that is widely used in the computer networks community for validating and testing protocols. We present comparative results on data delivery performance, aggregate routing traffic (algorithm overhead), as well as the degree of resilience for our new algorithms and two traditional routing algorithms in current use. We also show that the performance of our algorithms scale well with increase in network size-using a realistic topology.

AIJ Journal 1997 Journal Article

The common order-theoretic structure of version spaces and ATMSs

• Carl A. Gunter
• Teow-Hin Ngair
• Devika Subramanian

We demonstrate how order-theoretic abstractions can be useful in identifying, formalizing, and exploiting relationships between seemingly dissimilar AI algorithms that perform computations on partially-ordered sets. In particular, we show how the order-theoretic concept of an anti-chain can be used to provide an efficient representation for such sets when they satisfy certain special properties. We use anti-chains to identify and analyze the basic operations and representation optimizations in the version space learning algorithm and the assumption-based truth maintenance system (ATMS). Our analysis allows us to (1) extend the known theory of admissibility of concept spaces for incremental version space merging, and (2) develop new, simpler label-update algorithms for ATMSs with DNF assumption formulas.

AIJ Journal 1997 Journal Article

The relevance of relevance

• Devika Subramanian
• Russell Greiner
• Judea Pearl

IJCAI Conference 1993 Conference Paper

Conceptual Design and Artificial Intelligence

• Devika Subramanian
• Cornell University

IJCAI Conference 1993 Conference Paper

Provably bounded optimal agents

• Stuart J. Russell
• Devika Subramanian
• Ronald Parr

A program is bounded optimal for a given computational device for a given environment, if the expected utility of the program running on the device in the environment is at least as high as that of all other programs for the device. Bounded optimality differs from the decision-theoretic notion of rationality in that it explicitly allows for the finite computational resources of real agents. It is thus a central issue in the foundations of artificial intelligence. In this paper we consider a restricted class of agent architectures, in which a program consists of a sequence of decision procedures generated by a learning program or given a prion. For this class of agents, we give an efficient construction algorithm that generates a bounded optimal program for any episodic environment, given a set of training examples. The algorithm includes solutions to a new class of optimization problems, namely scheduling computational processes for real-time environments. This class appears to contain significant practical applications.

AAAI Conference 1990 Conference Paper

The Utility of EBL in Recursive Domain Theories

• Devika Subramanian
• Ronen Feldman

We investigate the utility of explanation-based learning in recursive domain theories and examine the cost of using macro-rules in these theories. The compilation options in a recursive domain theory range from constructing partial unwindings of the recursive rules to converting recursive rules into iterative ones. We compare these options against using appropriately ordered rules in the original domain theory and demonstrate that unless we make very strong assumptions about the nature of the distribution of future problems, it is not profitable to form recursive macro-rules via explanation-based learning in these domains.

IJCAI Conference 1987 Conference Paper

The Relevance of Irrelevance

• Devika Subramanian
• Michael R. Genesereth

This research describes the formalization of statements of the form fact f is irrelevant to fact g given theory M. We motivate the need for representing and reasoning with such statements in problem-solving systems, and outline the semantics and properties of statements about irrelevance. We then describe a logic irrelevance that serves as a language for specifying irrelevance claims in the world, and present an associated calculus that allows us to draw new irrelevance conclusions from given ones. The utility of the formalization and the types of inferences it sanctions are demonstrated with examples from data interpretation, representation reformulation and experiment design.

AAAI Conference 1986 Conference Paper

Factorization in Experiment Generation

• Devika Subramanian

Experiment generation is an important part of incremental concept learning. One basic function of experimentation is to gather data to refine the existing space of hypotheses[DB83]. Here we examine the class of experiments that accomplish this, called discrimination experiments, and propose factoring as a technique for generating them efficiently.