# Introduction to Artificial Intelligence - Assignment 1

By Md Motasim Bhuiyan

B21-08

[e-mail]

**Table of Contents**
- [Introduction to Artificial Intelligence - Assignment 1](#Introduction-to-artificial-intelligence---assignment-1)
- [PEAS Description](#Peas-Description)
- [Performance Measure](#Performance-mMeasure)
- [Environment](#Environment)
- [Actuators](#Actuators)
- [Sensors](#Sensors)
- [Algorithm Flows](#Algorithm-Flows)
- [A* Algorithm](#A-Algorithm)
- [Backtracking Algorithm](#Backtracking-Algorithm)
- [Static Analysis](#Static-Analysis)
- [Individual statistics](#Individual-Statistics)
- [Comparison](#Comparison)
- [Map Example](#Map-Example)
- [Impossible Scenario](#Impossible-Scenario)
- [Repeated Cells](#Repeated-Cells)
- [Additional Findings](#Additional-Findings)
- [Priority Comparison between A* and Backtracking](#Priority-Comparison-between-A-and-Backtracking)

## PEAS Description
In this assignment, **Jack Sparrow** is the actor agent. And the PEAS is measured with respect to him.

### Performance Measure
The actor will reach Dead Man's Island avoiding the dangers and will follow the shortest path on it's way.
### Environment
The environment for the actor is a 9x9 lattice with obstacles and goals.

**Properties**
* Partially observable - The actor cannot see the whole grid
* Multiple agent - Apart from the actor agent there are other agents like Davy Jones, the Kraken etc.
* Deterministic - The next state of environment can be predicted based on the current state and the action applied
* Sequential - Current decision of the actor will have consequences on future decisions (i.e. visiting Tortuga will let the actor kill Kraken)
* Static - The environment do not change while the actor is thinking
* Discrete - The environment has states
* Known - The designer of the actor has full knowledge about the environment

### Actuators
Moving to a neighboring cell based on the decision taken.

### Sensors
* The **compass**
* Spyglass for variant 1
* Spyglass for variant 2

## Algorithm Flows

For both of the algorithms, 2 scenarios are considered - by not visiting Tortuga and avoiding the Kraken, and by visiting Tortuga and attacking the Kraken if required. After that, both cases are compared and the one generating shorter path is accepted.

### A* Algorithm
The A* algorithm uses the following function for prioritization of visits-
$$f(x) = dist(x) + h(x)$$
where $dist(x)$ is the distance of the cell $x$ from starting position and $h(x)$ is the distabce of the cell from the destination. For this assignment, it is possible to find the distance of two cells using the following formula-
$$distance(c1, c2) = max(|c1.x - c2.x|, |c1.y - c2.y|)$$
The cell with smallest $f(x)$ is prioritized first. In case, $f(x)$ of several cells are same, the one with smallest $h(x)$ is prioritized for visiting.

For a given origin and destination, the algorithm starts from the origin cell. It starts by adding the origin cell to the priority queue. Until the queue is empty or the destination is reached, the algorithm picks one cell and puts all valid (not visited, safe and does not increase cost of visiting) neighbor cells to a priority queue. Then it marks the cell as visited, updates $dest(x)$ and moves to the next cell. If the origin is reached, updated $dest(x)$ of the destination cell is returned. Otherwise `infinity` (100 for this assignment) is returned.
In case both of the scenarios return `infinity`, the map is a lose case.

### Backtracking Algorithm
Since checking the all the possible paths is a $O(2^{n^2})$ operation (effectively $k\times2^{81}$ for this assignment) which is impossible to generate and compare within finite time, modifications were made to reduce the number of *potential shortest paths*. Two techniques used for the modifications were-
* Not visiting a cell (and adding it to the optimal path) unless visiting will guarantee a smaller path than what it currently belongs to.
* Greedily picking the next cell for recursive call. For example, if there are 2 or more neighbour cells present for recursive calls, the one having the least $f(x)$ will be checked first. Although, unlike *A**, backtracking will go through all the neighbors eventually, this appraoch takes advantage of the first method and reduces the number of cells to check.

The backtrack function starts with an origin and a destination to reach. At the same time, it keeps track of the length of the path this call belongs to (for the position of Jack Sparrow, path length is 0). For initial checks if the cell is destination, path length is returned. In case of cell being invalid (visited or unsafe), `infinity` is returned. If none of the initial checks are applicable, $dist(x)$ is set to the current path length and cell is marked as visited. After that, neighboring cells are picked and sorted for visiting next. For each valid (On basis of modificatin 1) cell, backtrack function from that cell to destination is called with path length of `current length + 1`. After going through all of the neighboring cells, the minimum path length is returned.

## Static Analysis
For statical analysis, 1000 test cases were randomly generated and tested. Analysis that were done-
1. Mean, Mode, Median and standard deviation of time consumption for each algorithm and variant
2. Number of win condition, lose condition and win percentage
3. Comparison of different algorithms and variants

It was noticed that most of the generated maps were giving very small path length $\leq 4$ which is not ideal for accurate measurement. Maps that has solution path of length $\geq 6$ were only considered. For lose cases of such restriction, we considered if $dist(tortuga) \geq 6$ or not. It is worth noting that for lose cases, time consumption were not calculated.

Specs used for analysis-
* Device: HP Probook 4540s
* Processor: Intel Core i5-3360M (2.8 GHz, 3MB L3 cache, 2 cores)
* RAM: 4GB DDR3 PC3-10600 SDRAM
* GPU: Built-in

### Individual statistics

**A\* Algorithm (Variant 1)**
| Stat | Result|
| -------- | -------- |
|Mean|0.15ms|
|Mode|0.11ms|
|Median|0.11ms|
|Standard Deviation|0.59ms|
|Win cases | 947|
|Lose cases| 53|
|Win percentage| 94.7%|

**A\* Algorithm (Variant 2)**
| Stat | Result|
| -------- | -------- |
|Mean|0.12ms|
|Mode|0.09ms|
|Median|0.09ms|
|Standard Deviation|0.33ms|
|Win cases | 947|
|Lose cases| 53|
|Win percentage| 94.7%|

**Backtracking Algorithm (Variant 1)**
| Stat | Result|
| -------- | -------- |
|Mean|4.31ms|
|Mode|3.64ms|
|Median|3.93ms|
|Standard Deviation|2.62ms|
|Win cases | 947|
|Lose cases| 53|
|Win percentage| 94.7%|

**Backtracking Algorithm (Variant 2)**
| Stat | Result|
| -------- | -------- |
|Mean|4.46ms|
|Mode|4.26ms|
|Median|3.96ms|
|Standard Deviation|3.69ms|
|Win cases | 947|
|Lose cases| 53|
|Win percentage| 94.7%|

### Comparison
For the 947 win maps, time consumption comparison for 4 different cases were analyzed and comparisons were made. For each case, the algorithm and variant gets highest number of faster path finding is considered a winner and rest of the statistics are made with respect to that algorithm and variant.
For speed comparison, *10% trimmed mean* were taken and compared.

For this part of the report the following abbreviations were used-
* BT -> Backtracking
* V1 -> Variant 1
* V2 -> Variant 2
* *c/t* -> Compared to
* Map Count -> Number of maps where winner algorithm was faster
* Map Percentage -> Percentage of maps where winner algorithm was faster

| Case | Winner | Map Count | Map Percentage|Speed comparison|
| -------- | -------- | -------- | -------- |-------- |
|A* V1 *c/t* A* V2|A* V2|652|68.85%|A* V2 is 13.4% faster|
|BT V1 *c/t* BT V2|BT V1|503|53.12%|BT V1 is 0.77% faster|
|A* V1 *c/t* BT V1|A* V1|947|100%|A* V1 is 3445% faster|
|A* V2 *c/t* BT V2|A* V2|947|100%|A* V2 is 3972% faster|

## Map Example
For the examples, following unicode symbols were used-
| Cell | Unicode symbol in the report | ASCII symbol in console or output files |
| -------- | -------- | -------- |
| Jack Sparrow |👨|J
| Davy Jones |💀|D
| Kraken |🐙|K
| Rock |🗿|R
| Tortuga |🏝️ |T
| Dead Man's Island |💰|I
| Enemy perception zones |🟥|!
| Normal cells |⬛|-
| Visited cell |🟩|*
| Cells that were visited twice |🟢|o

### Impossible Scenario
There can be two cases of impossible scenarios-
* All paths towards Dead Man's islands are bloced (i.e. cells are either enemy/rock or in enemy perception zone)
* Jack Sparrow starts in enemy perception zone hence killing him instantly.

One example of the first example is-

[0,0] [5,6] [7,7] [5,8] [8,8] [6,8]
1

visualized as

👨⬛⬛⬛⬛⬛⬛⬛⬛
⬛⬛⬛⬛⬛⬛⬛⬛⬛
⬛⬛⬛⬛⬛⬛⬛⬛⬛
⬛⬛⬛⬛⬛⬛⬛⬛⬛
⬛⬛⬛⬛⬛🟥🟥🟥⬛
⬛⬛⬛⬛⬛🟥💀🟥🗿
⬛⬛⬛⬛⬛🟥🟥🟥🏝️ 
⬛⬛⬛⬛⬛⬛🟥🐙🟥
⬛⬛⬛⬛⬛⬛⬛🟥💰

Input for the second case can be following-

[0,0] [1,1] [6,4] [8,3] [7,5] [3,1]
2

which can be visualized as-

👨🟥🟥⬛⬛⬛⬛⬛⬛
🟥💀🟥⬛⬛⬛⬛⬛⬛
🟥🟥🟥⬛⬛⬛⬛⬛⬛
⬛🏝️⬛⬛⬛⬛⬛⬛⬛
⬛⬛⬛⬛⬛⬛⬛⬛⬛
⬛⬛⬛⬛🟥⬛⬛⬛⬛
⬛⬛⬛🟥🐙🟥⬛⬛⬛
⬛⬛⬛⬛🟥💰⬛⬛⬛
⬛⬛⬛🗿⬛⬛⬛⬛⬛

### Repeated Cells
Even though the logics implemented inside the algorithms ensure that no cells are visited twice, it is possible that in some cases, visiting two cells are mandatory. For some cases, visiting a cell twice does not affect path length (explained further in [later part of the report](#priority-comparison-between-a-and-backtracking)).

Following is a scenario where part of a path is visited twice-

👨⬛⬛⬛⬛⬛⬛⬛⬛
⬛⬛⬛⬛⬛⬛⬛⬛⬛
⬛⬛⬛⬛⬛⬛⬛⬛⬛
⬛⬛⬛⬛⬛⬛⬛⬛🟥
⬛⬛⬛⬛⬛⬛⬛🟥🐙
⬛⬛⬛⬛⬛🟥🟥🟥🟥
⬛⬛⬛⬛⬛🟥💀🟥💰
⬛⬛⬛⬛⬛🟥🟥🟥🗿
⬛⬛⬛⬛⬛⬛⬛⬛🏝️

with the input

[0,0] [6,6] [5,7] [8,5] [8,7] [6,0]
1

The solution of the map is following-

🟩⬛⬛⬛⬛⬛⬛⬛⬛
⬛🟩⬛⬛⬛⬛⬛⬛⬛
⬛⬛🟩⬛⬛⬛⬛⬛⬛
⬛⬛⬛🟩⬛⬛⬛🟩⬛
⬛⬛⬛⬛🟩🟩🟩⬛🟩
⬛⬛⬛⬛🟢⬛⬛⬛🟩
⬛⬛⬛⬛🟢⬛⬛⬛🟩
⬛⬛⬛⬛🟢⬛⬛⬛⬛
⬛⬛⬛⬛⬛🟢🟢🟢🟩

## Additional Findings
### Priority Comparison between A* and Backtracking
While testing on several maps, difference of paths in A* and Backtracking were observerd. Although the path lengths were same and the paths were optimal in terms of their respective maps, the differences were quiet interesting.
For, map `[0,0] [5,5] [2,6] [0,6] [1,7] [4,0]`, the outputs of A* and Backtracking were-

🟩⬛⬛⬛⬛⬛⬛⬛⬛
⬛🟩⬛⬛⬛⬛⬛🟩⬛
⬛⬛🟢⬛🟩⬛🟩⬛⬛
⬛🟢⬛🟩⬛🟩⬛⬛⬛
🟩⬛⬛⬛⬛⬛⬛⬛⬛
⬛⬛⬛⬛⬛⬛⬛⬛⬛
⬛⬛⬛⬛⬛⬛⬛⬛⬛
⬛⬛⬛⬛⬛⬛⬛⬛⬛
⬛⬛⬛⬛⬛⬛⬛⬛⬛

and

🟩⬛⬛⬛⬛⬛⬛⬛⬛
🟩⬛⬛⬛⬛⬛⬛🟩⬛
🟩⬛⬛⬛⬛⬛🟩⬛⬛
🟩⬛⬛⬛🟩🟩⬛⬛⬛
🟩🟩🟩🟩⬛⬛⬛⬛⬛
⬛⬛⬛⬛⬛⬛⬛⬛⬛
⬛⬛⬛⬛⬛⬛⬛⬛⬛
⬛⬛⬛⬛⬛⬛⬛⬛⬛
⬛⬛⬛⬛⬛⬛⬛⬛⬛

respectively. It is clearly visible that A* algorithm has path with 2 cells visited twice. Although both are shortest path, the difference is quite interesting. After some analysis, it was found that for two neighbors with same $f(x)$, $dist(x)$ and $h(x)$, A* algorithm picks the diagonal one, while backtracking picks the linear one. However, such paths are generated only when Tortuga is visited, and since the path from `[0,0]` to tortuga and the path from Tortuga to Dead Man's Island is calculated separately, same cells are deemed to be visited twice.