Performance Evaluation of Pathfinding Algorithms of Maze Solver

2021 COE Engineering Design Project (TY07)

---

Faculty Lab Coordinator

Truman Yang

Topic Category

Software Systems

Preamble

Pathfinding is the search for an optimal path from a start location to a goal location in a maze. In Artificial Intelligence, pathfinding algorithms are typically designed as a kind of graph search. The performance of these algorithms is affected by several factors such as the maze size, path length, the number and distribution of obstacles. In this project, students will evaluate the performance of different pathfinding algorithms. Some are AI based such as Q-learning algorithms. Some are not, for example, A*, DFS, BFS, Dijacstra, etc. Our evaluation focus will be more on AI-based algorithms.

Objective

The object of the project is to implement a few pathfinding algorithms for a maze. The algorithms are compared by some criteria such as length of the found path, time for finding the path, etc. The results, presented analytically and graphically, show the application of different algorithms for mazes with various size and number of obstacles. In addition, improvement on Q-learning algorithm should be proposed and evaluated.

Partial Specifications

(1) Students’ design will be based on existing code of searching and Q-learning algorithms. Further improvement on design and performance evaluation are needed.
(2) Software development with Python should be efficient and effective.

Suggested Approach

(1) Literature review of pathfinding algorithms for maze will be conducted.
(2) Idea generation technique with SCAMPER.

Group Responsibilities

Design, implement, and test the algorithms as specified above.

Student A Responsibilities

Implement A*, DFS and BFS pathfinding algorithms

Student B Responsibilities

Evaluate the performance of A*, DFS and BFS pathfinding algorithms

Student C Responsibilities

Implement Q-learning algorithms

Student D Responsibilities

Evaluate Q-learning algorithms

Course Co-requisites

AI-related courses COE318: Software Systems

To ALL EDP Students

Due to COVID-19 pandemic, in the event University is not open for in-class/in-lab activities during the Winter term, your EDP topic specifications, requirements, implementations, and assessment methods will be adjusted by your FLCs at their discretion.