WAFR 2000 Fourth International Workshop on Algorithmic Foundations of Robotics March 16-18 Dartmouth College Hanover, NH

TALKS BY INVITED SPEAKERS

ABSTRACT: Self-Assembly is the spontaneous aggregation of apparently simple objects to make complex structures. Self-assembling structures have long fascinated natural scientists, since they give the appearance of generating order from disorder. The very thin films of molecules that enclose soap bubbles, the crystalline arrays of bubbles ("bubble rafts") that may float on the surface of a liquid, the arrays of silica microspheres that make up the mineral opal: each is an example of a self-assembling structure.
Self-assembly of molecules is important in living systems. Almost every component of a cell--from its membrane to the clusters of proteins that replicate DNA, express genes, and synthesize proteins­is influenced by self-assembly. Understanding the complex phenomena that underlie self-assembly is one of the interesting challenges at the border between chemistry, physics, pharmacology and molecular biology. The best understood of self-assembling systems are those that involve molecules. There has been relatively little research in self-assembly of larger objects (objects visible with the unaided eye--from 1 mm to 100 µm--and smaller). The work described in this talk is an exploration of this new world of self-assembling medium-sized ("meso-scale") particles. It has developed one representative self-assembling system--that of small plastic plates floating at the interface between two liquids--into one that shows many of the rules that will operate in most self-assembling meso-scale systems. The most plausible application of the work is on areas such as microassembly. Many man-made devices are becoming "micro": the computer industry was, of course, the first to lead into the micro world, but now machines, analytical systems, motors, displays, and chemical reactors are all shrinking for one or another reason or application. Taking small parts and assembling them remains a very substantial challenge: self-assembly is one approach. (We could never assemble a living cell by external manipulation; the cell must assemble itself. Why not consider the same approach for man-made systems?) The fundamental scientific aspect of the work in this research is to lay out the ground rules for the assembly of small objects, not molecules. The work also has an aesthetic component: some of the patterns that are formed on assembly are regular and remarkably attractive visually. Making patterns that please the eye is a part of science, and also a stimulus to design.

ABSTRACT: Implementing geometric algorithms out of their abstract descriptions is a difficult task. This transformation is made particularly hard by two types of premises of most theoretical geometric algorithms: the choice of complexity measures and (more crucially) the handling of robustness issues. The talk will start with illustrations of the dichotomy between the theory and practice of geometric algorithms, together with a survey of solutions to robustness problems. The second part of the talk will briefly review the CGAL project and library. The CGAL project is a joint effort by a number of research groups in Europe to produce a robust software library of geometric algorithms and data structures. The library is now available for use with significant functionality. I'll describe the central goals and results of the project. The third part will be devoted to arrangements and motion planning. I'll concentrate on the maps and arrangements part of the CGAL library. Then I'll describe two packages developed on top of CGAL for constructing robust geometric primitives for motion algorithms.

ABSTRACT: A probabilistic-roadmap (PRM) planner is presented to solve motion planning problems where a robot must avoid collision with moving obstacles under kinematic and dynamic constraints. The planner samples the state$\times$time space of the robot by picking piecewise constant control inputs and integrating the corresponding robot motions. The result is a collection of samples called milestones connected by short feasible trajectories. The underlying principle is the same as for previous PRM planners solving purely geometric path planning problems: under reasonable assumptions, a rather small number of milestones ``see'' a large fraction of the state$\times$time space and are sufficient to capture this space's connectivity with high probability. The planner does not precompute the roadmap, as it would require knowing the obstacle trajectories well in advance. Instead, for each planning query, it tries to generate a small roadmap that connects the input initial and goal states without collision. A major difference with previous PRM planners is that the roadmap is a directed graph oriented along the time axis of the state space. Interestingly, the formal guarantees of performance of PRM planners, established for geometric path planning, can be adapted to this new planner. The planner was successfully tested both in simulated environments and with a real robot. In the later case, the obstacle motions were determined by a vision module just before planning; the planner was then allocated a small amount of time to return a trajectory. If the vision module detected a change in the obstacle trajectories, the planner computed a new robot trajectory on the fly.

ABSTRACT: Recent approaches to motion planning compute roadmaps in the configuration space of a given mechanical system. A roadmap is a graph allowing to apply a retraction method to find collision-free paths. This talk will focus on visibility roadmaps. Visibility roadmaps are bipartite graphs: the guard nodes tend to cover the free-space while the connection nodes tend to capture its connectivity. Both covering and connectivity depend on the local method used to account the kinematic constraints of the system. The interest of such roadmaps is discussed. They allow to introduce intrinsic parameters controlling their computation by probabilistic algorithms. Moreover they allow to focus the configuration space search onto narrow regions.

ABSTRACT: Minimally invasive procedures are revolutionizing current surgical practice. To be effective, however, a surgeon needs the ability to visualize the surgical field as if it were completely open, and to visualize the interaction of his instruments with tissue, even if she is operating through narrow openings. This in turn requires methods for contructing geometrical models of patient anatomy from medical scans, for registering those models with the actual surgical field, for adapting those models to reflect tissue changes during the procedure, for tracking instruments within the field, and ultimately for guiding and assisting the surgeon through computer vision and robotic aids. The talk will discuss ongoing projects in these areas, with focus on systems that are already being used in surgical cases.