CS440/ECE448 Spring 2020

Assignment 2: Configuration Space Planning

Due date: Wednesday Febrary 19, 11:59pm

Credits (Fall 2018): Micky Abir, Chris Benson, Krishna Kothapalli, and JD Lee
Credits (Fall 2019): Zih-Siou Hung, Devansh Shah
Credits (Spring 2020): Heting Gao, Jialu Li

In this assignment you will write code that transforms a 2D planning problem for a robotic arm into a configuration space, and then searches for a path in that space. See Section 25.4 of the textbook and Lecture 7 for background information.


General guidelines

Basic instructions are the same as in MP 1. Your code must be in Python 3.6 or 3.7 and will be submitted to gradescope. Your code may import extra modules, but only ones that are part of the standard python library . Extra credit is capped at 10% (so the score for the MP will not exceed 110%).

Two changes from MP 1:

  • In addition to the standard python libraries and pygame, you may import numpy.
  • The extra credit portion will be submitted separately on gradescope.

For general instructions, see the main MP page and the syllabus.

You will need to re-use your bfs code from MP 1.

Problem Statement

You are given a two-link arm in 2D space as explained in class. This arm has two links of length \(L_1\) and \(L_2\) respectively. The arm is free to rotate about its base that is pivoted on the ground and link-2 can rotate about the joint where it connects with link-1. Let's use \(\alpha \) for the angle between the link-1 and the ground (equivalent to \(\theta_1\)). Let's use \(\beta \) for the angle between link-2 and link-1 (equivalent to \(\theta_2\)). The robot is shown at the top of the page with visualization of \(\theta_1\) and \(\theta_2\). Note that the angles are measured counter-clockwise.

For each planning problem, you will be given:

More details can be found in Map Configuration.

You need to find a shortest path for the robotic arm from its starting position to any of the goals so that the tip (open end of the arm) touches or is inside the goal and the number of steps rotating the arm is minimized.

The tricky bit is that the robotic arm may not pass through any of the circular objects including a goal and an obstacle. Also, any part of the arm should not get out of the given window. So configurations like the following are NOT allowed:

Note that the blue and the red circle denote a goal and an obstacle, respectively.

You will do your path planning in two steps:

  • Compute a configuration space map (Maze) that shows which joint angles are blocked by obstacles or by the window.
  • Use your code from MP 1 (search.py) to compute a shortest path in this configuration space map. Use the bfs search algorithm for search.

For compatibility with MP 1, you will digitize the angles \(\alpha\) and \( \beta \) when creating your configuration space map so that the map will only be an approximation to real life. Also, the arm is allowed to only change one of \(\alpha\) or \( \beta \) in one step. Each step will change one of the angles by a fixed number called the angular resolution that is measured in degrees. The angular resolution will be an input parameter to your method, so that it can be adjusted for your tests and for our evaluation of your code. There is a tradeoff here: finer resolution will allow the arm to get through smaller gaps between obstacles but it will also slow down your search.

Part 0: Map configuration

First of all, you need to understand the 2D space that describes a robotic arm, a goal, and obstacles. The following example map, named 'Test1', would help you to understand map configuration specifications.

    Window : (300, 200)                     # (width, height)
    ArmBase : (150, 200)                    # (x-coordinate, y-coordinate)
    ArmLinks : [
                    (100, 95, 5, (0, 180)), # (length, initial angle, padding distance, (min angle, max angle)
                    (50, 60, 5, (-150, 150)),
    Obstacles : [
                    (125, 70, 10),          # (x-coordinate, y-coordinate, radius)
                    (80, 90, 10),
                    (165, 30, 10),
                    (185, 60, 10)
    Goals : [
                (150, 50, 10),               # (x-coordinate, y-coordinate, radius)
                (100, 50, 10)