Introduction

We are attacking the problem of implementing satisfying interaction with very high DOF systems of (partially) constrained geometric objects, with applications both in modular robot kinematics and constraint-based CAD systems. For algebraically underconstrained situations, we are considering control schemes based on information-theoretic principles determined experimentally from human subjects by perceptual psychologists [4]. To disambiguate any remaining (e.g. Bezout) finite solution choice we are investigating an integration of a Riemann surface-based complex tracing algorithm [5] with a geometric constraint solver.

Inverse Kinematics in Modular Robotics

Consider a simulation of a tower built with the reconfigurable modular robot MultiShady [1], as shown in the figure below (upper left). If we allow the joints of the modules to rotate, such a tower is a mechanism with many degrees of freedom (DOF). The figure shows one of the possible movements of the tower, a bending that aims the top of the tower towards a lower part of the tower.

Six stills from a simulation of bending a MultiShady a tower. This joint angles in this simulation were computed by hand.

Such a bending might be desirable, for example, to allow a camera that would be mounted to the top of the tower to examine the lower part of the tower.

The total number of rotational joints in this example is 150. Loops in the kinematic topology of the robot constrain 15 DOF. Still, the task of moving the top of the tower so that it is posed in (2D) space as the user desires requires only 3 DOF. Thus, the robot is free to move within a 132-dimensional subspace of its joint space while still achieving the requested task of placing the tower top. More intuitively, if we fix the tower top so that it's "looking at" the lower part of the tower as in the last figure above, then there are still many different ways to arrange the bending of intermediate parts of the tower which still maintain the topology of the robot.

A mechanism with such extra DOF relative to its task is called redundant, and much research has gone into how to best control such mechanisms [2]. The problem is not necessarily easy: the space of possible motions can be huge, its topology can be convoluted, and it's not always clear how to define "best". In the simulation pictured above, the joint angle trajectories were manually planned by a human. We would like to add inverse kinematics capability to the simulation software so that it can perform this type of job automatically, with the human operator only specifying the task (in this case, the pose of the tower top).

Least Surprising Behavior

We are developing methods to address this problem which directly aim to minimize the surprisal, to the user, of the system's behavior [3]. For (algebraically) underconstrained cases like that shown above, we intend to apply principles from Structural Information Theory (SIT), a branch of information theory which has been developed mainly by psychologists [4]; its definition of information is given in terms of human cognition. It states that the information content of an object increases as the object becomes, literally, more surprising to the average human observer.

Even in "fully constrained" mechanisms, i.e. where the available number of DOF matches the number required to perform the task, there still generally exist a finite (e.g. Bezout) number of possible solutions, and the software must pick one. To address this, we are exploring an adaptation of complex tracing [5] that cooperates with a geometric constraint solver. The solver produces functions (generally multi-valued) that give the state of dependent elements as a function of the interaction input (e.g. the mouse position). The complex tracing algorithm first assigns a connected two-manifold (the Riemann surface) as the domain of each such multi-valued function so that the function is single-valued over this domain. It then traces the input trajectory through this surface, thus selecting a single one of the multiple solutions for each value of the interaction input.

Generalizing to CAD

A sufficiently general solution for the above-described problem can be more widely applicable than just in inverse kinematics for modular robots. For example, consider a mechanical engineer tasked with designing a machine crank like that shown below (left) in a constraint-based CAD system. She may first draw some circles representing the shaft holes and constrain their centers to lie on the crank's symmetry axis (center). How should the system respond if she then rotates the line of this axis about the left circle's center point (right)?

A machine crank, the beginning of a design for the crank in a constraint-based CAD system, and a rotation of the symmetry axis of the crank.

It's not hard to see that this situation is similar to the above tower bending problem. Consider that the relative distance between the circles is not constrained. Indeed, the radii of the circles are not even fixed. So, again, we have a geometric system that is only partially constrained, the user has requested that it perform some "task", and we would like the software to show the geometry achieving that task in a way that maintains the constraints and that is minimally surprising to the user (for example, we probably do not want to see the radius of either circle changed!).

In fact, both problems are instances of a more generic one, which we call "interaction with constrained geometry".

Next Steps

We have already developed preliminary versions of a simple CAD system called DSketch and of a self-reconfigurable modular robot simulator called MultiShadySim, which we used to produce most of the figures herein. We are now beginning to develop algorithms, as described above, for a third software component, to be called the Interaction Kernel, which will allow us to implement interaction in DSketch and MultiShadySim in a least-surprising way.

References:

[1] Carrick Detweiler, Alex Hornstein, Keith Kotay, Peter Osagie, Daniela Rus, Paulina Varshavskaya, Iuliu Vasilescu, Marsette A. Vona, Justin Werfel, and Yeoreum Yoon. MultiShady: A Bipartite Heterogeneous Unit Modular Self-Reconfigurable Robot. In CSAIL Research Abstracts, 2005.

[2] Samuel R. Buss. Introduction to Inverse Kinematics with Jacobian Transpose, Pseudoinverse and Damped Least Squares Methods. Unpublished, available at http://www.math.ucsd.edu/~sbuss/ResearchWeb/ikmethods/iksurvey.pdf.

[3] Marsette A. Vona. Least Surprising Interaction with Constrained Geometry: Applications in CAD and Modular Robotics. Ph.D. thesis proposal, MIT department of Electrical Engineering and Computer Science. To be submitted in 2005.

[4] P. A. van der Helm. The resurrection of simplicity in vision. In M. A. Peterson, B. Gillam, & H. A. Sedgwick (Eds.), In the Mind's Eye: Julian Hochberg on the Perception of Pictures, Film, and the World. Oxford: Oxford University Press, 2004.

[5] Ulrich Kortenkamp. Foundations of Dynamic Geometry. Ph.D. thesis, Swiss Federal Institute of Technology, Zurich. 1999.