{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1 System Modelling\n",
    "\n",
    "This notebook contains the theory on using the vehicle Kinematics Equations to derive the linearized state space model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from scipy.integrate import odeint\n",
    "from scipy.interpolate import interp1d\n",
    "import cvxpy as cp\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "plt.style.use(\"ggplot\")\n",
    "\n",
    "import time"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## kinematics model equations\n",
    "\n",
    "The variables of the model are:\n",
    "\n",
    "* $x$ coordinate of the robot\n",
    "* $y$ coordinate of the robot\n",
    "* $v$ velocity of the robot\n",
    "* $\\theta$ heading of the robot\n",
    "\n",
    "The inputs of the model are:\n",
    "\n",
    "* $a$ acceleration of the robot\n",
    "* $\\delta$ steering of the robot\n",
    "\n",
    "These are the differential equations f(x,u) of the model:\n",
    "\n",
    "$\\dot{x} = f(x,u)$\n",
    "\n",
    "* $\\dot{x} = v\\cos{\\theta}$ \n",
    "* $\\dot{y} = v\\sin{\\theta}$\n",
    "* $\\dot{v} = a$\n",
    "* $\\dot{\\theta} = \\frac{v\\tan{\\delta}}{L}$\n",
    "\n",
    "Discretize with forward Euler Integration for time step dt:\n",
    "\n",
    "${x_{t+1}} = x_{t} + f(x,u)dt$\n",
    "\n",
    "* ${x_{t+1}} = x_{t} + v_t\\cos{\\theta}dt$\n",
    "* ${y_{t+1}} = y_{t} + v_t\\sin{\\theta}dt$\n",
    "* ${v_{t+1}} = v_{t} + a_tdt$\n",
    "* ${\\theta_{t+1}} = \\theta_{t} + \\frac{v\\tan{\\delta}}{L} dt$\n",
    "\n",
    "----------------------\n",
    "\n",
    "The Model is **non-linear** and **time variant**, but the Numerical Optimizer requires a Linear sets of equations. To approximate the equivalent **LTI** State space model, the **Taylor's series expansion** is used around $\\bar{x}$ and $\\bar{u}$ (at each time step):\n",
    "\n",
    "$ f(x,u) \\approx f(\\bar{x},\\bar{u}) +  \\frac{\\partial f(x,u)}{\\partial x}|_{x=\\bar{x},u=\\bar{u}}(x-\\bar{x}) + \\frac{\\partial f(x,u)}{\\partial u}|_{x=\\bar{x},u=\\bar{u}}(u-\\bar{u})$\n",
    "\n",
    "This can be rewritten usibg the State Space model form Ax+Bu :\n",
    "\n",
    "$ f(\\bar{x},\\bar{u}) +  A|_{x=\\bar{x},u=\\bar{u}}(x-\\bar{x}) + B|_{x=\\bar{x},u=\\bar{u}}(u-\\bar{u})$\n",
    "\n",
    "Where:\n",
    "\n",
    "$\n",
    "A =\n",
    "\\quad\n",
    "\\begin{bmatrix}\n",
    "\\frac{\\partial f(x,u)}{\\partial x} & \\frac{\\partial f(x,u)}{\\partial y} & \\frac{\\partial f(x,u)}{\\partial v} & \\frac{\\partial f(x,u)}{\\partial \\theta} \\\\\n",
    "\\end{bmatrix}\n",
    "\\quad\n",
    "=\n",
    "\\displaystyle \\left[\\begin{matrix}0 & 0 & \\cos{\\left(\\theta \\right)} & - v \\sin{\\left(\\theta \\right)}\\\\0 & 0 & \\sin{\\left(\\theta \\right)} & v \\cos{\\left(\\theta \\right)}\\\\0 & 0 & 0 & 0\\\\0 & 0 & \\frac{\\tan{\\left(\\delta \\right)}}{L} & 0\\end{matrix}\\right]\n",
    "$\n",
    "\n",
    "and\n",
    "\n",
    "$\n",
    "B = \n",
    "\\quad\n",
    "\\begin{bmatrix}\n",
    "\\frac{\\partial f(x,u)}{\\partial a} & \\frac{\\partial f(x,u)}{\\partial \\delta} \\\\\n",
    "\\end{bmatrix}\n",
    "\\quad\n",
    "= \n",
    "\\displaystyle \\left[\\begin{matrix}0 & 0\\\\0 & 0\\\\1 & 0\\\\0 & \\frac{v \\left(\\tan^{2}{\\left(\\delta \\right)} + 1\\right)}{L}\\end{matrix}\\right]\n",
    "$\n",
    "\n",
    "are the *Jacobians*.\n",
    "\n",
    "\n",
    "\n",
    "So the discretized model is given by:\n",
    "\n",
    "$ x_{t+1} = x_t + (f(\\bar{x},\\bar{u}) +  A|_{x=\\bar{x}}(x_t-\\bar{x}) + B|_{u=\\bar{u}}(u_t-\\bar{u}) )dt $\n",
    "\n",
    "$ x_{t+1} = (I+dtA)x_t + dtBu_t +dt(f(\\bar{x},\\bar{u}) - A\\bar{x} - B\\bar{u}))$\n",
    "\n",
    "The LTI-equivalent kinematics model is:\n",
    "\n",
    "$ x_{t+1} = A'x_t + B' u_t + C' $\n",
    "\n",
    "with:\n",
    "\n",
    "$ A' = I+dtA|_{x=\\bar{x},u=\\bar{u}} $\n",
    "\n",
    "$ B' = dtB|_{x=\\bar{x},u=\\bar{u}} $\n",
    "\n",
    "$ C' = dt(f(\\bar{x},\\bar{u}) - A|_{x=\\bar{x},u=\\bar{u}}\\bar{x} - B|_{x=\\bar{x},u=\\bar{u}}\\bar{u}) $"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-----------------\n",
    "[About Taylor Series Expansion](https://courses.engr.illinois.edu/ece486/fa2017/documents/lecture_notes/state_space_p2.pdf):\n",
    "\n",
    "In order to linearize general nonlinear systems, we will use the Taylor Series expansion of functions.\n",
    "\n",
    "Typically it is possible to assume that the system is operating about some nominal\n",
    "state solution $\\bar{x}$ (possibly requires a nominal input $\\bar{u}$) called **equilibrium point**.\n",
    "\n",
    "Recall that the Taylor Series expansion of f(x) around the\n",
    "point $\\bar{x}$ is given by:\n",
    "\n",
    "$f(x)=f(\\bar{x}) + \\frac{df(x)}{dx}|_{x=\\bar{x}}(x-\\bar{x})$ + higher order terms...\n",
    "\n",
    "For x sufficiently close to $\\bar{x}$, these higher order terms will be very close to zero, and so we can drop them.\n",
    "\n",
    "The extension to functions of multiple states and inputs is very similar to the above procedure.Suppose the evolution of state x\n",
    "is given by:\n",
    "\n",
    "$\\dot{x} = f(x1, x2, . . . , xn, u1, u2, . . . , um) = Ax+Bu$\n",
    "\n",
    "Where:\n",
    "\n",
    "$ A =\n",
    "\\quad\n",
    "\\begin{bmatrix}\n",
    "\\frac{\\partial f(x,u)}{\\partial x1} & ... & \\frac{\\partial f(x,u)}{\\partial xn} \\\\\n",
    "\\end{bmatrix}\n",
    "\\quad\n",
    "$ and $ B = \\quad\n",
    "\\begin{bmatrix}\n",
    "\\frac{\\partial f(x,u)}{\\partial u1} & ... & \\frac{\\partial f(x,u)}{\\partial um} \\\\\n",
    "\\end{bmatrix}\n",
    "\\quad $\n",
    "\n",
    "Then:\n",
    "\n",
    "$f(x,u)=f(\\bar{x},\\bar{u}) + \\frac{df(x,u)}{dx}|_{x=\\bar{x}}(x-\\bar{x}) + \\frac{df(x,u)}{du}|_{u=\\bar{u}}(u-\\bar{u}) = f(\\bar{x},\\bar{u}) + A_{x=\\bar{x}}(x-\\bar{x}) + B_{u=\\bar{u}}(u-\\bar{u})$\n",
    "\n",
    "-----------------"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## ODE Model\n",
    "Motion Prediction: using scipy intergration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define process model\n",
    "# This uses the continuous model\n",
    "def kinematics_model(x, t, u):\n",
    "    \"\"\"\n",
    "    Returns the set of ODE of the vehicle model.\n",
    "    \"\"\"\n",
    "\n",
    "    L = 0.3  # vehicle wheelbase\n",
    "    dxdt = x[2] * np.cos(x[3])\n",
    "    dydt = x[2] * np.sin(x[3])\n",
    "    dvdt = u[0]\n",
    "    dthetadt = x[2] * np.tan(u[1]) / L\n",
    "\n",
    "    dqdt = [dxdt, dydt, dvdt, dthetadt]\n",
    "\n",
    "    return dqdt\n",
    "\n",
    "\n",
    "def predict(x0, u):\n",
    "    \"\"\" \"\"\"\n",
    "\n",
    "    x_ = np.zeros((N, T + 1))\n",
    "\n",
    "    x_[:, 0] = x0\n",
    "\n",
    "    # solve ODE\n",
    "    for t in range(1, T + 1):\n",
    "\n",
    "        tspan = [0, DT]\n",
    "        x_next = odeint(kinematics_model, x0, tspan, args=(u[:, t - 1],))\n",
    "\n",
    "        x0 = x_next[1]\n",
    "        x_[:, t] = x_next[1]\n",
    "\n",
    "    return x_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 3.39 ms, sys: 0 ns, total: 3.39 ms\n",
      "Wall time: 2.79 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "\n",
    "u_bar = np.zeros((M, T))\n",
    "u_bar[0, :] = 0.2  # m/ss\n",
    "u_bar[1, :] = np.radians(-np.pi / 4)  # rad\n",
    "\n",
    "x0 = np.zeros(N)\n",
    "x0[0] = 0\n",
    "x0[1] = 1\n",
    "x0[2] = 0\n",
    "x0[3] = np.radians(0)\n",
    "\n",
    "x_bar = predict(x0, u_bar)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 11464 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 2 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# plot trajectory\n",
    "plt.subplot(2, 2, 1)\n",
    "plt.plot(x_bar[0, :], x_bar[1, :])\n",
    "plt.plot(np.linspace(0, 10, T + 1), np.zeros(T + 1), \"b-\")\n",
    "plt.axis(\"equal\")\n",
    "plt.ylabel(\"y\")\n",
    "plt.xlabel(\"x\")\n",
    "\n",
    "plt.subplot(2, 2, 2)\n",
    "plt.plot(np.degrees(x_bar[2, :]))\n",
    "plt.ylabel(\"theta(t) [deg]\")\n",
    "# plt.xlabel('time')\n",
    "\n",
    "\n",
    "plt.tight_layout()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## State Space Linearized Model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "Control problem statement.\n",
    "\"\"\"\n",
    "\n",
    "N = 4  # number of state variables\n",
    "M = 2  # number of control variables\n",
    "T = 20  # Prediction Horizon\n",
    "DT = 0.2  # discretization step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_linear_model(x_bar, u_bar):\n",
    "    \"\"\"\n",
    "    Computes the LTI approximated state space model x' = Ax + Bu + C\n",
    "    \"\"\"\n",
    "\n",
    "    L = 0.3  # vehicle wheelbase\n",
    "\n",
    "    x = x_bar[0]\n",
    "    y = x_bar[1]\n",
    "    v = x_bar[2]\n",
    "    theta = x_bar[3]\n",
    "\n",
    "    a = u_bar[0]\n",
    "    delta = u_bar[1]\n",
    "\n",
    "    A = np.zeros((N, N))\n",
    "    A[0, 2] = np.cos(theta)\n",
    "    A[0, 3] = -v * np.sin(theta)\n",
    "    A[1, 2] = np.sin(theta)\n",
    "    A[1, 3] = v * np.cos(theta)\n",
    "    A[3, 2] = v * np.tan(delta) / L\n",
    "    A_lin = np.eye(N) + DT * A\n",
    "\n",
    "    B = np.zeros((N, M))\n",
    "    B[2, 0] = 1\n",
    "    B[3, 1] = v / (L * np.cos(delta) ** 2)\n",
    "    B_lin = DT * B\n",
    "\n",
    "    f_xu = np.array(\n",
    "        [v * np.cos(theta), v * np.sin(theta), a, v * np.tan(delta) / L]\n",
    "    ).reshape(N, 1)\n",
    "    C_lin = DT * (\n",
    "        f_xu - np.dot(A, x_bar.reshape(N, 1)) - np.dot(B, u_bar.reshape(M, 1))\n",
    "    )\n",
    "\n",
    "    return np.round(A_lin, 4), np.round(B_lin, 4), np.round(C_lin, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 2.71 ms, sys: 0 ns, total: 2.71 ms\n",
      "Wall time: 1.82 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "\n",
    "u_bar = np.zeros((M, T))\n",
    "u_bar[0, :] = 0.2  # m/s\n",
    "u_bar[1, :] = np.radians(-np.pi / 4)  # rad\n",
    "\n",
    "x0 = np.zeros(N)\n",
    "x0[0] = 0\n",
    "x0[1] = 1\n",
    "x0[2] = 0\n",
    "x0[3] = np.radians(0)\n",
    "\n",
    "x_bar = np.zeros((N, T + 1))\n",
    "x_bar[:, 0] = x0\n",
    "\n",
    "for t in range(1, T + 1):\n",
    "    xt = x_bar[:, t - 1].reshape(N, 1)\n",
    "    ut = u_bar[:, t - 1].reshape(M, 1)\n",
    "\n",
    "    A, B, C = get_linear_model(xt, ut)\n",
    "\n",
    "    xt_plus_one = np.dot(A, xt) + np.dot(B, ut) + C\n",
    "\n",
    "    x_bar[:, t] = np.squeeze(xt_plus_one)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 10548 characters]\n",
      "text/plain": [
       "<Figure size 432x288 with 2 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# plot trajectory\n",
    "plt.subplot(2, 2, 1)\n",
    "plt.plot(x_bar[0, :], x_bar[1, :])\n",
    "plt.plot(np.linspace(0, 10, T + 1), np.zeros(T + 1), \"b-\")\n",
    "plt.axis(\"equal\")\n",
    "plt.ylabel(\"y\")\n",
    "plt.xlabel(\"x\")\n",
    "\n",
    "plt.subplot(2, 2, 2)\n",
    "plt.plot(np.degrees(x_bar[2, :]))\n",
    "plt.ylabel(\"theta(t)\")\n",
    "# plt.xlabel('time')\n",
    "\n",
    "\n",
    "plt.tight_layout()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The results are the same as expected, so the linearized model is equivalent as expected."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [conda env:.conda-jupyter] *",
   "language": "python",
   "name": "conda-env-.conda-jupyter-py"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
