WIXLIB

Robot Puppets5waving, reaching) that can be combined together in phrases. How one combinesand orders these motions determines the stability and smoothness of transitionsbetween motions.This paper is organized as follows: Section 2 introduces marionette puppetryand articulates the distinct technical challenges of generating recognizable andartistic motions using marionettes. Section 3 describes typical analytical approaches in dynamic simulation and optimal control and the specific softwarerequirements these approaches create. Section 4 discusses which special considerations should be taken into account when working in discrete time. Section 5illustrates our software approach and briefly discusses examples of systems thatthe software automatically optimizes successfully. Section 6 discusses the relevant features of the current framework and the broader impacts for automatedpuppetry and the engineering of autonomous theater.2Puppets: Aesthetic and Mechanical ConsiderationsFrom antiquity to the present, artists and engineers have sought to create mechanical figures that generate expressive and lifelike behaviors [18, 13]. Puppetsare part of this lineage, and are representatives par excellence of humanity’s insatiable thirst for bringing ordinary object to life through motion. As art andtechnology scholar Chris Salter has observed, the histories of performing machines and robotic art have often involved a continual mingling between mimeticaspects (that is, objects that are imitative of lifelike behavior in appearance) andmachinic aspects (electromechanical behavior that, though animate, is not anthropomorphic) rather than a disambiguation [19]. That is, human artists areinterested in designing machines that emulate aspects of human creativity. Before the advent of computing and electronics, the approach was to design objectsthat appeared lifelike and imitated human actions, such as the 18th century humanoid automata built by Jacques de Vaucanson and Henri-Louis and PierreJaquet-Droz [20]. Puppets are the progenitors to these and other attempts tocreate mechanical life, and are part of a lineage that extends to present-dayanimatronics.Puppets can take the shape of realistic or abstract figures, and are designedfor use in theatrical settings. A puppet is generally defined as a material object that makes temporal use of sources of power that exist outside of itself,and that are not its own attributes [13, 21]. Animatronics are puppets that areelectronically controlled through various actuators (electrical, hydraulic, pneumatic), however the absence of a human performer and repetitive or open-loopperformance means that they are not typically regarded in the same way thathuman-powered puppets are. Setting aside for a moment the question of humanagency, we recognize that the main purpose of a puppet is movement: to establish a meaningful presence the puppet relies on motions to create a character orpresence that is both recognizable to the spectator and conveys a certain artistictruth. The puppet’s power of expression is therefore not determined by how wellit precisely mimics human behavior, but rather by its ability to abstract human

6E. Jochum et al.motions and offer an artistic projection of those motions and behaviors. In otherwords, the goal of puppetry motion is not to copy but to create. As Kingston etal. have also observed, a puppets primary purpose is to communicate throughmotion [6].Puppeteers are extremely inventive, and have developed numerous methodsfor controlling (often called “manipulating”) and constructing expressive, movingobjects. String marionettes are dynamically unique among puppets, and morethan other types of puppets have the potential to teach us about optimal control.Unlike glove puppets or rod puppets which are controlled through direct, corporeal contact (hands-on, hands-in), string marionettes are operated from above bya varying number of strings. For humanoid puppets, these strings are usually attached to the puppet’s head, torso, shoulders, arms, and legs, and can be strungto generate specific actions based on the specifications of the choreography. Thestrings can be manipulated with a variety of controls—the most common is themulti-stringed wooden control or “airplane” (crossbar) mechanism. This technique is used in Asian and European puppetry forms, and puppeteers can optto vary the string lengths and attachment points according to the needs of eachproduction or scene. The precision of the puppet’s motions is relative to thecontrol of the figures—the longer the strings, the weaker the impetus, which results in softer, less precise movements [13]. Puppeteers can control marionettesat ground level working alongside the puppet and in full view of the audience,or from a position high above the stage from a bridge and out of the audience’s sight lines. In either arrangement, the puppeteer must learn to balancethe dynamics of the puppet against the need to execute expressive choreographythat convincingly imitates—but does not replicate—human motions. Becausestring marionettes resist the puppeteer’s attempts to direct them, puppeteershave developed highly-evolved strategies for generating sequences of complexmotions—this is what is known as marionette choreography. Because of theirdynamics, string marionettes are arguably the most difficult type of puppet tooperate. This also makes them a good testbed for a control-based analysis.3Typical ApproachIn this section we discuss typical analytical approaches to optimal control andthe types of software infrastructure these approaches assume. We start with adiscussion of how one might describe the dynamics of a mechanical system andthen discuss computing optimal controllers for that system.3.1DynamicsMarionettes are subject to the physics of the world: they swing and sway according to the forces of gravity and the interplay between the different bodies—individual units such as the torso, forearms, and legs —in the marionette. Thisinterplay between the bodies falls within the realm of dynamics and simulation,where the dynamic description comes from a physics-based understanding of

Robot Puppets7puppet motion. When computing dynamics we are typically trying to computeequations of the formẋ f (x, u)(1)where x (q, q̇) and q Q describes the configuration of the system. For rigidbody systems, it has historically been convenient to write down the rigid bodysystem in Newton-Euler coordinates (i.e., Q SE(3)n , where n is the numberof rigid bodies in the system. This yields a state space of dimension 12n thatis subject to constraints. For a typical humanoid marionette, for instance, themarionette alone (no actuators) has 10 rigid bodies, so the state space wouldbe more than 120 dimensions. If one includes string actuation in the degreecount, that adds one degree of freedom for each string’s length and an additionalelement of SE(3) for each string endpoint (treating the inputs as “kinematicinputs” [22]). For a typical marionette with 6 strings of variable lengths, thisbrings the total nominal dimension of the state space up to 12 · 10 2 · 6 12 ·6 204. Naturally, we don’t want to be solving for feedback controllers in a204 dimensional space if it can be avoided. To avoid such high dimensions, we(a)(b)Fig. 2: Simulation of complex rigid bodies can take advantage of the mechanicaltopology of the system. For instance, a marionette is being simulated in (a) usinga tree structure representation of the humanoid form in (b) and representing theconstraints by cycles in the graph (see [23]).don’t want to represent Eq. (1) as Newton-Euler equations and instead insist onworking in generalized coordinates. In the case of the marionette, this reduces thedimension of the state to 2m, where m is the number of generalized coordinates.This yields 22 configuration variables for the marionette itself and another 18degrees of freedom for the string actuators (6 strings with endpoints moving inR2 R), yielding 80 states. By utilizing a kinematic reduction [24, 25] we canreduce the state of the actuators down to 18 because they are fully actuated.

8E. Jochum et al.This gives us equations of motion of the following form:ẋa uẋp f (xp , xa )(2)where xa is the kinematic configuration of the actuators and xp (qp , q̇p ) isthe dynamic configuration and velocity of the marionette itself. (For details onthis, see [22].) This leaves us with a much smaller, more manageable system towork with that only has a total of 62 dimensions in its state space. Crucially, thestrings are modeled as holonomic constraints, relating the lengths of the stringsto the dynamic configurations, of the formh(xa , qp ) 0(3)which must be maintained during simulation and control. Assuming for the moment that Eqs (2) and (3) can be stably simulated in an efficient manner, howdo we then construct the differential equation and constraints in a systematicmanner? The standard way to do this is based on Featherstone’s early work[12] on articulated body dynamics. This work was largely used in the contextof animation and digital puppetry, where the requirements are substantially different than embedded control. For example, animation requires a simulation to“look right” only once, while controlled physical systems must be repeatable.Recursive approaches to calculating dynamics [26, 12] take advantage of specialrepresentations of mechanical systems that allow the values needed for simulation to be calculated quickly and avoid redundant calculations. The work in thispaper is based on the methods presented in [23] (based on [12]). Here, systemsare represented as graphs where each node is a coordinate frame in the mechanical system and the nodes are connected by simple rigid body transformations(typically translations along and rotations about the X, Y , and Z axes, thoughany rigid body screw motion can be used). Transformations are either constantor parameterized by real-valued variables. The set of all variables establishes thegeneralized coordinates for the system. Figure 2 is an example of a simulatedmarionette. The graph description can include closed kinematic chains, but inpractice the graph is converted to an acyclic directed graph (i.e. a tree) and augmented with holonomic constraints to close the kinematic chains. This approachleads to fast calculations of f (·, ·) in Eq. (2) and h(·) in Eq. (3). Moreover, onecan use the same structure to efficiently calculate the linearization [27], which iscritical to nonlinear optimal control calculations, discussed in the next section.3.2Nonlinear Optimal ControlControlling marionettes involves choosing how the strings must be operated inorder to achieve some desired trajectory. For instance, if we wish a marionetteto generate a walking motion, the strings must pull the limbs in such a waythat the body of the marionette indicates walking. The choice of string motionswill, of course, depend on the physics-based description of the marionettes. For

Robot Puppets9instance, if the masses of the legs are very high, we might have to pull on thestrings differently than if the masses were very low. Optimal control plays asignificant role in determining the outcome because it provides an algorithmicmeans of choosing string lengths and endpoint positions in a manner that takesthe physics-based description of the marionettes into account. Optimal controltypically starts out with a cost function of some sort, often of the formZtfJ L(x(t), xref (t), u(t))dt m(x(tf ), xref (tf ))(4)t0where L(·) represents a weighted estimate of the error between the state and thereference state (which is potentially not a feasible trajectory for the system) suchas in the imitation problem mentioned above. We can minimize this cost functionsubject to the dynamics in Eqs. (2) and (3) by using iterative descent methods.In particular, one uses the equivalence between the constrained minimizationand the unconstrained minimization of the objective function composed with adifferentiable projection P(·) onto the constrained subspace. That is, the twominimizationsmin g(v) min g(P(v))v W Vv V(where V is the vector space and W is the differentiable submanifold of admissible vectors) are equivalent [28]. The projection operator P(·) comes fromcomputing a feedback law (discussed in more detail in the next section). In particular, if one interprets the “gradient” descent algorithm as starting at somenominal trajectory ξ (x(t), u(t)) and solving for a descent direction ζ (z, v)that optimizes the local quadratic modelζ arg min Dg(ξ) · DP(ξ) · ζ kζk2 ,ζthen one must only solve a standard time-varying LQR problem. This meansthat one must be able to compute the time-varying linearizationż A(t)z B(t)v(5) fwhere A(t) fdx (x(t), u(t)) D1 f (x(t), u(t)) and B(t) du (x(t), u(t)) D2 f (x(t), u(t)). One has to be able to do so for arbitrary trajectories in thestate space, potentially including infeasible trajectories (in the case of linearizingabout the desired trajectory). Solving for the descent direction involves computing the Riccati equationsṖ A(t)T P P A(t) Q P B(t)R 1 B(t)T P 0.(6)If we additionally want to guarantee quadratic convergence, then we can find adescent direction by solving a different LQR problemζ arg min Dg(ξ) · DP(ξ) · ζ kζk2D2 Jζ

10E. Jochum et al.whereD2 J(ξ) · (ζ 1 , ζ 2 ) D2 g(ξ) · (DP(ξ) · ζ 1 , DP(ξ) · ζ 2 ) Dg(ξ) · D2 P(ξ) · (ζ 1 , ζ 2 ).The second derivative D2 P(·) requires that we be able to also calculate22(7) 2fdx2 , fand dxdu. The details of this approach can be found in [28] and elsewhere,but for our purposes we should be able to compute Eqs. (2), (3), (4), (5), (6),and (7) in software. The difficulty of this approach is that we are representingthe optimal control problem in continuous time while the actual computationsare in discrete time. We will discuss this further in Section 4 and we see that itis only when we perform optimal control calculations in discrete time that wearrive at convergence of the algorithms that provide motion imitation. fdu2 ,3.3Choreography and Hybrid Optimal ControlIn [29–31] we developed an optimal control interpretation of puppet choreography. In particular, we formalized choreography as a sequence of modes that canbe pieced together to form a script of motions. Each mode has its own dynamics,creating a system with dynamicst (τi , τi 1 )ẋ f(x(t), u(t)) fi (x(t), u(t))where each i corresponds to a different mode of the system. To optimize such asystem, one needs to be able to minimize an objective function J with respect tothe switching times τi of the system. For a gradient descent algorithm, one must J—the derivative of the cost function withbe able to compute the derivative τirespect to the switching times—which depends on the switching time adjointequation L 0(8)ρ̇ A(t)T ρ xalong with a boundary condition at ρ(tf ) (see [32–35]). This adjoint equationonly needs to be computed once to compute all the derivatives of J. If one wantsto compute the second derivative of J, e.g. to utilize Newton’s method, then thesecond-order switching time adjoint equationṖ A(t)T P P A(t) 2L X 2f k ρk 0 x2 x2(9)kalong with its boundary condition P (tf ) must be solved [33]. This adjoint equation, along with a solution to Eq. (8), needs to be computed only once to obtain all the derivatives of J. Note that the second-order switching time adjointequation is the same as the Riccati equation in Eq. (6) except that the Riccatiequation has a different final term. Indeed, both Eq. (8) and Eq. (9) only requirefirst and second derivatives of fi with respect to the state, so those are all thatare needed for software; hence, the choreographic optimization requires the samesoftware capabilities as the smooth optimization described in Section 3.2.

Robot Puppets411Discrete time with scalabilityAs previously mentioned, the continuous representation of dynamics found inEq. (1) is not what we actually use to do computations. Moreover, when thereare constraints, such as those seen in Eqs. (2) and (3), standard methods suchas Runge-Kutta methods fail to preserve the constraints. Typically one woulduse solvers designed for Differential Algebraic Equations (DAEs) that projectthe numerical prediction onto the set of constrained solutions defined by theconstraint in Eq. (3). We have found, however, that for high-index DAEs suchas the marionette a tremendous amount of “artificial stabilization” is requiredto make the simulation of the DAE stable. This artificial stabilization—whichtypically takes the constraint h(q) as a reference and introduces a feedback lawthat “stabilizes” the constraint—changes the dynamics of the system, and if thefeedback gain is high, this often creates a multi-scale simulation problem thatis incompatible with real-time operation. As an alternative, we consider variational integrators [36–42]. Variational integration methods use the stationaryaction principle as a foundation for numerical integration that does not involvedifferential equations. This approach has several advantages such as guaranteesabout conservation of momenta, the Hamiltonian, and the constraints, as wellas guaranteed convergence to the correct trajectory as the time step convergesto zero. More importantly, variational integration techniques exactly simulate amodified Lagrangian system where the modified Lagrangian is a perturbation ofthe original Lagrangian. The Discrete Euler-Lagrange (DEL) equations areD1 Ld (qk , qk 1 , k) D2 Ld (qk 1 , qk , k) Fkh(qk 1 ) 0(10)(11)where Ld is a discretized form of the Lagrangian and Fk is an external forceintegrated over the k time step. This forms a root solving problem in which,given qk 1 and qk , one solves for qk 1 . Alternatively, one can utilize the discreteLegendre transform to define the discrete generalized momentum pk , and thenconvert the root solving problem of Eq. 11 into a one-step rootsolving problemwhere given the pair (qk , pk ) one implicitly solves for the next timestep pair(qk 1 , pk 1 ). Repeating this rootsolving procedure forms the basis of simulation.Using this method, we can (using a recursive tree description similar to the onedescribed in Section 3.1), simulate the marionette in real-time using time stepsof 0.01 s without adding any sort of numerical heuristics, such as artificial stabilization. Let’s say we start from the DEL equations and assume, by applicationof the implicit function theorem, that the solution exists and is locally unique[43]. Once we have made a choice of state (we choose xk (qk , pk )), we have anupdate equation of the formxk 1 fk (xk , uk )just as we would if we had started from a differential equation. That is, thegeneral form of the discrete time equation we wish to optimize is in principle nodifferent in the variational integrator case than it is in the standard ODE case.

12E. Jochum et al.Fig. 3: Software using variational integrators as the basis for simulation can accurately predict marionette motion using comparatively large time steps. In thiscase, the time step is dt 0.01s

Scripts of puppet plays describe the action using four parameters: temporal duration, agent, space, and motion (i.e., when, who, where, and what). These motions are grouped and executed a