tutorial_uninformed_search.ipynb 18.4 KB
 Edmond Irani Liu committed Nov 13, 2020 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 ``````{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Tutorial: Uninformed Search Algorithms\n", "\n", "This tutorial shows how we can combine motion primitives of vehicles, i.e., short trajectory segments, with uninformed search algorithms to find feasible trajectories that connect the **initial state** and the **goal region** of a given planning problem." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 0. Preparation\n", "Before you proceed with this tutorial, make sure that\n", "\n", "* you have gone through the tutorial for **CommonRoad Input-Output**.\n", "* you have installed all necessary modules for **CommonRoad Search** according to the installation manual.\n", "\n", "Let's start with importing relevant modules and classes for setting up the automaton and the CommonRoad (CR) scenario." ] }, { "cell_type": "code", `````` Edmond Irani Liu committed Nov 13, 2020 27 `````` "execution_count": 1, `````` Edmond Irani Liu committed Nov 13, 2020 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 `````` "metadata": {}, "outputs": [], "source": [ "%matplotlib inline\n", "%load_ext autoreload\n", "%autoreload 2\n", "\n", "import os\n", "import sys\n", "path_notebook = os.getcwd()\n", "\n", "# add the SMP folder to python path\n", "sys.path.append(os.path.join(path_notebook, \"../../\"))\n", "\n", "# add the 1_search_algorithms folder to python path\n", "sys.path.append(os.path.join(path_notebook, \"../\"))\n", "\n", "import matplotlib.pyplot as plt\n", "\n", "from commonroad.common.file_reader import CommonRoadFileReader\n", "from commonroad.visualization.draw_dispatch_cr import draw_object\n", "\n", "from SMP.motion_planner.motion_planner import MotionPlanner\n", "from SMP.maneuver_automaton.maneuver_automaton import ManeuverAutomaton\n", "from SMP.motion_planner.utility import plot_primitives, display_steps" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1. Loading CR Scenario and Planning Problem\n", "In the next step, we load a CommonRoad scenario and its planning problem, which should be solved with the search algorithms. The meaning of the symbols in a scenario are explained as follows:\n", "* **Dot**: initial state projected onto the position domain\n", "* **Red rectangle**: static obstacle\n", "* **Yellow rectangle**: goal region projected onto the position domain" ] }, { "cell_type": "code", `````` Edmond Irani Liu committed Nov 13, 2020 68 `````` "execution_count": 2, `````` Edmond Irani Liu committed Nov 13, 2020 69 `````` "metadata": {}, `````` Edmond Irani Liu committed Nov 13, 2020 70 71 72 73 74 75 76 77 78 79 80 81 82 83 `````` "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAA2AAAAA+CAYAAABN/ni+AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAKaUlEQVR4nO3dbYxcZ3XA8f/Zndl1snFlI0KgjltSFCpRW0BkklgRiL4kDajCtFKrhL5EgOQikQhEkID2QxGfKA1IbVq1dUUkKpEEIurWqiiQiqp8ybaO3ai280LWi6nXthKcEJY1XWd35/TDXKcbZ8aekJl77+79/yRrZp65c/dojs+dOTPPfSYyE0mSJEnS6I1VHYAkSZIkNYUNmCRJkiSVxAZMkiRJkkpiAyZJkiRJJbEBkyRJkqSS2IBJkiRJUklag2wUEceAHwMrwHJm7hhlUJIkSZK0Hg3UgBV+OTNPjywSSZIkSVrnnIIoSZIkSSWJzLz4RhHfA34IJPC3mbnnQts/8MADefz48eFEKEmSJElrzJ133nk6My8/f3zQKYg3ZObJiHgN8GBEPJ6Z31m9QUTsBnYDPPTQQ2zduvUVBy1JkiRJa9T3ew0ONAUxM08Wl08De4Fre2yzJzN3uECHJEmSJPV20QYsIqYiYuO568BNwOGLPGY40UmSJEnSOjLIFMQrgL1FU9UC7s3Mb1zoAZs3b2ZpaYmFhQUGOcdMkiRJkprgog1YZs4Cb35ZO221aLVatNttGzFJkiRJKryc3wF7+TsvGrGJiQkWFxc5c+bMKP+cJEmSJNXaSBswgE6nQ2YSEUxNTY36z0mSJElSbY2sAVtZWXlh+mGn0xnVn5EkSZKkNWMkDdji4qKNlyRJkiSdZyQN2Pz8/Ch2K0mSJElr2kA/xCxJkiRJeuVswCRJkiSpJDZgkiRJklSSkZwDduDAAWZmZkaxa0mSJElasyIzh77T6enp4e9UkiRJktaInTt3HsjMHeePOwVRkiRJkkoyUAMWETdHxBMRMRMRnxxg+1cemSStQ53lZRafeYb52VlO73+Y5448WnVIkiSpRBc9BywixoG/Am4E5oD9EbEvM/u+a9i8eTNLS0ssLCwwiimOkrSWPHnXF5hcXiGWlhhbWWYDwSXAxgiObZhk0y+9qeoQa+Pb/3gXnD0xvB1ObuFX3vvx4e1PkqRXaJBFOK4FZjJzFiAi7gd2AX0bsFarRavVot1u24hJGppDh57j4MFnueaaV7F9+6aqwxnYhrPP8+ZLLoGJiZfcd/z5sxVEVGNnT3D7jcNbxOkvHxzariRJGopBGrAtwPFVt+eA6wbaedGITUxMsLi4yJkzZ36aGCWJQ4ee44479rO01KHdHuPuu9+2ZpqwbLf73hdLSyVGIkmSqjZIA9brhK6XfJ0VEbuB3QBHjx59YbzT6ZCZRARTU1M/bZySGu7w4TmWljp0OrC83OHw4QWuv35L1WENZGzDBlhe7nlfu5NsaLcZ7/HtWBONjw93bajx8TFfeyRJtTJIAzYHbF11+0rg5PkbZeYeYA/A7OxsrqysvDD9sNPpDCVYSc21bdtltNtjLC11aLXG2LbtsjXzrfry+Bj07r+YJPnhyZNccvnl5QZVUysrw329WFnprJn/J5KkZhikAdsPXB0RVwEngFuA913oAYuLizZekoZq+/ZN3H3329bkOWA5OckTPzjN2Uxyok222t3Ldpt87Wu58tJLqw5RkiSV5KINWGYuR8TtwDeBceCezDxyocfMz88PKTxJ+n/bt29aU43XOVt/7310zp6lvXEjMebPL17Q5JbhLpwxuTamqUqSmiNGsTrh9PS0Sx5KkiRJaqydO3ceyMwd54/7UawkSZIklcQGTJIkSZJKMpIpiBHxA+D7Q9/x8LwaOF11EHqB+agX81Ev5qNezEe9mI96MR/1Yj6q9/OZ+ZJljkfSgNVdRDzcaz6mqmE+6sV81Iv5qBfzUS/mo17MR72Yj/pyCqIkSZIklcQGTJIkSZJK0tQGbE/VAehFzEe9mI96MR/1Yj7qxXzUi/moF/NRU408B0ySJEmSqtDUb8AkSZIkqXSNasAi4uaIeCIiZiLik1XH0zQRsTUi/i0iHouIIxHxkWL80xFxIiIeKf69u+pYmyIijkXEoeJ5f7gYe1VEPBgRTxaXm6uOswki4hdX1cAjETEfER+1PsoVEfdExNMRcXjVWM+aiK6/KF5T/jsirqku8vWpTz7+LCIeL57zvRGxqRh/fUT876pa+ZvqIl+f+uSj7zEqIj5V1McTEfHr1US9fvXJx1dW5eJYRDxSjFsfNdKYKYgRMQ58F7gRmAP2A7dm5qOVBtYgEfE64HWZeTAiNgIHgPcCvwMsZOZdlQbYQBFxDNiRmadXjX0OeDYzP1t8ULE5Mz9RVYxNVByvTgDXAe/H+ihNRLwDWAD+PjO3FWM9a6J4o3kH8G66ufrzzLyuqtjXoz75uAn4dmYuR8SfAhT5eD3wz+e20/D1ycen6XGMiog3AfcB1wI/C/wr8MbMXCk16HWsVz7Ou//zwI8y8zPWR7006Ruwa4GZzJzNzOeB+4FdFcfUKJl5KjMPFtd/DDwGbKk2KvWwC/hScf1LdJtkletXgaOZWecftF+XMvM7wLPnDferiV103/hkZk4Dm4oPmjQkvfKRmd/KzOXi5jRwZemBNVSf+uhnF3B/Zp7NzO8BM3Tfi2lILpSPiAi6H3DfV2pQGkiTGrAtwPFVt+fwzX9lik9i3gr8RzF0ezGd5B6nvJUqgW9FxIGI2F2MXZGZp6DbNAOvqSy65rqFF79oWh/V6lcTvq5U7wPAv6y6fVVE/FdE/HtEvL2qoBqo1zHK+qjW24GnMvPJVWPWR000qQGLHmPNmH9ZMxFxGfA14KOZOQ/8NfAG4C3AKeDzFYbXNDdk5jXAu4APF9MZVKGImADeAzxQDFkf9eXrSoUi4o+BZeDLxdAp4Ocy863Ax4B7I+JnqoqvQfodo6yPat3Kiz/Isz5qpEkN2BywddXtK4GTFcXSWBHRptt8fTkz/wEgM5/KzJXM7AB/h1MUSpOZJ4vLp4G9dJ/7p85Noyoun64uwkZ6F3AwM58C66Mm+tWErysViYjbgN8AfjeLk9mLqW7PFNcPAEeBN1YXZTNc4BhlfVQkIlrAbwFfOTdmfdRLkxqw/cDVEXFV8QnzLcC+imNqlGI+8heBxzLzC6vGV58z8ZvA4fMfq+GLiKliMRQiYgq4ie5zvw+4rdjsNuCfqomwsV70qaX1UQv9amIf8AfFaojX0z3Z/VQVATZJRNwMfAJ4T2b+ZNX45cUCNkTELwBXA7PVRNkcFzhG7QNuiYjJiLiKbj7+s+z4GurXgMczc+7cgPVRL62qAyhLsVrS7cA3gXHgnsw8UnFYTXMD8PvAoXPLogJ/BNwaEW+hOzXhGPCH1YTXOFcAe7t9MS3g3sz8RkTsB74aER8E/gf47QpjbJSIuJTuSq2ra+Bz1kd5IuI+4J3AqyNiDvgT4LP0romv010BcQb4Cd0VKzVEffLxKWASeLA4fk1n5oeAdwCfiYhlYAX4UGYOumCEBtAnH+/sdYzKzCMR8VXgUbpTRT/sCojD1SsfmflFXnoeMVgftdKYZeglSZIkqWpNmoIoSZIkSZWyAZMkSZKkktiASZIkSVJJbMAkSZIkqSQ2YJIkSZJUEhswSZIkSSqJDZgkSZIklcQGTJIkSZJK8n8NNM2jlq6+ewAAAABJRU5ErkJggg==\n", "text/plain": [ "