TIME-OPTIMAL BANG-BANG TRAJECTORIES USING BIFURCATION RESULT
CHANG EON SHIN
ABSTRACT. This paper is concerned with the control problem x(t)=F(x)+u(t)G(x) , t E [0,T], x(O) =0,
whereF and G are smooth vector fields onRn, and the admissible controlsu satisfy the constraintlu(t)1 ::;1. We provide the sufficient condition that the bang-bang trajectories having different switching orders intersect.
1. Introduction
Consider the control system
(1.1) x(t) =F(x)+u(t)G(x), t E [0,T]' x(O) =0,
where the vector fields F and G are smooth on Rn and admissible controls u are measurable functions taking values in [-1,1]. The aim of this paper is to investigate the optimality of bang-bang trajectories steering the above system from the origin to a given point in Rn in minimum time.
We now review the main definitions and notations which will be used in this paper. Ifu(t) = 1 almost everywhere(a.e.) on an interval I, then the corresponding trajectory is called an X -arc on I, while if u(t) = -1 a.e., the corresponding trajectory is called aY-arc on I, where X = F +G and Y = F - G. A trajectory is called bang-bang if it is a concatenation of X -arcs and Y -arcs. We say that a control and its corresponding trajectory are extremal if they satisfy Pontrya- gin's Maximum Principle, which provides a necessary condition for a
Received October 2, 1996.
1991 Mathematics Subject Classification: 49J30.
Key words and phrases: bang-bang, optimal trajectory, bifurcation.
This work was supported by BSRI-94-1412.
554 Chang Eon Shin
trajectory to be optimal. For a small time optimal control problem, several authors have investigated the optimality of bang-bang trajec- tories in JR3[2]'[7]'[1l] and inJR4[7] under the generic assumptions for the structures ofX, Y and Lie brackets ofX andY showing that they lose optimality at third switching points inJR3 and at fourth switching points inJR4. Ifwe can show that any two extremal bang-bang trajec- tories of (1.1) having different switching orders reach a point at a same total time and those points form a (n-1)-dimensional manifold, then they are not optimal from the point of intersection. [9] In this paper, we provide the sufficient condition for an existence of a surface consisting of those points. We call this surface by a cut-locus. We prove the main theorem by means of an application of general bifurcation theory from the simple eigenvalue.
We can develop the above program to the general bifurcation prob- lem derived from a differential equation. Let Xo,··· ,Xn be smooth vector fields inJRn. Denote lengths of time intervals by Si,ti and TO = 0, Ti =SI+ ...+Si, T =Tn . Consider the (n+l)-dimensional system
(1.2) where
cI?(S t), = (cI?0cI?1(S,t)(s,t)) =0 E JRn+l,
(1.3) cI?o(s, t) = [SI + ... +sn] - [to+ ... +tn - 1],
Here, e7Z(p) denotes the value at time T of the solution to the Cauchy problem
yet) = Z(y(t)), y(O) = p.
System (1.2) have trivial solution branch:
to =Sn =0, ti =Si, for i =1,··· ,n - 1.
If it occurs that there are solutions to (1.2) which branch off from the trivial solution, then by substituting X for XI,X3 ,· .• , and Y
for Xo, X2,··· , we can confirm optimality of bang-bang trajectories of (1.1) having n switchings.
We define the usual Lie bracket [F,G](x) of smooth vector fields F, G in a given local coordinate by
(DxG(x))F(x) - (DxF(x))G(x).
The main result of this paper is:
THEOREM 1. lVhen Sn =0,to =°andSi =ti fori = 1,'·· ,n - 1,
ifthere exists an adjoint vectorp(.) (refer to §2) such that at some point (SI,·'· ,Sn-l) = (SI,'·· ,Sn-l),
AI) the equations
i = 0,··· ,n - 2
determine the nonzero n-dimensional vectorp(T) uniquely up to a scalar multiplication and the vectorp(T) satisfies
p(T)[Xn(x(T)) - X n-l(x(T))] =°and
A2) p(T) [Xn-1,Xn](x(T)) =J0,
where x (t) is the solution of the Cauchy problem x(t) = Xi(t), on [Ti-l, Ti] (i =1,·" ,n), x(o) = 0,
then the point (S1,··· ,Sn-l) = (SI,·'· ,sn-d is the bifurca- tion point for <P.
2. Bifurcation result
Let A,U and W be Banach spaces. Consider the equation
(2.1) \f!(v,J.L) = 0,
where \f!: A x U -+W. We assume that \f! E C2(A x U, W) and that
(2.2) \f!(v,O) = ° \/v E A.
556 Chang Eon Shin
Ifthere is a sequence(vn ,Jln) E Ax U withJln =1=0 such that 'IT(vn ,Jln)
= 0 and (vn , Jln) -+ (v,O), then the point v is called the bifurcation point for 'IT. Clearly, ifv = v is a bifurcation point, by the implicit TImc- tion theorem, the partial derivative ~:(v,0) is not invertible, where aa'IT (v,0) = 'IT /-L(v,0) is the matrix of the first derivatives aa'ITi (v,0).
Jl ~
Let vbe a point in Aand we assume that
We set
a'IT
B = aJl (v,0), Aj = -a -aa a'IT(v,O), j =1,··· ,N,
Vj Jl
which are m X m matrices. Inaneighborhood of(v,O), we expand W in Taylor approximation, by writing
N
(2.3) 'IT (v, Jl) = 'IT(v,0)+BJl+L(Vj - Vj )AjJl+N(v, Jl),
j=l
where
N(v,0) ==0, and aN _aJl (v,O) = 0 since'IT(v,0) = 0 for any v E A.
THEOREM 2. Tbe point v isa bifurcation point for 'IT in (2.1) pro- vided tbat
B1) dim(ker B) =1, and
B2) for some.e, Range(B)EB [At· ker(B)] = W.
Proof. By assumption B1), there exists Jlo E U such that ker(B) is spanned by the element J.lo. By B1) and B2), the spacesU and W can be decomposed as
where Uo= ker(B) = span{Jlo}, W1 = Range(B), Wo = At· ker(B) and U1 is the topological complement ofUo in U. Notice that for any
J.l E U, there exist J.ll E U1 and r E JR. such that f-L rf-Lo + f-Ll.
Let's denote the projections from W onto Wo and WI, by 7ro and 7rI, respectively. It is obvious that equation (2.1) is equivalent to
(2.4)
and (2.5)
7ro(W(v,f-L)) = 0,
Rewriting (2.3) as w(v, f-L) = Bf-L+cjJ(v, f-L), equation (2.5) is equivalent to
(2.6) We set
'lj;(v, r, f-Ll) = Bf-Ll + 7rl(cjJ(v, rf-Lo + f-Ld)·
Differentiating'lj; with respect to f-Ll at (v, r, f-Ld =(iI,0,0), we get the map
'lj;J.tl(iI,0, 0) :w1---+Bw+ 7rl(cjJJ.t(iI,0))w.
It is clear that from (2.3), cjJJ.t(iI,0) is the zero map and 'lj;J.tl(iI,0, 0) = B.
Since the restriction of B to U1 is bijective onto W1 , by the implicit function theorem, equation (2.5) can be solved uniquely for f-Ll in a neighborhood U of (v, r) = (iI,0), Le.,
f-Ll = f-Li:(v, r).
By the uniqueness of f-Ll on U satisfying (2.5), f-Li(v,O) = 0 for any (v,O) EU. We can substitute f-Li(v, r) for f-Ll in (2.6) to get
(2.7)
Differentiating (2.7) with respect tor at (v, r) = (iI,0), we have
8* ( 8*)
B :;/(iI,0)r+7r1 cjJJ.t(iI,f-Li:(iI,O))[f-Lo+ :;/r] =0 for any r E JR..
558 Chang Bon Shin
(2.8)
Since J.Li(D,0) = 0 and4>f.L(D,0) is the zero map,
C)J.L* '
B C)/(D,O)r = 0for any r ER
C)J.L*
Hence, C)/(D, O)r E Uo nUI = {O} for any r E R In other words, C)J.L*
C)/(D,0) is the zero map from lR to UI .
Next, we consider equation (2.4) which is equivalent to
N
1ro[B(rJ.LO+J.Lt(v,r)]+ L(Vj - Dj)Aj(rJ-Lo+J-Lt(v,r))+
j=l
N(v,rJ.Lo+J.Lt(v,r))] = O.
Settingwo(v, r) = 1ro(w (v, J-L)) = 1ro(w(v, rJ.Lo+J-LiCv, r))), Wo E C2 and wo(v,O) = 0 sincew(v,0) = 0 for anyv. Hence, we can define the map G : Ax lR-+Wo by
{
r-Iwo(v, r) G(v, r) = C)wo
C)r (v,O) Then, G(v,r) E Cl and notice that
ifr =1= 0, ifr = O.
C)w0 ( C)w C)J.Li )
C)r (v,O) = 1ro C)J.L(v, O)[J.Lo+ C)r (v,0)]
and
c)G ( C) C)w )
C)ve (D,O) =1ro C)ve C)J.L(D,O)J.Lo
since C):;}(D,0) is the zero map. Assumption B2) implies that
!:l(D,O)c)G =1ro(AeJ-Lo) =1= O.
uve
By the implicit function theorem, the equation G(v, r) = 0 can be solved for Ve in a neighborhoodV of(DI,··· ,De-I,Df-+l,··· ,DN, 0),
Observe that v£ = V;(VI,··· ,V£-I,VHI,··· ,VN,O) and by shrinking V, we may assume that for (VI,··· ,V£-I, V£+l,···VN, r) EV,
(VI,··· ,V;,· .. ,vN,r) EU.
Taking into account that
1T"o('l1(V,p)) =0 if and only if G(v,r) =0, there exist nontrivial solutions of'l1(v,p) = 0,
V£ =v;(VI,··· ,V£-I,V£+ll··· ,vN,r),
where (VI,··· ,V£-I,V£+l,··· ,VN,r) E V, and for (VI,··· ,V£-I,V£+l,
... ,VN,r) E V,
(VI,··· ,V;,· .. ,VN,r) EU.
Therefore V =vis a bifurcation point. o
In (1.2), let Pn = Sn, Pn+l = to,Pi = Si - ti and Vi = Si + ti for i = 1,··· ,n - 1. The trivial branch of cl> in (1.2) is Pi = 0 for i = 1, ... ,n+1. By replacing variables Si, ti in (1.2) by Vi, Pi, we can regard cl> as a map from ]Rn-l x ]Rn+l to ]Rn+! with variables Vi and Pi. We can explicitly compute matrix B to get
B= (at
aILl
Define the intervals Ij by h-1, Tj], j = 1,··· ,n. The union of the time intervals Ij's is [0,T]. Call p(.) the adjoint vector satisfying the equation
p(t) = -p(t)DxXj(x(t)) on Ij ,
where x(t) is the trajectory in Theorem 1. Let M(t, s) be the funda- mental matrix solution of the variational equation
with M(t, t) being the identity matrix.
560
3. Proof of theorem 1
Chang Eon Shin
When J-Li =°for i =0,··· ,n+1, the matrix B is
( 1 1 -1)
M(T,TdX1(x(Td) Xn(X(T)) -M(T,O)Xo(O) .
We claim that the matrix B satisfies conditions Bl) and B2). Let J-L = (0,··· ,0). Observing that
by assumption (AI), we obtain that
for i = 0, ... ,n - 1.
SettingPo = -p(T)· M(T, TdX1(x(Tl)) and p = (po,p(T)), p. B = 0 and by the uniqueness ofp(T) , dim(ker B) = 1 and condition Bl) is satisfied.
Next, we claim that Range(B) EI3[An-I'ker(B)] = W Observe that vector L).x= (L).Xl,··· ,L).xn+l) E ker(B) if and only if
(3.1)
and
(3.2) - M(T, O)Xo(x(O))b.xn+l +M(T, Tr)X1(X(Tl))L).xl + ...
+M(T, Tn-l))Xn-l(X(Tn-:l))L).Xn-l +Xn(X(Tn))b.xn= O.
To compute- aa aa<P' extend the length of intervalIn - 1 by c so that Vn-l J.L
the terminal point becomesT +c instead ofT, and Ti are unchanged
for i =0, ... ,Tn-2. If~xE ker(B) , then by (3.2)
{) {)~l . d (
-£1-~~X= hm -d[M(T+c,T) -M(T,O)Xo(x(O))~Xn+l+
UVn-l up 10-+0 c
... +M(T,Tn-dXn-l(X(Tn-d)~xn-d
+ Xn(X(Tn+c))~xn]
=lim dd [Xn(X(Tn+e))
10-+0 c
- M(T+c,T)Xn(X(Tn))]~Xn
=[DxXn(x(T))Xn_1(x(T))
- DxXn-l(X(T))Xn(x(T))]~xn
=[Xn-l,Xn](x(T))~xn.
Since for any v ERange(B), p'v =0, if
{) {)~
p' -£1-!:1~X= peT) . [Xn- 1,Xn](x(T))~xn =1= 0,
ulIn-l up
then An-1 •~x ~ Range(B) and Range(B) E9 [An-I' ker B] =W. By assumption A2), we only have to show that ~xn =1= O. Write
Wi = M(T, Ti)Xi(X(Ti)), and
for i = 1, ... ,n.
By the definition of matrix M(t,s), we obtain
and therefore
If(~Xl,... ,~Xn+l)E ker(B), ~Xn+l =~Xl+ ... +~xn and the last
562
n components ofBb.x is
Chang Eon Shin
wnb.xn+wn-Ib.xn-I +wn- 2b.xn-2+ ... +wIb.XI - WO(b.xI + ... +b.xn )
= (wn - Wn-I)b.xn+Wn-I(b.xn+b.xn-d +wn- 2b.xn-2+ ... .
+wIb.XI - Wo(b.xI+ ... +b.xn)
=
= (wn - Wn-I)b.xn+(Wn-I - Wn-2)(~Xn+b.Xn-l)+ ...
+(W2 - WI)(b.x2 + ... +b.xn )+WI(b.XI + ... +b.xn)
- WO(b.xI + ... +b.xn )
n
= Laivi,
i=1
where ai = b.xi + ... +b.xn .
n
Thus L aivi = 0 if and only if (b.XI,·" ,b.xn , b.xn+d E ke;-(B).
i=1
By the uniqueness ofp(T) such thatp(T) .Vi = 0 for i = 1, ... ,n,
dim span{vI,'" ,vn } =n - 1.
Observing that an = 0 if and only if Vn tt span{VI, . .. ,Vn-d, if an =0,
dim span{VI, ... ,Vn-I}= n - 2 and the equations
do not determinep(T) uniquely up to a scalar multiplication.
By assumption Ai), b.xn =an =1= O. Hence1/ =i/ is the bifurcation point for system (1.2).
4. Example.
Let F, Gbe smooth vector fields on a four-dimensional manifoldM with F(po) = 0. Consider the control system
(4.1) x(t) = F(x(t))+uG(x(t)), x(O) =Po,
where the controlu is a measurable function taking values in [-1,1].
It is assumed that
the vectorsG, [G, F], [[G, F], F] and [G, [G, F]] are linearly independent at Po.
By performing a suitable rescaling of time and space coordinates [1], (4.1) takes the form
(4.2) (Xl,X2,Xa,X4) = (U,Xl,x2,xi!2)+h(x), .x(O) =0, where the vector field h plays the role of a small perturbation. In the special case h== 0, we apply Theorem 1 to system (4.2).
Let x(t) be the solution of (4.2) and p(t) the adjoint vector with P(SI + S2+ sa) =P= (Pl,P2,pa,P4) corresponding to the control u(t) having the values Ion[0,SI)U[SI+S2,SI+S2+Sa] and -Ion[S1,SI+S2).
Hence p(t) = (Pl(t),P2(t),Pa(t),P4(t)) satisfies that Ih(t) = -P2 - P4 Xl,
P2(t) = -Pa, Pa(t) = 0, P4(t) = 0.
We can explicitly compute x(t) and [X, Y] : on [0,SI), on [SI,SI+S2),
on [SI + S2,SI + S2 + Sa],
[X,Y] = ( ~ ).
2Xl
564
Due to
Chang Eon Shin
y-x=n}
assumption AI) implies that Pl(Ti) = 0 for i = 0,1,2, where Ti
So+ ... +Si· SincePI(r3) = 0, ih = O. Whenih =0,
(4.3)
(4.4)
(4.5)
PI(0) =[2p2(SI+S2 +S3) +P3(sI +2S1 S 2+s~+2S1S3+2S2S3+s~) +P4(Sr +2S1S2 - s~+2S 1 S 3 - 2S2 S 3 +s~)]j2.
In (4.3), we can solve forP2 to get
_ _ ( S3 ) P3 S 3 ,
P2 = -P4 SI - S2 +2 - -2- = P2·
- ( 2 2)
Wh - " P4 -SI S2+S2 - SI S3+S2 S 3 - S3 " d
enP3 =P3' P2 = =P2 an
82 +S3
If81 =83, then there exists nonzero vector
which is unique up to a scalar multiplication.
In this case,
_ 28 2 8 3
p. [X,Y](X('T3)) = ----'---'--
82+83
which does not vanish if82 =f:.0 or 83 =f:. O. IfPI(0) =PI('TI) = PI ('T2) = 0,(PI('T3) =0 is excluded), and 81 =83, then we have
(4.6)
(4.7)
(4.8)
and direct computation yields that the equations
i = 0,1,2, whereXl =X3 =X and Xo=X2 =Y, determine
566 Chang Eon Shin
uniquely up to a scalar multiplication.
Hence, for small s4 >0, there exist ti(i = 0,1,2,3) satisfying (1.3)- (1.4) for the system (4.2), but to may be a negative number which is not acceptable. Inthe following computation, we show that aaS4 > 0,
to whenSi =ti , S4 =0,to =°for i =1,2,3. Assume that
Let u+(t) and u-(t) be the controls such that
on [0,to) U[to + tb 1 - t2), on [to, to + td U [1 - t2,1],
{
1 on [0,SI) U[1 - s3 - S4,1 - S4)
u+(t) =
-1 on [Sb1 - S3 - S4)U [1 - S4,1],
and let x+(t) = (xt(t), xt(t), xt(t), xt(t)) and x-et) = (x1(t), x2(t), Xg(t),x4(t)) be the trajectories corresponding to the controls u+and u-, respectively. By direct computation, at t = 1,
+ 1 2 2
x2 =-2"+ 2s1 - SI + S3+ 2S3 S 4 ,
+ 1 2 sf+s~ 2 2
x3 = -6 +SI - SI + 3 + S3 S 4+ S3 S 4,
Xl =-1+2t1 +2t2,
- 1 2 2
x 2 = -2"+2t1 - 2tot 1 - t1+t 2,
- 1 2 2 2 tf+t~
x 3 = -6 + t1 - 2tot 1+tot 1 - t1+tot1+ 3 Solving the equations
for i = 1,2,3
\I
for s/sand computing the derivative ofS4 with respect toto atto = 0, we obtain
(4.9)
so to is positive while S4 >O.
Hence at SI = S3, bifurcation occurs and when h == 0, any bang- bang trajectory of (4.2) loses optimality at or before fourth switching point if the cut-locus forms 3-dimensional manifold.
References
[1] A. Bressan, Nilpotent approximations and optimal trajectories in: Controlled Dynamical Systems, Birkhouser, Boston, 1991.
[2] , The generic local time-optimal stabilizing control in dimension 3, SIAM J. Control& Opt. 24 (1986),177-190.
[3] A. Bressan, Lecture notes on the Mathematical Theory of Control, SISSA, 1991.
[4] R. L. Bishop and R. J. Crittenden, Geometry of Manifolds, Academic Press, 1964.
[5] L. Cesari, Optimization Theory and Applications, Springer-Verlag, 1983.
[6] S. N. Chow and J. K. Hale, Methods of Bifurcation Theory, Springer-Verlag, 1982.
[7] A. Krener and H. Schattler, The structure of small time reachable sets in low dimensions, SIAM J. Control& Opt. 27 (1989), 120-147.
[8] J. D. Logan, Applied Mathematics, John Wiley & Sons, 1987.
[9] H. Schattler, Conjugate points and intersections of bang-bang trajectories, in:
Proceedings of the 28th Conference on Decision and Control (1989), Tampa, 1121-1126.
[10] , On the local structure of time-optimal bang-bang trajectories in JR3, SIAM J. Control& Opt. 26 (1988), 186-204.
[11] H. Sussmann, Envelopes, high-order optimality conditions and Lie brackets, in: Proceedings of the 28th Conference on Decision and Control, Tampa, 1989.
Department of Mathematics, Sogang University,
Seoul 121-742, Korea
E-mail: [email protected]