1 Sparse signals for the control of human movements using the infinity norm Geoffrey George Gamble1, Mehrdad Yazdani2 1 Geoffrey George Gamble ∗, Department of Computer Science and Engineering, University of California at San Diego, La Jolla, California, United States of America 2 Mehrdad Yazdani, Qualcomm Institute, University of California at San Diego, La Jolla, California, United States of America 6 ∗ E-mail: [email protected] 1 0 2 n a J 7 ] Y S . s c [ 1 v 0 1 4 1 0 . 1 0 6 1 : v i X r a 2 1 Abstract Optimal control models have been successful tools in describing many aspects of human movements. Whilethesemodelshaveasoundtheoreticalfoundation,theinterpretationofsuchmodelswithregardto the neuronal implementation of the human motor system, or how robotic systems might be implemented to mimic human movement, is not clear. One of the most important aspects of optimal control policies is the notion of cost...This body of mathematics seeks to minimize some notion of cost, while meeting certain goals. We offer a mathematical method to transform the current methodologies found in the literature from their traditional form by changing the norm by which cost is assessed. In doing so we show how sparsity can be introduced into current optimal control approaches that use continuous control signals. We assess cost using the L norm. This influences the optimization process to produce ∞ optimal signals which can be represented by a small amount of Dirac delta functions, as opposed to the traditionalcontinuouscontrolsignals. Inrecentyearssparsityhasplayedanimportantroleintheoretical neuroscience for information processing (such as vision). Typically, sparsity is imposed by introducing a cardinality constraint or penalty (measured or approximated by the one-norm). In this work, however, to obtain sparse control signals, the L norm is used as a penalty on the control signal, which is then ∞ encoded with Dirac delta functions. We show that, for a basic physical system, a point mass can be moved between two points in a way that resembles human fast reaching movements. Despite the sparse natureofthecontrolsignal, themovementsthatresultarecontinuousandsmooth. Thesecontrolsignals are simpler than their non-sparse counterparts, yet yield comparable if not better results when applied towards modeling human fast reaching movements. In addition, such sparse control signals, consisting of Dirac delta functions have a neuronal interpretation as a sequence of spikes, giving this approach a biologicalinterpretation. Actualneuronalimplementationsareclearlymorecomplex,astheymayconsist oflargenumbersofneurons. However,thisworkshows,inprinciple,thatsparselyencodedcontrolsignals are a plausible implementation for the control of fast reaching movements. The presented method could easily be scaled up to arbitrarily large numbers of duplicates, thus representing larger numbers of spikes. We show how leading techniques for modeling human movements can easily be adjusted in order to introduce sparsity, and thus the biological interpretation and the simplified information content of the control signal. 2 Introduction Optimal control theory has provided a great deal of insight with regard to developing mathematical models that describe human movements (for example, [1–5]). These works, amongst many others, have shown that humans move with strategies that can be described/driven by various control signals1 and related cost functions to model movement. However, as [6] points out, while the development of optimal control models has given mathematical insights into the properties of human movements, and perhaps the costs that forged our motor system via evolution, the connection to the neuronal implementation of the motor system is not clear. In contrast to these models, we show that a novel penalty on a control signal results in signals which can be represented more simply, and that have more plausible biological interpretations, while maintaining the ability to model human movements accurately. To demonstrate the utility of sparse optimal control signals for human movements, we will compare twoversionsofaclassofproblemscalled“minimumeffort”controlproblems,whichattempttominimize the “size” or “effort” of the control signal when modeling human movements, as explained in [7]. In the first, and more traditional version, the effort to be minimized is defined as the L norm of the 2 control signal over some time course within which a movement is completed. The goal is to minimize that signal. One of the first, and most famous of this family of models is the “minimum jerk” control policy,proposedoriginallybyFlashandHogan[1]. TheFlashandHogancontrolstrategymodelshuman 1Controlsignalsaretobedescribedinmoredepthlater,butfornowitisasignalthatcontrolselementsofasystem. 3 reaching movements, and uses jerk (the third derivative of position) as a control signal, and minimizes thatsignaltotheextentallowedbyawelldefinedreachingtask. Intuitively, mostaremorefamiliarwith thinking of acceleration as a control signal (e.g. pressing the accelerator in a car controls the speed). In the Flash and Hogan case, jerk is the derivative of acceleration, so it “controls” the acceleration in the same way acceleration “controls” velocity. Because jerk is the minimized control signal, we refer to jerk as the “effort term”. Because they attempt to minimize their control signal, this as a minimum effort problem, and is referred to as “minimum jerk”. WorksinceFlashandHoganhasconsidereddifferentcostfunctionsastheefforttermasdefinedabove, such as minimizing torque over the course of a movement [8], or minimizing torque change (derivative of torque) over the movement [2,9]. Other works have added more terms to the a cost function but have maintainedaneffortterm. Additionstotheefforttermincludeend-pointstability(howmuchadjustment is needed once the target area of a reaching movement is breached) or end-point accuracy (how close to thetargetwhenthereachingmovementends)[5]. Suchextensions,however,havenotleadtoanyinsights into the neuronal implementation of control signals in the CNS, nor do they simplify the nature of the control signal. WewillshowthatusingtheL norminsteadoftheL normformeasuringandpenalizingthe“effort” ∞ 2 ofthecontrolsignalresultsinsignalsthatcanbeencodedsparselyviaDiracdeltafunctions. Thereexists a family of models where this technique is applicable, specifically, because they all employ an “effort” term. Practically, the sparsification of signals generated by this family of optimal control models might be useful in a robotic system in order to achieve human like-movement. Due to the simplicity (sparsity) of the resulting signal, implementations of human-like robotic control may be easier to comprehend and construct. Models of reaching movements leading to this work were considered in [10–12]. These works referred totheirsignalsas“bang-bang”or“intermittent”(see[13,14]formoreonintermittentcontrol). However, the control signals were not sparse, rather, they were square wave continuous. Other types of motor control such as standing and keeping balance have been modeled via intermittent control, notably, two such models are compared in [15]. Here, we demonstrate a mathematical relationship that can convert non-sparsity to sparsity with regard to the control signal. This relationship is related to the metric used to measure the control signal (i.e. how is the effort measured?), but more importantly a sparse encoding of the signal via Dirac delta functions. We also show that sparse optimal control signals model real human arm movements with high accuracy, thus supporting sparse optimal control signals as a plausible controlstrategyusedbyahuman’sbiologicalsystem. Weemphasizethat,usingsparsesignalsinthecases shownherehasnodownsideintermsofmodelperformance,buthasthebenefitsofasimplerencodingof the control signal, a biological interpretation in terms of neural spike timing, and potentially, a simpler controlstrategywhichmaybeusefulinrobotics...Allofthesequalitiesareabsentfromnon-sparsesignals. 2.1 Optimal Control Overview Inthissectionwegiveanoverviewofoptimalcontroltheoryandhighlighttwooptimalcontrolproblems: theminimum-timeandtheminimum-effortcontrolproblems. Ouroverviewismeantasmeanstoestablish commonnotationandterminology. Foramoreindepthoverview,see[6,16]. Optimalcontroltheoryisan applicationofoptimizationtheorytothecontrolofadynamicsystem. Inoptimizationtheory,weseekto find an element in a domain that minimizes (or maximizes) a criterion (also referred to as an objective), whilesatisfyingaconstraintset. Whentheelementsintheintersectionofthedomainandconstraintsets arefunctions, thecriterionistypicallyreferredtoasanobjectivefunctionaloracostfunctional, whereas when the elements are points in a vector space, the criterion is referred to as an objective function or a cost function. In optimal control, we seek an optimal controller (typically a function of time if the system is continuous or a vector if the system is discrete) that has certain constraints (for example, the controller is limited by a specified amount of power or resources) that minimizes a criterion. 4 We describe dynamic systems as a set of first-order differential equations: x˙(t)=a(x(t),u(t),t). (1) x(t) is referred to as the “state” of the system, u(t) is the controller of the system, and a(·,·,t) is, in general, a non-linear time dependent function describing the dynamics of the state as determined by the state and controller at time t. We assume that the initial state x(t ) and initial time is known. Often 0 the dynamic system is assumed to be linear time-invariant (LTI) and can be expressed as x˙(t)=Ax(t)+Bu(t). (2) Given the dynamic system of equation 1 and an initial state x(t ), we seek a control signal u(t) 0 to transfer the system to a desired state in a finite time. In practice, the control signal u(t) is not unconstrained,butratherboundedbytheavailableresources(suchasfuel,energy,orsupply). Inoptimal control theory, we seek an optimal control signal u∗(t) that, in addition to transferring the system to a desired state, also minimizes a cost functional J(u(t)). The cost functional is application dependent and theoptimalsolutionu∗(t)dependsonwhatweconsidertobe“cost”. Forexample,inthecostfunctional we may penalize large control signals or penalize deviations from a desired trajectory. Subsequently we will discuss two important cost functionals. 2.1.1 Minimum-Time Control In the minimum-time control problem, the objective is to transfer a system to a final state with a constrained control signal as quickly as possibly. Thus, the cost functional penalizes the total time it takes to transfer the initial state to a final state and can be expressed as J(u(t))=t −t (3) f 0 where the initial state x(t ), initial time t , and final state x(t ) are known, while t is unknown, and 0 0 f f the system dynamics are described by equation 1. We furthermore constrain the control signals to be bounded |u(t)|≤B. (4) We now show the solution to the minimum-time control problem for an LTI system as described by equation 2. We consider A and B to be constant n×n and n×m matrices respectively. Thus the minimum-time control problem can be expressed as minimize T u(t),T subject to x˙ (t)=Ax (t)+Bu(t) n n (5) x (0)=x n i x (T)=x n f |u(t)|≤B where we have defined T ≡t −t and assumed t =0. This special case has been solved by Pontryagin f 0 0 and colleagues. Their conclusions lead to several important points upon which this work builds, as they guarantee a control signal which switches a finite number of times between two possible values. These points are summarized below (see [17] for more details). P.1 ForagivenLTIsystem,thereisone,andonlyoneoptimalsignaltodrivethesystemfromaninitial state to a desired state. 5 P.2 Becausethegoalofaminimum-timeproblemistomovethesystemtothedesiredstateintheleast amount of time, a control signal representing a dynamic variable (such as acceleration) is always at one of two extremes, +B or −B. These extremes are defined in the constraints of equation 5. Intuitively, if you want to get from point X to point Y as fast as possible, you would change from zero acceleration to maximum positive acceleration to speed up initially, and then to maximum decelerationtoslowdowntoreachpointY,andthentozeroaccelerationtomaintainyourstarting position. Thetwoextremevaluesaretheonlyvaluesthatyieldtoaminimumtime(optimal)result. P.3 The control signal will switch between these two extremes at most n+1 times, where n is the derivative of position we choose to be the control signal. For example, for velocity, acceleration, andjerk,nis1,2and3respectively,andthushasamaximumof2,3,and4(respectively)switches between the extremes of the control signal. This type of control signal is sometimes referred to as a “bang-bang” control signal since the signal switches between the lower bound and upper bound of the inequality constraint of equation 4 (see [16] formore). Itcanalsoberegardedasa“sparse”controlsignalsincethenumberofchangesinthesignal’s values is small. In other words, the changes in the control signal can be described by a bounded number ofswitchesbetweenthelowerandupperbound. TheseswitchescanbeencodedbyaseriesofDiracdelta functions, which resemble neural bursts or spikes. 2.1.2 Minimum-Effort Control In the minimum-effort control problem, the objective is to transfer a system from an initial state to a final state with a control signal that is as “small” as possible (hence, minimum “effort”). Typically, the “size” of a control signal is measured with a penalty function. In this work we consider the L norm p penalty function and can express the cost functional as (cid:18)(cid:90) (cid:19)1/p J(u(t))= u(t)pdt (6) which denotes the L norm (and is typically the L norm), and the system dynamics are described by p 2 equation1. Wecanalsohaveadditionalconstraintsintheminimum-effortcontrolproblem,andjustasin the minimum-time control problem, there can be many variations by introducing additional constraints or additional costs to the objective. For example, a simple extension would be to consider a control problemwherethecostfunctionaltrades-offbetween“effort”andthetransfertimeandcanbeexpressed as a combination of equations 3 and 6 (cid:18)(cid:90) (cid:19)1/p J(u(t))=γ u(t)pdt +t −t (7) f 0 where γ ≥ 0 is a trade-off parameter between “effort” and the state transfer time and can be varied depending on the application. As an example of a minimum-effort problem, Flash and Hogan considered the following minimum- effort control problem which introduced constraints on initial and final state in order to describe human movements: (cid:18)(cid:90) (cid:19)1/2 minimize u(t)2dt u(t) subject to x˙(t)=Ax(t)+Bu(t) (8) x(0)=x i x(T)=x f 6 (cid:2) (cid:3)(cid:62) where x(t) = x(t) x˙(t) x¨(t) is the state vector, x and x are the initial and final boundary i f conditions, and T is the duration of the movement (with movement starting at time t = 0). Flash and ... Hogan used a jerk control signal (u(t)= x(t)), and furthermore used a third-order integrator model for the linear time-invariant dynamic equation parameters:     0 1 0 0 A=0 0 1 and B=0. (9) 0 0 0 1 This simple model yields trajectories that are remarkably similar to those of humans. Naturally, simple extensionsofthisoptimizationproblemcanyieldresultsthatareevenmorerealisticandmanyresearches have begun exploring these extensions. For example, [4] has noted that when humans make movements toatarget, thetargetthatisreachedisanotaspecificpoint, butratheradistributionofpoints. Hence, in their optimization procedure they relaxed the constraints of equation 8, which specify an exact final state. 2.2 Sparse optimal control policies for straight point-to-point trajectories In a previous work, we show how square wave control signals, with abrupt switches between two states (firstalludedtoinP.2,withanexamplegiveninfigure1(a)),caneffectivelymodelsmoothhumanreaching movements [11]. This work extends that notion by developing a method to represent neural signals via sparse usage of the Dirac delta function. These sparse signals can be thought of as encoding a series of positive (excitatory) or negative (inhibitory) neural spikes, or, more plausibly, groups of neurons spiking forbriefperiods. Insummary,wetakethesquarewavecontrolsignalsdescribedin[11],andencodethem as a sparse series of Dirac delta functions, each of which signifies one of the abrupt switching points for the control signal. We define a sparse optimal control policy as a control policy that meets optimality constraints with the lowest cost, as defined by the chosen cost function, that can be encoded by a finite number of discontinuous changes in the signal. An example of a signal that can be encoded as a sparse series is a rectangular pulse function, much like the control signals explored in [11], and shown in figure 1(a). Functions like these can be encoded by impulse functions (see Figure 1(b)). The control signals in the minimum-time control problem discussed on in section 2.1.1 is an example of sparse control signals that are optimal in terms of state transfer time. Henseforth, we will refer to the control signal (square wave) as “sparse”, as it is easily transformed into a sparse signal consisting of Dirac delta functions. Here we discuss sparse optimal control signals that solve the minimum-effort problem. The control signal is defined as the n-th order derivative in terms of position x(t), dn u (t)= x(t). (10) n dtn The minimum effort control problem that results in sparse control signals uses the L norm and is ∞ written as minimize sup |u(t)| un(t) 0≤t≤T subject to x˙ (t)=A x (t)+B u (t) n n n n n (11) x (0)=x n i x (T)=x n f (cid:104) (cid:105)T wherex (t)= x(t) dx(t) d2 x(t) ... dn−1 x(t) isthestatevector,x andx aretheinitialand n dt dt2 dtn−1 i f final boundary conditions, T is the duration of the movement (with movement starting at time t = 0), 7 Rectangular Pulse Sequence of Impulse Functions 1 1 0.8 u(t + 0.5) − u(t − 0.5)00..46 δδ(t+0.5) − (t − 0.5) 0.05 −0.5 0.2 0 −1 −2 −1.5 −1 −0.5 0 0.5 1 1.5 2 −2 −1.5 −1 −0.5 0 0.5 1 1.5 2 t t (a) An example of the types of sparsely driven (b) RateofchangeofsparsesignalshowninFig- signalsgeneratedbyminimizingthecontrolsignal ure 1(a). These sparse impulse functions can be asmeasuredbytheL∞ norm. thought of as driving (or encoding) the control signalinfigure1(a),alongwithinitialconditions, they are all that is needed to encode the control signalin1(a). Figure 1. Example of a control signal and its sparse spike encoding. and sup |.| is the L norm. Here we consider a system that is an n-th order integrator, thus 0≤t≤T ∞ (cid:20) (cid:21) (cid:20) (cid:21) 0 I 0 A = (n−1)×1 (n−1)×(n−1) and B = (n−1)×1 . (12) n 0 0 n 1 1×(n−1) ... The authors of [11] considered the special case u (t) = x(t), (n = 3), and showed that this particular 3 sparse control signal explains the trajectories of human movements better than the traditional Flash and Hogan model of equation 8. Perhaps more importantly, sparse control signals are biologically more realistic than non-sparse signals (See the Discussion section for more on this). As we will demonstrate, mostformulationsofminimumeffortproblemscanbeeasilyconvertedtogeneratesparsecontrolsignals, completewiththeaforementionedbenefits. Bysimplymeasuringtheefforttermintheobjectivefunction via the L norm (as opposed to the 2-norm), we can frame the control signal solution to these problems ∞ in terms of discontinuous switching states. Wenowshowthegeneralanalyticsolutionforequation11. Toderivethegeneralsolution,weassume that the boundary conditions are (cid:20) (cid:21) (cid:20) (cid:21) x x x = i and x = f . (13) i 0 f 0 (n−1)×1 (n−1)×1 That is, we assume that the movement starts at rest and ends at rest. We solve the general sparse minimum effort control problem by manipulating equation 11 to a form that has been previously solved. Namely, note that every optimization problem can be written equivalently as an optimization problem with a linear objective by introducing an auxiliary variable K and we can equivalently express equation 11 as follows: minimize K un(t),K subject to x˙ (t)=A x (t)+B u (t) n n n n n (14) x (0)=x n i x (T)=x n f |u (t)|≤K. n 8 where u (t), A , B , x , and x are defined as before in equations 10, 12, and 13 respectively, and we n n n i f have used the fact that ||u (t)|| ≤ K =⇒ |u (t)| ≤ K. The equivalency between equations 11 and n ∞ n 14 is due to the fact that every objective can be bounded, and this bound is expressed as an additional constraint in equation 14. The optimization problem of equation 14 has the same form as equation 5. We can therefore use the results from the minimum-time control problem and apply them here (namely that the results of Pon- tryagin and colleagues still hold). The difference is that in equation 5 the unknown is time T, whereas in equation 14 the unknown is the bound K on the control signal u (t). Since the dynamic system in n equation 14 is an n-th order integrator, we can use the result from [18] and write the following theorem: Number of Switches for an N-th Order Integrator. Theorem 1. For a control problem of the type in equations 5 or 14 where the system dynamic equations are an n-th order integrator (as in equation 12),thenthenumberofswitchingsinthecontrolsignalisexactlyn+1andthecontrolsignalissymmetric. Inotherwords,asinitiallydiscussedinP.3,astheorderofthecontrolsignalincreases(asnincreases), the number of switches in the control signal increases by the same amount. [19] solved the general n-th order minimum-time control problem of equation 5 for an n-th order integrator. We adapt their results for the general n-th order minimum-effort control problem of equation 14 and summarize the solution as follows: 22(n−1)(n−1)!(x −x ) K∗ = f i (15) n Tn (cid:18) (cid:19) πi t∗ =Tsin2 , i=0,...,n (16) i 2n where K∗ denotes the optimal amplitude or bound on the control signal, and t∗ denotes the optimal i switching times. Figure 2 shows examples of several sparse optimal control signals. 2.3 Sparse Optimal Control Signals in Fast Human Movements The sparse optimal control signals introduced in section 2.2 are not only optimal with respect to a minimum-effortobjective,butarealsomorebiologicallyplausiblewhencomparedwithnon-sparsesignals. Sparse optimal control signals can be are those that can be efficiently represented with Dirac delta functions, which resemble neuronal bursts or spikes. If we treat each spike as an idealized Dirac delta function, as done in [20], and as visualized in Figure 1(b), then a spike sequence that represents an n-th order optimal control signal can be expressed as n (cid:88) ρ (t)=K∗ (−1)iδ(t−t∗) (17) n n i i=0 where K∗ and t∗ can be found from equations 15 and 16 respectively. The spike train represented by n i equation 17 is not postulated to be from a single neuron, but rather a population of excitatory and inhibitory neurons forming a network. The work of [10,11] showed that a sparse optimal control signal that corresponds to jerk (expressed as ρ (t) in the notation of equation 17) can model fast human movements with greater accuracy than 3 the smooth control signal that results from using the L norm. We now also propose that the control 2 signals the nervous system uses are not limited to the jerk control signal. There is nothing preventing the nervous system from using a higher-order control signal (see Figure 4 for comparisons higher-order 9 u(t) u(t) 3 4 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 t t u(t) u(t) 5 6 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 t t Figure 2. Examples of sparse optimal control signals u (t) for i=3,...,6. Shown are movements that i start from t=0 and end at t=1. 10 derivative control signals). With each increase in the order of the control signal, the number of spikes increases and the timing of those spikes changes (as shown in Figure 2). Because each wave form is different, these high-order derivative control signals can form a basis set, the elements of which are combined to form a subspace of control signals. The neuroscience motor control literature commonly refers to the elements in such basis sets as “motor primitives”. These primitives are combined to control a variety of animal movements [21]. 2.4 Application of Sparsity to Extensions of Minimum Effort Control The minimum effort control problem proposed in section 2.1.2 can be extended in numerous ways, e.g. [1,2,5,10,11,22,23]. Theseworksandothers,accountforvariousaspectsofmovementanddrawdifferent conclusions regarding the nature of the motor system. For example, in [5], several types of reaching movements under various conditions are analyzed and modeled via an extension of the minimum effort problem. The types of movements included both two and three dimensional reaching, with and without target perturbation, with and without obstacle avoidance, and under various instructions to the subject regarding how the target should be impacted. The following is a simplified version of the model in [5] that maintains its core concepts: a term for effort and a term for final state error. Equations 18 and 19 give an example of how minimum effort control problems can easily be adapted to our method of generating sparse signals. (cid:90) T minimize ||x(T)−x ||2+w u(t)2dt f 2 effort u(t) 0 (18) subject to x˙(t)=Ax(t)+Bu(t) x(0)=x i Equation 18 is the same as the minimum effort control problem discussed earlier, with the exception that hard equality constraints (the end-point boundary conditions) are now “soft” constraints and are penalized as a cost. The w term dictates a trade off between minimizing effort and meeting the final effort boundary conditions. To have a sparse implementation of the above, we use the infinity-norm (sup) as before: minimize ||x(T)−x ||2+w sup |u(t)| f 2 effort u(t) 0≤t≤T (19) subject to x˙(t)=Ax(t)+Bu(t) x(0)=x i This optimization problem, similar to the sparse minimum effort problem above in equation 11 can be written as follows: minimize K u(t),K,K1,K2 subject to x˙(t)=Ax(t)+Bu(t) x(0)=x i K =K +K (20) 1 2 ||x(T)−x ||2 ≤K f 2 1 |u(t)|≤K2/weffort K ≥0,K ≥0 1 2 As before, we are using the property that every optimization function can be written equivalently as an optimization problem with a linear objective by introducing an auxiliary variable. Again, we have