Travelling-tube method

A direct method for the numerical solution of problems of optimal control with constraints on the phase coordinates and control functions. The original problem of optimal control by discretization (with respect to time $t$ and phase vector $x$) can be reduced to the minimization of a function of the type

$$I(x_0,\dots,x_N)=\sum_{i=0}^{N-1}\phi_i(x_i,x_{i+1}),$$

where $x_i$ is the value of the vector $x$ at the nodal points of hyperplanes given in the $(t,x)$-space by the equations $t=t_i$. The discretization with respect to $t$ and $x$ is effected by given steps $\Delta t$ and $\Delta x$. To each set of vectors $\{x_0,\dots,x_N\}$ there corresponds a polygonal line passing through the nodes, which is an approximate representation of the trajectory $x(t)$ of the original problem of optimal control. The length $I(x_0,\dots,x_N)$ of this line is the sum of the (generalized) lengths $\phi_i(x_i,x_{i+1})$ of the individual pieces. The polygonal line having shortest length is found with the aid of the recurrence relation

$$l_s(i+1)=\min_k(l_k(i)+l_{ks}(i))$$

(cf. Variational calculus, numerical methods of).

The search for a global minimum on any graph thus obtained requires a large operation memory and long computing times (especially in connection with the diminution of $\Delta x$ and $\Delta t$ to obtain a solution of desired accuracy).

The required amounts of memory and the number of operations can be considerably reduced if the attempt to find a global minimum is abandoned. The algorithm used works by successive approximations; the optimal trajectory is not sought on the entire graph, but on a subgraph given by a "tube" containing the initial polygonal line; this is the initial approximation. Each cross-section of the tube contains a given amount of nodes. The polygonal line which is found is taken as the successive approximation, after which the computations are repeated on a new subgraph.

Estimates show that in the travelling-tube method the number of operations increases linearly with the number of grid nodes with respect to $x$ (with decreasing step-size $\Delta x$), while in the method of global selection the increase is quadratic.

A special case of the travelling-tube method is the method of local variations (cf. Local variations, method of), in which the number of nodes in each cross-section is minimal (and equal to two).

References

[1]	N.N. Moiseev, "Elements of the theory of optimal systems" , Moscow (1975) (In Russian)

'