使用BFS, UCS以及A*搜索算法，探索时间旅行最短路径的问题。
Overview
This is a programming assignment in which you will apply AI search techniques
to some future “ time traveling “ problems with some limited simplifications. As shown in
Figure 1, there are many possible worlds along with the timeline indexed by
the years. Each world is a grid of space with (x, y) locations in which your
agent can use some elementary actions to move to one of the eight neighboring
grid locations. Within a possible grid world, there are some special bi-
directional time-traveling channels located at certain locations that will
allow your agent to travel in time forward or backward in the history. For
example, in Figure 1, there is a time-travel channel located at (x=3,y=4) in
the year 2020 that could allow your agent to time-travel to the future year
2023, or vice versa. Similarly, there is a channel at (x=9, y=7) in the year
2020 that could allow your agent to time-travel back to the year 2018, or vice
versa.
At a special location where there is a time-travel channel, your agent may use
an action called “jaunt” to time-travel to a different year in the history at
the other end of the channel. To represent your agent’s time-location in the
history configuration, we may use the term “year-location.” For example, if
your agent is at (year=2020, x=4, y=7), that means your agent is in the year
2020 at the grid location (x=4, y=7). If there is a time-travel channel at
your agent’s current year-location, then your agent may choose to jaunt and
time-travel. For example, at (2020,3,4), your agent may jaunt to the year-
location (2023,3,4). Similarly, jaunting at (2020,9,7) will take your agent
back in history to (2018,9,7). Of course, at such a location, your agent may
choose not to jaunt but move normally inside the same grid world of the same
year. For example, moving north at (2020,3,4) will take your agent to
(2020,3,5); moving southwest at (2020,3,4) will result in (2020,2,3); moving
southeast at (2020,3,4) will go to (2020,2,5); and moving south at (2020,3,4)
will go to (2020,3,3). Notice that if your agent is trying to move outside the
grid world, then that action will have no effect and result your agent to stay
where it is.
Your programming task is as follows. Given three inputs: (1) a time-traveling
configuration, such as the one in Figure 1; (2) an initial year-location, and
(3) a goal or target year-location, your program must search in the
configuration and find the optimal shortest path from the initial year-
location to the target year-location, using the elementary move actions and
jaunt.
Conceptually, the specification of a time-traveling problem is given as a list
of max-x, max-y, initial-year-location, target-year-location, plus a list
time-travel channels. For example (Note: The exact input format will be given
in section 5 and 6 below),
INPUT: 100,100, (2020,1,3), (2023,4,6), [(2020,3,4,2023), (2018,9,7,2020)]
is a specification for grid worlds of size 100 x 100, with the initial year-
location of (2020,1,3), the target year-location of (2023,4,6), and the two
time-travel channels as illustrated in Figure 1. Notice that the number of
time-travel channels may vary from one problem to another. This example input
indicates that your agent is given a time-travel configuration of grid worlds
of size 100x100, plus two time-travel channels as shown in Figure 1, and your
agent is required to find the shortest path from the initial year-location
(2020,1,3) to the target year-location (2023,4,6). Given such inputs, your
program may find and output a shortest path as follows. Notice that every step
in your output must be a legal action as specified above (Note: the exact
output format will be given in section 5 and 6 below.)
OUTPUT: (2020,1,3), (2020,2,4), (2020,3,4), (2023,3,4), (2023,4,5), (2023,4,6).
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.
Grading
Your code will be tested and graded as follows: Your program should not
require any command-line argument. It should read a text file called
“input.txt” in the current directory that contains a problem definition. It
should create and write a file “output.txt” with your solution in the same
current directory. Format for input.txt and output.txt are specified as in
section 5 below, and will be supplemented with some details in section 6. End-
of-line character is LF (since vocareum is a Unix system and follows the Unix
convention).
The grading A.I. script will test your program for 50 test cases for grading
as follows:
- Create an input.txt file, and delete any old output.txt file.
- Run your code to create your output.txt file.
- Check correctness of your program’s output.txt file.
- If your outputs for all 50 test cases are correct, you get 100 points.
- If one or more test case fails, you get 50-N points where N is the number of failed test cases.
Note that if your code does not compile, or somehow fails to load and parse
input.txt, or writes an incorrectly formatted output.txt, or no output.txt at
all, or OuTpUt.TxT, you will get zero points. Anything you write to stdout or
stderr will be ignored and is ok to leave in the code you submit (but it will
likely slow you down). Please test your program on Vocareum’s terminal window
with the provided sample files to avoid any problems.
Project Description
In this project, we twist the problem of path planning a little bit just to
give you the opportunity to deepen your understanding of search algorithms by
modifying search techniques to fit the criteria of a more realistic
application. To give you a realistic context for expanding your ideas about
search algorithms, we invite you to take part in a time-traveling mission in
the future. The goal of this mission is to send your sophisticated and
intelligent agent from a specific year-location to a target year-location. You
are invited to develop an algorithm to find the optimal and shortest path and
navigate through a complex time-traveling configuration based on a particular
objective.
We assume a time-travel configuration that is specified by a set of possible
grid worlds along the timeline indicated by the year. Every grid world has the
same format and is a matrix (X, Y) with H rows (where H is a strictly positive
integer) and W columns (W is also a strictly positive integer). For example, a
grid world may be a map with W=3 columns and H=2 rows. By convention, we will
use East (E) as the positive direction for X; West (W) as the negative
direction of X; North (N) as positive direction for Y; and South (S) as the
negative direction for Y. In addition, each possible grid world has a time
value specified as a year in the timeline history, as illustrated in Figure 1.
The input of your program includes three elements: a time-travel
configuration, an initial year-location, and a target year-location, plus
perhaps some other quantities that control the quality of the solution. Each
possible grid world can be imagined as a surface in a 2-dimensional space. A
popular way to represent “time” is to use a year value assigned to each grid
world. At each location of a grid world, your agent can move to each of the 8
possible neighbor grid locations: North, Northeast, East, Southeast, South,
Southwest, West, and Northwest. Actions are assumed to be deterministic and
error-free. If your agent’s action is legal, then your agent will always end
up at the intended neighbor grid location. If your agent tries to move outside
a grid world, the result will be nil and your agent will remain in its current
location.
In addition to the eight normal move actions, the jaunting action will allow
your agent to time-travel to a different year in the history if your agent is
located at the same location of a bi-directional time-travel channel. If there
is no time-travel channel at the current location, the jaunting action will
have no effect and your agent will remain stay at its current location.
Search for the Optimal Paths
You will write a program that will take an input file that describes the time-
travel configuration, the initial year-location, the target year-locations,
and characteristics of the agent. For each target year-location, you should
find the optimal (shortest) path from the initial year-location to that target
year-location. A path is composed of a sequence of legal moves. Each legal
move consists of moving the agent to one of its 8 neighbors in the same grid
world in the current year, or a jaunting action through a time-travel channel
at the current location.
Your agent must search through all possible paths of normal and time-travel
movements and find the shortest path to travel from the initial year-location
to the target year-location, and then output the results. Ideally, your agent
can go anywhere in the space-time configuration, and usually the shortest path
is defined as the optimal path.
To find the solution you will use the following algorithms:
- Breadth-first search (BFS)
- Uniform-cost search (UCS)
- A* search (A*).
Your algorithm should return an optimal path, that is, with shortest possible
operational path length. Operational path length is further described below
and is not equal to geometric path length as per the specifications given
ahead. If an optimal path cannot be found, your algorithm should return “FAIL”
as further described below.
To help us distinguish between your three algorithm implementations, you must
follow the following conventions for computing operational path length: - Breadth-first search (BFS)
In BFS, each move from one location to any of its 8 neighbors counts for a
unit path cost of 1. You do not need to worry about the fact that moving
diagonally (e.g., Northeast) actually is a bit longer than moving along the
North to South or East to West directions. So, any allowed move from one
location to an adjacent location costs 1. A jaunting action will cost 1 as
well regardless of the size of the jump in time. - Uniform-cost search (UCS)
When running UCS, you should compute unit path costs in 2D. Let us assume that
a location’s center coordinates projected to a 2D ground plane are spaced by a
2D distance of 10 North-South and East-West. That is, a North or South or East
or West move from a grid location to one of its 4-connected straight neighbors
incurs a unit path cost of 10, while a diagonal move to a neighbor incurs a
unit path cost of 14 as an approximation to 10 when running UCS. As usual, a
jaunting action will cost the number of years it time-travels. - A* search (A*).
When running A*, you should compute an approximate integer unit path cost of
each move as in the UCS case (unit cost of 10 when moving North to South or
East to West, and unit cost of 14 when moving diagonally). A jaunting action
will cost the number of years it time-travels. Notice that for A*, you need to
design an admissible heuristic for A* for this problem.
Input: The file input.txt in the current directory of your program will be
formatted as follows: - First line: Instruction of which algorithm to use, as a string: BFS, UCS or A*
- Second line: Two strictly positive 32-bit integers separated by one space character, for “W H” the number of columns (width) and rows (height) for all grid worlds.
- Third line: Three positive 32-bit integers separated by a space character, “Year X Y” for the initial year-location, where
0 ≤ X ≤ W-1and0 ≤ Y ≤ H-1. That is, we use 0-based indexing into a grid world: X increases when moving east, Y increases when moving north, and (0,0) is the southwest corner of the grid world. - Fourth line: Three positive 32-bit integers separated by a space character, “Year X Y” for the target year-location, where
0 ≤ X ≤ W-1and0 ≤ Y ≤ H-1. That is, we use 0-based indexing into a grid world: X increases when moving east, Y increases when moving north, and (0,0) is the southwest corner of the grid world. - Fifth line: A strictly positive 32-bit integer N, indicating the number of time-travel channels in the configuration.
- Next N lines:
Four positive 32-bit integers separated by one space character, for “Year X Y
Year”, specifying the coordinates of the time-travel channel and the two years
at the ends of the channel. Again, wehave 0 ≤ X ≤ W-1,0 ≤ Y ≤ H-1,
and 0-based indexing into the grid worlds.
For example:
A*
100 200
2020 8 12
3472 13 17
2020 12 16 3011
3011 56 77 2487
3011 14 19 3472
In this example, all grid worlds are of size 100 x 200, the initial year-
location is (year=2020,x=8,y=12), and the target year-location is
(year=3472,x=13,y=17). There are three time-travel channels, the first one is
located at (12,16) between the years 2020 and 3011, the second one located at
(56,77) between the years 3011 and 2487, and the third one located at (14,19)
between the years 3011 and 3472.
Output: The file output.txt that your program creates in the current directory
should be formatted as follows: - First line: A single integer C, indicating the total cost of your found solution. If no solution was found (target year-location is unreachable from the given initial year-location), then write the word “FAIL”.
- Second line: A single integer N, indicating the total number of steps in your solution including the starting position.
- N lines: Report the steps in your solution travelling from the initial year-location to the target year-location as were given in the input.txt file.
- Write out one line per step with cost. Each line should contain a tuple of four integers: Year, X, Y, Cost, separated by a space character, specifying the year-location with the step cost to visit that year-location by your agent during its (time) traveling from the initial year-location to the target year-location.
For example, the following is a sample output of the corresponding input
above:
2020 8 12 0
2020 9 13 14
2020 10 14 14
2020 11 15 14
2020 12 16 14
3011 12 16 991
3011 13 17 14
3011 14 18 14
3011 14 19 10
3472 14 19 461
3472 13 18 14
3472 13 17 10
- Write out one line per step with cost. Each line should contain a tuple of four integers: Year, X, Y, Cost, separated by a space character, specifying the year-location with the step cost to visit that year-location by your agent during its (time) traveling from the initial year-location to the target year-location.
Notes and hints:
- Please name your program “homework.xxx” where ‘xxx’ is the extension for the programming language you choose (“py” for python, “cpp” for C++, and “java” for Java). If you are using C++11, then the name of your file should be “homework11.cpp” and if you are using python3 then the name of your file should be “homework3.py”. Please use the programming languages mentioned above for this homework.
- Likely (but no guarantee) we will create 15 BFS, 15 UCS, and 20 A* test cases.
- Your program will be killed after some time if it appears stuck on a given test case, to allow us to grade the whole class in a reasonable amount of time. We will make sure that the time limit for a given test case is at least five times longer than the time it took for the reference Python algorithm written by the TA to solve that test case correctly.
- There is no limit on input size, number of time-travel channels, etc., other than specified above (32-bit integers, etc). If several optimal solutions exist, then any of them will count as correct.
- Please submit your homework code through Vocareum ( https://labs.vocareum.com/ ) under the assignment HW1. Useranme is your email address. 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 so that we will invite you again.
- 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. Late penalty will be applied as specified in the syllabus if your latest submission is after the deadline.
