Description

1. Overview

This is a programming assignment in which you will apply AI search techniques to lead an exploration team to explore an underground cave system such as the one shown in Figure 1. Conceptually speaking, each cave system is like a sophisticated 3D maze, as shown in Figure 2, which consists of a grid of points (not cells) with (x, y, z) locations in which your agent may use one of the 18 elementary actions (see their definitions below), named X+, X-, Y+, Y-, Z+, Z-; X+Y+, X-Y+, X+Y-, X-Y-, X+Z+, X+Z-, X-Z+, X-Z-, Y+Z+, Y+Z-, Y-Z+, Y-Z-; to move to one of the 18 neighboring grid point locations. At each grid point, your agent is given a list of actions that are available for the current point your agent is at. Your agent can select and execute one of these available actions to move inside the 3D maze. For example, in Figure 2, there is a “path” from (0,0,0) to (10,0,0) and to travel this path starting from (0,0,0), your agent would make ten actions: X+, X+, X+, X+, X+, X+, X+, X+, X+, X+, and visit the following list of grid points: (0,0,0),

(1,0,0), (2,0,0), (3,0,0), (4,0,0), (5,0,0), (6,0,0), (7,0,0), (8,0,0), (9,0,0), (10,0,0). At each grid point, your agent is given a list of available actions to select and execute. For example, in Figure 2, at the grid point (60,45,30) there are two actions for your agent: Z+ for going up, and Y- for going backwards. At the grid point (60,103,97), the available actions are X+ and Y-. At (60,45,97), the three available actions are Y+, Z-, and X-Y+. If a grid point has no actions available, then that means such a point has nowhere to go. For example, the point (24,86,31) (not shown in Figure 2) has nowhere to go and is not accessible.

Figure 2: Cave (3D Maze) Configuration: grids world that contains travelable actions

Figure 3: Definitions of Actions in the Maze

The 18 actions are defined as follows. They are roughly divided as “straight-move” and “diagonal-move” actions. As shown in Figure 3, the six straight-move actions are X+, X-, Y+, Y-, Z+, Z-, and they allow your agent to move in a straight-line to the next grid point. The diagonal-move actions are further defined on xy, xz, and yz planes, respectively. For example, the actions X+Y+, X+Y-, X-Y+, and X-Y-, are those moves diagonally on the xy plane. Similarly, the actions X+Z+, X+Z-, X-Z+, and X-Z-, are those moves diagonally on the xz plane. Finally, the actions Y+Z+, Y+Z-, Y-Z+, and Y-Z-, are those moves diagonally on the yz plane. Notice that not all actions may be available for a given grid location, and not all grid locations may have actions. For clear format purpose, we name or encode these actions as follows:

Act	X+	X-	Y+	Y-	Z+	Z-	X+Y+	X+Y-	X-Y+	X-Y-	X+Z+	X+Z-	X-Z+	X-Z-	Y+Z+	Y+Z-	Y-Z+	Y-Z-
Code	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18

Your programming task is as follows. Given as inputs: (1) a list of grid points with their available actions, (2) an entrance grid location, e.g., (0,0,0) in Figure 2, and (3) an exit grid location, e.g., (100,103,97) , your program must search in the maze configuration and find the optimal shortest path from the entrance to the exit, using a list of actions that are available along the way.

Conceptually, the specification of a grid location and its associated actions is given as a grid location with a list of actions. For example (Note: The exact input format will be given in section 5 and 6 below),

INPUT LINE: (60 45 97), Y+, Z-, X-Y+

INPUT LINE: (60 46 97), Y-, Y+

INPUT LINE: (60 45 96), Z+, Z-,

INPUT LINE: (59 46 97), X+Y-, X-Y+

is a specification, for Figure 2, that at the grid location (60,45,97), the available actions are Y+, Z-, and X-Y+. At the grid (60,46,97), the available actions are Y- and Y+, and at the grid (60,45,96), the available actions are Z+ and Z-, and at the grid (59,46,97), the available actions are X+Y- and X-Y+ for moving diagonally on the xy plane.

Once your agent finds an optimal path from the entrance to the exit, your agent should output a list of points that have been visited along the path. For example, if the entrance and exit would be changed at (60,103,97) and (64,103,97) respectively, then the correct output path would be:

OUTPUT: (60,103,97), (61,103,97), (62,103,97), (63,103,97), (64,103,97).

To assist your programming, you will be provided some sample inputs and outputs (see below). Please understand that the goal of these samples is to check that you can correctly parse the problem definitions and generate a correctly formatted output. The samples are very simple, and it should not be assumed that if your program works on the samples it would definitely work on all test cases for grading. There will be more complex test cases and it is your task to make sure that your program will work correctly on any valid input. You are encouraged to design and try your own test cases to check how your program would behave in some complex special cases that you might think of. Since each homework is checked via an automated A.I. script, your output should match the specified format exactly. Failure to do so will most certainly cost some points. The output format is simple, and examples are provided. You should upload and test your code on vocareum.com at their terminal window which is a Linux-like environment. Please make sure you test your program at the terminal window at vocareum.com before you click the submit button there. You can submit as many times as you like, and the last submission before the due time will be used to grade your results. You may use any of the following programming languages: C++, Java, Python, but Python may be the preferred language to use in today’s large-scale AI program applications.

Do not copy code or written material from another student. Even single lines of code should not be copied.

Do not collaborate on this assignment. The assignment is to be solved individually.

Do not copy code off the web. This is easier to detect than you may think.

Do not share any custom test cases you may create to check your program’s behavior in more complex scenarios than the simplistic ones considered below.

5. • There is no limit on input size, number of grid points that have actions, etc., other than specified above (32-bit integers, etc). However, we will seriously consider the complexity of each test case. You should take care of the data structures used in your algorithms so that the program returns in a bounded time. Additional information may be posted on Piazza if necessary. Please keep your eyes on it.

5. • If several optimal solutions exist, then any of them will count as correct.

5. • Please submit your homework code through Vocareum (https://labs.vocareum.com/) under the assignment HW1. Your username is your email address (DEN username). Click “forgot password” for the first-time login. You should have been enrolled in this course on Vocareum. If not, please post a private question with your email address and USC ID on Piazza (under “hw1” folder) so that we will invite you again.

5. • You can submit your homework code (by clicking the “submit” button on Vocareum) as many times as you want. Only the latest submission will be considered for grading. After the initial deadline, the submission window will still be open for 2 days. However, a late penalty will be applied as 20% per day if your latest submission is later than the initial deadline.

5. • Every time you click the “submit” button on Vocareum, your submitted agent will be run and tested by our AI script on a number of test cases and the results will be reported to you in the submission-report which you can read and exam. You may use these reports for debugging and improving your agent. Notice that these are “test cases”, and they are not the “grading cases”. The grading cases are reserved for grading purposes and may not be available to your agent before the grading process begins.

5. • It’s highly suggested to reserve some time for submission and testing on Vocareum because you may come across some technical issues if this is the first time to use it. Anyway, don’t wait until the last minute!

5. Sample Inputs and Outputs

Example 1 (BFS):

=======input.txt=============

BFS

10 10 10

1 3 1

5 3 4

13

1315

1321611

2322511

23361416

2421117

322315

324716

33245

3336141718

34314

43411011

53425

535614

===========================

=======output.txt============

6

7

1310

1321

2321

3331

3241

4341

5341

============================

Example 2 (UCS):

=======input.txt=============

UCS

10 10 10

7 0 1

5 2 3

11

513316

5225817

523146

61135815

612369

62148

622418

6232

70119

71189

80129

===========================

=======output.txt============

48

5

7010

61114

61210

52214

52310

===========================

Example 3 (A*):

=======input.txt=============

A*

5 5 5

1 0 4

3 1 2

12

0011

0338

1012

104316

113135121617

1144612

12217

12349

21211213

213213

311135

31226

===========================

=======output.txt=============

38

4

1040

11314

21214

31210

============================

Example 4 (BFS with no solution):

=======input.txt=============

BFS

4 4 4

0 0 0

2 3 1

8

000711

101714

110710

2111015

220510

2216

222318

2324

===========================

=======output.txt=============

FAIL

============================

12