This has been a 6 year project, begun in September 2001, and work related to the project is still ongoing. We had a number of broad research goals in this research project:

• Developing new methods of creating complex, three-dimensional, photo-realistic, interactive models of large historical and archaeological sites.
• Developing a system to create a new class of information visualization systems that integrate three-dimensional models, two dimensional images, text, and other web-based resources to annotate the physical environment. This system will support scientists in the field, as well as facilitate on-site interpretation and distance learning.
• Developing new database technology to catalogue and access a site's structures, artifacts, objects, and their context. This will significantly improve a user's ability to query and analyze a site's information.
• Developing methods and resources that will permit teachers and students to access the model and associated information over the Internet and to use it both in the classroom and at home. The goal is to allow flexible access on a variety of educational levels to a mass of emerging scientific and historic data to show how discovery and change are a part of both scientific and interpretive dynamic processes.

Project Participants:

Peter Allen Computer Science
James Conlon Media Center for Art History, Archaeology, Preservation
Steven Feiner Computer Science
Lynn Meskell Anthropology
Stephen Murray Art History and Archaeology
Kenneth Ross Computer Science

This research has 2 components. The first is a patented method for 3-D CAD models from range data. The second part is the AVENUE project which extends these methods to create geometric and photometric correct models of large outdoor structures (buildings). We are currently pursuing three testbeds for this research: the Columbia University campus, the Cathedral of Saint Pierre in Beauvais, France, and the Columbia University excavation in Amheida, Egypt.

AVENUE stands for Autonomous Vehicle for Exploration and Navigation in Urban Environments. The project targets the automation of the urban site modeling process. The main goal is to build not only realistically looking but also geometrically accurate and photometrically correct models of complex outdoor urban environments. These environments are typified by large 3-D structures that encompass a wide range of geometric shapes and a very large scope of photometric properties.

The models are needed in a variety of applications, such as city planning, urban design, historical preservation and archaeology, fire and police planning, military applications, virtual and augmented reality, geographic information systems and many others. Currently, such models are typically created by hand which is extremely slow and error prone. AVENUE addresses these problems by building a mobile system that will autonomously navigate around a site and create a model with minimum human interaction, if any.

The task of the mobile robot is to go to desired locations and acquire requested 3-D scans and images of selected buildings. The locations are determined by the sensor planning (a.k.a view planning) system and are used by the path planning system to generate reliable trajectories which the robot then follows. When the robot arrives at the target location, it uses the sensors to acquire the scans and images and forwards them to the modeling system. The modeling system registers and incorporates the new data into the existing partial model of the site (which in the beginning could be empty). After that, the view planning system decides upon the next best data acquisition location and the above steps repeat. The process starts from a certain location and gradually expands the area it covers until a complete model of the site is obtained.

The entire task is complex and requires the solution of a number of fundamental problems:

the creation of complete 3-D models of buildings and other large urban structures
the fusion of range and image data
the automated planning of new viewpoints
the automated acquisition of range and image data

Our current efforts are focused on constructing a biomechanically realistic human hand model. Such a model would serve to aid clinicians planning reconstructive surgeries of a hand, since many of the mechanical aspects of this complex organ are still not fully understood. However, this sort of model would also allow us to determine which features of the human hand are the most important to be mimicked when designing a robotic hand. These beneficial features will be identified by creating several versions of the human hand model, each with different sets of features, and analyzing the ability of each hand to perform a set of grasping and manipulation tasks. The iterative refinements include skin deformations, realistic human joints to determine the benefits of a compliant kinematic structure, and the network of tendons to determine what are the advantages, if any, of indirect actuation of the joints.

One difficulty in understanding human hand control is the large number of degrees of freedom (DOFs) involved. This flexibility gives rise to an enormous set of possible hand configurations. The high dimensionality of the control space also explains the difficulty in creating effective control algorithms for all but the simplest artificial hand designs.

One possible explanation for human efficiency in selecting appropriate grasps assumes that humans unconsciously simplify the large search space through learning and experience. Recent advances in neuroscience research have shown that control of the human hand during grasping is indeed dominated by movement in a configuration space of highly reduced dimensionality. In my work, I extend this concept to robotic hands and show how a similar dimensionality reduction can be defined using a number of basis vectors called eigengrasps. This framework can be used to derive optimization algorithms that simplify the task of finding stable grasps even for highly complex hand designs. Furthermore, it offers a unified approach for controlling different hands, even if the kinematic structures of the models are significantly different.

Image: planning results obtained by searching the eigengrasp space for stable grasps. The planning method uses a unified treatment for all robotic hand models in the image, even though the kinematic specifications are significantly different.

The ability to plan and execute a realizable and stable grasp on a 3-D object is crucial for many robotics applications, but many grasp planning approaches ignore the relative sizes of the robotic hand and the object being grasped or do not account for physical joint and positioning limitations. We have developed a grasp planner that can consider the full range of parameters of a real hand and an arbitrary object, including physical and material properties as well as environmental obstacles and forces, and produce an output grasp that can be immediately executed without any further computation. We do this by decomposing a 3D model into a superquadric "decomposition tree". We can then use this decomposition tree to prune the intractably large space of possible grasps into a subspace that is likely to contain many good grasps. The parameters of the grasps that lie within this subspace can then be sampled and the results evaluated in GraspIt!, to find a highly stable grasp to output. We have experimental results on a database of object models using a Barrett hand. We have also implemented an SVM classifier that can be used to reduce the number of candidate grasps.

We have developed a system that combines human input and automatic grasp planning for controlling an artificial hand, with applications in the area of hand neuroprosthetics. We consider the case where a user attempts to grasp an object using a robotic hand, but has no direct control over the hand posture. An automated grasp planner searches for stable grasps of the target object and shapes the hand accordingly, allowing the user to successfully complete the task. We rely on two methods for achieving the computational rates required for effective user interaction: first, grasp planning is performed in a hand posture subspace of highly reduced dimensionality; second, our system uses real-time input provided by the human user, further simplifying the search for stable grasps to the point where solutions can be found at interactive rates. We demonstrate our approach on a number of different hand models and target objects, in both real and virtual environments.
Columbia University Robotics Lab.

Matei T. Ciocarlie and Peter K. Allen

We have developed a Finite Element Method based engine for dynamic simulation of deformable objects (top image shows this engine used to compute the deformation of a box-shaped object under the effect of gravity). This software can be used as a C++ library, and also as a stand-alone application as it includes an OpenGL-based visualization component. The engine can currently use three simulation methods:

Newton iteration method converging to the equilibrium position of the system
Newmark step based method, used for dynamic simulations and computing the velocity and accelerations at the vertices of the deformable mesh
modified Newton iteration accounting for frictional contacts against planar surfaces. If the direction of relative motion at the contact is specified, this will compute the effects of contact normal forces as well as friction on the vertices of the deformable mesh.
This engine has been used for studying robotic fingertips (as described above) as well as human fingertips. The bottom image shows an anatomically correct fingertip model (with outer surface as well as the inner bone obtained from medical images) deforming under pressure from a planar surface.

Step 1: Wash

Step 2: Touch

Step 3: Streak 

The goal of the Protein Streak Seeding project is the creation of an innovative high-throughput (HTP) microrobotic system for a protein crystallography task called streak seeding. The system uses visual feedback from a camera mounted on a microscope to control a micromanipulator which has the mounting tool attached as its end-effector. For use with our robotic system, we have developed unique new tools, called miscroshovels, which are designed to address certain limitations of the traditionally used by crystallographers whiskers, bristles, or other kinds of hair.

Task Description
Streak seeding is useful when the initial crystallization experiments yield crystals which are too small (less than 40um in size) and/or of low quality and can not be used for structure determination. To obtain higher quality crystals, a new reaction is setup like the original one, however, before incubation, small fragments of the initially obtained crystals are transferred to the new protein-reagent mixture to bootstrap the crystallization process. This crystal fragment transfer process is called streak seeding.

The task of streak seeding consists of three steps (right). First, the tool to be used is washed in clean water to remove any residue. Second, the tool is used to touch and probe the existing crystals thus breaking them up into fragments and picking some up. Third, the tool is streaked through the fresh mixture, which deposits some of the fragments in it. For this to work, the tool has to have the necessary properties to be able to break up, retain and release crystal fragments. Typically, various types of hair, bristles, whiskers or horse tail are used.

System Design And Operation
We have designed and assembled a micro-robotic system for protein crystal manipulation, which we use for our research and experiments. The system uses our own custom tools, called microshovels, which we designed and fabricated using MEMS technology.

The streak seeding system is designed to work with the hanging drop crystallization method, seeding from source crystals on a 22mm square coverslip to destination drops on a coversheet for a 96-well plate. The user sets up the system by placing on the stage the coverslip with the protein crystals, the coversheet of the 96-well plate with the target protein droplets, and a microbridge with water used for cleaning the seeding tool. Then the system is started and it performs the seeding autonomously. The video on the right (sped up twice) shows the system in operation.

The goal of the Protein Crystal Mounting project is to produce a microrobotic system capable of autonomously mounting protein crystals on a tool for the purpose of X-ray data collection. The system uses visual feedback from a camera mounted on a microscope to control a micromanipulator which has the mounting tool attached as its end-effector. For use with our robotic system, we have developed unique new tools, called miscroshovels, which are designed to address certain limitations of the traditionally used by crystallographers cryogenic loops and capillaries.

Endoscopic imaging for minimal access surgery has many limitations that include: 2D and narrow angle imaging, limited workspace of the endoscope caused by the fulcrum effect of the body wall, and the presence of the endoscope in the incision that prevents use of the incision for other instrumentation. We have designed a novel stereoscopic 3D imaging device with 5 DOF and remote control that can be inserted and attached in the body cavity. The device, contained within a 11/16" tube, includes two miniature cameras and five small motors that position the cameras to provide a stereoscopic view of the surgical site. When inserted the cameras are retracted and protected by an outer shell. After the device is fixed within the abdominal cavity, a motor rotates an inner shell to expose the cameras. Once exposed, the cameras can tilt in tandem, translate independently along the axis of the tube, and independently pan. The software controls the cameras to create new views for the surgeon, to move along the adjustable baseline, to verge for stereoscopic viewing, and to potentially track moving organs. We have completed a proof of concept design, which includes CAD models and animations of the device, and we are currently building a physical prototype. Once the prototype is completed, we will begin testing it in a surgical mock-up, followed by animal and clinical trials. [Patent pending]

Andrew Miller, Peter Allen, and Dennis Fowler. “In-vivo stereoscopic imaging system with 5 degrees-of-freedom for minimal access surgery.” In Medicine Meets Virtual Reality 12, pp. 234-240, January, 2004.

My specific interest in machine vision is to monitor a large assembly workcell (about the size of a classroom). I want to visually track objects like tools, workpieces and grippers as they move around in the workcell. We therefore custom built a ceiling-mounted gantry and attached a pan-tilt unit (PTU) and camera at the end-effector. The net result is a hybrid 5 degrees-of-freedom (DOF) robot that can position and orient the camera anywhere in the workspace. Our hybrid robot servos the camera to keep the moving object centered in its field-of-view and at a desired image resolution.
Approach

Traditionally researchers attacked similar problems by measuring 3-D object pose from 2-D camera images. This requires a priori knowledge of the object geometry and hence researchers typically use CAD-based models or paint fiducial marks at specific locations on the object. The 3-D object pose measurements are then used with image and manipulator Jacobians to map velocity changes in the camera's image space to the robot's joint space. The net effect is that the robot servos the camera to regulate a desired camera-to-object pose constraint.

The caveat of such a regulation technique is that the robot's motors may not have sufficient bandwidth (torque capabilities) to maintain such a constraint. Our gantry is slow because of its heavy linkages. Failure to accelerate the camera fast enough will result in loss of visual contact. Furthermore, abrupt accelerations generate endpoint vibrations which effect image acquisition. By contrast, the PTU is lightweight and fast and can quickly rotate the camera to maintain visual contact. The net effect is that tracking performance depends on which DOF are invoked in the tracking task.

My approach to the tracking problem was to design a control law that defines a joint coupling between the PTU and gantry. This idea came from casually observing human tracking behavior. People also have joints (eyes, neck, torso) of varying bandwidths and kinematic range. We synergize all of our DOF when tracking a moving object and we don't need a priori object geometry knowledge. One also notices that the eyes and neck tend to pan in the same direction as we follow an object's motion trajectory. This behavior suggests an underlying kinematic joint coupling.
(Paul Y. Oh)