KITTI_Scenario_Coverage.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Scenario K-Projection Coverage over Kitti Data Sets\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Put these at the top of every notebook, to get automatic reloading and inline plotting\n",
    "%reload_ext autoreload\n",
    "%autoreload 2\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from nndependability.metrics import ScenarioKProjection"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A. Understanding combinatorial effects in scenario coverage\n",
    "\n",
    "Load scenario description file, which contains all possible categorizations to partition the input space. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "metric = ScenarioKProjection.Scenario_KProjection_Metric(\"data/kitti/description.xml\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For the loaded example in data/kitti/description.xml, \n",
    "* Condition <ego_vn> (ego velocity to the north) has been discretized to 7 categorizations.\n",
    "* Condition <left_box_existence> has been discretized to 2 categorizations\n",
    "\n",
    "One can thus derive the total number of possible scenarios, by picking one item in each condition, equals 7x7x7x7x2x8x9x4x2x8x9x4x2x8x9x4x2x8x9x4, around 2.64x10^14. Such a huge number clearly shows that it is impossible to achieve 100% coverage even when one wants to cover each scenario with one test case. \n",
    "\n",
    "\n",
    "Therefore, we would like to have a \"relative form\" of completeness, where one is able to argue 100% but the confidence of completeness is lower. An analogy apeears in software testing, where compared to path coverage or MC/DC coverage, line coverage is a weaker form - it is easy to achieve \"100%\" but the \"100%\" provides weaker guarantee. This brings us to the concept of K-projection coverage.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## B. Process raw data from Kitti, and compute 2-projection coverage\n",
    "\n",
    "As the description.xml describes all possible discrete partitionings, the next step is to translate raw data in Kitti into concrete scenarios such that we can compute coverage. We have stored the translated scenarios inside data/kitti/scenarios.xml. \n",
    "\n",
    "\n",
    "[Optional] If you want to generate scenarios.xml yourself, you can do it by executing the kitti_scenario_creator.py (available at the root), in the following way\n",
    "\n",
    "```sh\n",
    "$ python3 kitti_scenario_creator.py\n",
    "```\n",
    "\n",
    "The raw data used in generating scenarios.xml includes\n",
    "* data/kitti/oxts: GPS and IMU data of the ego vehicle\n",
    "* tracklet_labels.xml: Object tracking information derived from consecutive images including nearby vehicles and pedestrians. \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2-projection coverage (without considering domain restrictions): 287/6772\n"
     ]
    }
   ],
   "source": [
    "metric.addScenariosFromFile(\"data/kitti/scenarios.xml\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When one adds scenraios into the metric, the current 2-projection coverage is computed (i.e., k=2). One can observe that the computed 2-projection coverage has a denominator of 6772, which is substantially smaller than 2.64x10^14. \n",
    "\n",
    "The concept of 2-projection coverage are highly related to the idea of combinatorial testing and coverage arrays, where instead of testing all possible combinations, we just ensure that the set of test cases we have can cover every criterion pair, in contrast to every tuple in 2.64x10^14. For further details, see https://arxiv.org/abs/1805.04333 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## C. Proposing new scenarios\n",
    "\n",
    "Apart from computing coverage, another task is to generate new scenarios to maximally increase coverage. Here we have some issues where certain combination is just impossible. We use a file to specify the domain restrictions into constraints. \n",
    "\n",
    "\n",
    "\n",
    "The domain restriction file in data/kitti/domain-restrictions.xml contains constraints similar to below one.\n",
    "\n",
    "    <constraint>\n",
    "        <upperbound>MAX</upperbound>\n",
    "        <lowerbound>3</lowerbound>\n",
    "        <item>3, left_box_existence.True</item>\n",
    "        <item>1, left_box_rotation.0</item>\n",
    "        <item>1, left_box_type.Misc</item>\n",
    "        <item>1, left_box_occlusion.0</item>\n",
    "    </constraint>\n",
    "    \n",
    "This constraint says that if  left_box_existence equals False, then \n",
    "* left_box_rotation must be 0\n",
    "* left_box_type must be Misc \n",
    "* left_box_occlusion must be 0\n",
    "\n",
    "\n",
    "[Note] If you see the above computed coverage, it actually says \"(without considering domain restrictions)\". When one adds domain restrictions, then deriving the denominator equals to the problem of model counting, which is a hard problem itself. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.0 <=  + 3.0 C4_0 + 1.0 C5_0 + 1.0 C6_7 + 1.0 C7_0 <= inf\n",
      "3.0 <=  + 3.0 C8_0 + 1.0 C9_0 + 1.0 C10_7 + 1.0 C11_0 <= inf\n",
      "3.0 <=  + 3.0 C12_0 + 1.0 C13_0 + 1.0 C14_7 + 1.0 C15_0 <= inf\n",
      "3.0 <=  + 3.0 C16_0 + 1.0 C17_0 + 1.0 C18_7 + 1.0 C19_0 <= inf\n"
     ]
    }
   ],
   "source": [
    "metric.addDomainRestrictionsFromFile(\"data/kitti/domain-restrictions.xml\")\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can ask the solver to propose a scenario candidate which increases coverage while satisfying constraints as specified in domain restriction."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Timeout but feasible solution found in 10 seconds\n",
      "Maximum possibility for improvement = 6485\n",
      "Optimal objective value computed from IP = 189\n",
      "\n",
      "for criterion ego_vn, set it to -3\n",
      "for criterion ego_ve, set it to -2\n",
      "for criterion ego_ax, set it to 0\n",
      "for criterion ego_ay, set it to -3\n",
      "for criterion left_box_existence, set it to True\n",
      "for criterion left_box_rotation, set it to 1\n",
      "for criterion left_box_type, set it to DontCare\n",
      "for criterion left_box_occlusion, set it to 2\n",
      "for criterion right_box_existence, set it to True\n",
      "for criterion right_box_rotation, set it to 0\n",
      "for criterion right_box_type, set it to Misc\n",
      "for criterion right_box_occlusion, set it to 3\n",
      "for criterion closest_box_1_existence, set it to True\n",
      "for criterion closest_box_1_rotation, set it to 0\n",
      "for criterion closest_box_1_type, set it to Misc\n",
      "for criterion closest_box_1_occlusion, set it to 3\n",
      "for criterion closest_box_2_existence, set it to True\n",
      "for criterion closest_box_2_rotation, set it to 6\n",
      "for criterion closest_box_2_type, set it to DontCare\n",
      "for criterion closest_box_2_occlusion, set it to 2\n"
     ]
    }
   ],
   "source": [
    "from nndependability.atg.scenario import scenariogen\n",
    "variableAssignment = scenariogen.proposeScenariocandidate(metric)\n",
    "metric.writeScenarioToFile(variableAssignment, \"local/tmp.xml\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now add this new scenario to the existing data set, and one observes that the value of the computed metric has increased."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2-projection coverage (without considering domain restrictions): 476/6772\n"
     ]
    }
   ],
   "source": [
    "metric.addScenariosFromFile(\"local/tmp.xml\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One may continue the process and propose more candidates. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Timeout but feasible solution found in 10 seconds\n",
      "Maximum possibility for improvement = 6296\n",
      "Optimal objective value computed from IP = 184\n",
      "\n",
      "for criterion ego_vn, set it to 3\n",
      "for criterion ego_ve, set it to 2\n",
      "for criterion ego_ax, set it to -3\n",
      "for criterion ego_ay, set it to 3\n",
      "for criterion left_box_existence, set it to True\n",
      "for criterion left_box_rotation, set it to 6\n",
      "for criterion left_box_type, set it to Person_sitting\n",
      "for criterion left_box_occlusion, set it to 3\n",
      "for criterion right_box_existence, set it to True\n",
      "for criterion right_box_rotation, set it to 5\n",
      "for criterion right_box_type, set it to Tram\n",
      "for criterion right_box_occlusion, set it to 2\n",
      "for criterion closest_box_1_existence, set it to True\n",
      "for criterion closest_box_1_rotation, set it to 7\n",
      "for criterion closest_box_1_type, set it to Van\n",
      "for criterion closest_box_1_occlusion, set it to 2\n",
      "for criterion closest_box_2_existence, set it to True\n",
      "for criterion closest_box_2_rotation, set it to 2\n",
      "for criterion closest_box_2_type, set it to Pedestrian\n",
      "for criterion closest_box_2_occlusion, set it to 3\n"
     ]
    }
   ],
   "source": [
    "variableAssignment = scenariogen.proposeScenariocandidate(metric)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "metric.writeScenarioToFile(variableAssignment, \"local/tmp2.xml\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2-projection coverage (without considering domain restrictions): 660/6772\n"
     ]
    }
   ],
   "source": [
    "metric.addScenariosFromFile(\"local/tmp2.xml\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Timeout but feasible solution found in 10 seconds\n",
      "Maximum possibility for improvement = 6112\n",
      "Optimal objective value computed from IP = 171\n",
      "\n",
      "for criterion ego_vn, set it to -1\n",
      "for criterion ego_ve, set it to 1\n",
      "for criterion ego_ax, set it to -2\n",
      "for criterion ego_ay, set it to 0\n",
      "for criterion left_box_existence, set it to True\n",
      "for criterion left_box_rotation, set it to 3\n",
      "for criterion left_box_type, set it to Pedestrian\n",
      "for criterion left_box_occlusion, set it to 1\n",
      "for criterion right_box_existence, set it to True\n",
      "for criterion right_box_rotation, set it to 7\n",
      "for criterion right_box_type, set it to Van\n",
      "for criterion right_box_occlusion, set it to 0\n",
      "for criterion closest_box_1_existence, set it to True\n",
      "for criterion closest_box_1_rotation, set it to 2\n",
      "for criterion closest_box_1_type, set it to Pedestrian\n",
      "for criterion closest_box_1_occlusion, set it to 0\n",
      "for criterion closest_box_2_existence, set it to True\n",
      "for criterion closest_box_2_rotation, set it to 1\n",
      "for criterion closest_box_2_type, set it to Tram\n",
      "for criterion closest_box_2_occlusion, set it to 2\n"
     ]
    }
   ],
   "source": [
    "variableAssignment = scenariogen.proposeScenariocandidate(metric)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "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.6.6rc1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}