roboarm-finding-shortest-path.ipynb

{"metadata":{"kernelspec":{"language":"python","display_name":"Python 3","name":"python3"},"language_info":{"pygments_lexer":"ipython3","nbconvert_exporter":"python","version":"3.6.4","file_extension":".py","codemirror_mode":{"name":"ipython","version":3},"name":"python","mimetype":"text/x-python"}},"nbformat_minor":4,"nbformat":4,"cells":[{"source":"<a href=\"https://www.kaggle.com/code/patimejia/roboarm-competition-finding-the-shortest-path?scriptVersionId=136622330\" target=\"_blank\"><img align=\"left\" alt=\"Kaggle\" title=\"Open in Kaggle\" src=\"https://kaggle.com/static/images/open-in-kaggle.svg\"></a>","metadata":{},"cell_type":"markdown"},{"cell_type":"markdown","source":"# Optimizing Robotic Arm Competition: Minimizing Channel Swapping and Link Costs by Finding the Shortest Path\n\nThe first robotic arm competition utilized a model that can efficiently find the shortest path between the start and end points without any collisions. The objective was to minimize the cost of changing channels and links.\n\nThis notebook showcases a solution to the Santa optimization problem. The solution includes creating a submission file for the competition using either a greedy algorithm or an A-star algorithm to find the shortest path. However, no heuristic function or prioritization was implemented.\n\nCurrently, the submitted file contains a simple solution for the entire eight-link arm. While a better algorithm exists, it requires a significant amount of time to run, and further learning is necessary to implement it effectively.","metadata":{}},{"cell_type":"markdown","source":"# Welcome to *The Christmas Card Conundrum*! #\n\nEach year Kaggle hosts a special Santa-themed optimization challenge. This year you're challenged to optimize the path of a robotic arm over the points of an image, minimizing both the movement of the arm and the change in color from step to step.\n\nThis notebook introduces the problem and defines a number of convenience functions you might find useful. We also look at the problem's \"configuration space\", which might provide a more natural setting for optimization. Finally, we create a simple baseline submission.","metadata":{}},{"cell_type":"code","source":"import matplotlib.pyplot as plt\nimport matplotlib.ticker as ticker\nimport numpy as np\nimport pandas as pd\nfrom functools import *\nfrom itertools import *\nfrom pathlib import Path\nfrom PIL import Image\n\nplt.style.use('seaborn-whitegrid')\n\ndata_dir = Path('/kaggle/input/santa-2022')","metadata":{"_kg_hide-input":true,"execution":{"iopub.status.busy":"2022-12-20T15:59:49.216135Z","iopub.execute_input":"2022-12-20T15:59:49.216664Z","iopub.status.idle":"2022-12-20T15:59:49.222489Z","shell.execute_reply.started":"2022-12-20T15:59:49.216636Z","shell.execute_reply":"2022-12-20T15:59:49.221451Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# The Image #\n\nThe `image.csv` file contains the canonical color values for the image as well as their respective Cartesian coordinates. (Instead of array indicies, we use Cartesian coordinates to refer to points in the image, with the center of the image at `(0, 0)`.) This file is what you should use when computing the score for your solution. It's the same file that the official scoring function uses.","metadata":{}},{"cell_type":"code","source":"df_image = pd.read_csv(data_dir / 'image.csv')\n\ndf_image","metadata":{"execution":{"iopub.status.busy":"2022-12-20T15:59:49.224089Z","iopub.execute_input":"2022-12-20T15:59:49.224489Z","iopub.status.idle":"2022-12-20T15:59:49.423533Z","shell.execute_reply.started":"2022-12-20T15:59:49.224462Z","shell.execute_reply":"2022-12-20T15:59:49.422553Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Here we'll define some convenience functions to transform the image between various formats and then transform the dataframe into a numpy array.","metadata":{}},{"cell_type":"code","source":"# Functions to map between cartesian coordinates and array indexes\ndef cartesian_to_array(x, y, shape):\n    m, n = shape[:2]\n    i = (n - 1) // 2 - y\n    j = (n - 1) // 2 + x\n    if i < 0 or i >= m or j < 0 or j >= n:\n        raise ValueError(\"Coordinates not within given dimensions.\")\n    return i, j\n\n\ndef array_to_cartesian(i, j, shape):\n    m, n = shape[:2]\n    if i < 0 or i >= m or j < 0 or j >= n:\n        raise ValueError(\"Coordinates not within given dimensions.\")\n    y = (n - 1) // 2 - i\n    x = j - (n - 1) // 2\n    return x, y\n\n\npoint = (1, 8)\nshape = (9, 9, 3)\nassert cartesian_to_array(*array_to_cartesian(*point, shape), shape) == point\n\n\n# Functions to map an image between array and record formats\ndef image_to_dict(image):\n    image = np.atleast_3d(image)\n    kv_image = {}\n    for i, j in product(range(len(image)), repeat=2):\n        kv_image[array_to_cartesian(i, j, image.shape)] = tuple(image[i, j])\n    return kv_image\n\n\ndef image_to_df(image):\n    return pd.DataFrame(\n        [(x, y, r, g, b) for (x, y), (r, g, b) in image_to_dict(image).items()],\n        columns=['x', 'y', 'r', 'g', 'b']\n    )\n\n\ndef df_to_image(df):\n    side = int(len(df) ** 0.5)  # assumes a square image\n    return df.set_index(['x', 'y']).to_numpy().reshape(side, side, -1)","metadata":{"execution":{"iopub.status.busy":"2022-12-20T15:59:49.424754Z","iopub.execute_input":"2022-12-20T15:59:49.425511Z","iopub.status.idle":"2022-12-20T15:59:49.438158Z","shell.execute_reply.started":"2022-12-20T15:59:49.425475Z","shell.execute_reply":"2022-12-20T15:59:49.4365Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"> ### my notes:\n>\n>- `cartesian_to_array` converts the cartesian coordinates to array indexes and gives the shape of the image\n>\n> - `image_to_dict` converts the image to a dictionary by mapping the cartesian coordinates to the RGB values. For example, the pixel at (1, 8) has RGB values (0, 0, 0)","metadata":{}},{"cell_type":"code","source":"image = df_to_image(df_image)\nassert image_to_df(image).equals(df_image)  # ensure transforms are inverses\n\nradius = 128\nfig, ax = plt.subplots(figsize=(10, 10))\nax.matshow(image, extent=(-radius, radius+1, -radius, radius+1))\nax.grid(None);","metadata":{"execution":{"iopub.status.busy":"2022-12-20T15:59:49.440576Z","iopub.execute_input":"2022-12-20T15:59:49.440952Z","iopub.status.idle":"2022-12-20T15:59:50.030954Z","shell.execute_reply.started":"2022-12-20T15:59:49.440922Z","shell.execute_reply":"2022-12-20T15:59:50.029953Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"> ### my notes:\n>\n>- `assert image_to_df(image).equals(df_image)` this line of code does nothing. It is used to check if the image is equal to the dataframe. If it is equal, then the assert statement does nothing. If it is not equal, then the assert statement throws an error.\n>\n> - `assert` is a no-op in optimized code. no-op means no operation. It is a statement that does nothing. It is used as a placeholder when a statement is required syntactically, but no code needs to be executed. \n>\n> - `ax.matshow(image, extent=(-radius, radius+1, -radius, radius+1))`: this line of code makes the image appear in the notebook\n>\n> - `ax.grid(None);`: this line of code removes the grid from the image","metadata":{}},{"cell_type":"markdown","source":"# The Robotic Arm #\n\nThe robotic arm has eight links of length 64, 32, 16, 8, 4, 2, 1, and 1 connected at joints like so:","metadata":{}},{"cell_type":"markdown","source":"> ## my note:\n- q1 is joint 1\n- q2 is joint 2\n- q3 is joint 3\n- q4 is joint 4\n- q5 is joint 5\n- q6 is joint 6\n- q7 is joint 7\n- q8 is joint 8\n","metadata":{}},{"cell_type":"code","source":"# l is the robotic arm link length\nl1 = 64\nl2 = 32\nl3 = 16\nl4 = 8\nl5 = 4\nl6 = 2\nl7 = 1\nl8 = 1","metadata":{"execution":{"iopub.status.busy":"2022-12-20T15:59:50.03384Z","iopub.execute_input":"2022-12-20T15:59:50.035139Z","iopub.status.idle":"2022-12-20T15:59:50.040229Z","shell.execute_reply.started":"2022-12-20T15:59:50.035081Z","shell.execute_reply":"2022-12-20T15:59:50.039195Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":">\n> -------------\n>","metadata":{}},{"cell_type":"code","source":"def plot_configuration(config, image=None, ax=None, color='0.25', **figure_args):\n    def get_position(config):\n        return reduce(lambda p, q: (p[0] + q[0], p[1] + q[1]), config, (0, 0))\n\n    if ax is None:\n        _, ax = plt.subplots(**figure_args)\n\n    k = 2 ** (len(config) - 1) + 1\n    X, Y = (np.vstack([[(0, 0)], np.asarray(config).cumsum(axis=0)])[:-1].T - 0.5)\n    U, V = np.asarray(config).T \n    ax.quiver(\n        X, Y, U, V,\n        angles='xy', scale_units='xy', scale=1,\n        color=color,\n        width=0.005,\n        zorder=10,\n    )\n    point = get_position(config)\n    ax.plot(point[0]-0.5, point[1]-0.5, '.', color='k', zorder=11)\n    if image is not None:\n        ax.matshow(image, extent=[-k-1, k, -k-1, k])\n    ax.set_xlim(-k-1, k)\n    ax.set_ylim(-k-1, k)\n    ax.set_aspect('equal')\n    ax.set_xticks(np.arange(-k, k+1))\n    ax.set_yticks(np.arange(-k, k+1))\n    return ax","metadata":{"_kg_hide-input":true,"execution":{"iopub.status.busy":"2022-12-20T15:59:50.041484Z","iopub.execute_input":"2022-12-20T15:59:50.042825Z","iopub.status.idle":"2022-12-20T15:59:50.057474Z","shell.execute_reply.started":"2022-12-20T15:59:50.042766Z","shell.execute_reply":"2022-12-20T15:59:50.056059Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"> ### my notes\n>\n> - `X, Y = (np.vstack([[(0, 0)], np.asarray(config).cumsum(axis=0)])[:-1].T - 0.5)`:  `vstack` stacks the arrays vertically. `cumsum` adds the elements of the array. `T` transposes the array.\n>\n> -  `ax.plot(point[0]-0.5, point[1]-0.5, '.', color='k', zorder=11)`: we use -.5 to center the point on the pixel because the pixel is 1x1 and the point is 0x0. otherwise the point will be on the edge of the pixel and not in the middle of the pixel. ","metadata":{}},{"cell_type":"code","source":"ax = plot_configuration([(64, 0), (32, 0), (16, 0), (8, 0), (4, 0), (2, 0), (1, 0), (1, 0)], figsize=(20, 1))\nax.set_xlim(0, radius+1)\nax.set_ylim(-1, 0)\nax.grid(None)\nax.set_aspect('auto')","metadata":{"_kg_hide-input":true,"execution":{"iopub.status.busy":"2022-12-20T15:59:50.058766Z","iopub.execute_input":"2022-12-20T15:59:50.05906Z","iopub.status.idle":"2022-12-20T15:59:51.647017Z","shell.execute_reply.started":"2022-12-20T15:59:50.059012Z","shell.execute_reply":"2022-12-20T15:59:51.64622Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":">\n> -------------\n>","metadata":{}},{"cell_type":"markdown","source":"We'll use arms with fewer links for most of the examples to simplify the presentation, however. Here's an arm with links of length 2, 1, and 1.","metadata":{}},{"cell_type":"code","source":"ax = plot_configuration([(2, 0), (1, 0), (1, 0)], figsize=(10, 1))\nax.set_xlim(0, 4)\nax.set_ylim(-1, 0)\nax.grid([])\nax.set_aspect('auto')","metadata":{"_kg_hide-input":true,"execution":{"iopub.status.busy":"2022-12-20T15:59:51.648302Z","iopub.execute_input":"2022-12-20T15:59:51.648846Z","iopub.status.idle":"2022-12-20T15:59:51.754611Z","shell.execute_reply.started":"2022-12-20T15:59:51.64881Z","shell.execute_reply":"2022-12-20T15:59:51.753563Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":">\n> -------------\n>","metadata":{}},{"cell_type":"markdown","source":"> ### my notes \n> ### finding different color channels\n","metadata":{}},{"cell_type":"code","source":"#The following code shows the red channel:\n\nfig, ax = plt.subplots(figsize=(10, 10))\nax.matshow(image[:, :, 0], extent=(-radius, radius+1, -radius, radius+1))\nax.set_title('Red Channel')\nax.grid(None);\n\n# The following code shows the green channel:\nfig, ax = plt.subplots(figsize=(10, 10))\nax.matshow(image[:, :, 1], extent=(-radius, radius+1, -radius, radius+1))\nax.set_title('Green Channel')\nax.grid(None);\n\n\n# The following code shows the blue channel:\nfig, ax = plt.subplots(figsize=(10, 10))\nax.matshow(image[:, :, 2], extent=(-radius, radius+1, -radius, radius+1))\nax.set_title('Blue Channel')\nax.grid(None);","metadata":{"execution":{"iopub.status.busy":"2022-12-20T15:59:51.756007Z","iopub.execute_input":"2022-12-20T15:59:51.756378Z","iopub.status.idle":"2022-12-20T15:59:52.453238Z","shell.execute_reply.started":"2022-12-20T15:59:51.75634Z","shell.execute_reply":"2022-12-20T15:59:52.451448Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":">\n> -------------\n>","metadata":{}},{"cell_type":"markdown","source":"We describe the **configuration** of the arm by giving the displacement vector of each link oriented at its joint. The first link (the longest one) is oriented at the point $(0, 0)$, so we can get the **position** of the arm by summing up the displacement vectors.\n\nHere's an example with a four-link arm.","metadata":{}},{"cell_type":"code","source":"def get_position(config):\n    return reduce(lambda p, q: (p[0] + q[0], p[1] + q[1]), config, (0, 0))\n\n\n# The configuration of a 4-link arm descibed by a list of displacement vectors. \nconfig = [(4, 0), (-2, 2), (-1, 0), (-1, 1)]\n\nget_position(config)","metadata":{"execution":{"iopub.status.busy":"2022-12-20T15:59:52.454542Z","iopub.execute_input":"2022-12-20T15:59:52.454924Z","iopub.status.idle":"2022-12-20T15:59:52.464666Z","shell.execute_reply.started":"2022-12-20T15:59:52.454873Z","shell.execute_reply":"2022-12-20T15:59:52.463519Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"> ### my notes\n> #### End effector\n> - `get_position` returns the position of the **end effector** of the arm. It is the sum of the displacement vectors starting from the origin.\n> - **end effector** is the position of the end of the arm. It is usually the position of the gripper of the arm or the position of the tip of the arm where the tool is attached.","metadata":{}},{"cell_type":"code","source":"config = [(4, 0), (-2, 2), (-1, 0), (-1, 1)]\n\nprint('The end effector of the arm is at position {}'.format(get_position(config)))\n","metadata":{"execution":{"iopub.status.busy":"2022-12-20T15:59:52.466399Z","iopub.execute_input":"2022-12-20T15:59:52.467069Z","iopub.status.idle":"2022-12-20T15:59:52.479525Z","shell.execute_reply.started":"2022-12-20T15:59:52.466937Z","shell.execute_reply":"2022-12-20T15:59:52.478454Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":">\n> -------------\n>","metadata":{}},{"cell_type":"markdown","source":"> ### my notes:\n>\n>  code below displays a plot of the arm's configuration with the image overlaid on top of it.\n","metadata":{}},{"cell_type":"code","source":"# The following code plots the configuration of the arm with the image overlaid\nax = plot_configuration(config, image=image, figsize=(6, 6), dpi=90)\nax.set_xlim(-4, 4)\nax.set_ylim(-4, 4)\nax.xaxis.set_major_locator(plt.MaxNLocator(9))\nax.yaxis.set_major_locator(plt.MaxNLocator(9))\nax.set_xlabel('x')\nax.set_ylabel('y')\nax.set_title('Configuration of a 4-link arm');\n\n# arrow that points to the `end efffector`\nax.quiver(-.5, -.5, *get_position(config), angles='xy', scale_units='xy', scale=1, color='r', width=0.005, zorder=10)\nax.legend(['End Effector']);","metadata":{"execution":{"iopub.status.busy":"2022-12-20T15:59:52.480948Z","iopub.execute_input":"2022-12-20T15:59:52.481767Z","iopub.status.idle":"2022-12-20T15:59:52.826846Z","shell.execute_reply.started":"2022-12-20T15:59:52.481729Z","shell.execute_reply":"2022-12-20T15:59:52.826096Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":">\n> -------------\n>","metadata":{}},{"cell_type":"code","source":"ax = plot_configuration(config, figsize=(6, 6), dpi=90)\nax.set_title(f\"Configuration {config}\\nPosition {get_position(config)}\");","metadata":{"_kg_hide-input":true,"execution":{"iopub.status.busy":"2022-12-20T15:59:52.828006Z","iopub.execute_input":"2022-12-20T15:59:52.828778Z","iopub.status.idle":"2022-12-20T15:59:53.102384Z","shell.execute_reply.started":"2022-12-20T15:59:52.82875Z","shell.execute_reply":"2022-12-20T15:59:53.101107Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"A link of length $l$ with displacement vector $(x, y)$ must satisfy the condition $\\max\\left(\\mid x \\mid, \\mid y \\mid\\right)=l$. (This condition essentially defines what it means for a link to have length $l$.) The links, in other words, travel around the perimeter of a square with sides of length $2l$.","metadata":{}},{"cell_type":"code","source":"def rotate_link(vector, direction):\n    x, y = vector\n    if direction == 1:  # counter-clockwise\n        if y >= x and y > -x:\n            x -= 1\n        elif y > x and y <= -x:\n            y -= 1\n        elif y <= x and y < -x:\n            x += 1\n        else:\n            y += 1\n    elif direction == -1:  # clockwise\n        if y > x and y >= -x:\n            x += 1\n        elif y >= x and y < -x:\n            y += 1\n        elif y < x and y <= -x:\n            x -= 1\n        else:\n            y -= 1\n    return (x, y)\n\n\ndef rotate(config, i, direction):\n    config = config.copy()\n    config[i] = rotate_link(config[i], direction)\n    return config\n\n\ndef get_square(link_length):\n    link = (link_length, 0)\n    coords = [link]\n    for _ in range(8 * link_length - 1):\n        link = rotate_link(link, direction=1)\n        coords.append(link)\n    return coords","metadata":{"collapsed":false,"jupyter":{"outputs_hidden":false},"execution":{"iopub.status.busy":"2022-12-20T15:59:53.107606Z","iopub.execute_input":"2022-12-20T15:59:53.108368Z","iopub.status.idle":"2022-12-20T15:59:53.120394Z","shell.execute_reply.started":"2022-12-20T15:59:53.108333Z","shell.execute_reply":"2022-12-20T15:59:53.118979Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"> ### my notes:\n>\n> - The displacement vector of a link must be one of the following: ($l$, 0), (-$l$, 0), (0, $l$), or (0, -$l$).\n>\n> - This is because the maximum of the absolute value of the $x$ and $y$ components of the displacement vector is l and the other component becomes 0.\n>\n> - This means that the link travels around the perimeter of a $square$ 🔳 with sides of length $2l$\n>\n> - `rotate_link` returns the displacement vector of a link after rotating it $clockwise$ (-1) or $counter-clockwise$ (1) by 45°📐. \n>\n> - The rotation is done by changing the displacement vector of the link by one of the following: (1, 0), (-1, 0), (0, 1), or (0, -1) depending on the direction of rotation and the current displacement vector of the link.\n>\n> - i.e. counter-clockwise rotation of a link with displacement vector ($l$, 0) will result in a displacement vector of ($l$-1, 0).\n    ","metadata":{}},{"cell_type":"markdown","source":"In addition, the vectors must be integer valued, so there are $8l$ possible values for a vector of length $l$.","metadata":{}},{"cell_type":"code","source":"link_length = 2\nsquare = np.asarray(get_square(link_length))\nfig, ax = plt.subplots()\nax.plot(square[:, 0], square[:, 1], 'ok')\nax.plot([0], [0], 'xb')\nax.set_aspect('equal');","metadata":{"_kg_hide-input":true,"execution":{"iopub.status.busy":"2022-12-20T15:59:53.122078Z","iopub.execute_input":"2022-12-20T15:59:53.122393Z","iopub.status.idle":"2022-12-20T15:59:53.287401Z","shell.execute_reply.started":"2022-12-20T15:59:53.122361Z","shell.execute_reply":"2022-12-20T15:59:53.285621Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"> ### my notes\n>\n> - `link_length = 2` because the maximum of the absolute value of the $x$ and $y$ components of the displacement vector is 2 and the other component becomes 0. As a result, the link travels around the perimeter of a square with sides of length 4.\n>\n>- `get_square` returns the displacement vectors of the links of a 4-link arm that travels around the perimeter of a square with sides of length $2l$.","metadata":{}},{"cell_type":"markdown","source":"Here we can see the second link (with length 2) making a complete rotation around all 16 of its possible directions.","metadata":{}},{"cell_type":"code","source":"for _ in range(16):\n    print(config)\n    config = rotate(config, 1, direction=1)","metadata":{"collapsed":false,"jupyter":{"outputs_hidden":false},"execution":{"iopub.status.busy":"2022-12-20T15:59:53.288834Z","iopub.execute_input":"2022-12-20T15:59:53.289153Z","iopub.status.idle":"2022-12-20T15:59:53.296403Z","shell.execute_reply.started":"2022-12-20T15:59:53.289126Z","shell.execute_reply":"2022-12-20T15:59:53.295Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"> ### my notes\n> \n> - the above code displays possible configurations of 4-link arm moving around perimeter of square with sides of length 2l\n>\n> - First configuration is [(4, 0), (-2, 2), (-1, 0), (-1, 1)]\n>\n> - Last configuration is [(4, 0), (-1, 2), (-1, 0), (-1, 1)]\n>\n> - Configurations are listed in clockwise order\n>\n> - There are a total of 16 configurations\n>\n> - Each of the 4 links can be rotated clockwise or counter-clockwise by 45 degrees, resulting in 4*4= 16 configurations","metadata":{}},{"cell_type":"markdown","source":"The design of the arm allows it to reach any position within a $(2L + 1) \\times (2L + 1)$ image, where $L$ is the total length of the arm (the sum of the link lengths). The 8-link arm has a length of 128, so it can reach any position in a $257 \\times 257$ image.","metadata":{}},{"cell_type":"markdown","source":"> ### my notes\n>\n> Describing the ***reachable-workspace*** (and ***collision-free*** area) of a robotic arm jointed with multiple $l-link$.\n>\n> - An 8-link arm with a length of 128 can reach any position within the perimeter of a square with sides of length 256, or within a 257x257 image\n>\n> - A 4-link arm with a length of 8 can reach any position within the perimeter of a square with sides of length 16, or within a 17x17 image\n> \n> - A 2-link arm with a length of 4 can reach any position within the perimeter of a square with sides of length 8, or within a 9x9 image\n> \n> - A 1-link arm with a length of 2 can reach any position within the perimeter of a square with sides of length 4, or within a 5x5 image","metadata":{}},{"cell_type":"markdown","source":">\n> -------------\n>","metadata":{}},{"cell_type":"markdown","source":"### Changing the Configuration ###","metadata":{}},{"cell_type":"markdown","source":"We can move the position of the arm over the image by changing its configuration step-by-step. At each step, we may rotate each link of the arm either counter-clockwise or clockwise (or keep it the same). The **neighbors** of a configuration are those configurations that can be reached from it in a single step.","metadata":{}},{"cell_type":"markdown","source":"> ### my notes\n>\n> - **source configuration** is the current configuration of the robotic arm \n> - **target configuration** is the  desired reachable configuration\n> - **neighbor configuration** is a reachable configurations if rotating a single link once (⟲, ⟳ or none)\n\n","metadata":{}},{"cell_type":"code","source":"def get_neighbors(config):\n    nhbrs = (\n        reduce(lambda x, y: rotate(x, *y), enumerate(directions), config)\n        for directions in product((-1, 0, 1), repeat=len(config))\n    )\n    return list(filter(lambda c: c != config, nhbrs))","metadata":{"collapsed":false,"jupyter":{"outputs_hidden":false},"execution":{"iopub.status.busy":"2022-12-20T15:59:53.298378Z","iopub.execute_input":"2022-12-20T15:59:53.298784Z","iopub.status.idle":"2022-12-20T15:59:53.308263Z","shell.execute_reply.started":"2022-12-20T15:59:53.298754Z","shell.execute_reply":"2022-12-20T15:59:53.306495Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"> ### my notes \n>\n> - this is a generator expression that generates all the neighbors of the configuration config by rotating each link in the configuration config in all three directions (i.e. clockwise, counterclockwise, and not at all) and then combining the resulting configurations into a list of configurations called nhbrs (i.e. the list of neighbors of the configuration config) \n>\n> - configuration config is the **source configuration**","metadata":{}},{"cell_type":"code","source":"neighbors = get_neighbors(config)\n\nlen(neighbors)","metadata":{"collapsed":false,"jupyter":{"outputs_hidden":false},"execution":{"iopub.status.busy":"2022-12-20T15:59:53.310158Z","iopub.execute_input":"2022-12-20T15:59:53.310526Z","iopub.status.idle":"2022-12-20T15:59:53.323542Z","shell.execute_reply.started":"2022-12-20T15:59:53.310497Z","shell.execute_reply":"2022-12-20T15:59:53.322526Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"neighbors = get_neighbors(config) \n\n#  print len(neighbors) with title \nprint(\"The number of neighbors of the configuration config is\", len(neighbors))","metadata":{"execution":{"iopub.status.busy":"2022-12-20T15:59:53.324781Z","iopub.execute_input":"2022-12-20T15:59:53.325184Z","iopub.status.idle":"2022-12-20T15:59:53.335393Z","shell.execute_reply.started":"2022-12-20T15:59:53.325157Z","shell.execute_reply":"2022-12-20T15:59:53.333744Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"point = (0, 0)\ncs = neighbors\nk = 2 ** (len(config) - 1) + 1\ncolors = cycle(plt.rcParams[\"axes.prop_cycle\"].by_key()[\"color\"])\n\nfig, ax = plt.subplots(figsize=(10, 11))\nfor c in cs:\n    X, Y = (np.vstack([[(0, 0)], np.asarray(c).cumsum(axis=0)])[:-1].T - 0.5)\n    U, V = np.asarray(c).T\n    ax.quiver(\n        X, Y, U, V,\n        angles='xy', scale_units='xy', scale=1,\n        color=next(colors),\n        width=0.0025,\n        zorder=10,\n        alpha=0.25,\n    )\n    point = get_position(c)\n    ax.plot(point[0]-0.5, point[1]-0.5, '.', color='k', zorder=11)\npoint = get_position(config)\nax.plot(point[0]-0.5, point[1]-0.5, 'o', color='C3', zorder=11)\nax.set_xlim(-k-1, k)\nax.set_ylim(-k-1, k)\nax.set_aspect('equal')\nax.set_xticks(np.arange(-k, k+1))\nax.set_yticks(np.arange(-k, k+1))\nax.grid(True, color='0.5')\nax.set_title(f\"Neighbors of {config}\", fontsize=20);","metadata":{"_kg_hide-input":true,"execution":{"iopub.status.busy":"2022-12-20T15:59:53.337386Z","iopub.execute_input":"2022-12-20T15:59:53.337736Z","iopub.status.idle":"2022-12-20T15:59:54.022069Z","shell.execute_reply.started":"2022-12-20T15:59:53.337709Z","shell.execute_reply":"2022-12-20T15:59:54.020913Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Note that there will typically be many more neighboring *configurations* (lists of vectors) than neighboring *positions* (points in the image, the sum of the vectors), since each position can typically be reached by many configurations.\n\nIn the figure above, the starting configuration is positioned at the red point. It can reach any of the other indicated positions in a single step (though at varying costs, as we will see).","metadata":{}},{"cell_type":"markdown","source":"# The Cost Function #\n\nThe goal of the competition is to create a sequence of configurations reaching every point in the image while minimizing both a *reconfiguration cost* and a *color cost*. The starting configuration must be `[(64, 0), (-32, 0), (-16, 0), (-8, 0), (-4, 0), (-2, 0), (-1, 0), (-1, 0)]`, which is positioned at the point `(0, 0)` in the image.\n\nThe **reconfiguration cost** at each step is the square root of the number of links rotated at that step, while the **color cost** is the sum of the absolute change in the color components from the previous step's position to the current position multiplied by a scaling constant. The total cost at each step is the sum of the reconfiguration cost and the color cost.","metadata":{}},{"cell_type":"markdown","source":"> ## my notes\n>\n>- minimizing **reconfiguration cost** \n> - $min[count(n)]^{1/2}$ where $n$ is the *number of links rotated in 1-step*\n>\n>- minimizing **color cost**\n","metadata":{}},{"cell_type":"code","source":"# Functions to compute the cost function\n\n# Cost of reconfiguring the robotic arm: the square root of the number of links rotated\ndef reconfiguration_cost(from_config, to_config):\n    nlinks = len(from_config)\n    diffs = np.abs(np.asarray(from_config) - np.asarray(to_config)).sum(axis=1)\n    return np.sqrt(diffs.sum())\n\n\n# Cost of moving from one color to another: the sum of the absolute change in color components\ndef color_cost(from_position, to_position, image, color_scale=3.0):\n    return np.abs(image[to_position] - image[from_position]).sum() * color_scale\n\n\n# Total cost of one step: the reconfiguration cost plus the color cost\ndef step_cost(from_config, to_config, image):\n    from_position = cartesian_to_array(*get_position(from_config), image.shape)\n    to_position = cartesian_to_array(*get_position(to_config), image.shape)\n    return (\n        reconfiguration_cost(from_config, to_config) +\n        color_cost(from_position, to_position, image)\n    )","metadata":{"collapsed":false,"jupyter":{"outputs_hidden":false},"execution":{"iopub.status.busy":"2022-12-20T15:59:54.023409Z","iopub.execute_input":"2022-12-20T15:59:54.023882Z","iopub.status.idle":"2022-12-20T15:59:54.034769Z","shell.execute_reply.started":"2022-12-20T15:59:54.023851Z","shell.execute_reply":"2022-12-20T15:59:54.032372Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"We'll see some examples of computing the cost of a path below.","metadata":{}},{"cell_type":"markdown","source":"# The Configuration Space #\n\nWe can take an alternative view of the optimization problem to make it similar to a traditional Traveling Salesman Problem.\n\nIn a single step, any of the links in the arm can transition to either of two states by a counter-clockwise rotation or a clockwise rotation. Laying out the transitions for each link along perpendicular axes, we form the **configuration space** of the arm. In general, an arm with $N$ links will create a configuration space with $N$ dimensions. Each unique configuration will occupy a point in a lattice (or grid) in this space. Filling in this lattice gives us a *cubical complex*, a bunch of cubes pasted together on their faces.\n\nThe configuration space for a 2-link arm is just a grid of squares, as the following figures show.","metadata":{}},{"cell_type":"code","source":"# Create an artificial test image\nconfig = [(1, 0), (-1, 0)]\nneighbors = get_neighbors(config)\n\nside = 5\nimage = np.zeros((side, side, 3))\nimage[:, :, 0] = np.linspace(0, 1, side)\nimage[:, :, 1] = np.linspace(0, 1, side).reshape(-1, 1)\nfig, ax = plt.subplots()\nax.matshow(image)\nax.grid([]);","metadata":{"collapsed":false,"jupyter":{"outputs_hidden":false},"execution":{"iopub.status.busy":"2022-12-20T15:59:54.036364Z","iopub.execute_input":"2022-12-20T15:59:54.036721Z","iopub.status.idle":"2022-12-20T15:59:54.371524Z","shell.execute_reply.started":"2022-12-20T15:59:54.036688Z","shell.execute_reply":"2022-12-20T15:59:54.37021Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"In the image we created above, each position has a unique color. We map these into the configuration space of the 2-link arm below.","metadata":{}},{"cell_type":"code","source":"square = [(1, 0)]\nfor _ in range(7):\n    square.append(rotate(square, -1, direction=-1)[-1])\nconfigurations = list(product(square, repeat=2))\n\nfig, ax = plt.subplots(figsize=(8, 8), dpi=90)\ncspace = np.zeros((len(square), len(square), 3))\nfor i, x in enumerate(square):\n    for j, y in enumerate(square):\n        cspace[i, j] = image[cartesian_to_array(*get_position([x, y]), image.shape)]\n        ax.plot([i], [j], 'o', color=cspace[i, j])\nax.set_aspect('equal')\nax.set_xlabel('Link 1')\nax.set_xticks(range(len(square)))\nax.set_xticklabels(square)\nax.set_ylabel('Link 0')\nax.set_yticks(range(len(square)))\nax.set_yticklabels(square)\nax.set_title(\"Configuration Space of the 2-Link Arm\");","metadata":{"_kg_hide-input":true,"execution":{"iopub.status.busy":"2022-12-20T15:59:54.373561Z","iopub.execute_input":"2022-12-20T15:59:54.374287Z","iopub.status.idle":"2022-12-20T15:59:54.596037Z","shell.execute_reply.started":"2022-12-20T15:59:54.374222Z","shell.execute_reply":"2022-12-20T15:59:54.59484Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"A movement in the positive direction (right/up) indicates a counter-clockwise rotation, while a movement in the negative direction (left/down) indicates a clockwise rotation. Moving across the *diagonal* of a square means a rotation of both links in a single step. The reconfiguration cost is simply the ordinary Euclidean distance in this space: $1$ for a step across the edge of a square, $\\sqrt{2}$ for a step across a diagonal. So we could think about the Santa optimization problem as being like a shortest path problem in the configuration space. (Note however that we don't need to visit *every* point in the configuration space, just some set of points corresponding to unique positions in the image.)\n","metadata":{}},{"cell_type":"markdown","source":"For more on configuration spaces, you might enjoy this article: [Ghrist, R., & Peterson, V. (2007). The geometry and topology of reconfiguration.](https://scholar.google.com/scholar?cluster=7705042403448786239&hl=en&as_sdt=0,37).","metadata":{}},{"cell_type":"markdown","source":"# A Simple Solution #\n\nNow let's use what we know to create a simple solution to this problem. Our stategy will be to write a function that can create a sequence of configurations with a given initial configuration that terminates at a desired position.","metadata":{}},{"cell_type":"code","source":"def get_direction(u, v):\n    \"\"\"Returns the sign of the angle from u to v.\"\"\"\n    direction = np.sign(np.cross(u, v))\n    if direction == 0 and np.dot(u, v) < 0:\n        direction = 1\n    return direction\n\n\n# We don't use this elsewhere, but you might find it useful.\"\"\"\ndef get_angle(u, v):\n    \"\"\"Returns the angle (in degrees) from u to v.\"\"\"\n    return np.degrees(np.math.atan2(\n        np.cross(u, v),\n        np.dot(u, v),\n    ))\n\n# ------------------\ndef get_path_to_point(config, point):\n    \"\"\"Find a path of configurations to `point` starting at `config`.\"\"\"\n    path = [config]\n    # Rotate each link, starting with the largest, until the point can\n    # be reached by the remaining links. The last link must reach the\n    # point itself.\n    for i in range(len(config)):\n        link = config[i]\n        base = get_position(config[:i])\n        relbase = (point[0] - base[0], point[1] - base[1])\n        position = get_position(config[:i+1])\n        relpos = (point[0] - position[0], point[1] - position[1])\n        radius = reduce(lambda r, link: r + max(abs(link[0]), abs(link[1])), config[i+1:], 0)\n        # Special case when next-to-last link lands on point.\n        if radius == 1 and relpos == (0, 0):\n            config = rotate(config, i, 1)\n            if get_position(config) == point:  # Thanks @pgeiger\n                path.append(config)\n                break\n            else:\n                continue\n        while np.max(np.abs(relpos)) > radius:\n            direction = get_direction(link, relbase)\n            config = rotate(config, i, direction)\n            path.append(config)\n            link = config[i]\n            base = get_position(config[:i])\n            relbase = (point[0] - base[0], point[1] - base[1])\n            position = get_position(config[:i+1])\n            relpos = (point[0] - position[0], point[1] - position[1])\n            radius = reduce(lambda r, link: r + max(abs(link[0]), abs(link[1])), config[i+1:], 0)\n    assert get_position(path[-1]) == point\n    return path\n# -----------------","metadata":{"collapsed":false,"jupyter":{"outputs_hidden":false},"execution":{"iopub.status.busy":"2022-12-20T15:59:54.597881Z","iopub.execute_input":"2022-12-20T15:59:54.599055Z","iopub.status.idle":"2022-12-20T15:59:54.613122Z","shell.execute_reply.started":"2022-12-20T15:59:54.598959Z","shell.execute_reply":"2022-12-20T15:59:54.612178Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"The `get_path_to_point` function only rotates a single link per step and doesn't account for the color cost at all, so it isn't very efficient. You can likely come up with something much better!\n\nWe'll create a simple solution for a 2-link arm here to illustrate and then apply it to the full image in the next section.","metadata":{}},{"cell_type":"code","source":"config = [(1, 0), (-1, 0)]\npoint = (-2, -2)\npath = get_path_to_point(config, point)\n\npath","metadata":{"collapsed":false,"jupyter":{"outputs_hidden":false},"execution":{"iopub.status.busy":"2022-12-20T15:59:54.614373Z","iopub.execute_input":"2022-12-20T15:59:54.615564Z","iopub.status.idle":"2022-12-20T15:59:54.629399Z","shell.execute_reply.started":"2022-12-20T15:59:54.615527Z","shell.execute_reply":"2022-12-20T15:59:54.628511Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"N = len(path)\ncolors = plt.cm.viridis(np.linspace(0, 1, N))\nfig, ax = plt.subplots(figsize=(10, 10))\nfor i, c in enumerate(path):\n    plot_configuration(c, color=colors[i], ax=ax)\nstart = get_position(config)\n# Black X is starting position, red X is target position.\nax.plot(start[0]-0.5, start[1]-0.5, 'x', ms=20, color='k', zorder=11)\nax.plot(point[0]-0.5, point[1]-0.5, 'x', ms=20, color='C3', zorder=11);","metadata":{"_kg_hide-input":true,"execution":{"iopub.status.busy":"2022-12-20T15:59:54.630632Z","iopub.execute_input":"2022-12-20T15:59:54.632152Z","iopub.status.idle":"2022-12-20T15:59:54.776427Z","shell.execute_reply.started":"2022-12-20T15:59:54.632085Z","shell.execute_reply":"2022-12-20T15:59:54.775195Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"(*Exercise:* Try plotting this in the configuration space instead.)","metadata":{}},{"cell_type":"markdown","source":"Let's also write a function that will transition from one configuration to another.","metadata":{}},{"cell_type":"code","source":"def get_path_to_configuration(from_config, to_config):\n    path = [from_config]\n    config = from_config.copy()\n    while config != to_config:\n        for i in range(len(config)):\n            config = rotate(config, i, get_direction(config[i], to_config[i]))\n        path.append(config)\n    assert path[-1] == to_config\n    return path","metadata":{"collapsed":false,"jupyter":{"outputs_hidden":false},"execution":{"iopub.status.busy":"2022-12-20T15:59:54.777714Z","iopub.execute_input":"2022-12-20T15:59:54.778086Z","iopub.status.idle":"2022-12-20T15:59:54.786136Z","shell.execute_reply.started":"2022-12-20T15:59:54.77805Z","shell.execute_reply":"2022-12-20T15:59:54.783807Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Now we can get a path through the entire image by just iterating through each point and extending the path created. Here we create a simple solution for a two-link arm.","metadata":{}},{"cell_type":"code","source":"n = 2\norigin = [(1, 0), (-1, 0)]\npoints = list(product(range(-n, n + 1), repeat=2))\n\npath = [origin]\nfor p in points:\n    config = path[-1]\n    path.extend(get_path_to_point(config, p)[1:])\n\n# Now make sure we end at the \"origin\" configuration\npath.extend(get_path_to_configuration(path[-1], origin)[1:])\n\nlen(path)","metadata":{"collapsed":false,"jupyter":{"outputs_hidden":false},"execution":{"iopub.status.busy":"2022-12-20T15:59:54.787748Z","iopub.execute_input":"2022-12-20T15:59:54.788346Z","iopub.status.idle":"2022-12-20T15:59:54.802581Z","shell.execute_reply.started":"2022-12-20T15:59:54.788307Z","shell.execute_reply":"2022-12-20T15:59:54.801054Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"And indeed we see that our path of configutions was positioned at every point in the image and ends at the origin configuration.","metadata":{}},{"cell_type":"code","source":"# Plot path\nN = len(path)\ncolors = plt.cm.viridis(np.linspace(0, 1, N))\nfig, ax = plt.subplots(figsize=(8, 8))\nfor i, c in enumerate(path):\n    plot_configuration(c, color=colors[i], ax=ax)\nstart = get_position(path[0])\nax.plot(start[0]-0.5, start[1]-0.5, 'x', ms=20, color='k', zorder=11);","metadata":{"_kg_hide-input":true,"execution":{"iopub.status.busy":"2022-12-20T15:59:54.803868Z","iopub.execute_input":"2022-12-20T15:59:54.80425Z","iopub.status.idle":"2022-12-20T15:59:55.138864Z","shell.execute_reply.started":"2022-12-20T15:59:54.804214Z","shell.execute_reply":"2022-12-20T15:59:55.137989Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"We can also compute the total cost of this solution by mapping the `step_cost` function over successive pairs in the path. We'll use the same test image as before.","metadata":{}},{"cell_type":"code","source":"# Compute total cost of path over image\ndef total_cost(path, image):\n    return reduce(\n        lambda cost, pair: cost + step_cost(pair[0], pair[1], image),\n        zip(path[:-1], path[1:]),\n        0,\n    )\n\n\ntotal_cost(path, image)","metadata":{"collapsed":false,"jupyter":{"outputs_hidden":false},"execution":{"iopub.status.busy":"2022-12-20T15:59:55.140307Z","iopub.execute_input":"2022-12-20T15:59:55.14083Z","iopub.status.idle":"2022-12-20T15:59:55.149638Z","shell.execute_reply.started":"2022-12-20T15:59:55.140796Z","shell.execute_reply":"2022-12-20T15:59:55.14905Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# Create a Submission #\n\nNow let's create a simple solution for the full eight-link arm and create save it as a submission file.","metadata":{}},{"cell_type":"markdown","source":"And here we compute the total cost of the solution.","metadata":{}},{"cell_type":"code","source":"image = df_to_image(df_image)\n\ntotal_cost(path, image)","metadata":{"execution":{"iopub.status.busy":"2022-12-20T15:59:55.150889Z","iopub.execute_input":"2022-12-20T15:59:55.151493Z","iopub.status.idle":"2022-12-20T15:59:55.169499Z","shell.execute_reply.started":"2022-12-20T15:59:55.151459Z","shell.execute_reply":"2022-12-20T15:59:55.168501Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"from tqdm import tqdm\n\norigin = [(64, 0), (-32, 0), (-16, 0), (-8, 0), (-4, 0), (-2, 0), (-1, 0), (-1, 0)]\nn = origin[0][0] * 2\npoints = list(product(range(-n, n + 1), repeat=2))\n\npath = [origin]\nfor p in tqdm(points):\n    config = path[-1]\n    path.extend(get_path_to_point(config, p)[1:])\n\n# Now make sure we end at the \"origin\" configuration\npath.extend(get_path_to_configuration(path[-1], origin)[1:])\n\nlen(path)","metadata":{"execution":{"iopub.status.busy":"2022-12-20T15:59:55.170846Z","iopub.execute_input":"2022-12-20T15:59:55.17157Z","iopub.status.idle":"2022-12-20T16:00:08.418921Z","shell.execute_reply.started":"2022-12-20T15:59:55.171532Z","shell.execute_reply":"2022-12-20T16:00:08.417942Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Now let's convert our simple solution into the format expected of a submission file.","metadata":{}},{"cell_type":"code","source":"def config_to_string(config):\n    return ';'.join([' '.join(map(str, vector)) for vector in config])\n\n\nsubmission = pd.Series(\n    [config_to_string(config) for config in path],\n    name=\"configuration\",\n)\n\nsubmission.head()","metadata":{"collapsed":false,"jupyter":{"outputs_hidden":false},"execution":{"iopub.status.busy":"2022-12-20T16:00:08.420464Z","iopub.execute_input":"2022-12-20T16:00:08.420728Z","iopub.status.idle":"2022-12-20T16:00:09.235144Z","shell.execute_reply.started":"2022-12-20T16:00:08.420702Z","shell.execute_reply":"2022-12-20T16:00:09.234431Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"submission.to_csv('submission.csv', index=False)","metadata":{"collapsed":false,"jupyter":{"outputs_hidden":false},"execution":{"iopub.status.busy":"2022-12-20T16:00:09.23618Z","iopub.execute_input":"2022-12-20T16:00:09.236425Z","iopub.status.idle":"2022-12-20T16:00:09.443461Z","shell.execute_reply.started":"2022-12-20T16:00:09.236399Z","shell.execute_reply":"2022-12-20T16:00:09.442457Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Feel free to copy any of the code in this notebook for your own solutions. We're looking forward to seeing what you come up with!","metadata":{}},{"cell_type":"markdown","source":"# My other submission (wip)","metadata":{}},{"cell_type":"code","source":"image = df_to_image(df_image)\n# start = [(64, 0), (-32, 0), (-16, 0), (-8, 0)]\n# end = [(-4, 0), (-2, 0), (-1, 0), (-1, 0)]\n\n\nfrom tqdm import tqdm\n\norigin = [(64, 0), (-32, 0), (-16, 0), (-8, 0), (-4, 0), (-2, 0), (-1, 0), (-1, 0)]\nn = origin[0][0] * 2\npoints = list(product(range(-n, n + 1), repeat=2))\n\npath = [origin]\nfor p in tqdm(points):\n    config = path[-1]\n    path.extend(get_path_to_point(config, p)[1:])\n\n# Now make sure we end at the \"origin\" configuration\npath.extend(get_path_to_configuration(path[-1], origin)[1:])\n\nlen(path)","metadata":{"execution":{"iopub.status.busy":"2022-12-20T16:00:09.445214Z","iopub.execute_input":"2022-12-20T16:00:09.445584Z","iopub.status.idle":"2022-12-20T16:00:22.604647Z","shell.execute_reply.started":"2022-12-20T16:00:09.445546Z","shell.execute_reply":"2022-12-20T16:00:22.603271Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## Now we look at algorithms that ***optimize the switching between links and channels***.\n\nSome algorithm to find the shortest path are:\n\n1. Dijkstra’s Algorithm\n1. greedy algorithm\n1. A* algorithm\n1. A* algorithm with a heuristic function\n1. A* algorithm with a heuristic function and a priority queue\n\n\n","metadata":{}},{"cell_type":"code","source":"image = df_to_image(df_image)\nstart = [(64, 0), (-32, 0), (-16, 0), (-8, 0)]\nend = [(-4, 0), (-2, 0), (-1, 0), (-1, 0)]","metadata":{"execution":{"iopub.status.busy":"2022-12-20T16:00:22.606663Z","iopub.execute_input":"2022-12-20T16:00:22.606983Z","iopub.status.idle":"2022-12-20T16:00:22.616744Z","shell.execute_reply.started":"2022-12-20T16:00:22.606957Z","shell.execute_reply":"2022-12-20T16:00:22.61536Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# The heuristic function is the sum of the absolute difference between the current position and the target position\ndef heuristic(config, target):\n    return sum(abs(np.array(config) - np.array(target)))\n","metadata":{"execution":{"iopub.status.busy":"2022-12-20T16:00:22.618474Z","iopub.execute_input":"2022-12-20T16:00:22.61882Z","iopub.status.idle":"2022-12-20T16:00:22.625172Z","shell.execute_reply.started":"2022-12-20T16:00:22.618793Z","shell.execute_reply":"2022-12-20T16:00:22.623854Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"<sup>w.i.p.</sup>","metadata":{}},{"cell_type":"code","source":"# # A* algorithm to find the shortest path\n# def a_star_path(start, end, image):\n#     path = [start]\n#     config = start\n#     while config != end:\n#         costs = []\n#         for i in range(len(config)):\n#             for direction in [-1, 1]:\n#                 new_config = rotate(config, i, direction)\n#                 costs.append(step_cost(config, new_config, image))\n#         i = np.argmin(costs)\n#         config = rotate(config, i // 2, -1 if i % 2 == 0 else 1)\n#         path.append(config)\n#     return path\n\n# path = a_star_path(start, end, image)\n\n# len(path)\n\n# total_cost(path, image)","metadata":{"execution":{"iopub.status.busy":"2022-12-20T16:02:05.193609Z","iopub.execute_input":"2022-12-20T16:02:05.193932Z","iopub.status.idle":"2022-12-20T16:02:05.199958Z","shell.execute_reply.started":"2022-12-20T16:02:05.193906Z","shell.execute_reply":"2022-12-20T16:02:05.198474Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# from tqdm import tqdm\n\n# origin = [(64, 0), (-32, 0), (-16, 0), (-8, 0), (-4, 0), (-2, 0), (-1, 0), (-1, 0)]\n# n = origin[0][0] * 2\n# points = list(product(range(-n, n + 1), repeat=2))\n\n# path = [origin]\n# for p in tqdm(points):\n#     config = path[-1]\n#     path.extend(a_star_path(config, p, image)[1:])\n\n# # Now make sure we end at the \"origin\" configuration\n# path.extend(get_path_to_configuration(path[-1], origin)[1:])\n\n# len(path)\n\n# total_cost(path, image)","metadata":{"execution":{"iopub.status.busy":"2022-12-20T16:02:55.059317Z","iopub.execute_input":"2022-12-20T16:02:55.060242Z","iopub.status.idle":"2022-12-20T16:02:55.065573Z","shell.execute_reply.started":"2022-12-20T16:02:55.060211Z","shell.execute_reply":"2022-12-20T16:02:55.064246Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# submission.to_csv('a_star_submission.csv', index=False)","metadata":{"execution":{"iopub.status.busy":"2022-12-20T16:00:59.411695Z","iopub.status.idle":"2022-12-20T16:00:59.411979Z","shell.execute_reply.started":"2022-12-20T16:00:59.411832Z","shell.execute_reply":"2022-12-20T16:00:59.411847Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"The last method is not very fast and we lack some experience.","metadata":{}},{"cell_type":"markdown","source":"Notes\n\n```python\n# The heuristic function is the sum of the absolute difference between the current position and the target position\ndef heuristic(config, target):\n    return sum(abs(np.array(config) - np.array(target)))\n\n# The cost function is the sum of the absolute difference between the current position and the target position\ndef cost(config, target):\n    return sum(abs(np.array(config) - np.array(target)))\n\n# The A-star algorithm\n\ndef a_star(start, target):\n    # The open list is a priority queue that contains the nodes that have been visited but not yet expanded\n    open_list = PriorityQueue()\n    # The closed list is a list that contains the nodes that have been visited and expanded\n    closed_list = []\n    # The parent dictionary contains the parent of each node\n    parent = {}\n    # The g dictionary contains the cost of the path from the start node to the current node\n    g = {}\n    # The f dictionary contains the cost of the path from the start node to the current node plus the heuristic cost\n    f = {}\n    # The start node is added to the open list\n    open_list.put((0, start))\n    # The start node is added to the parent dictionary\n    parent[start] = None\n    # The cost of the start node is added to the g dictionary\n    g[start] = 0\n    # The cost of the start node plus the heuristic cost is added to the f dictionary\n    f[start] = heuristic(start, target)\n    # The algorithm continues until the open list is empty\n    while not open_list.empty():\n        # The node with the lowest f cost is removed from the open list\n        current = open_list.get()[1]\n        # The node is added to the closed list\n        closed_list.append(current)\n        # If the current node is the target node, the algorithm is finished\n        if current == target:\n            break\n        # The neighbors of the current node are found\n        neighbors = get_neighbors(current)\n        # The neighbors are iterated through\n        for neighbor in neighbors:\n            # If the neighbor is in the closed list, it is skipped\n            if neighbor in closed_list:\n                continue\n            # The cost of the path from the start node to the neighbor is calculated\n            g_score = g[current] + cost(current, neighbor)\n            # If the neighbor is not in the open list or the cost of the path from the start node to the neighbor is less than the cost of the path from the start node to the neighbor in the open list, the neighbor is added to the open list\n            if neighbor not in open_list.queue or g_score < g[neighbor]:\n                # The parent of the neighbor is set to the current node\n                parent[neighbor] = current\n                # The cost of the path from the start node to the neighbor is added to the g dictionary\n                g[neighbor] = g_score\n                # The cost of the path from the start node to the neighbor plus the heuristic cost is added to the f dictionary\n                f[neighbor] = g_score + heuristic(neighbor, target)\n                # The neighbor is added to the open list\n                open_list.put((f[neighbor], neighbor))\n    # The path is initialized\n    path = []\n    # The current node is set to the target node\n    current = target\n    # The algorithm continues until the current node is the start node\n    while current != start:\n        # The current node is added to the path\n        path.append(current)\n        # The current node is set to the parent of the current node\n        current = parent[current]\n    # The start node is added to the path\n    path.append(start)\n    # The path is reversed\n    path.reverse()\n    # The path is returned\n    return path\n```\n\nThe A-star algorithm is a lot faster than the greedy algorithm. However, it is still too slow to run on the full eight-link arm. A better algorithm would be to use a heuristic function to prioritize the nodes in the open list. Or a faster algorithm could be used to find the neighbors of the current node..\n\nAn algorith to find the neighbors of the current node could be to use a breadth-first search algorithm. It works by finding the neighbors of the current node, then finding the neighbors of the neighbors of the current node, and so on. However, it is still too slow to run on the full eight-link arm.\n\n\n\n","metadata":{}},{"cell_type":"markdown","source":"# Conclusion\n\nA good model will be able to find the shortest path between the start and end points without collision. ***The goal is to minimize the cost of changing channels and links***.\n\nIn this notebook, we have seen how to create a simple solution to the Santa optimization problem. We have also seen how to create a submission file for the competition. We have used either a greedy algorithm or an A-star algorithm to find the shortest path, but we have not used any heuristic function or prioritization.\n\nFor now, the submitted file is the simple solution for the full eight-link arm, as the better algorithm takes a lot of time to run and more learning is necessary.","metadata":{}}]}