We are developing network-based applications for education, journalism, and entertainment where many users share control of a single physical resource. Our latest project, Sharecam, is a single robotic pan, tilt, and zoom digital camera. In this proect we explore algorithms for controlling the camera frame based on independent requests from online users. We propose a metric for the degree of satisfaction for each user and formulate frame selection as an optimization problem. We propose a computational geometry-based algorithm and its distrbuted version. For n users, the algorithm runs in O(n2) time. Its distributed versions run in O(n) time on the client side and in O(n log n) time on the server side.
Figure 1: Sharecam's collaborative camera control interface on the Internet. Each Internet-based user loads two image windows. The lower window is a fixed image of the camera's reachable range of view. Each user requests a camera frame by positioning a dashed rectangle in the lower window. Based on these requests, the algorithm computes an optimal camera frame (shown with solid rectangle), moves the camera accordingly, and displays the resulting live image in the upper window. Requests and camera frames are updated every 10 seconds.
1Graduate Student (non-EECS)
2Visiting Professor, Utrecht University, The Netherlands
Existing fixtures for holding sheet metal parts are generally bulky, part-specific, and designed by human trial-and-error. In this project, we propose unilateral fixtures, a new class of fixtures that addresses these limitations using modular fixturing elements that lie almost completely on one side of the part, maximizing access on the other side for welding, assembly, or inspection. The primary holding elements are cylindrical jaws with conical grooves that expand between pairs of part hole corners; each grooved jaw provides the equivalent of four point contacts and facilitates part alignment during loading. We present a two-phase algorithm for designing unilateral fixtures. The first phase assumes the part is rigid and uses 2D and 3D kinematic analysis of form-closure to identify all pairs of candidate jaw locations. For this analysis we propose and prove three new grasp properties for 2D and 3D grips at concave vertices, and a new quality metric based on the sensitivity of part orientation to infinitesimal relaxation of jaw position. The first phase also sets bounds on jaw cone angles. The second phase addresses part deformation with a finite element method (FEM) analysis that arranges secondary contacts at part edges and interior surfaces. For a given sheet-metal part, given as a 2D surface embedded in 3D with n concavities and m mesh nodes, the kinematic algorithm takes O(n2) time to compute a list of all unilateral fixtures ranked by quality, or a report that none exist for that part. The FEM deformation analysis arranges r secondary contacts considering m part elements in O(m(sup>3r). We have implemented both phases of the algorithm and report alignment data from experiments with two physical parts.
Figure 1: Unilateral fixture used to hold sheet metal parts
Figure 2: Addition of secondary jaws to minimize deformation as calculated using a FEM mesh
1Graduate Student (non-EECS)
2Professor, Ford Motor Co.
3Outside Adviser (non-EECS), Ford Motor Co.
4Outside Adviser (non-EECS), Ford Moror Co.
To facilitate training and planning for surgical procedures such as prostate brachytherapy, we are developing new models for needle insertion and radioactive seed implantation in soft tissues. We describe a new 2D dynamic FEM model based on a reduced set of scalar parameters such as needle friction, sharpness, and velocity, and a 7-phase insertion sequence where the FEM mesh is updated to maintain element boundaries along the needle shaft. The computational complexity of our model grows linearly with the number of elements in the mesh and achieves 24 frames per second for 1250 triangular elements on a 750 Mhz PC. We use the simulator to characterize the sensitivity of seed placement error to surgical and biological parameters. Results indicate that seed placement error is highly sensitive to surgeon-controlled parameters such as needle position, sharpness, and friction, and less sensitive to patient-specific parameters such as tissue stiffness and compressibility.
Figure 1: Simulation of needle insertion based on an ultrasound image of a human prostate cancer patient. Frame (a) outlines the prostate (in green) and the target implant location (small white dot) which is fixed in the world frame. Our simulation places a radioactive seed (large green disc) at this location (d). After needle extraction and tissue retraction, the placement error, the distance between the target and resulting seed location shown in (f), is 30% of the width of the prostate. Needle plans that compensate for tissue deformation can reduce placement errors like these that damage healthy tissue and fail to kill cancerous cells.
The Soft Walls project is a technological response to the September 11, 2001 tragedy . The project goal is to design an aircraft control system to enforce government-mandated no-fly zones. The no-fly zones will include major cities, government centers, military installations, chemical and nuclear plants, and critical infrastructure centers. As an aircraft approaches a no-fly zone, the flight control system will force the aircraft away, giving the pilot a sensation of an external force. The no-fly zone boundaries are called Soft Walls, because aircraft are gently diverted as they approach these zones.
In the future, all aircraft are likely to use fly-by-wire systems, where pilot controls are mediated by computers, rather than being mechanically or hydraulically connected to the aircraft control surfaces. We are designing our control system for such fly-by-wire aircraft. The aircraft will carry a three-dimensional model of the earth’s surface, augmented with the no-fly zones. The model will change only when the no-fly zones change. One of our design principles is to give the pilot as much control as possible, subject to the constraint that the aircraft can never enter the no-fly zone.
We have developed a control algorithm for a two-dimensional infinite wall . This algorithm uses a simplified model of the aircraft dynamics and adds a bias to the pilot's control as the aircraft gets near the no-fly zone. The bias is increased and decreased gradually, and the algorithm is provably safe, that is, the aircraft can never enter the no-fly zone. Our next goal is to find a control algorithm which works for any convex, two-dimensional no-fly zone.
The goal of the cots-bots project is to use commercial off-the-shelf (COTS) components to build and deploy inexpensive and modular robots which can be used to investigate algorithms, and for cooperation and distributed sensing in large (> 50) robot networks. Current work is targeted towards providing a standard robot platform (both hardware and software) with a variety of modular sensor and actuator boards. The software used is based on the TinyOS operating system developed by Professor David Culler's group. Because the robots are intended to be simple in terms of computation, communication, and sensors, many of the algorithms demonstrated on the CotsBots platform will find future use in the MEMS Microrobot project.
To date, 50 robots have been built, a software platform has been developed, a simulator has been created, and work has begun on a low-cost inertial navigation system. Current algorithms being investigated include localization, robot diffusion, mapping, and pursuit-evasion games.
Figure 1: An example of a CotsBots robot--all hardware components are off-the-shelf and the software is open-source. The goal is to create an inexpensive and modular robot platform on which to test a variety of distributed robot algorithms.
We are considering the problem of evaluating the performance of Kalman filtering techniques on a sensor network. Communication delay and loss of data cannot be neglected in this new scenario. Starting from the discrete Kalman filtering formulation, making use of graphical models, we have made a first attempt to generalize the Kalman filter to take into account a model for the communication accross the network sensor.
Our research is part of an effort with the Mixed Initiative Control of Automata teams program (MICA). Our team works on developing agents that can deal with “intelligent,” as we term them, adversaries. The focus of my research is designing missions for unmanned aerial vehicles (UAVs). In particular, we are given that some enemy activity may take place in a specific region at a specific time in the future. My task is to provide algorithms for the helicopters to guide them into flying over that region in such a manner as to suppress enemy activity. These flight patterns vary greatly depending on the nature of the expected enemy activity. For example, some missions will require that the helicopters observe every part of a specific region as often as they possibly can. Other missions require the UAVs to move in such a way as to effectively “corner” a moving target. To successfully design such algorithms, we draw upon a wide range of resources, including game theory, network flow, and statistical learning theory.
The aim of this project is to build a navigation framework for an unmanned aerial vehicle, and to apply the result to the unmanned helicopter within the BEAR project. Navigation schemes that rely on a perfect knowledge of the environment are naturally unreliable. We consider this assumption unrealistic. We will divide the navigation problem into two tightly coupled subproblems: sensing and planning.
Sensing the environment is an essential requisite for any navigation problem. We'll make use of computer vision and gps/ins sensors and combine them in order to acquire a confident knowledge of the environment and of our motion in it. Sensor redundancy will also assess robustness with respect to fault detection and handling.
Motion planning, i.e., the capability of deciding what motion to execute in order to reach a goal, is fundamental to the design and realization of autonomous robots. A good motion planning algorithm must ensure safety, by avoiding collision and planning feasible paths, and efficiency (minimum travel time, etc.).
We study non-local two-qubit operations from a geometric perspective. By applying a Cartan decomposition to su(4), we find that the geometric structure of non-local gates is a 3-Torus. We derive the invariants for local transformations, and connect these local invariants to the coordinates of the 3-Torus. Since different points on the 3-Torus may correspond to the same local equivalence class, we use the Weyl group theory to reduce the symmetry. We show that the local equivalence classes of two-qubit gates are in one-to-one correspondence with the points in a tetrahedron except on the base. We then study the properties of perfect entanglers, that is, the two-qubit operations that can generate maximally entangled states from some initially separable states. We provide criteria to determine whether a given two-qubit gate is a perfect entangler and establish a geometric description of perfect entanglers by making use of the tetrahedral representation of non-local gates. We find that exactly half the non-local gates are perfect entanglers. We also investigate the non-local operations generated by a given Hamiltonian. We first study the gates that can be directly generated by a Hamiltonian. Then we explicitly construct a quantum circuit that contains at most three non-local gates generated by a two-body interaction Hamiltonian, together with at most four local gates generated by single qubit terms. We prove that such a quantum circuit can simulate any arbitrary two-qubit gate exactly, and hence it provides an efficient implementation of universal quantum computation and simulation.
Unmanned air vehicles (UAV) have been a very active area of research. Despite recent remarkable achievements obtained with fixed and rotary aircrafts , their use in many tasks is still limited by their maneuverability and size. However, the extraordinary flight capabilities of insects have inspired the design of small UAVs with flapping wings mimicking real flying insects. Their unmatched maneuverability, low fabrication cost, and small size make them very attractive for cost-critical missions in environments that are unpenetrable for larger size UAVs. In order to fabricate a micromechanical flying insect (MFI) eventually capable of stable flight, it is necessary to design and develop sensors capable of estimating the orientation of the insect. We are currently investigating the use of ocelli, a set of biologically inspired sensors, capable of estimating the orientation. The ocelli are four wide-angle photoreceptors placed on the head of the insect. They are oriented in such a way they collect light from different region of the sky (see Figure 1). The intensity of the light from the sky is a function of the latitude only, therefore, in principle, it is possible to estimate the orientation of the insect by opportunely combining the output of the four photoreceptors. Our goal is to use this information to design stabilizing controllers for hovering and maneuvering flight modes for an MFI.
Figure 1: Ocelli modeling: every photoreceptor collects light intensity from a specific area of the sky.
In the past few years we have been witnessing the explosion of Internet and wireless networking. Computation and communication are becoming ubiquitous and affordable at very large scale. An enormous amount of information becomes readily available to assist any decision process. Centralized algorithms for computation of this information are doomed to fail because of their intrinsic lack of scalability. In this research we propose to develop a framework for the design of distributed algorithms for large wireless sensor networks and evaluate their performance with respect to some predefined metrics. In particular, we propose to integrate a wireless sensor network into the pursuit evasion games (PEGs) framework . In this framework, a group of unmanned pursuers (ground robots and helicopters) monitors an unknown terrain searching for evaders. The pursuers cooperate via radio communication to catch the moving evaders. We propose to extend this framework by deploying, into the environment, a large scale wireless sensor network consisting of about one thousand nodes. Every node in this network is equipped with sensors capable of detecting an object moving nearby, and it is subject to tight power, bandwidth, and communication constraints. Any centralized algorithm to estimate the position and track the motion of the evaders would show poor scalability properties in this modified scenario. In our approach we propose alternative algorithms where computation is distributed among the nodes and then transmitted to the pursuers.
The goal of this work is the development of a software simulator (VIFS) for the flight of a micromechanical flying insect (MFI) inside a virtual environment. The final version of the simulator should eventually include several units to make it realistic: a model for the aerodynamics, a model for the dynamics, a model for the electromechanical architecture, a model for the sensors, and a set of flight control and path planning algorithms. We would like to add a graphical interface that would provide a visualization of the behavior of the MFI in the environment.
There are several reasons why it is useful to have a software simulator: it can (1) simulate insect body dynamics; (2) give a faster simulation of aerodynamics than scaled insect models; (3) be easily integrated with any elecromechanical and sensory system models; (4) provide insights to direct mechanical design, thus speeding up the fabrication of the real MFI; and (5) pre-train learning flight controllers, thus reducing the risk of damaging the real MFI.
The VIFS is decomposed into several units, each of them responsible of an independent task, as shown in Figure 1.
Figure 1: Virtual insect flight simulator (VIFS) architecture
Computer vision is gaining importance as a cheap, passive, and information-rich source complementing the sensor suite for control of unmanned aerial vehicles (UAV). A vision system on board a UAV typically augments a sensor suite that might include a Global Positioning System (GPS), inertial navigation sensors (INS), laser range finders, a digital compass, and sonar. Because of its structured nature, the task of autonomous landing is well-suited for vision-based state estimation and control and has recently been an active topic of research.
In our research , we have designed and implementated a real-time vision system for a rotorcraft unmanned aerial vehicle to estimate its state relative to a known landing target at 30 Hz. Our vision system consists of off-the-shelf hardware to perform image processing, segmentation, feature point extraction, camera control, and both linear and nonlinear optimization for model-based state estimation. Flight test results show our vision-based state estimates are accurate to within 5 cm in each axis of translation and 5 degrees in each axis of rotation, making it a viable sensor to be placed in the control loop of a hierarchical flight vehicle management system.
Recently , we developed a multiple view algorithm for vision-based landing of an unmanned aerial vehicle. Our algorithm is based on our recent results in multiple view geometry that exploit the rank deficiency of the so-called multiple view matrix. We show how the use of multiple views significantly improves motion and structure estimation. We compare our algorithm to our previous linear and nonlinear two-view algorithms using an actual flight test.
Furthermore, we have conducted vision-in-the-loop flight experiments and used the above vision system to successfully track a pitching landing deck which simulates the motion of a ship in 2 meter waves in 5 knot winds.
Figure 1: Berkeley UAV test-bed with on-board vision system: Yamaha R-50 helicopter with pan/tilt camera and computer box hovering above a pitching landing platform
Figure 2: Berkeley UAV test-bed with on-board vision system: Yamaha R-50 helicopter tracking a pitching landing platform, foreground shows the camera view of landing target
Figure 3: Vision monitoring station
In , we present an algorithm for infinitesimal motion estimation from multiple central panoramic views. We first derive the optical flow equations for central panoramic cameras as a function of both pixel coordinates and back-projection rays. We then derive a rank constraint on the optical flows across many frames, which must lie in a six dimensional subspace of a higher-dimensional space. We then propose a factorization approach for recovering camera motion and scene structure.
In , we generalize this approach to the case where there are multiple independently moving objects. We show that one can apply a factorization technique to estimate the number of independently moving objects and segment the omnidirectional optical flow based on the fact that the flows generated by independently moving objects lie in orthogonal subspaces to each other.
We present experimental results of the proposed motion segmentation and estimation algorithm on a real image sequence with two independently moving mobile robots, and evaluate the performance of the algorithm by comparing the vision estimates with ground-truth GPS measurements gathered by the mobile robots.
Figure 1: Showing the optical flow of an omnidirectional camera viewing two independently moving mobile robots
Figure 2: Showing the multi-body motion segmentation of the mobile robots
Modeling time series is a fundamental problem in many scientific and engineering disciplines. In particular, in computer vision the problem arises when one tries to characterize the dynamics of visual processes, for instance, the appearance of smoke, fire, foliage of trees, or walking gaits. All of these examples can be modeled as a linear hybrid system, that is, a system whose evolution is determined by a collection of linear models connected by switches among a number of discrete states.
In  and  we analyze the observability of the continuous and discrete states of a class of linear hybrid systems. We derive rank conditions that the structural parameters of the model must satisfy in order for filtering and smoothing algorithms to operate correctly. Our conditions are simple rank tests that exploit the geometry of the observability subspaces generated by the output of a linear hybrid system. We also derive weaker rank conditions that guarantee the uniqueness of the reconstruction of the state trajectory from a specific output, even when the hybrid system is unobservable. We also study the identifiability of the model parameters by characterizing the set of models that produce the same output measurements. Finally, when the data is generated by a model in the class, we give conditions under which the true model can be identified.
In [1-3], we consider the problem of distributed formation control for nonholonomic mobile robots equipped with central-panoramic cameras. Our approach is to translate the formation control problem from the configuration space into separate visual servoing tasks in the image plane. We present an algorithm for infinitesimal multi-body motion estimation and segmentation from multiple central panoramic views. We derive a rank constraint on the optical flows across many frames, from which one can estimate the position and velocities of each leader in the paracatadioptric plane of the follower. We design a tracking controller for each mobile robot and show that there exist degenerate formation configurations due to the nonholonomy of the robot dynamics and the nonlinearity of the central-panoramic projection model. The control law naturally incorporates collision avoidance by using a navigation function that exploits the geometry of central-panoramic cameras. We present experimental results on multi-body motion estimation, segmentation of a real image sequence, and simulation results on vision-based control for many formation configurations.
Figure 1: A sample motion segmentation of mobile robots based on omni-directional vision.
Figure 2: Three mobile robots switching from a triangle to a line formation while avoiding collision.
We present an algebraic geometric approach for segmenting both static and dynamic scenes from image intensities. We introduce the multibody affine constraint as a geometric relationship between the motion of multiple objects and the image intensities generated by them. This constraint is satisfied by all the pixels, regardless of the body to which they belong and regardless of depth discontinuities or perspective effects. We propose a polynomial factorization technique that estimates the number of affine motion models as well as their motion parameters in polynomial time. The factorization technique is used to initialize a nonlinear algorithm that minimizes the algebraic error defined by the multibody affine constraint. Our approach is based solely on image intensities, hence it does not require feature tracking or correspondences. It is therefore a natural generalization of the so-called direct methods in single-body structure from motion to multiple moving objects. We present simulation and experimental results that validate our approach.
We study the problem of estimating the motion of independently moving objects observed by a moving perspective camera. We show that infinitesimal image measurements corresponding to independent motions lie on orthogonal six-dimensional subspaces of a higher-dimensional linear space. We propose a factorization algorithm that estimates the number of independent motions, the segmentation of the image points, and the motion of each object relative to the camera from a set of image points and their optical flows in multiple frames. We evaluate the proposed algorithm on synthetic and real image sequences.
Figure 1: Segmentation of two independent motions: the camera and the car.
We present a vision-based algorithm for the detection of multiple autonomous vehicles for a pursuit-evasion game scenario. Our algorithm computes estimates of the poses of multiple moving evaders from visual information collected by multiple moving pursuers, without previous knowledge of the segmentation of the image measurements or the number of moving evaders. We evaluate our algorithm in pursuit-evasion games with unmanned ground and aerial vehicles.
Figure 1: A pursuit-evasion game with two ground and one aerial pursuer and one ground evader.
We present a geometric approach for the analysis of dynamic scenes containing multiple rigidly moving objects seen in two perspective views. Our approach exploits the algebraic and geometric properties of the so-called multibody epipolar constraint and its associated multibody fundamental matrix, which are natural generalizations of the epipolar constraint and of the fundamental matrix to multiple moving objects. We derive a rank constraint on the image points from which one can estimate the number of independent motions and linearly solve for the multibody fundamental matrix. We prove that the epipoles of each independent motion lie exactly in the intersection of the left null space of the multibody fundamental matrix with the so-called Veronese surface. We then show that individual epipoles and epipolar lines can be uniformly and efficiently computed by using a novel polynomial factorization technique. Given the epipoles and epipolar lines, the estimation of individual fundamental matrices becomes a linear problem. Then, motion and feature point segmentation is automatically obtained from either the epipoles and epipolar lines or the individual fundamental matrices.