Many animals can change their aspect ratio by extending or bunching up. This allows animals like cats and rats to fit into small places and squeeze through small holes.

You will be moving an alien robot based on this idea. Specifically, the robot lives in 2D and has three degrees of freedom:

• It can move the (x,y) position of its center of mass.
• It can switch between three forms: a long horizontal form, a round form, and a long vertical form.

Notice that the robot cannot rotate. Also, to change from the long vertical form to/from the long horizontal form, the robot must go through the round form, i.e., it cannot go from its vertical oblong shape to its horizontal oblong shape directly.

The round form is a disk (or a filled circle). The horizontal or vertical long form is a "sausage" shape, defined by a line segment and a distance "d", i.e., any point within a given distance "d" of the LINE SEGMENT between the alien's head and tail is considered to be within the alien .

For each planning problem you will be given a 2D environment specified by:

• The size of the workspace.
• The widths of the long and round forms.
• The starting (x,y) center-of-mass position and shape of the alien.
• A list of goals, each of which is defined by disk described by an (x,y) position and a radius.
• A set of obstacles, each of which is a line segment.

You need to find a shortest path for the alien robot from its starting position to ONE of the goal positions.

The tricky bit is that the alien may not pass through any of the obstacles. Also, no part of the robot should go outside the workspace. So configurations like the following are NOT allowed:

Also note that, since we are discretizing the state space, we want to add a safety buffer equal to the half diagonal of a square whose side length is the granularity we're using to digitize our map. Specifically, if the granularity is G, we want our alien to be at least $\frac{G}{\sqrt{2}}$ units way from any obstacles and the same distance away from the edges of the workspace. This ensures that the alien will not accidentally bump into an obstacle of go out of bounds while executing its path in the real world. This is important for, configurations like the one below, where the granularity is set to 10 pixels:

Note that it seems that the alien turned red despite not visibly colliding with any wall. That is because at this coarse granularity, the safety buffer is very large. Keep that in mind as you visually debug later (this effect should be less perceptible at finer granularities).

Note that for reaching the goal, we DO NOT apply the collision buffer we use for obstacles and out-of-bounds checking, as we want to guarantee that we actually touch the goal.

• Adapt your MP2 State and A* code to be able to search in three dimensions.
  • This is primarily a housekeeping activity to ensure your code is not hardcoded to work for a specific type of search, but can handle generic search spaces.
• Compute a configuration space (Maze) from the original alien motion space. This configuration space is 3D because the alien robot has three degrees of freedom (x,y centroid position and shape).
• Convert that configuration space into a 3D version of MP2's map format and use your previously written 3D A* code to compute the shortest path in this configuration space map.

In order to represent the alien's configuration space as a 3D maze, you will digitize the alien's current shape and 2D movement patterns. Each shape of the alien ('Vertical', 'Ball', 'Horizontal') can be represented by a "level" in the maze, while the walls in the maze are determined by the configurations where the current shape collides with obstacles. It is important to remember that the robot's configuration is comprised of both its (x,y) centroid position and its shape! In the mazes we want you to solve, the robot will have to switch its shape to reach the goal.

Part 0: Understanding Map configuration

  [Test1]
  Window : (300, 200)                     # (Width, Height)
  Obstacles : [
                  (0,100,100,100),  #(startx,starty,endx,endy)
                  (0,140,100,140),
                  (100,100,140,110),
                  (100,140,140,130),
                  (140,110,175,70),
                  (140,130,200,130),
                  (200,130,200,10),
                  (200,10,140,10),
                  (175,70,140,70),
                  (140,70,130,55),
                  (140,10,130,25),
                  (130,55,90,55),
                  (130,25,90,25),
                  (90,55,90,25)
              ]
  Goals : [
              (110, 40, 10)               # (x-coordinate, y-coordinate, radius)
          ]
  Lengths: [40,0,40]
  Widths: [11,25,11]
  StartPoint: [30,120]

• Window: The window size for the given example map is 300x200 pixels. Note that (0, 0) is the top-left corner and (300, 200) is the bottom-right corner .
• Lengths: The lengths of the robot are in the form ['Horizontal Length', 'Ball length (always 0)', 'Vertical Length']. The length of the robot is defined by the distance between its head and tail
• Widths: widths of the robot represent the radius of the circle that is added to the line segment "body" of the alien, i.e.. how far away from the line segment defining the body is still considered to be "inside" the robot. These are ordered in the same manner as the Lengths
• Obstacles: There are many walls in the maze which are represented by a list of endpoints for line segments in the format (startx, starty, endx, endy)
• A list of disk goals specified in the form (x,y,radius). In this particular maze, there is one goal at (110,40) that has radius 10 pixels.
• The alien is set to start at the position (30,120), in its default disk configuration
• The name of this map is Test1

Here is how the map from this configuration looks:

You can play with the maps (stored in config file "maps/test_config.txt") by manually controlling the robot by executing the follwing command:

python3 mp3.py --human --map Test1 --config maps/test_config.txt

Once the window pops up, you can manipulate the alien using the following keys:

• w / a / s / d: move the alien up / left / down/ right
• q / e: switch between horizontal, ball, and vertical forms of the alien. "q" will cycle backwards (Vertical -> Ball -> Horizontal) and "e" will cycle forwards (Horizontal -> Ball -> Vertical

Part 1: Adapt A*

search.py

• astar(maze): returns optimal path in a list of MazeState objects, which contains start and objectives. If no path found, return None.
• backtrack(visited_states, current_state): this should be similar to your MP 2 implementation.

To implement search, you will also need to finish the implementation of MazeState in state.py. It might help to review some of the states you made in the previous MP. Complete all of the TODOs to finish the implementation. Note that unlike the previous MP, we do not include the MST in the heuristic, because we only need to reach one goal. Given the new objective, our old heuristic would not be consistent and admissible.

Run part 1 by using the following command

python3 part1.py mazes/small-3d

You can control the agent with keyboard inputs as usual by using arrow keys to navigate on the same level and 'u' and 'd' to move up/down a level

python3 part1.py mazes/small-3d --human

Part 2: Geometry

The alien robot has two forms that are represented with geometric shapes:

Form 1 (Ball): A disk with a fixed radius. This entire disk is the alien's body.

Form 2 (Oblong): An oblong (sausage shape). This is represented as a line segment with a fixed length and a radius. Any point within the specified radius of the line segment belongs to the alien's body, hence its sausage-like appearance.

We provide a helper class to help you: Alien. Do not modify this class . To solve MP3, you will likely find the following Alien methods to be useful:

alien.py

• get_centroid(): Returns the centroid position of the alien (x,y)
• get_head_and_tail(): Returns a list with the (x,y) coordinates of the alien's head and tail [(x_head,y_head),(x_tail,y_tail)], which are coincidental if the alien is in its disk form.
• get_length(): Returns the length of the line segment of the current alien shape
• get_width(): Returns the radius of the current shape. In the ball form this is just simply the radius. In the oblong form, this is half of the width of the oblong, which defines the distance "d" for the sausage shape.
• is_circle(): Returns whether the alien is in circle or oblong form. True if alien is in circle form, False if oblong form.
• set_alien_pos(pos): Sets the alien's centroid position to the specified pos argument
• set_alien_shape(shape): transforms the alien to the passed shape
• set_alien_configuration((x,y,shape)): Places the alien in that specified configuration, placing its centroid in position (x,y) and forcing its shape to be "shape"

The main geometry problem is then to check whether

• the alien touches the goal.
• the alien runs into obstacles
• all parts of the alien remain within the given window (bounds)

To do this, you need to implement the following functions:

geometry.py

• does_alien_touch_walls(alien, walls, granularity): Determine whether any part of the alien touches the walls given a certain space granularity, returns True if it does and False otherwise.
• does_alien_touch_goals(alien, goals): Determine whether any part of the alien touches goals, returns True if it does and False otherwise.
• is_alien_within_window(alien, window, granularity): Determine whether the alien stays within the window given a certain space granularity, returns True if it does and False otherwise.