Time Travelling Configuration - Uniform-Cost Search - Breadth-First Search - IT Assignment Help

Assignment Task:

Overview:

This is a programming assignment in which you will apply AI search techniques to some future “time travelling” 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 neighbouring grid locations. Within a possible grid world, there are some special bi-directional time- travelling channels located at certain locations that will allow your agent to travel in time forward or backwards in 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 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 1 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 in your agent to stay where it is. 

Your programming task is as follows. Given three inputs: (1) a time-travelling 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-travelling problem is given as a list of max-x, max-y, initial- year-location, target-year-location, plus a list of time-travel channels. For example (Note: The exact input format will be given at the end.

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 the shortest path as follows. Notice that every step in your output must be a legal action as specified above 

OUTPUT: (2020,1,3), (2020,2,4), (2020,3,4), (2023,3,4), (2023,4,5), (2023,4,6). 

Problem Description:

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 a 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 neighbour 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 neighbour 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 a 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 neighbours 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 the shortest possible operational path length. The 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 neighbours 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 centre 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 neighbours incurs a unit path cost of 10, while a diagonal move to a neighbour incurs a unit path cost of 14 as an approximation to 10√2 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-1 and 0 ≤ 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) in the southwest corner of the grid world. 
? The fourth line: Three positive 32-bit integers separated by a space character, “Year X Y” for the target year-location, where 0 ≤ X ≤ W-1 and 0 ≤ 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) in the southwest corner of the grid world. 
? The 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, we have 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 
3 
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 the cost. Each line should contain a tuple of four integers: Year, X, Y, Cost, separated by a space character, specifying the year- a location with the step cost to visit that year-location by your agent during its (time) travelling from the initial year-location to the target year-location.
 
For example, the following is a sample output of the corresponding input above: 
1570 
12 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 

Sample Inputs and Outputs 
Example 1 (BFS with no solution): 
input.txt

BFS 99 87 
2020 8 12 
2021 8 12 
2 2020 12 16 3011 
12 56 77 1 
output.txt

FAIL 

Example 1 (BFS with solution): 
input.txt

BFS 
99 87 
2020 8 12 
2020 8 12 2 
2020 12 16 3011 
3011 56 77 2487 
output.txt

0 1 2020 8 12 0 

Example 3 (UCS): 
input.txt

UCS 
99 87 
2020 8 12 
2024 8 13 
5 2020 12 16 3011 
3011 56 77 1 
12 0 0 2 
2 0 0 2024 
2020 8 13 2024 

output.txt

14 3 2020 8 12 0 
2020 8 13 10 
2024 8 13 4 
 
Example 4 (A*): 
input.txt

A* 99 87 
2020 8 12 
0 8 12 
1 2020 8 11 0 

output.txt

2040 
4 2020 8 12 0 
2020 8 11 10 
0 8 11 2020 
0 8 12 10 

This IT Assignment has been solved by our IT Experts at My Uni Paper. Our Assignment Writing Experts are efficient to provide a fresh solution to this question. We are serving more than 10000+ Students in Australia, UK & US by helping them to score HD in their academics. Our experts are well trained to follow all marking rubrics & referencing style.

Be it a used or new solution, the quality of the work submitted by our assignment experts remains unhampered. You may continue to expect the same or even better quality with the used and new assignment solution files respectively. There’s one thing to be noticed that you could choose one between the two and acquire an HD either way. You could choose a new assignment solution file to get yourself an exclusive, plagiarism (with free Turnitin file), expert quality assignment or order an old solution file that was considered worthy of the highest distinction.