Fourth International Workshop on
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.
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.
ABSTRACT: Many tasks in robotics and automation require a cyclic exchange of energy between a machine and its environment. Since most environments are "under actuated" -- that is, there are more objects to be manipulated than actuated degrees of freedom with which to manipulate them -- the exchange must be punctuated by intermittent repeated contacts. Since centralized control schemes are expensive (and possibly prohibitively so), there is considerable interest in developing cyclic behaviors that are as decoupled as possible, promoting decentralized regulation. Since good regulation mechanisms are hard to find, there is considerable interest in developing techniques for composing existing behaviors to get new ones. In this talk, I will report on our work in progress concerning the synthesis and regulation of cyclic behaviors for intermittent environments with the goal of decentralized implementation and principled composition. We are particularly interested in applications to legged locomotion at present, and I will describe the manner in which some of our previous juggling work has been generalized and formalized to the new setting. We believe that similar syntheses may afford more robust reactive automation systems, and I will speculate briefly on that connection as well.