blob: 1672c403564fec1f5542809ee09a751babf532e0 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{parskip}
\title{Writing 2}
\author{Matt Strapp}
\date{2021-02-26}
\begin{document}
\maketitle
\section*{Theta*}
This paper is about a modification of the $A^{\ast}$ algorithm that is dubbed $\theta^{\ast}$ \cite{paper}.
The paper is proposing a new algorithm by building on a previous one and altering it for other conditions.
Theta$^{\ast}$ modifies A$^{\ast}$ by allowing A$^{\ast}$ where any vertex can be the parent of any other vertex, compared to A$^{\ast}$ where the only successors allowed are the direct parents of the node.
The differences can best be demonstrated when there are obstacles in a given grid system. This is demonstrated in the paper as obstacles in a video game. The paper also mentions that it can be used for robotics for the same reason: pathfinding.
In the paper, the authors validate the algorithm with experiments involving small grids, large grids, and maps from the CRPG Baludr's Gate II.
The starting and stopping points were random for all of the experiments used.
The basic Theta$^{\ast}$ ran slightly faster than its angle-propagating counterpart in the experiments given.
While the full details of the experiments were not directly given, each of the algorithms were run either 500 times each for the random grids or 118 times each using the Baldur's Gate II maps.
The averages table was given of both the path lengths and the runtimes for everything except for A$^{\ast}$ using visibility graphs because of the large runtime that occured.
The experiments ran showed that the basic Theta$^{\ast}$ and a modified version of Theta$^{\ast}$ that adds angle propagation to the path selections ran faster and had better results than A$^{\ast}$ and a similar algorithm that also uses edge propagation titled Field D$^{\ast}$.
Neither the raw data nor the actual C\# used to test were given in the paper or in any of its references.
Pseudocode was given which allows others to write their own code and test their data against the data given in the paper.
The conclusion the paper draws is that basic Theta$^{\ast}$ and Angle-propagating Theta$^{\ast}$ compromise between speed and accuracy to make an algorithm made mainly for dealing with obstacles.
This is supported by all of the experiments that were ran.
The paper was well-written assuming someone has at least moderate understanding in artificial intelligence algorithms and the various mathematics involved with them.
It should be recommended that anyone reading this paper should also understand A$^{\ast}$ because Theta$^{\ast}$ is best described as both a derivative and variant of A$^{\ast}$.
Anyone who has not read on A$^{\ast}$ will likely be unable to discern what many of the variables stand for as their meanings are only given in context of Theta$^{\ast}$ and not A$^{\ast}$ or other algorithms as a whole.
The pseudocode given was documented as a figure and was also explained step-by-step by describing what it does and how Theta$^{\ast}$ works.
The most interesting part of the paper was probably its possible uses in the fields of robotics and game design where navigating around obstacles is important.
Obstacles are a paramount thing in both real life and CRPGs so finding a way to get around them quickly is tantamount to their functions.
As someone who plays CRPGs it is interesting to see how the AI works to find the best path around obstacles that exist in the gamespace.
\medskip
\bibliographystyle{unsrt}
\bibliography{writing2}
\end{document}
|
