Subject: Fundamentals of Artificial Intelligence
Lecture: Bui Tien Len
TA: Nguyen Thai Vu
Student: Dang Ngoc Tien - 20127641
1. Introduction
In this project, students research and implement the searching algorithm. In addition, students have to visualize the result of the searching algorithm.
2. Requirements
- Individual project.
- Programming language: Python (for visualization, we recommend students use turtle library of Python)
- Timeline: 2 weeks.
- Code folder: include every coding files.
- Report folder: include file report.pdf:
- Student’s information
- Each algorithm, student report:
- The idea of the algorithm.
- Example (reference section input/output)
- Conclusion, pros and cons.
- Evaluation:
- Implement 5 searching algorithm: 70%.
- Report: 30%
- Every cheat/copy/lie will be punished with a course score of 0.
3. Problem
a. Problem description
- The robot has been sent to a maze of size M x N, and the robot has to find the path from the Source (starting position) to the Goal (ending position). The robot allows to move in 4 directions: up, down, left, right. In the maze, there are some obstacles.
- The student as asked to implement 5 search algorithms:
- Breadth-first search
- Uniform-cost search
- Iterative deepening search that uses depth-first tree search as core component and avoids loops by checking a new node against the current path.
- Greedy-best first search using the Manhattan distance as heuristic.
- Graph-search A* using the Manhattan distance as heuristic.
b. Input/output format
-
The format of the input file:
- First line: the size of the maze width, height.
- Second line: the position of the Source and Goal. For example: 2 2 19 16 meaning source point is (2, 2) and goal point is (19, 16).
-
Third line: the number of the obstacles in the maze.
-
The next following line, defining the obstacle by the rule:
- The obstacle is a Convex polygon.
- A polygon is a set of points that are next to each other clockwise. The last point will be implicitly concatenated to the first point to form a valid convex polygon.
-
The output:
- Graphical representation of polygons and path.
- Cost.
-
The example of input.txt
(Everything is relative, depend on your implementation)
22 18
2 2 19 16
3
4 4 5 9 8 10 9 5
8 12 8 17 13 12
11 1 11 6 14 6 14 1
4. References
The document in the Computer Science Department at the University of Science, Vietnam National University, Ho Chi Minh City.