\documentclass[12pt,fullpage]{article}
\usepackage{indentfirst}
\usepackage{mathptmx}
\setlength{\textwidth}{6.75in} %{6.5in}
\setlength{\topmargin}{-0.25in} %{0.5in}
\setlength{\oddsidemargin}{-0.1250in}
\setlength{\textheight}{9.0in} %{8.5in}
\author{Dmitriy Bespalov}
\title{Introduction to AI. \\ Assignment 1a -- Implementing the BFS and DFS algorithms.}
\date{}
\begin{document}
\maketitle
\section*{1.}
\begin{description}
\item [States:] Each state represents a piece of railway in the loop that we are trying to form.
\item [Initial State:] A piece of rail track that we start construction of the loop. In case we
start with multiple tracks, a piece on one of the ends will become our starting track.
\item [Successor Function:] From each state it is possible to go in three directions: straight,
left or right (one straight piece and two corners).
\item [Goal Test:] A path of railway pieces that we are constructing is a closed loop without
intersections (intersections are checked at the moment of expanding nodes though).
\item [Path Cost:] In this problem we assign path cost to be 1.
\end{description}
\section*{2.}
I have chosen the following data structure to represent the nodes. Each node stores a railway piece
that this node represents. Also, our data structure stores path information from the root to itself.
This allows us to quickly check for intersections of the tracks and decide whether a goal state is
reached. Furthermore, we only need to maintain nodes that are on the fringe.
The data structure for railway pieces is as follows. Each railway piece has three points in discreet
coordinates, such that the first randomly generated piece is placed in the origin of these coordinates.
These coordinates are used to trace intersections and establish if a goal state is reached, no constraints
are introduced by this reference frame. The three points that every railway piece stores are: coordinates of
the point where this piece is placed and coordinates of two points that adjacent to the first one, and represent
which sides this railway is connecting. Finally, by agreeing to use the last two points in a particular
way, a direction of our path can be introduced (we choose direction from $(x_1,y_1)$ to $(x_2,y_2)$).
\section*{3.}
Implemented. Please see README file for information on how to run the program.
\section*{4. Test 1.}
The first test was a single run of each of the three algorithms (BFS, DFS, DLS) with an initial state
corresponding to a straight piece. Run time is provided in the table below. You can obtain more information
from the output of the program which can be found in \emph {output\_1\_BFS.txt}, \emph {output\_1\_DFS.txt},
\emph {output\_1\_DLS.txt} (BFS, DFS, DLS algorithms respectively) in \emph {Outputs} directory.
\section*{Test 2.}
The second test was a single run of each of the three algorithms (BFS, DFS, DLS) with an initial state
corresponding to a curved piece. Run time is provided in the table below. You can obtain more information
from the output of the program which can be found in \emph {output\_2\_BFS.txt}, \emph {output\_2\_DFS.txt},
\emph {output\_2\_DLS.txt} (BFS, DFS, DLS algorithms respectively) in \emph {Outputs} directory.
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
& Test 1 & Test 2 \\
\hline
BFS & 0.078s & 0.060s \\
\hline
DFS & 0.035s & 0.063s \\
\hline
DLS & 0.035s & 0.050s \\
\hline
\end{tabular}
\end{center}
\section*{Test 3.}
The third experiments performed consisted of 20 runs of each algorithm with 5 randomly generated
pieces as an initial configuration. Outputs of all runs are available in \emph {Outputs} directory
in files \emph {output\_3.*\_BFS.txt}, \emph {output\_3.*\_DFS.txt}, \emph {output\_3.*\_DLS.txt}.
Here are some of the data we obtained from this experiment.
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
& \parbox[t]{0.7in}{Average number of nodes visited\\}
& \parbox[t]{0.7in}{Average number of nodes stored in the memory}
& \parbox[t]{0.7in}{Min number of nodes stored in memory }
& \parbox[t]{0.7in}{Max number of nodes stored in memory}
& \parbox[t]{0.7in}{Average execution time}
& \parbox[t]{0.7in}{Min execution time}
& \parbox[t]{0.7in}{Max execution time} \\
\hline
BFS & 2362.4 & 831.8 & 0 & 6839 & 0.5924s & 0.035s & 4.284s \\
\hline
DFS & 31.9 & 4.1 & 0 & 35 & 0.03715s & 0.035s & 0.041s \\
\hline
DLS & 1729 & 5.9 & 0 & 25 & 0.0808s & 0.035s & 0.744s \\
\hline
\end{tabular}
\end{center}
Values appearing in this table can be obtained from the output file \emph {test3\_data.txt} in
\emph {Outputs} directory for the script \emph {runTests.py}.
\section*{5.}
Breadth-First Search has exponential running time and memory usage in terms of length of the
path to the closest solution state. As a result we can see that it took significant amount
of time as well as memory to find the solution. Although, solutions are optimal.
Although Depth-First and Depth-Limited searches can give us exponential time,
my search was designed in such a way that at each expansion it would consider right piece,
then left and straight pieces. That resulted in fast running time and efficient
memory usage. On the other hand, solutions were not always optimal. Finally, for
Depth-Limited Search we were getting optimal solutions more often (depth limitation
prevented the search from going too far), on the other hand average running time and
memory usage were bigger than for DFS.
\end{document}