James Millns

BSc Computing (Software Engineering)

Project Title: Artificial Neural Networks used for Pathfinding and Navigation

Project Description

Artificial Intelligence (AI) has been a growing field of study since its inception during 1943 with Alan Turing’s Enigma Code cracking computer. It has grown to the point where modern Artificial Neural Networks (ANN) can be trained to perform increasingly complex tasks.

This project aims to test whether an Artificial Neural Network can be applied to the pathfinding problem in a meaningful way, whereby it performs comparatively to more deterministic pathfinding solutions and algorithms.

The hypothesis of the project postulates that it is possible to make an Artificial Neural Network (ANN) based pathfinding artificial intelligence (AI) that can navigate a path through a dynamic and changing environment with similar performance to more deterministic algorithm-based pathfinding solutions.

Unity was used to implement an environment that could support three different pathfinding implementations;
A-Star: a search algorithm that efficiently finds the shortest path.
NavMesh: a native pathfinding solution available in unity and other game design engines.
MLAgents: a library available for Unity that was used to make an ANN that uses ray casts to survey its environment

The ANN was trained with the Reinforcement learning method, whereby it tries to maximise a reward over multiple generations. In this case it was rewarded for desirable behaviour like reaching the target, and punished for undesirable behaviour like moving into walls or boundaries and running out of time.
Over multiple generations of training, the ANN learned to navigate through complex environments and reach the target.

Each pathfinding method was tested 1000 times on 21 levels, each with an incremental number of randomly placed obstacles. In total, 63,000 simulations were performed to gain the results. The results showed that A-star performed the best out of the three, while NavMesh and ANN performed very comparatively. The ANN was able to successfully navigate to the target ~75% of the time in the most complex environment used.

The project’s aim to develop an ANN that could path find through a dynamic environment was successfully met. The results gained from the simulations indicate that an ANN can be effective at pathfinding. This supports the initial hypothesis of the project.

I wanted to improve my IT skills and challenge myself. I enjoy problem solving, maths, and creating solutions.

I was recommended UWTSD due to the good reputation.

I would like to go into a software development role, or continue with my studies to further investigate the applications of Artificial Intelligence.

Visit James’s LinkedIn

Share this page:

Share on facebook
Share on twitter
Share on linkedin