Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due

CS 7638: Artificial Intelligence for Robotics

Introduction

This PDF serves as a problem specification document and thus the information in this document is not referring to any details regarding any specific algorithm to solve the problem. Its’ purpose is to definethe problem along with the relevant details needed to solve it. It acts as a summary of the rules that are implemented in the testing suite code provided to you (which you can reference when you need further clarification). An interactive GUI mode (TEST_MODE) is also available for you to use (which you can use to validate your understanding of the specifications). Lastly, the example calculations and images in this PDF are also a good resource to use when looking for clarifications.

In this project, you will implement search algorithms to guide a robot through a warehouse to pick up and drop off boxes to a designated drop zone area.

The template code provides 3 classes, one for each part of the project: DeliveryPlanner_Part[A, B, C]

Part A (40%)

Your task is to pick up and deliver all boxes listed in the todo list. You will do this by providing a list of motions that the testing suite will execute in order to complete all the deliveries. Your algorithm should determine the optimal path to take while completing this task.

DeliveryPlanner_PartA's constructor must take five arguments: self, warehouse_viewer, dropzone_location, todo, and box_locations. It must also have a method called plan_delivery that takes 2 arguments: self and debug (set to False by default).

Part A Input Specifications

NOTE: In part A, your code will not know (nor should it depend on) the size of the warehouse (n and m). You are only allowed to use the warehouse_viewer object (WarehouseAccess) in the following 2 ways, if we find that your code is using any other methods/approaches to use or manipulate the warehouse object, you will receive a 0 for part A (this may be done manually after the project is due):

The goal in part A is to not only find an optimal solution, but to do so in an efficient manner. Efficiency here means that your algorithm should access (view) as few of the warehouse cells as possible. Accessing a particular cell more than once will NOT hurt you as we will only tally the unique cells that your algorithm accesses each test case. It is your responsibility to make sure you are not using any other way to glean information from the warehouse other than the 2 methods above. There are some precautions in place to help notify you when you are improperly using the warehouse object, however, these are not exhaustive.

Note that the box locations and the dropzone are counted as viewed cells because they are given to you as input.

The characters in each string will be one of the following: . (period) : traversable space. The robot may enter from any adjacent space.

@ (dropzone) : the starting point for the robot and the space where all boxes must be delivered. The dropzone may be traversed like a . (period). 

[0-9a-zA-Z] (any alphanumeric character) : a box. At most one of each alphanumeric character will be present in the warehouse (meaning there will be at most 62 boxes). A box may not be traversed, but if the robot is adjacent to the box, the robot can pick up the box. Once the box has been lifted, the space that the lifted box previously occupied now functions as a . (period).

'#1#2#',

'#.#.#',

'#..@#',

'#####']

is a 5x5 warehouse.

• The dropzone is at the warehouse cell in row 3, column 3.

• Box 1 is located in the warehouse cell in row 1, column 1.

• Box 2 is located in the warehouse cell in row 1, column 3.

• There are walls within the warehouse at cells (row 1, column 2) and (row 2, column 2) and around the warehouse.

• The remaining five warehouse cells (which includes the dropzone) are traversable spaces.

The argument todo is a list of alphanumeric characters giving the order in which the boxes must be delivered to the dropzone. For example, if todo = ['1','2'] is given with the above example warehouse, then the robot must first deliver box 1 to the dropzone, and then the robot must deliver box 2 to the dropzone.

Part A Rules & Costs for Motions

• The robot may move in 8 directions (N, E, S, W, NE, NW, SE, SW)

• The robot may not move outside the warehouse. The warehouse does not “wrap” around (it is not cyclic).

• Two spaces are considered adjacent if they share an edge or a corner.

• The robot may pick up a box that is in an adjacent square.

• The robot may put a box down in an adjacent square, so long as the adjacent square is empty (. or @).

• While holding a box, the robot may not pick up another box.

• There are 4 kinds of motions that the robot can take (below are the costs associated with each type):

– [cost]: type

– [ 2 ]: horizontal or vertical movement

– [ 3 ]: diagonal movement

– [ 4 ]: pick up box (regardless the direction)

– [ 2 ]: put down box (regardless the direction)

• If a box is placed on the @ space, it is considered delivered and is removed from the warehouse, thus the @ space is still traversable after dropping a box on it.

• The warehouse will be arranged so that it is always possible for the robot to move to the next box on the todo list without having to rearrange any other boxes.

• The robot will end up in the same location when an illegal motion is performed.

• An illegal motion will incur a penalty cost of 100 in addition to the motion cost.

• Illegal motions include:

– attempting to move to a nonadjacent, nonexistent, or occupied space

– attempting to pick up a nonadjacent or nonexistent box

– attempting to pick up a box while already holding one (attempting to put down a box while not holding one)

– attempting to put down a box on a nonadjacent, nonexistent, or occupied space (this means the robot may not drop a box on the drop zone while the robot is occupying the drop zone)

• 'move {d}', where '{d}' is replaced by the direction the robot should move: "n", "e", "s", "w", "ne", "se", "nw", "sw"

• 'lift {x}', where '{x}' is replaced by the alphanumeric character of the box being picked up

• 'down {d}', where '{d}' is replaced by the direction the robot will put the box down

For example, for the values of warehouse and todo given previously (reproduced below):

'#1#2#',

'#.#.#',

'#..@#',

'#####']

Part A Scoring

Part B (40%)

DeliveryPlanner_PartB's constructor must have four arguments: self, warehouse, warehouse_cost, and todo.

Part B Input Specifications

• The only box in the warehouse will be: 1 (the single box to be delivered).

• The warehouse will NOT necessarily be surrounded by walls.

• There are NO restrictions on your code accessing the warehouse object in part B and C. You may view as many cells as you wish.

'.#.',

'..@']

[10, w, 2],

[ 2, 10, 2]]

where w represents a wall. Note that the value of w has no consequence since the robot can’t occupy a space containing a wall.

The argument todo is limited to a single box as follows: todo = ['1']

There is no input for initial robot location because the robot may “wake up” at any point in the warehouse and must be handed a “policy” so that no matter where it is, it can retrieve the box. Further, because it may lift the box from different squares depending on its starting location, it requires another “policy” to deliver the box to the dropzone.

• Note: You must update your internal warehouse state in your code as this is not done for you.

Part B Rules for Motions

Part B Costs for Actions

• motion cost (same as part A)

• floor cost

– movements: value of the destination cell the robot is moving into

– lift: value of the cell the box is located in prior to lifting

– down: value of the cell the box is being placed into

For example the lowest cost route to box 1 is not [‘move e’, ‘move e’]:

'....',

'.##.']

[ 1, 1, 1, 1],

[ 1, w, w, 1],]

• If the robot enters (0,1) from (0,0) then the total action cost will be: total action cost = motion cost (horizontal movement) + floor cost (destination) = 2 + 95 = 97.

• If the robot enters (0,1) from (1,0) then the total action cost will be: total action cost = motion cost (diagonal movement) + floor cost (destination) = 3 + 95 = 98.

Note that the floor cost to move into cell (0,1) is 95 regardless of the direction the robot is entering from.

Three example calculations for the total action cost of illegal motions (i.e. attempting to move into (or put down a box at) an occupied space or outside the warehouse) are:

Part B Method Return Specifications

plan_delivery should return two policies, each as a list of lists of strings indicating the motion to take at each square on the grid. The format of the commands is the same as in part A. The special command ‘-1’ should be placed at any square for which there is no valid command, such as a wall.

For example, for the values of warehouse and todo given previously (reproduced below):

'.#.',

'..@']

where: ‘B’ indicates the box location.

For the “Deliver Box Policy”, the dropzone includes a motion in the event the robot starts on, lifts an adjacent box, and then must move off the dropzone to deliver it.

Part B Scoring

Part C (20%)

DeliveryPlanner_PartC's constructor must have five arguments: self, warehouse, warehouse_cost, todo, and stochastic_probabilities.

In part A and B we dealt with a deterministic robot. In real life however, we are inevitably faced with stochasticity. As such, part C is about finding an optimal policy based on stochastic robot motions.

Note: For this part you should find 2 individually optimal policies: pick up and drop off. This means your main algorithm should be executed 2 times: once to obtain the optimal policy to pick up the box and once to obtain the optimal policy to deliver the box.

Part C Rules for Motions

Rules for motions are almost the same as part A & B. Instead of deterministic movements however, the robot will move according to a probability distribution defined by stochastic_probabilities. stochastic_probabilities will give you the probability that the movement will be as_intended, slanted, or sideways as depicted in the grids below. Since these are probabilities, the sum of all possible outcomes will be one: 2 ∗ (sideways+slanted) +as_intended = 1. Your code should be able to handle any distribution provided to you in stochastic_probabilities. as_intended will be strictly greater than 0% and strictly less than 100%. The as_intended direction in the images below indicates the intended movement by the robot. Note that slanted and sideways are with respect to the intended movement direction. 

Note that Example 2 and 3 above are the same example since orientation does not matter in this project, they are both provided to emphasize that the unintended stochastic outcomes are with respect to the intended movement direction.

• as intended = 70%

• slanted = 10%

• sideways = 5%

Do yourself a favor and validate that the sum of all possible outcomes for this example is indeed 1. The probability distribution showing the outcomes of an intended movement of “move n” in 3 different scenarios are depicted below:

Notice that in example #5, the two locations occupied by a wall prevent the robot from moving into those spaces and therefore the robot stays in place 15% (10% + 5% ) of the time. Similarly, any attempt to move outside the warehouse will result in the robot staying in the same location (as seen in example #6).

Only directional movement is stochastic. The lift and down motions are deterministic.

Part C Costs for Actions

For example, if the intended motion is a vertical movement, but the robot ends up performing a slanted movement then the result will incur a diagonal movement cost. Similarly, if the intended motion is a diagonal movement, but the robot ends up performing a sideways movement then the result will incur a diagonal movement cost. [This last statement is NOT a typo. Please reference the provided example images #1, #2, and #3 above to convince yourself.]

Part C Output Specifications

Part C Scoring

TL;DR: for each correct policy (to-box and to-dropzone) you will earn 0.5 points for a total of 1 point per test case. More details about the scoring are below, but not required to complete the project.

Before starting the to-zone policy procedure, the testing suite will place the robot at location robot_init2 and pick up the box. This is to allow you partial credit to earn points for a correct to-dropzone policy even if you failed the to-box policy.

Note that there is very little information that can be gleaned from analyzing correct_performed_actions. This is not intended as a means of debugging for the students, rather as a way to grade the policy. This means you aren’t given a crutch that tells you exactly what your code should be outputting, instead you must analyze your code by scrutinizing your implementation of the algorithm and making sure to adhere to the warehouse rules laid out in this document.

Environment Test

Visualization

In addition, there is a GUI based visualization, set VISUALIZE_FLAG=True. You can change the GUI frame rate speed in the visualizer.py file. The 6 choices are [1,2,3,4,5] (slow to fast) and [0] which is MANUAL-PAUSE mode (this will not proceed to the next time step until you press the space bar). You can conveniently quit any test case by pressing the Esc (escape) key. An example demo video can be found at the following link: https://mediaspace.gatech.edu/media/t/1_onp8ge69

Part A’s visualization will also indicate to you which cells your algorithm (did and didn’t) access during the search process. The cells with a dark overlay on them indicate cells that your algorithm didn’t access.

In testing_suite_partA.py you can turn on TEST_MODE to control the robot with your keyboard. This can be used to validate and build your understanding about the rules of the game. The controls are the following (note that NumLock may need to be turned off):

Development and Debugging

• Set the TIME_OUT to a very large value (like 600 seconds)
• Set DEBUGGING_SINGLE_PROCESS = True (this disables multiprocessing, which messes up most debuggers)
• Set VERBOSE_FLAG = True
• provides a simple console based visualization
• provides line numbers for any syntax errors that occur
• if exceptions are raised provides detailed stack trace

Surrounding the warehouse policy are the row and column indexes so it is easier to locate a particular index (helpful on larger warehouses). The arrows denote the policy motion. The empty square denotes a box. The white square denotes a wall. + denotes a lift command. - denotes a down command. Note that lift and down for part C are a little more lax as they do not check the box number nor direction.

If you also return a set of values to accompany your policies then these will be displayed (as integers) next to your motions. These values can represent anything you want and can serve as a way to visually see why certain motions are as they are.

The correct actions performed and student actions performed are output for part C. The difference between these are marked with ˆ indicating the place where the lists do not match.