Euler method

For most systems, the integration must be performed numerically. A system simulator based on numerical integration can be constructed by breaking $ t$ into smaller intervals and iterating classical methods for computing numerical solutions to differential equations. The Euler method is the simplest of these methods. Let $ \Delta t$ denote a small time interval over which the approximation will be made. This can be considered as an internal parameter of the system simulator. In practice, this $ \Delta t$ is usually much smaller than the $ \Delta t$ used in the discrete-time model of Section 14.2.2. Suppose that $ x(0)$ and $ u(0)$ are given and the task is to estimate $ x(\Delta t)$.

By performing integration over time, the state transition equation can be used to determine the state after some fixed amount of time $ \Delta t$ has passed. For example, if $ x(0)$ is given and $ u(t^\prime)$ is known over the interval $ t^\prime \in [0,\Delta t]$, then the state at time $ \Delta t$ can be determined as

$\displaystyle x(\Delta t) = x(0) + \int_0^{\Delta t} f(x(t),u(t)) dt .$ (14.14)

The integral cannot be evaluated directly because $ x(t)$ appears in the integrand and is unknown for time $ t > 0$.

Using the fact that

$\displaystyle f(x,u) = {\dot x}= \frac{dx}{dt} \approx {x(\Delta t) - x(0) \over \Delta t} ,$ (14.15)

solving for $ x(\Delta t)$ yields the classic Euler integration method

$\displaystyle x(\Delta t) \approx x(0) + \Delta t \; f(x(0),u(0)) .$ (14.16)

The approximation error depends on how quickly $ x(t)$ changes over time and on the length of the interval $ \Delta t$. If the planning algorithm applies a motion primitive $ {\tilde{u}}^p$, it gives $ t_F({\tilde{u}}^p)$ as the time input, and the system simulator may subdivide the time interval to maintain higher accuracy. This allows the developer of the planning algorithm to ignore numerical accuracy issues.

Steven M LaValle 2012-04-20