91 lines
3.9 KiB
TeX
91 lines
3.9 KiB
TeX
\documentclass{article}
|
|
\date{2022-09-29}
|
|
|
|
%\usepackage{amsmath}
|
|
%\usepackage{amssymb}
|
|
\usepackage{fancyhdr}
|
|
|
|
\usepackage[hmargin=1in,vmargin=1in]{geometry}
|
|
\pagestyle{fancy}
|
|
\lhead{Emi Simpson}
|
|
\chead{Introduction to AI - Lab 1 - Summer Orienteering}
|
|
\rhead{\thepage}
|
|
\fancyfoot{}
|
|
|
|
\newcommand{\f}[1]{\textnormal{#1}}
|
|
\newcommand{\st}{\textnormal{ s.t. }}
|
|
\newcommand{\bb}[1]{\mathbb{#1}}
|
|
\newcommand{\var}[1]{\textnormal{#1}}
|
|
\newcommand{\bld}[1]{\textbf{#1}}
|
|
\newcommand{\flr}[1]{\left\lfloor#1\right\rfloor}
|
|
\newcommand{\paren}[1]{\left(#1\right)}
|
|
\newcommand{\sqb}[1]{\left[#1\right]}
|
|
\newcommand{\ben}{\begin{enumerate}}
|
|
\newcommand{\een}{\end{enumerate}}
|
|
|
|
\begin{document}
|
|
\section{Writeup}
|
|
|
|
My code is divided into a fed discrete modules, each of which detailed below.
|
|
|
|
\subsection{\texttt{read\_in} and \texttt{write\_out}}
|
|
|
|
These two modules are dedicated to transforming data to and from the specified format.
|
|
For improving testability, as many functions as possible work on data itself. Other
|
|
than that, it's pretty mundane.
|
|
|
|
Of note, I've chosen to represent distances and elevations as integer values rather
|
|
than floating point. To ensure that no significant data is lost, we measure distances
|
|
in millimeters and speeds is seconds per kilometer (or equivalently microseconds per
|
|
meter). This was mostly done out of my strong distaste for floating point numbers,
|
|
but seems to have benefitted performance slightly.
|
|
|
|
\subsection{\texttt{a\_star}}
|
|
|
|
This is where the actual routing algorithm lies, although not the heuristic nor the
|
|
neighbor finding algorithm. The A* algorithm I've implement is pretty generic and
|
|
works on any search space for which a neighbor function and a heuristic can be
|
|
defined.
|
|
|
|
It may be interesting to you that I've combined the cost and neighbor function. This
|
|
mostly to make the code a little simpler. However, the core mechanics of the
|
|
algorithm work nonetheless.
|
|
|
|
I've also written the function \texttt{pathfind\_multi}, which is able to find a path
|
|
which passes through several different checkpoints. This is the function which is
|
|
ultimately called to perform pathfinding.
|
|
|
|
This function simply repeatedly calls the normal \texttt{pathfind} function for each
|
|
pair of adjacent goals.
|
|
|
|
\subsection{\texttt{world}}
|
|
|
|
Perhaps the most interesting part of the code, this module is what defines the search
|
|
space, heuristic function, and neighbor function. Each node is simply represented by
|
|
a tuple containing an X and a Y coordinate. When the \texttt{neighbor} function is
|
|
called, these coordinates are looked up. Each adjacent node is evaluated, and a cost
|
|
(in seconds) is produced for moving to any valid node, and the results are returned.
|
|
More details about the specifics can be found in the detailed doccomment written for
|
|
the \texttt{neighbor} function.
|
|
|
|
This section also contains a heuristic function, which is considerably simpler. By
|
|
looking only at the coordinates of the function, we can compute the minimum distance
|
|
needed to be travelled between the two points. On a flat surface, this computation is
|
|
exact. For performance, we leave out height from the computation. However, by
|
|
assuming that all terrain is flat, we have not affected the admissibility of the
|
|
heuristic. Real conditions will be equivalent or worse than the predicted measure.
|
|
|
|
The last step in computing the heuristic is simply to convert between distance (in
|
|
millimeters) and time (in microseconds). To do this, we just use the fastest speed
|
|
possible, as to keep admissibility. In our implementation, this happens to be 500
|
|
microseconds per millimeter, the speed we have selected for \texttt{ROAD} terrain, and
|
|
also a reasonable human jogging speed.
|
|
|
|
\subsection{Conclusion}
|
|
|
|
If this writeup has left you with any unanswered questions, I encourage you to look
|
|
into the docstrings I've left in my code. Almost all functions defined for this
|
|
project should be documented, and most have examples that you can run using
|
|
doctesting.
|
|
|
|
\end{document} |