reinforcement_learning/rl_traveling_salesman_vehicle_routing_coach/rl_traveling_salesman_vehicle_routing_coach.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Traveling Salesman Problem with Reinforcement Learning"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Description of Problem\n",
    "\n",
    "The travelling salesman problem (TSP) is a classic algorithmic problem in the field of computer science and operations research. Given a list of cities and the distances between each pair of cities, the problem is to find the shortest possible route that visits each city and returns to the origin city.\n",
    "\n",
    "The problem is NP-complete as the number of combinations of cities grows larger as we add more cities. \n",
    "\n",
    "In the classic version of the problem, the salesman picks a city to start, travels through remaining cities and returns to the original city. \n",
    "\n",
    "In this version, we have slightly modified the problem, presenting it as a restaurant order delivery problem on a 2D gridworld.  The agent (driver) starts at the restaurant, a fixed point on the grid.  Then, delivery orders appear elsewhere on the grid.  The driver needs to visit the orders, and return to the restaurant, to obtain rewards.  Rewards are proportional to the time taken to do this (equivalent to the distance, as each timestep moves one square on the grid)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Why Reinforcement Learning?\n",
    "\n",
    "For canonical Operations problems like this one, we're very interested about RL's potential to push the state of the art.\n",
    "\n",
    "There are a few reasons we think RL offers some unique value for this type of problem:\n",
    "1. RL seems to perform well in high-dimensional spaces, when an approximate solution to a complex problem may be of greater value than an exact/optimal solution to a simpler problem.\n",
    "2. RL can do quite well in partially observed environments.  When there are aspects of a problem we don't know about and therefore can't model, which is often the case in the real-world (and we can pretend is the case with these problems), RL's ability to deal with the messiness is valuable.\n",
    "3. RL may have things to teach us!  We've seen this to be the case with Go, and Dota 2, where the RL agent came up with innovative strategies that have later been adopted by human players.  What if there are clever strategies we can use to solve versions of TSP, Knapsack, Newsvendor, or extensions of any of those?  RL might surprise us."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Easy Version of TSP\n",
    "In the Easy Version, we are on a 5x5 grid.  All orders are generated at the start of the episode.  Order locations are fixed, and are invariant (non-random) from episode to episode.  The objective is to visit each order location, and return to the restaurant.  We have a maximum time-limit of 50 steps.  \n",
    "\n",
    "### States\n",
    "At each time step, our agent is aware of the following information:\n",
    "\n",
    "1. For the Restuarant:\n",
    "    1. Location (x,y coordinates)\n",
    "    \n",
    "2. For the Driver\n",
    "    1. Location (x,y coordinates)\n",
    "    2. Is driver at restaurant (yes/no)\n",
    "\n",
    "3. For each Order: \n",
    "    1. Location (x,y coordinates)\n",
    "    2. Status (Delivered or Not Delivered)\n",
    "    3. Time (Time taken to deliver reach order -- incrementing until delivered)\n",
    "4. Miscellaneous\n",
    "    1. Time since start of episode\n",
    "    2. Time remaining until end of episode (i.e. until max time)\n",
    "\n",
    "### Actions\n",
    "At each time step, our agent can take the following steps:\n",
    "- Up - Move one step up in the map\n",
    "- Down - Move one step down in the map\n",
    "- Right - Move one step right in the map\n",
    "- Left - Move one step left in the map\n",
    "\n",
    "### Rewards\n",
    "Agent gets a reward of -1 for each time step. If an order is delivered in that timestep, it gets a positive reward inversely proportional to the time taken to deliver. If all the orders are delivered and the agent is back to the restaurant, it gets an additional reward inversely proportional to time since start of episode. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Using AWS SageMaker for RL\n",
    "\n",
    "AWS SageMaker allows you to train your RL agents in cloud machines using docker containers. You do not have to worry about setting up your machines with the RL toolkits and deep learning frameworks. You can easily switch between many different machines setup for you, including powerful GPU machines that give a big speedup. You can also choose to use multiple machines in a cluster to further speedup training, often necessary for production level loads."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Prerequisites \n",
    "\n",
    "#### Imports\n",
    "\n",
    "To get started, we'll import the Python libraries we need, set up the environment with a few prerequisites for permissions and configurations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sagemaker\n",
    "import boto3\n",
    "import sys\n",
    "import os\n",
    "import glob\n",
    "import re\n",
    "import subprocess\n",
    "from IPython.display import HTML\n",
    "import time\n",
    "from time import gmtime, strftime\n",
    "sys.path.append(\"common\")\n",
    "from misc import get_execution_role, wait_for_s3_object\n",
    "from sagemaker.rl import RLEstimator, RLToolkit, RLFramework"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Settings\n",
    "\n",
    "You can run this notebook from your local host or from a SageMaker notebook instance. In both of these scenarios, you can run the following in either local or SageMaker modes. The local mode uses the SageMaker Python SDK to run your code in a local container before deploying to SageMaker. This can speed up iterative testing and debugging while using the same familiar Python SDK interface. You just need to set local_mode = True."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# run in local mode?\n",
    "local_mode = False\n",
    "\n",
    "env_type = 'tsp-easy'\n",
    "\n",
    "# create unique job name \n",
    "job_name_prefix = 'rl-' + env_type\n",
    "\n",
    "# S3 bucket\n",
    "sage_session = sagemaker.session.Session()\n",
    "s3_bucket = sage_session.default_bucket()  \n",
    "s3_output_path = 's3://{}/'.format(s3_bucket)\n",
    "print(\"S3 bucket path: {}\".format(s3_output_path))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Install docker for `local` mode\n",
    "\n",
    "In order to work in `local` mode, you need to have docker installed. When running from you local machine, please make sure that you have docker or docker-compose (for local CPU machines) and nvidia-docker (for local GPU machines) installed. Alternatively, when running from a SageMaker notebook instance, you can simply run the following script to install dependenceis.\n",
    "\n",
    "Note, you can only run a single local notebook at one time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# only run from SageMaker notebook instance\n",
    "if local_mode:\n",
    "    !/bin/bash common/setup.sh"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Create an IAM role\n",
    "Either get the execution role when running from a SageMaker notebook `role = sagemaker.get_execution_role()` or, when running from local machine, use utils method `role = get_execution_role('role_name')` to create an execution role."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "try:\n",
    "    role = sagemaker.get_execution_role()\n",
    "except:\n",
    "    role = get_execution_role()\n",
    "\n",
    "print(\"Using IAM role arn: {}\".format(role))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Setup the environment\n",
    "\n",
    "The environment is defined in a Python file called “TSP_env.py” and the file is uploaded on /src directory. \n",
    "\n",
    "The environment also implements the init(), step(), reset() and render() functions that describe how the environment behaves. This is consistent with Open AI Gym interfaces for defining an environment. \n",
    "\n",
    "\n",
    "1. Init() - initialize the environment in a pre-defined state\n",
    "2. Step() - take an action on the environment\n",
    "3. reset()- restart the environment on a new episode\n",
    "4. render() - get a rendered image of the environment in its current state"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Configure the presets for RL algorithm \n",
    "\n",
    "The presets that configure the RL training jobs are defined in the “preset-tsp-easy.py” file which is also uploaded on the /src directory. Using the preset file, you can define agent parameters to select the specific agent algorithm. You can also set the environment parameters, define the schedule and visualization parameters, and define the graph manager. The schedule presets will define the number of heat up steps, periodic evaluation steps, training steps between evaluations.\n",
    "\n",
    "These can be overridden at runtime by specifying the RLCOACH_PRESET hyperparameter. Additionally, it can be used to define custom hyperparameters. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!pygmentize src/preset-tsp-easy.py"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Write the Training Code \n",
    "\n",
    "The training code is written in the file “train-coach.py” which is uploaded in the /src directory. \n",
    "First import the environment files and the preset files, and then define the main() function. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!pygmentize src/train-coach.py"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Train the RL model using the Python SDK Script mode\n",
    "\n",
    "If you are using local mode, the training will run on the notebook instance. When using SageMaker for training, you can select a GPU or CPU instance. The RLEstimator is used for training RL jobs. \n",
    "\n",
    "1. Specify the source directory where the environment, presets and training code is uploaded.\n",
    "2. Specify the entry point as the training code \n",
    "3. Specify the choice of RL toolkit and framework. This automatically resolves to the ECR path for the RL Container. \n",
    "4. Define the training parameters such as the instance count, job name, S3 path for output and job name. \n",
    "5. Specify the hyperparameters for the RL agent algorithm. The RLCOACH_PRESET or the RLRAY_PRESET can be used to specify the RL agent algorithm you want to use. \n",
    "6. Define the metrics definitions that you are interested in capturing in your logs. These can also be visualized in CloudWatch and SageMaker Notebooks. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "\n",
    "if local_mode:\n",
    "    instance_type = 'local'\n",
    "else:\n",
    "    instance_type = \"ml.m4.4xlarge\"\n",
    "    \n",
    "estimator = RLEstimator(entry_point=\"train-coach.py\",\n",
    "                        source_dir='src',\n",
    "                        dependencies = [\"common/sagemaker_rl\"],\n",
    "                        toolkit=RLToolkit.COACH,\n",
    "                        toolkit_version='0.11.0',\n",
    "                        framework=RLFramework.TENSORFLOW,\n",
    "                        role=role,\n",
    "                        train_instance_type=instance_type,\n",
    "                        train_instance_count=1,\n",
    "                        output_path=s3_output_path,\n",
    "                        base_job_name=job_name_prefix,\n",
    "                        hyperparameters = {\n",
    "                          #expected run time 12 mins for TSP Easy  \n",
    "                          \"RLCOACH_PRESET\": \"preset-\" + env_type, \n",
    "                        }\n",
    "                    )\n",
    "\n",
    "estimator.fit(wait=local_mode)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Store intermediate training output and model checkpoints \n",
    "\n",
    "The output from the training job above is stored on S3. The intermediate folder contains gifs and metadata of the training."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "job_name=estimator._current_job_name\n",
    "print(\"Job name: {}\".format(job_name))\n",
    "\n",
    "s3_url = \"s3://{}/{}\".format(s3_bucket,job_name)\n",
    "\n",
    "if local_mode:\n",
    "    output_tar_key = \"{}/output.tar.gz\".format(job_name)\n",
    "else:\n",
    "    output_tar_key = \"{}/output/output.tar.gz\".format(job_name)\n",
    "\n",
    "intermediate_folder_key = \"{}/output/intermediate\".format(job_name)\n",
    "output_url = \"s3://{}/{}\".format(s3_bucket, output_tar_key)\n",
    "intermediate_url = \"s3://{}/{}\".format(s3_bucket, intermediate_folder_key)\n",
    "\n",
    "print(\"S3 job path: {}\".format(s3_url))\n",
    "print(\"Output.tar.gz location: {}\".format(output_url))\n",
    "print(\"Intermediate folder path: {}\".format(intermediate_url))\n",
    "    \n",
    "tmp_dir = \"/tmp/{}\".format(job_name)\n",
    "os.system(\"mkdir {}\".format(tmp_dir))\n",
    "print(\"Create local folder {}\".format(tmp_dir))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Visualization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Comparing against a baseline policy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!pip install gym"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!pip install pygame"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "os.chdir(\"src\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Get baseline reward\n",
    "from TSP_env import TSPEasyEnv\n",
    "from TSP_baseline import get_mean_baseline_reward\n",
    "baseline_mean, baseline_std_dev = get_mean_baseline_reward(env=TSPEasyEnv(),num_of_episodes=1)\n",
    "print(baseline_mean,baseline_std_dev)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "os.chdir(\"../\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Plot metrics for training job\n",
    "We can pull the reward metric of the training and plot it to see the performance of the model over time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import matplotlib\n",
    "%matplotlib inline\n",
    "\n",
    "# csv_file has all the RL training metrics\n",
    "# csv_file = \"{}/worker_0.simple_rl_graph.main_level.main_level.agent_0.csv\".format(tmp_dir)\n",
    "csv_file_name = \"worker_0.simple_rl_graph.main_level.main_level.agent_0.csv\"\n",
    "key = intermediate_folder_key + \"/\" + csv_file_name\n",
    "wait_for_s3_object(s3_bucket, key, tmp_dir)\n",
    "\n",
    "csv_file = \"{}/{}\".format(tmp_dir, csv_file_name)\n",
    "df = pd.read_csv(csv_file)\n",
    "x_axis = 'Episode #'\n",
    "y_axis_rl = 'Training Reward'\n",
    "y_axis_base = 'Baseline Reward'\n",
    "df[y_axis_rl] = df[y_axis_rl].rolling(5).mean()\n",
    "df[y_axis_base] = baseline_mean\n",
    "y_axes = [y_axis_rl]\n",
    "ax = df.plot(x=x_axis,y=[y_axis_rl,y_axis_base], figsize=(18,6), fontsize=18, legend=True, color=['b','r'])\n",
    "fig = ax.get_figure()\n",
    "ax.set_xlabel(x_axis,fontsize=20)\n",
    "#ax.set_ylabel(y_axis,fontsize=20)\n",
    "#fig.savefig('training_reward_vs_wall_clock_time.pdf')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Visualize the rendered gifs\n",
    "The latest gif file found in the gifs directory is displayed. You can replace the tmp.gif file below to visualize other files generated."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "key = intermediate_folder_key + '/gifs'\n",
    "wait_for_s3_object(s3_bucket, key, tmp_dir)    \n",
    "print(\"Copied gifs files to {}\".format(tmp_dir))\n",
    "\n",
    "glob_pattern = os.path.join(\"{}/*.gif\".format(tmp_dir))\n",
    "gifs = [file for file in glob.iglob(glob_pattern, recursive=True)]\n",
    "extract_episode = lambda string: int(re.search('.*episode-(\\d*)_.*', string, re.IGNORECASE).group(1))\n",
    "gifs.sort(key=extract_episode)\n",
    "print(\"GIFs found:\\n{}\".format(\"\\n\".join([os.path.basename(gif) for gif in gifs])))    \n",
    "\n",
    "# visualize a specific episode\n",
    "gif_index = -1 # since we want last gif\n",
    "gif_filepath = gifs[gif_index]\n",
    "gif_filename = os.path.basename(gif_filepath)\n",
    "print(\"Selected GIF: {}\".format(gif_filename))\n",
    "os.system(\"mkdir -p ./src/tmp_render/ && cp {} ./src/tmp_render/{}.gif\".format(gif_filepath, gif_filename))\n",
    "HTML('<img src=\"./src/tmp_render/{}.gif\">'.format(gif_filename))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Evaluation of RL models\n",
    "\n",
    "We use the last checkpointed model to run evaluation for the RL Agent. \n",
    "\n",
    "#### Load checkpointed model\n",
    "\n",
    "Checkpointed data from the previously trained models will be passed on for evaluation / inference in the checkpoint channel. In local mode, we can simply use the local directory, whereas in the SageMaker mode, it needs to be moved to S3 first."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "\n",
    "wait_for_s3_object(s3_bucket, output_tar_key, tmp_dir)  \n",
    "\n",
    "if not os.path.isfile(\"{}/output.tar.gz\".format(tmp_dir)):\n",
    "    raise FileNotFoundError(\"File output.tar.gz not found\")\n",
    "os.system(\"tar -xvzf {}/output.tar.gz -C {}\".format(tmp_dir, tmp_dir))\n",
    "\n",
    "if local_mode:\n",
    "    checkpoint_dir = \"{}/data/checkpoint\".format(tmp_dir)\n",
    "else:\n",
    "    checkpoint_dir = \"{}/checkpoint\".format(tmp_dir)\n",
    "\n",
    "print(\"Checkpoint directory {}\".format(checkpoint_dir))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "\n",
    "if local_mode:\n",
    "    checkpoint_path = 'file://{}'.format(checkpoint_dir)\n",
    "    print(\"Local checkpoint file path: {}\".format(checkpoint_path))\n",
    "else:\n",
    "    checkpoint_path = \"s3://{}/{}/checkpoint/\".format(s3_bucket, job_name)\n",
    "    if not os.listdir(checkpoint_dir):\n",
    "        raise FileNotFoundError(\"Checkpoint files not found under the path\")\n",
    "    os.system(\"aws s3 cp --recursive {} {}\".format(checkpoint_dir, checkpoint_path))\n",
    "    print(\"S3 checkpoint file path: {}\".format(checkpoint_path))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Run the evaluation step\n",
    "\n",
    "Use the checkpointed model to run the evaluation step. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "estimator_eval = RLEstimator(role=role,\n",
    "                             source_dir='src/',\n",
    "                             dependencies = [\"common/sagemaker_rl\"],\n",
    "                             toolkit=RLToolkit.COACH,\n",
    "                             toolkit_version='0.11.0',\n",
    "                             framework=RLFramework.TENSORFLOW,\n",
    "                             entry_point=\"evaluate-coach.py\",\n",
    "                             train_instance_count=1,\n",
    "                             train_instance_type=instance_type,\n",
    "                             hyperparameters = {\n",
    "                                 \"RLCOACH_PRESET\": \"preset-tsp-easy\",\n",
    "                                 \"evaluate_steps\": 200, #max 4 episodes\n",
    "                             }\n",
    "                            )\n",
    "\n",
    "estimator_eval.fit({'checkpoint': checkpoint_path})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Medium version of TSP <a name=\"TSP-Medium\"></a>\n",
    "We make the problem much harder in this version by randomizing the location of destiations each episode. Hence, RL agent has to come up with a general strategy to navigate the grid. Parameters, states, actions, and rewards are identical to the Easy version of TSP.\n",
    "\n",
    "### States\n",
    "At each time step, our agent is aware of the following information:\n",
    "\n",
    "1. For the Restuarant:\n",
    "    1. Location (x,y coordinates)\n",
    "    \n",
    "2. For the Driver\n",
    "    1. Location (x,y coordinates)\n",
    "    2. Is driver at restaurant (yes/no)\n",
    "\n",
    "3. For each Order: \n",
    "    1. Location (x,y coordinates)\n",
    "    2. Status (Delivered or Not Delivered)\n",
    "    3. Time (Time taken to deliver reach order -- incrementing until delivered)\n",
    "4. Miscellaneous\n",
    "    1. Time since start of episode\n",
    "    2. Time remaining until end of episode (i.e. until max time)\n",
    "\n",
    "\n",
    "### Actions\n",
    "At each time step, our agent can take the following steps:\n",
    "- Up - Move one step up in the map\n",
    "- Down - Move one step down in the map\n",
    "- Right - Move one step right in the map\n",
    "- Left - Move one step left in the map\n",
    "\n",
    "### Rewards\n",
    "Agent gets a reward of -1 for each time step. If an order is delivered in that timestep, it gets a positive reward inversely proportional to the time taken to deliver. If all the orders are delivered and the agent is back to the restaurant, it gets an additional reward inversely proportional to time since start of episode."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Using AWS SageMaker for RL <a name=\"SM-TSP-Medium\"></a>\n",
    "\n",
    "### Train the model using Python SDK/Script mode\n",
    "\n",
    "Skipping through the basic setup, assuming you did that already for the easy version. For good results, we suggest you train for at least 1,000,000 steps. You can edit this either as a hyperparameter in the cell or directly change the preset file."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "\n",
    "# run in local mode?\n",
    "local_mode = False\n",
    "\n",
    "# create unique job name \n",
    "job_name_prefix = 'rl-tsp-medium'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "\n",
    "if local_mode:\n",
    "    instance_type = 'local'\n",
    "else:\n",
    "    instance_type = \"ml.m4.4xlarge\"\n",
    "    \n",
    "estimator = RLEstimator(entry_point=\"train-coach.py\",\n",
    "                        source_dir='src',\n",
    "                        dependencies = [\"common/sagemaker_rl\"],\n",
    "                        toolkit=RLToolkit.COACH,\n",
    "                        toolkit_version='0.11.0',\n",
    "                        framework=RLFramework.TENSORFLOW,\n",
    "                        role=role,\n",
    "                        train_instance_type=instance_type,\n",
    "                        train_instance_count=1,\n",
    "                        output_path=s3_output_path,\n",
    "                        base_job_name=job_name_prefix,\n",
    "                        hyperparameters = {\n",
    "                          \"RLCOACH_PRESET\": \"preset-tsp-medium\",\n",
    "                        }\n",
    "                    )\n",
    "\n",
    "estimator.fit(wait=local_mode)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Visualize, Compare with Baseline and Evaluate\n",
    "\n",
    "You can follow the same set of code used for TSP easy version."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Vehicle Routing Problem with Reinforcement Learning <a name=\"VRP-Easy\"></a>\n",
    "\n",
    "Vehicle Routing Problem (VRP) is a similar problem where the algorithm optimizes the movement of a fleet of vehicles. Our VRP formulation is a bit different, we have a delivery driver who accepts orders from customers, picks up food from a restaurant and delivers it to the customer. The driver optimizes to increase the number of successful deliveries within a time limit.\n",
    "\n",
    "Key differences from TSP: \n",
    "\n",
    "- Pathing is now automatic.  Instead of choosing \"left, right, up, down\", now you just select your destination as your action.  The environment will get you there in the fewest steps possible.\n",
    "- Since the routing/pathing is now taken care of, we add in complexity elsewhere...\n",
    "- There can be more than one restaurant, each with a different type of order (e.g. Pizzas vs. Burritos).  Each order will have a different type, and you have to visit the correct restuarant to pick up an order before dropping it off.\n",
    "- Drivers have a limited capacity; they cannot pick up an infinite number of orders.  Instead, they can only have (e.g. 5) orders in the car at any given time.  This means they will have to return to the restaurant(s) in between deliveries to pick up more supply.\n",
    "- Orders now come in dynamically over time, rather than all being known at time zero.  Each time step, there is some probability that an order will be generated.  \n",
    "- As the driver/agent, we now have the choice to fulfill an order or not -- there's no penalty associated with not accepting an order, but a potential penalty if we accept an order and fail to deliver it before Timeout.\n",
    "\n",
    "### States\n",
    "At each time step, our agent is aware of the following information:\n",
    "\n",
    "1. For each Restuarant:\n",
    "    1. Location (x,y coordinates)\n",
    "    \n",
    "1. For the Driver\n",
    "    1. Location (x,y coordinates)\n",
    "    2. Capacity (maximum # of orders you can carry, at one time, on the driver)\n",
    "    3. Used Capacity (# of orders you currently carry on the driver)\n",
    "\n",
    "1. For each Order: \n",
    "    1. Location (x,y coordinates)\n",
    "    2. Status (Accepted, Not Accepted, Delivered, Not Delivered)\n",
    "    3. Type (Which restuarant the order belongs to, like Pizza, or Burrito)\n",
    "    4. Time (Time since order was generated)\n",
    "    5. Promise (If you deliver the order by this time, you get a bonus reward)\n",
    "    6. Timeout (If you deliver the order after this time, you get a penalty)\n",
    "\n",
    "### Actions\n",
    "At each time step, our agent can do ONE of the following:\n",
    "- Choose a restaurant to visit (incremental step L,R,U,D, will be auto-pathed)\n",
    "- Choose an order to visit (incremental step L,R,U,D, will be auto-pathed)\n",
    "- Accept an order (no movement will occur)\n",
    "- Do nothing\n",
    "\n",
    "### Rewards\n",
    "- Driver gets a reward of -1 for each time step. \n",
    "- If driver delivers order, get a reward proportional to the time taken to deliver (extra bonus for beating Promise time)\n",
    "- If order expires (reaches Timeout), get a penalty"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Using AWS SageMaker RL <a name=\"SM-VRP-Easy\"></a>\n",
    "\n",
    "### Train the model using Python SDK/Script mode\n",
    "\n",
    "Skipping through the basic setup, assuming you did that already for the easy version. For good results, we suggest a minimum of 5,000,000 steps of training."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "\n",
    "# run in local mode?\n",
    "local_mode = False\n",
    "\n",
    "# create unique job name \n",
    "job_name_prefix = 'rl-vrp-easy'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "\n",
    "if local_mode:\n",
    "    instance_type = 'local'\n",
    "else:\n",
    "    instance_type = \"ml.m4.4xlarge\"\n",
    "    \n",
    "estimator = RLEstimator(entry_point=\"train-coach.py\",\n",
    "                        source_dir='src',\n",
    "                        dependencies = [\"common/sagemaker_rl\"],\n",
    "                        toolkit=RLToolkit.COACH,\n",
    "                        toolkit_version='0.11.0',\n",
    "                        framework=RLFramework.TENSORFLOW,\n",
    "                        role=role,\n",
    "                        train_instance_type=instance_type,\n",
    "                        train_instance_count=1,\n",
    "                        output_path=s3_output_path,\n",
    "                        base_job_name=job_name_prefix,\n",
    "                        hyperparameters = {\n",
    "                          \"RLCOACH_PRESET\": \"preset-vrp-easy\",\n",
    "                        }\n",
    "                    )\n",
    "\n",
    "estimator.fit(wait=local_mode)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Visualize, Compare with Baseline and Evaluate\n",
    "\n",
    "You can follow the same set of code used for TSP easy version."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "conda_tensorflow_p36",
   "language": "python",
   "name": "conda_tensorflow_p36"
  },
  "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.5"
  },
  "notice": "Copyright 2018 Amazon.com, Inc. or its affiliates. All Rights Reserved. Licensed under the Apache License, Version 2.0 (the \"License\"). You may not use this file except in compliance with the License. A copy of the License is located at http://aws.amazon.com/apache2.0/ or in the \"license\" file accompanying this file. This file is distributed on an \"AS IS\" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License."
 },
 "nbformat": 4,
 "nbformat_minor": 1
}