Minimal Data Set Optimal Classification
James R. Psota, Malik Magdon-Ismail, Yaser Abu-Mostafa

We are developing classification techniques to detect the nature of a pump malfunction given pump vibration sensor data. The size of the data set is very minimal, creating the need for an extremely robust classifier that incorporates all available information. We investigated several generalized nearest neighbor and Bayesian classifiers. By incorporating hints, or information about the problem known independently of the data set, we show that performance can be significantly improved. (full report)

Awareness-Based Computation: The Bin Packing Problem
Greg Billock, Demetri Psaltis, Christof Koch

In previous work (see report entitled Awareness-Based Computation), we have investigated the impact of using approaches to simulated environments/problems inspired by the way human beings use awareness and attentional mechanisms to interact with a complex world. In this work, we explore how this works in the context of a familiar computer science problem: bin packing. As an abstract problem, the bin-packing problem has the advantage of having been subjected to extensive analysis and so much is known about it. It is a very important practical problem, as well, with applications to cutting stock, machine and job scheduling, parallel processing scheduling, FPGA layout, loading problems, and more. By using ideas about reduced representations of what is most important in an on-line solution of the problem, we are able to devise a heuristic which outperforms existing heuristics, and understand how and why it does so. (full report)

Awareness-Based Computation
George Barbastathis, Greg Billock, Demetri Psaltis, Christof Koch

In this project, we are developing design principles for intelligent systems that can interact with very complex, variable, and poorly modeled environments. In doing so, we draw inspiration from the discoveries of neurobiology relating to the role of attention and awareness. These aspects of biological processing systems is key in conferring on them the ability to function in such high-dimensional real-world environments. At the heart of our architecture lies the idea of adapting an abstraction of awareness with which to endow artificial man-made systems. (full report)

Learning in Hardware
Alexander Nicholson, Arrigo Benedetti, Yaser Abu-Mostafa, Pietro Perona

We investigate the use of learning and adaptation for digital hardware design. We use reconfigurable hardware devices and discrete optimization methods to learn circuits from a set of examples. We have shown that this approach works well for the design of small arithmetic circuits and that significant performance improvements may be achieved by moving away from a strictly evolvable (genetic algorithms) approach. (full report)

The Bin Model for Generalization
Alexander Nicholson, Xubo Song, Yaser Abu-Mostafa

The problem of overfitting the data is attacked by using the Bin Model analysis. This provides a method of bounding generalization error without sacrificing valuable training data. (full report)

Monotonicity Hints in Machine Learning
Joseph Sill, Yaser Abu-Mostafa

This project focuses on both practical and theoretical aspects of the monotonicity constraint in machine learning. Learning methods which enforce monotonicity in models such as neural networks are being developed. In addition, the flexibility and expressive power of the class of monotonic binary output functions are analyzed and quantified from a theoretical perspective. (full report)

Support Vector Machines - A New Approach to Learning
Malik Magdon-Ismail, Jennie Yoder, Yaser Abu-Mostafa

Support Vector Machines are a method of extracting information from few noisy data points. A classification boundary is created allowing the largest possible margin of error. The technique is robust and easily implemented. (full report)

Distributed Collective Building of Two-Dimensional Structures Using Autonomous Robots
Kjerstin Easton, Alcherio Martinoli, Rodney Goodman

Using autonomous robots to build three-dimensional structures is a distant goal, but the first step in approaching collective building is to construct two-dimensional architectures. Using a team of miniature Khepera robots with manipulation and vision capabilities, we will implement a building technique modeled after qualitative stigmergic construction mechanisms used by social insects. This technique will allow the robots to communicate building instructions through modifications to the local environment, avoiding dependence on explicit robot-to-robot communication and lending itself to implementation with any number of robots. (full report)

Optimal Task Allocation and Distributed Sensing in Collective Autonomous Robotics
William Agassounon, Alcherio Martinoli, Rodney Goodman

Our research aims at studying two particular topics within the Collective Robotics field, these are the division of labor and the dynamic task allocation. The Swarm Intelligence approach can be applied to fully distributed systems that consist of several autonomous decision making entities working together with minimal communication and local perception to complete one or several tasks. Our approach is inspired by biological systems such as colonies of social insects (ants, bees, termites, etc) in which the collective behavior often emerges from a series of local agent-to-agent and agent-to-environment interactions. We are developing response threshold-based algorithms for optimal task allocation and probabilistic models that provide accurate forecast of the resulting collective behavior. Finally, one of the main strengths of this project is the attempt to create a theoretical framework for real embedded systems provided with threshold allocation mechanisms. These systems are therefore analyzed at several implementation levels, from analytical probabilistic models to real robots experiments through embodied sensor-based simulators. (full report)

Distributed Plume Tracing
Adam T. Hayes, Alcherio Martinoli, Owen Holland, Rodney M. Goodman

The objective of this project is to study biologically inspired algorithms which enable a robot or group of robots to track an odor plume to its source, with an appropriate combination of speed, efficiency, reliability, and accuracy. Research is conducted at three levels: non-embodied point simulations, embodied sensor-based simulations, and real robots. The simulations use sensors and actuators which are based on the capabilities of the real robots, and plume information is derived from empirical data files recorded from real plumes or realistic plume simulators. In simulation we explore the performance of various families of simple algorithms, as well as the potential for automated parameter tuning and on-line learning. We assess the most promising algorithms on real robots, which are equipped with Caltech olfactory sensors, anemometric devices, and simple communication systems. (full report)

Evolving Robust, Collective Patrolling Behavior Using Genetic Algorithms
Joseph Chen, Alcherio Martinoli, Rodney M. Goodman

Evolution is a powerful force. Harvester ants have successfully evolved to efficiently patrol their territory for different type of events (food items, enemy intrusion, etc.). The goal of this project is to study how effective and robust patrolling behavior can be evolved first in embodied, sensor-based simulations and then in real robot experiments. We will use evolutionary techniques (Genetic Algorithms, GA) for exploring the individual control parameters that play a crucial role in the team patrolling performance. In order to better understand the required individual and group capabilties for effective patrolling, we will test the influence of individual navigation capabilities and different fitness functions. We will also note whether any interesting collective behavior develops if the robots are allowed to directly communicate at each encounter, without introducing any type of stigmergic mechanism (e.g. pheromones). (full report)

Swarm Intelligence and Traffic Safety
Philip Tsao, Alcherio Martinoli, Rodney M. Goodman

An automotive controller that complements the driving experience must work to avoid collisions, enforce a smooth trajectory, and deliver the vehicle to the intended destination as quickly as possible. Unfortunately, satisfying these requirements with traditional methods proves intractable at best and forces us to consider biologically-inspired techniques such as Swarm Intelligence. A controller is currently being designed in a robot simulation program with the goal of implementing the system in real hardware to investigate these biologically-inspired techniques and to validate the results. (full report)

Set-Valued Analysis for Switching Systems
Todd Murphey, Joel W. Burdick

Conventional nonholonomic motion planning and control theories do not directly apply to "overconstrained vehicles,'' such as the Sojourner vehicle of the Mars Pathfinder mission. This research investigates some basic issues that are necessary to build a motion planning and control framework for this potentially important class of mobile robots. A power dissipation approach is used to model the governing equations of overconstrained vehicles that move quasi-statically. These equations are shown to be switched hybrid systems. Standard notions, such as the Lie bracket, are extended to these switched systems. We then develop a controllability test for such systems. We explore motion planning primitives in the context of simplified examples. Another application area is that of distributed manipulation, where parts are being oriented by a large array of actuators. Here, too, the issues of discrete behavior as the part traverses different contact states plays a large role in analyzing stability. (full report)

Detection of Human Motion in a Cluttered Scene
Yang Song, Xiaolin Feng, Luis Goncalves, Pietro Perona

Detecting humans in images is a useful application of computer vision. Loose and textured clothing, occlusion and scene clutter make it a difficult problem because bottom-up segmentation and grouping do not always work. We address the problem of detecting humans from their motion pattern in monocular image sequences; extraneous motions and occlusion may be present. We assume that we may not rely on segmentation, nor grouping and that the vision front-end is limited to observing the motion of key points and textured patches in between pairs of frames. We do not assume that we are able to track features for more than two frames. Our method is based on learning an approximate probabilistic model of the joint position and velocity of different body features. Detection is performed by hypothesis testing on the maximum a posteriori estimate of the pose and motion of the body. Our experiments on a dozen of walking sequences indicate that our algorithm is accurate and efficient. (full report)

Configurable Architectures and Systems for Real-Time Low-level Vision
Arrigo Benedetti, Pietro Perona

The long-term goal of this project is to build an infrastructure for the design and implementation of real-time computer vision systems. Since vision algorithms are compute-bound we have chosen the technology of Field Programmable Gate Array (FPGAs), that allow to exploit the parallelism inherent to the first stages of low-level vision tasks. The first problem that we have considered is the real-time computation of the optical flow measured from the sequence of images captured by a video camera. We have designed, built and demonstrated a system able to select in real-time 2-D visual features on a commercially available platform. During this process we have learned that the system level architectures of commercially available configurable systems are not optimized for low level vision tasks, therefore, we have designed a novel architecture dedicated to real-time processing of video streams. A system based on this architecture has been built and is currently being tested. More recently, we have studied the problem of bit-width computation for the optimization of the data paths found in digital video signal processors. (full report)

Learning Object Class Models
Markus Weber, Max Welling, Robert Fergus, Pietro Perona

We have developed a method to automatically learn models of visual object classes from sets of unlabeled and unsegmented training images. The method has been demonstrated to work on images of cars and handwritten characters and it is being adapted to human faces. (full report)

Finding Faces in Cluttered Scenes
Markus Weber, Michael Burl, Pietro Perona

We have designed algorithms that learn a probabilistic description of human faces and other object classes. We have implemented a real-time face detection system which runs at 1Hz and demonstrates the ability to handle deformations, occlusions and background clutter. (full report)

3D Vision with Minimal Equipment
Silvio Savarese, Jean-Yves Bouguet, Pietro Perona

The aim of our work is to investigate new approaches for three-dimensional reconstruction of objects. The proposed techniques require minimal and inexpensive equipment. (full report)

Perception and 3D Reconstruction of Specular Surfaces
Silvio Savarese, Pietro Perona

The aim of our work is to investigate how the human visual system perceives specular surfaces and which cues can be used to recover the shape of such class of objects. (full report)

3D Photography on Your Desk
Jean-Yves Bouguet, Pietro Perona

We are developing a simple and inexpensive method for extracting the three-dimensional shape of objects by using weak-structured lighting. Experimental results demonstrate that the error in reconstructing the surface is less than 1%. (full report)

Visual Input for Pen-Based Computers
Mario E. Munich, Pietro Perona

Our work focuses on the development of a visual interface for pen-based computers. We are building a system that visually tracks the trajectory of a pen in real-time and recovers the handwritten strokes with sufficient spatio-temporal resolution and accuracy to enable handwritten character recognition. (full report)

Camera-Based ID Verification by Signature Tracking
Mario E. Munich, Pietro Perona

The goal of this project is to develop a vision-based biometric technique based on visual capturing of signatures and to evaluate the performance of the system. (full report)

Divide and Conquer Strategy for Recognition
George Panotopoulos, Demetri Psaltis

We devised a classification strategy based on the division of a single complex question to more, simpler questions. We showed that this strategy corresponds to a tree structure and can be implemented by reconfigurable computers. We demonstrated the efficiency of this strategy on the problem of classification of handwritten digits. We derived analytical expressions linking the performance of the overall classifier to the performance of its parts. (full report)