Autonomous maze solving and obstacle avoid algorithms

2022 COE Engineering Design Project (TY07)

---

Faculty Lab Coordinator

Truman Yang

Topic Category

Software Systems

Preamble

Maze solving algorithm is the search for an optimal path from a start location to a goal location in a maze. Maze solving algorithms are typically designed as a kind of graph search. Some are AI-based, such as Q-learning algorithms. Some are not, for example, A*, DFS, BFS, Dijacstra, etc. 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 implement multiple maze solving and obstacle avoid algorithms using robot and evaluate their difference on performance.

Objective

The object of the project is to implement a few maze solving and obstacle avoid algorithms. 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 these algorithms should be proposed and evaluated.

Partial Specifications

(1) Students’ design will be based on existing 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 maze solving and obstacle avoid algorithms will be conducted.
(2) Idea generation technique with SCAMPER.
(3) All functions from experiment should be detailed documented.

Group Responsibilities

Familiar with existing algorithm. Design, implement, and test new algorithms as specified above.

Student A Responsibilities

Analyze and implement existing maze solving and obstacle avoid algorithms and implement them on the robot

Student B Responsibilities

Evaluate the performance of algorithms

Student C Responsibilities

Detail documentation of the project

Student D Responsibilities

Design and implement an App for demonstration

Course Co-requisites

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.