Accomplishing tasks with teams of miniature robots: design paradigms and performance evaluation

Maria Gini [web]

University of Minnesota, Department of Computer Science and Engineering

Teams of miniature robots can carry out many tasks more reliably, at less cost, and often faster, than a single large robot would be able to do. Since small robots lack sophisticated sensors and have very limited computing power, they require different paradigms to accomplish tasks.

We describe a miniature robot, called "scout", designed at the University of Minnesota. Space and power limitations on the scouts severely restrict their on-board computer power, as well as their RF communication channel capacity. On-board processing is limited to simple control and communication tasks, while proxy-processing is carried out at the base station. This allows the scouts to be autonomous, but the RF communication channels become a severe bottleneck.

We will focus on tasks that can be done by simple robots using loose cooperation strategies, and we present results on a variety of experimental performance studies. This includes a surveillance task in which multiple miniature robots patrol an area and watch for motion, search and retrieval with and without communication, and simultaneous localization and mapping using very limited odometry and sensors.

About the Speaker:

Maria Gini is a Professor in the Department of Computer Science and Engineering at the University of Minnesota, where she has been a faculty member since 1982. Her major contributions include robot navigation, robot motion planning, coordination of robots, and negotiation strategies for agents. She is currently the Chair of the ACM Special Interest Group on Artificial Intelligence (SIGART). She is on the editorial board of "Autonomous Robots" and "Integrated Computer-Aided Engineering", and on the Autonomous Agents steering committee. Additional information on the web.

The Forum for Artificial Intelligence meets every other week (or so) to discuss topics in artificial intelligence. All are welcome to attend.

Please send questions or comments to
Matt MacMahon or Jeff Provost.

Reinforcement Learning for Autonomous Diagnosis and Repair

Michael Littman [web]

Rutgers University

This talk describes ongoing work on an application of reinforcement learning in the context of autonomous diagnosis and repair. I will present a new formal model, cost-sensitive fault remediation (CSFR), which is a simplified partially observable environment model. CSFR is powerful enough to capture some real-world problems -- we've looked at network, disk-system, and web-server maintenance. However, it also admits simplified algorithms for planning, learning, and exploration, which I'll discuss.

The Personal Rover Project

Illah Nourbakhsh [web]

Carnegie Mellon University

The Personal Rover Project is a comprehensive effort to develop and deploy a low-cost rover platform for diverse environments, including the home. This rover serves as an exploration-centered, creative outlet for children as they shape the rover's daily and weekly activities. We argue that such a personal rover will excite and inspire users about math, science and engineering. Early project results include the CMUcam embedded vision board, a weight-shifting high COM prototype for climbing ledges and educational study results following a 30 student test course, Robotic Autonomy, that has now been taught for two consecutive summers at NASA/Ames and CMU West.

Recent results include the CMUcam2 vision board and the Personal Exploration Rover, which is now functioning at the Smithsonian Air & Space Museum, the San Francisco Exploratorium and other science centers across the country. In this talk, I will motivate the Personal Rover Project and will describe our most recent robotic technological results and educational robotics analyses.
For more information see www.cs.cmu.edu/~personalrover/PER and www.cs.cmu.edu/~cmucam

Poker for Fun and Profit (and Intellectual Challenge)

Robert Holte [web]

University of Alberta

This presentation describes recent work at the University of Alberta towards creating a program that can play poker at a world-class human level. The It will include a summary of the work reported at IJCAI'2003, which computes a Nash Equilibrium for a highly abstracted version of poker and applies the resulting strategy to the full game. It will also outline our current approach, which abandons Nash Equilibria in favour of opponent modelling. The presentation will be informal and accessible to a wide audience. No knowledge of poker or game theory will be assumed.

Parameterized maintainability and a polynomial time algorithm for it

Chitta Baral [web]

Arizona State University

In designing goal directed agents, in reactive control, and in planning one often comes across the notion of `maintenance' goals. A strict interpretation of `maintenance' is captured by the formal temporal logic specification `ALWAYS F'. A less stricter interpretation is captured by the formal temporal logic specification `ALWAYS EVENTUALLY F'. Often in presence of external agents (or the environment) one may need to account for the available window of opportunity (without the interference of external agents). Also, often one may need to have a numeric measure of an autonomous systems ability to maintain. Based on these intuitions we formulate a notion of k-maintainability, with respect to a parameter k. Such a notion of parameterized maintainability is important in specifying many maintenance goals such as maintaining a room clean, maintaining a database consistent, and maintaining the front of a rover obstacle free. We then present a sound and complete polynomial time algorithm for constructing k-maintainable policies. Our algorithm is based on SAT Solving and logic programming, and employs a suitable formulation of the existence of k-maintainable control in the Horn fragment of SAT which is tractable. We then give a logic programming implementation of our algorithm and use it to give a standard procedural algorithm.

Dijkstra's notion of self-stabilization is a special case of k-maintenance, and thus our algorithm suggests an approach to generate self-stabilization protocols. This talk is based on our work in AAAI'00 (the formulation part; co-authors: Mutsumi Nakamura, Marcus Bjareland), and to be published work in ICAPS'04 (the algorithm part; co-author: Thomas Eiter).

Large-Margin Methods for Natural Language Learning

Michael Collins [web]

AI Laboratory, Massachusetts Institute of Technology

Sequential data is everywhere: obvious examples being text (the web, or digital libraries), speech, and biological sequences. Algorithms which recover structure underlying this data are becoming increasingly important. This leads to an interesting class of learning problems: how to learn functions which map strings to other discrete structures such as trees, segmentations, or underlying state sequences?

In this talk I will present new algorithms for these problems, derived from Freund and Schapire's voted perceptron algorithm for classification tasks. Properties of the algorithm depend directly on a modified notion of "margin" on training examples. I will describe how the algorithm can be used to rerank N-best output from an existing probabilistic model, using essentially arbitrary features of competing analyses; how the "kernel trick" applied to discrete structures can lead to efficient learning with representations tracking an exponential number of "sub-fragments" of a tree or tagged sequence; and how the algorithm can be used for efficient discriminative training of weighted automata. A first motivation for the new algorithms concerns representation:in comparison to hidden Markov models, or probabilistic context-free grammars, the methods are considerably more flexible in the features that can be used to discriminate between competing structures. A second theme is discriminative training: the parameter estimation methods make relatively weak assumptions about the distribution underlying examples. During the talk I will present experiments with the methods, showing their utility on a number of natural language problems.

The Dynamics of Open-ended Learning

Jordan Pollack [web]

Brandeis University

How could something as complex as the brain, or as rich as cognition, be the result of a random evolutionary process? The difficulty in imagining how a chemical reaction far from equilibrium could dissipate energy and, through a local reversal of entropy, achieve an organizational complexity which exceeds human engineering design has led to a broad belief in the need for an outside creator. It has also led to disproportiate scientific funding to focus on "what exists" in biology rather than the more foundational question of "how can it come to exist?"

A true understanding of evolutionary self-organization in Nature would go beyond mere description to a formal explanation which can be implemented in software or electronics. It would dissipate energy (in the form of computational cycles) and produce higher and higher forms of organization. This AI complete problem of "self-writing software" is the core question of Artificial Life.

Co-evolutionary learning has begun to illuminate this question through the use of software models of evolution based upon relative comparisons within a population rather than absolute measurements of fitness from outside. The structure of a co-evolutionary system is usually that of a game, where individuals or species compete against each other. Often there is little fitness information except who "won", and even winning may be the result of random forces like dice rolls.

The hope has been that these kinds of models would lead to open-ended learning displaying "arms races" and spirals of complexity, where monotonically improved strategies would arise automatically. We and others have had intriguing but limited successes in areas such as sorting networks, Automata, classification, game playing, and robotics. However, the dynamics of such systems are quite complex, and often result in "mediocre stable states" due to memory loss and boom/bust cycles, or mediocre stability through winner-take-all monopolies or oligarchies which exclude innovation. Understanding why mediocrity arises and finding ways around it to achieve open-ended progress has become our primary focus, and I will review recent results which suggest that competition itself is incomplete as an organizing principle for evolutionary - and perhaps social - progress.

Bio:

Jordan Pollack has worked with computers since attending college in 1974, and worked for IBM upon graduation. He returned to graduate school in 1980, received the Ph.D from University of Illinois in 1987, and taught at Ohio State University from 1988-1994 prior to moving to Brandeis University. He has produced 12 Ph.D's so far, contributing to a broad range of interdisciplinary fields, like neural networks, dynamical systems, evolutionary computation, machine learning, cognitive science, artificial life, robotics, co-evolution, and educational technology. His laboratory, the Dynamical and Evolutionary Machine Organization has been partially funded by ONR, NSF, DOE, DARPA, and the Hewlett foundation. He holds 8 patents, advises several startup companies and incubators, and founded www.Thinmail.com . He was named one of MIT Technology Review's "TR 10" in January 2001 for his laboratory's work on automatically designed and manufactured robots. His next big thing is broadband P2P education .

Hybrid Mapping Models: Bridging the Gap between Robot Sensors and Symbolic Spatial Representations

Patrick Beeson [web] and Joseph Modayil [web]

Intelligent Robotics Lab [web], UTCS

In order to reliably move around a large-scale environment, a robot must have an adequate map. Thus, much research in mobile robotics has focused on the problem of building maps. Additionally, most researchers have focused on metrical maps, using range sensing devices to create a planar, 2D metrical description of the world. As robots explore larger and more complicated environments, researchers are struggling to have robots efficiently build these maps online, despite having more modern sensors and on-board computers.

On the other hand, a smaller group of researchers have promoted using topological maps of large environments. One of the pioneers of this branch of robotics has been Dr. Ben Kuipers here at UTCS. He proposed a theory for building discrete, symbolic descriptions of large-scale environments. Our lab, along with other researchers, have looked into how to build, check, and order topological map models given reliable actions and perceptions in the world. The problem with topological maps has always been in the way they ground the robot's sensory experience. This is often done in an ad-hoc way for each individual robot sensory setup. There is often little overlap in the approaches used throughout the community.

Today, our lab is joining a handful of other researchers in developing hybrid mapping techniques. We are promoting the use of metrical models to describe "small-scale space": akin to a human's ability to have a detailed model of their local surround. Topological maps are useful for representing "large-scale space": graph structures imply compact, hierarchical, symbolic descriptions useful for planning, communication, and storing multiple hypotheses.

Our talk will focus on how these two ontologies interact. In particular, we discuss what new concepts are necessary to move from detailed metrical descriptions of bounded local regions to graph-like structures of large, complex environments. We will present published work that shows several of the advances we have made in recent months as well as present the open questions that still need to be examined in more detail.

Accomplishing tasks with teams of miniature robots: design paradigms and performance evaluation

Maria Gini [web]

University of Minnesota, Department of Computer Science and Engineering

Teams of miniature robots can carry out many tasks more reliably, at less cost, and often faster, than a single large robot would be able to do. Since small robots lack sophisticated sensors and have very limited computing power, they require different paradigms to accomplish tasks.

We describe a miniature robot, called "scout", designed at the University of Minnesota. Space and power limitations on the scouts severely restrict their on-board computer power, as well as their RF communication channel capacity. On-board processing is limited to simple control and communication tasks, while proxy-processing is carried out at the base station. This allows the scouts to be autonomous, but the RF communication channels become a severe bottleneck.

We will focus on tasks that can be done by simple robots using loose cooperation strategies, and we present results on a variety of experimental performance studies. This includes a surveillance task in which multiple miniature robots patrol an area and watch for motion, search and retrieval with and without communication, and simultaneous localization and mapping using very limited odometry and sensors.

About the Speaker:

Maria Gini is a Professor in the Department of Computer Science and Engineering at the University of Minnesota, where she has been a faculty member since 1982. Her major contributions include robot navigation, robot motion planning, coordination of robots, and negotiation strategies for agents. She is currently the Chair of the ACM Special Interest Group on Artificial Intelligence (SIGART). She is on the editorial board of "Autonomous Robots" and "Integrated Computer-Aided Engineering", and on the Autonomous Agents steering committee. Additional information on the web.