Domain
\( \DeclareMathOperator{\Feventually}{\Diamond} \DeclareMathOperator{\Galways}{\Box}
\DeclareMathOperator{\Uuntil}{\mathbf{U}} \)
The
scaling chains of integrators domain is the simplest in terms of
dynamics and specifications, yet unlike the other domains, the system to be
controlled can be scaled easily to arbitrarily many dimensions. While this
problem is abstract in the sense that it is not modeling a specific physical
system, it is well-motivated because the double-integrator is just the basic
force equation \( F=ma \) of Newtonian mechanics, up to a scaling factor.
Informally, this problem domain concerns controlling acceleration or a higher
order derivative of a point-mass in high-dimensional spaces so as to visit goal
regions and avoid obstacles.
Dynamics and constraints
Let \( n \) and \( m \) be positive integers. Consider the differential equation
\begin{equation}
D^{m}q = u ,\label{eq:minteg}
\end{equation}
where \( q: [0,\infty [ \rightarrow \mathbb{R}^{n} \) and \( D \) is the differential
operator. The input \( u \) is bounded as \( \lVert u(t) \rVert_1 \leq
u_{\mathrm{max}} \). The system is called a chain of integrators
because it can be rewritten as a linear control system
\begin{equation}
\begin{split}
\dot{x}_1 &= x_2 \\
\dot{x}_2 &= x_3 \\
&\vdots \\
\dot{x}_{m-1} &= x_m \\
\dot{x}_m &= u \\
y &= x_1
\end{split}\label{eq:cintegdyn}
\end{equation}
where for time \( t \), each \( x_{i}(t)\in \mathbb{R}^n \) for \( i=1,\ldots,m \), and
\( x(t)=\left( x_{1}(t) , \ldots , x_{m}(t)\right)\in \mathbb{R}^{nm} \). The output
trajectories of \eqref{eq:cintegdyn} are exactly those of \eqref{eq:minteg},
given the same input, and thus we call them equivalent. In \eqref{eq:minteg},
control input is applied as the \( m \)-th derivative of an \( n \)-dimensional variable
\( q \), and the intermediate derivatives are made explicit in
\eqref{eq:cintegdyn}. A notable particular case is \( m=2 \), which is called the
"double integrator". If \( n \leq 3 \) then \( q \) may be referred to as the
"position".
To introduce process and sensor noise, consider the 2-dimensional system
\begin{align}
\dot{x} &= \left(
\begin{array}{cc}
0 & 1 \\
0 & 0
\end{array}
\right) x + \left(
\begin{array}{c}
0 \\
1
\end{array}
\right) u + \xi \label{eq:dintegdyn}\\
y &= \left(
\begin{array}{cc}
1 & 0
\end{array}
\right) x + \eta \label{eq:dintegobs},
\end{align}
where \( \xi \) and \( \eta \) are either bounded disturbances (nondeterministic) or
stochastic processes. Equivalence with \eqref{eq:minteg} in the case of
\( n=1, m=2 \) and \( \xi=\eta=0 \) is apparent using \( x_1 = q \) and \( x_2 = \dot{q} \). For \( n
> 1 \), the matrices in \eqref{eq:dintegdyn} and \eqref{eq:dintegobs} can be
repeated in block diagonal form to yield a new linear time-invariant system of
dimension \( 2n \) and which is again equivalent to \eqref{eq:minteg} for \( m=2 \).
Specifications
Task specifications will require visitation of regions while avoiding obstacles.
These can be regarded as a slight extension beyond classical motion planning.
There are two forms of specifications:
\begin{equation}\label{eq:dinteg-surveillance}
q(0) = \mathrm{init} \wedge \Galways \left( q(t) \notin \mathrm{Obs} \right) \wedge \bigwedge_{i} \Galways
\Feventually \mathrm{goal}_i
\end{equation}
and
\begin{equation}\label{eq:dinteg-timedreach}
q(0) = \mathrm{init} \wedge \Galways \left( q(t) \notin \mathrm{Obs} \right) \wedge \bigwedge_{i} \left(
\mathrm{counter}_i \leq T_{i} \right) \Uuntil \mathrm{goal}_i ,
\end{equation}
where \( \mathrm{Obs} \subset \mathbb{R}^n \) is the obstacle set, which is
represented by a finite union of polytopes. For each \( i \), \( \mathrm{counter}_i \)
is a discrete clock that enforces the real-time deadline \( T_i \) of reaching
region \( \mathrm{goal}_i \). Goal region \( \mathrm{goal}_i \) is defined by a convex
polytope. The initial position is a single point, \( \mathrm{init}\in
\mathbb{R}^n \). As part of the specification form \eqref{eq:dinteg-timedreach},
a time of initialization and rate of progression of the discrete counters is
specified. These are significant because they determine in what order and how
quickly the goal regions must be reached.
Approach
The solution used a traveling-salesman optimization to order goals, potential fields attracting
to
goals & repelling from obstacles, random walk to
avoid unfortunately generated polytopes and logic to indicate unsolvable scenarios. A
futher implementation was done by creating a bisimulation of the higher-order system with
a
lower-order system (which while less accurate will make finding a solution simpler.)