WAFR'98: Invited Speakers
WAFR'98: Invited Speakers
John Craig, Adept
Bruce Donald, Dartmouth
Herbert Edelsbrunner, UIUC
Leo Guibas, Stanford
Richard Murray, Caltech
Jocelyne Troccaz, Grenoble
Joe Warren, Rice
AdeptRAPID is a software package used to design and simulate robot-based flexible automation cells. Its goal is to simplify the concepting and design of automation installations used for applications such as mechanical assembly, material handling, or packaging. Ease of use is of paramount importance so that this technology can truly impact the way industrial automation is accomplished.
The need for ease of use drives the need for the simulation system to behave like the actual physical world. The more the simulator acts like the real world, the simpler the user interface paradigm for the user, since the physical world is the one we are all familiar with. At the same time, trade-offs for compuational speed and other factors have driven a design in which a particular "slice" of reality is simulated, while many details are not.
AdeptRAPID is well-suited as a host for a variety of geometric algorithms. The need to model various portions of the real world, as well as the need to unburden the user by making various computations of a geometric nature drive the need for such algorithms. AdeptRAPID provides the environment in which some advanced algorithms can be brought to bear on real problems occuring in industry.
This paper presents the current state of development of the AdeptRAPID simulator. Attention is paid to the various geometric algorithms already in place as well as the need for more and better algorithms.
As improvements in fabrication technology for MEMS (microelectromechanical systems) increase the availability and diversity of these micromachines, engineers are defining a growing number of tasks to which they can be put. The idea of carrying out tasks using large coordinated systems of MEMS units motivates the development of automated, algorithmic methods for designing and controlling these groups of devices. We report here on progress towards algorithmic MEMS, taking on the challenge of design, control, and programming of massively-parallel arrays of microactuators.
Arrays of MEMS devices can move and position tiny parts, such as integrated circuit chips, in flexible and predictable ways by oscillatory or ciliary action. The theory of programmable force fields can model this action, leading to algorithms for various types of micromanipulation that require no sensing of where the part is. Experiments support the theory.
[Joint paper with Karl Bohringer, Berkeley]
The use of geometric models for molecular conformations dates back at least to Lee and Richards who in the 70s defined the solvent accessible (SA) model as the union of spherical balls representing atoms. Soon thereafter, Richards and Greer introduced the molecular surface (MS) model as a `smooth' and possibly more realistic variant of the SA model.
This talk introduces the alpha complex as the dual of the Voronoi decomposition of an SA model. The complex is a combinatorial object that leads to fast and robust algorithms for visualizing and analyzing SA and MS models. As an example we will see that the alpha complex can be used to compute the volume and surface area of the SA and MS models without constructing them. The alpha complex offers a direct method to defining and computing cavities of molecules. The talk also introduces the skin model for molecules. It exhibits an inside-outside symmetry which makes it possible to mathematically talk about perfectly complementary molecules. These are interesting in the context of the molecular docking problem.
Suppose we are simulating a collection of continuously moving bodies, rigid or deformable, whose instantaneous motion follows known laws. As the simulation proceeds, we are interested in maintaining certain quantities of interest (for example, the separation of the closest pair of objects), or detecting certain discrete events (for example, collisions -- which may alter the motion laws of the objects). In this talk we will present a general framework for addressing such problems and tools for designing and analyzing relevant algorithms, which we call kinetic data structures. The resulting techniques satisfy three desirable properties: (1) they exploit the continuity of the motion of the objects to gain efficiency, (2) the number of events processed by the algorithms is close to the minimum necessary in the worst case, and (3) any object may change its `flight plan' at any moment with a low cost update to the simulation data structures.
This talk provides a survey of some recent applications of geometric mechanics and nonlinear control theory to problems in robotic locomotion and related areas. A common feature of locomotion systems is the role of constraints (and/or conservation laws) on the behavior of the system. By studying the geometric nature of mechanical systems in a general setting, it is possible to synthesize gaits for snake-like robots, generate parking and docking maneuvers for automated vehicles, generate swimming motions for underwater robots in inviscid, incompressible flow, and perform real-time trajectory generation for high performance aircraft. We also point out certain situations in which trajectory generation is particularly easy, allowing a dynamic motion planning problem to be reduced to a purely algebraic one. Simulations and videotape of experiments performed at Caltech will be used to illustrate the main ideas.
The purpose of Computer-Assisted Surgery (CAS) is to help physicians or surgeons to plan and to execute optimal strategies from multi-modal data. The execution of such planned strategies may be assisted by guiding systems. Passive systems based on 6D localizers give information to the operator such that he can compare the planned task to the real one he executes. Active systems are robots that realize part of the intervention autonomously. Semi-active systems, more generally called synergistic systems, are based on the cooperation of a robotic device with a human operator. We have developped such a synergistic device : PADyC (Passive Arm with Dynamic Constraints). The basic principle of PADyC is to have a manually actuated arm that constrains the authorized motions of the surgical tool held by the human operator in function of a planned task. For instance, if the task is to stay inside a given 3D cartesian region, the motions of the tool will be free inside the region whilst some of them will be forbidden on the borders of this region. These constraints are realized by a patented mechanical system.
The constraints are computed in the joint space from a cartesian description of the task. The algorithmic problems raised by such a device are very close to those of robot path planning. Since the environment of the robot is not completely structured, off-line computation is difficult and the algorithmic complexity of the algorithms has to be kept reasonably low. We have developped an approach for a 3 degrees of freedom prototype taking care of being able to generalize our algorithms to 6D.
In this paper, we will briefly describe state of the art surgical robotics, present the principle of PADyC and we will focus on the algorithms allowing to map the surgical task in the joint space of the robot.
[Joint paper with Yves Delnondedieu]
Representing curved shape is a fundamental problem in a variety of computational domains. Traditional methods have described curved shapes as the solution to a system of polynomial equations. More advanced techniques allow this description to be piecewise in nature.
In this talk, we described a relatively new technique for modeling curved shape: subdivision. Using subdivision, a curved shape is expressed as the limit of an infinite sequence of polygonal shapes (or polyhedral shapes). Successive polygons are related by relatively simple transformation rules. We conclude by discussing some of the properties of this representation and various algorithms for manipulating shapes defined through subdivision.