Transcription of Model Predictive Control - Stanford University
1 Model Predictive Control linear convex optimal Control finite horizon approximation Model Predictive Control fast MPC implementations supply chain managementProf. S. Boyd, EE364b, Stanford UniversityLinear time-invariant convex optimal controlminimizeJ= t=0 (x(t), u(t))subject tou(t) U, x(t) X, t= 0,1, ..x(t+ 1) =Ax(t) +Bu(t), t= 0,1, ..x(0) =z. variables: state and input trajectoriesx(0), x(1), .. Rn,u(0), u(1), .. Rm problem data: dynamics and input matricesA Rn n,B Rn m convex stage cost function :Rn Rm R, (0,0) = 0 convex state and input constraint setsX,U, with0 X,0 U initial statez XProf. S. Boyd, EE364b, Stanford University1 Greedy Control useu(t) = argminw{ (x(t), w)|w U, Ax(t) +Bw X} minimizes current stage cost only, ignoring effect ofu(t)on future,except forx(t+ 1) X typically works very poorly; can lead toJ= (when optimalugivesfiniteJ)Prof. S. Boyd, EE364b, Stanford University2 Solution via dynamic programming (Bellman)value functionV(z)is optimal value of Control problem as afunction of initial statez can showVis convex Vsatisfies Bellman or dynamic programming equationV(z) = inf{ (z, w) +V(Az+Bw)|w U, Az+Bw X} optimalugiven byu (t) =argminw U, Ax(t)+Bw X( (x(t), w) +V(Ax(t) +Bw))Prof.
2 S. Boyd, EE364b, Stanford University3 intepretation: termV(Ax(t) +Bw)properly accounts for future costsdue to current actionw optimal input has state feedback form u (t) = (x(t))Prof. S. Boyd, EE364b, Stanford University4 Linear quadratic regulator special case of linear convex optimal Control with U=Rm,X=Rn (x(t), u(t)) =x(t)TQx(t) +u(t)TRu(t),Q 0,R 0 can be solved using DP value function is quadratic:V(z) =zTP z Pcan be found by solving an algebraic Riccati equation (ARE)P=Q+ATP A ATP B(R+BTP B) 1 BTP A optimal policy is linear state feedback:u (t) =Kx(t), withK= (R+BTP B) 1 BTP AProf. S. Boyd, EE364b, Stanford University5 Finite horizon approximation use finite horizonT, impose terminal constraintx(T) = 0:minimize T 1 =0 (x(t), u(t))subject tou(t) U, x(t) X = 0, .. , Tx(t+ 1) =Ax(t) +Bu(t), = 0, .. , T 1x(0) =z, x(T) = 0. apply the input sequenceu(0), .. , u(T 1),0,0, .. a finite dimensional convex problem gives suboptimal input for original optimal Control problemProf.
3 S. Boyd, EE364b, Stanford University6 Example system withn= 3states,m= 2inputs;A,Bchosen randomly quadratic stage cost: (v, w) =kvk2+kwk2 X={v|kvk 1},U={w|kwk } initial point:z= ( , , ) optimal cost isV(z) = S. Boyd, EE364b, Stanford University7 Cost versus (z)Tdashed line showsV(z); finite horizon approximation infeasible forT 9 Prof. S. Boyd, EE364b, Stanford University8 Trajectories01020304050 1 10x1(t)u(t)t01020304050 1 tProf. S. Boyd, EE364b, Stanford University9 Model Predictive Control (MPC) at each timetsolve the (planning) problemminimize t+T =t (x( ), u( ))subject tou( ) U, x( ) X, =t, .. , t+Tx( + 1) =Ax( ) +Bu( ), =t, .. , t+T 1x(t+T) = 0with variablesx(t+ 1), .. , x(t+T),u(t), .. , u(t+T 1)and datax(t),A,B, ,X,U call solution x(t+ 1), .. , x(t+T), u(t), .. , u(t+T 1) we interpret these asplan of actionfor nextTsteps we takeu(t) = u(t) this gives a complicated state feedback controlu(t) = mpc(x(t))Prof. S. Boyd, EE364b, Stanford University10 MPC performance versus : MPC, dashed: finite horizon approximation, dotted:V(z)Prof.
4 S. Boyd, EE364b, Stanford University11 MPC trajectories01020304050 1 ,T= 10x1(t)u1(t)t01020304050 1 tProf. S. Boyd, EE364b, Stanford University12 MPC goes by many other names, , dynamic matrix Control , recedinghorizon Control , dynamic linear programming, rolling horizonplanning widely used in (some) industries, typically for systems with slowdynamics (chemical process plants, supply chain) MPC typically works very well in practice, even with shortT under some conditions, can give performance guarantees for MPCProf. S. Boyd, EE364b, Stanford University13 Variations on MPC add final state cost V(x(t+T))instead of insisting onx(t+T) = 0 if V=V, MPC gives optimal input convert hard constraints to violation penalties avoids problem of planning problem infeasibility solve MPC problem everyKsteps,K >1 use current plan forKsteps; then re-planProf. S. Boyd, EE364b, Stanford University14 Explicit MPC MPC with quadratic,XandUpolyhedral can show mpcis piecewise affine mpc(z) =Kjz+gj, z RjR1.
5 ,RNis polyhedral partition ofX(solution ofanyQP is PWA in righthand sides of constraints) mpc( ,Kj,gj,Rj) can be computed explicitly, off-line on-line controller simply evaluates mpc(x(t))(effort is dominated by determining which regionx(t)lies in)Prof. S. Boyd, EE364b, Stanford University15 can work well for (very) smalln,m, andT number of regionsNgrows exponentially inn,m,T needs lots of storage evaluating mpccan be slow simplification methods can be used to reduce the number of regions,while still getting good controlProf. S. Boyd, EE364b, Stanford University16 MPC problem structure MPC problem is highly structured (seeConvex Optimization, ) Hessian is block diagonal equality constraint matrix is block banded use block elimination to compute Newton step Schur complement is block tridiagonal withn nblocks can solve in orderT(n+m)3flops using an interior point methodProf. S. Boyd, EE364b, Stanford University17 Fast MPC can obtain further speedup by solving planning problem approximately fix barrier parameter; use warm-start (sharply) limit the total number of Newton steps results for simple C implementationproblem sizeQP sizerun time (ms)n mTvars constrfast mpc SDPT34 2 3 30360 4 30570 8 301110 can run MPC atkilohertzratesProf.
6 S. Boyd, EE364b, Stanford University18 Supply chain management nnodes (warehouses/buffers) munidirectional links between nodes, external world xi(t)is amount of commodity at nodei, in periodt uj(t)is amount of commodity transported along linkj incoming and outgoing node incidence matrices:Ain(out)ij={1linkjenters (exits) nodei0otherwise dynamics:x(t+ 1) =x(t) +Ainu(t) Aoutu(t)Prof. S. Boyd, EE364b, Stanford University19 Constraints and objective buffer limits:0 xi(t) xmax(could allowxi(t)<0, to represent back-order) link capacities:0 ui(t) umax Aoutu(t) x(t)(can t ship out what s not on hand) shipping/transportation cost:S(u(t))(can also include sales revenue or manufacturing cost) warehousing/storage cost:W(x(t)) objective: t=0(S(u(t)) +W(x(t)))Prof. S. Boyd, EE364b, Stanford University20 Example n= 5nodes,m= 9links (links8,9are external links)x1x2x3x4x5u1u2u3u4u5u6u7u8u9 Prof. S. Boyd, EE364b, Stanford University21 Example xmax= 1,umax= storage cost:W(x(t)) = ni=0(xi(t) +xi(t)2) shipping cost:S(u(t)) =u1(t) + +u7(t) transportation cost (u8(t) +u9(t)) revenue initial stock:x(0) = (1,0,0,1,1) we run MPC withT= 5, final cost V(x(t+T)) = 10(1Tx(t+T)) optimal cost:V(z) = ; MPC S.}
7 Boyd, EE364b, Stanford University22 MPC and optimal (t),x3(t)u3(t),u4(t) :x3(t),u4(t); dashed:x1(t),u3(t)Prof. S. Boyd, EE364b, Stanford University23 Variations on optimal Control problem time varying costs, dynamics, constraints discounted cost convergence to nonzero desired state tracking time-varying desired trajectory coupled state and input constraints, ,(x(t), u(t)) P(as in supply chain management) slew rate constraints, ,ku(t+ 1) u(t)k umax stochastic Control : future costs, dynamics, disturbances not known(next lecture)Prof. S. Boyd, EE364b, Stanford University24
