FIT ČVUT Course Pages
BI-ZUM — Základy umělé inteligence
Jdi na navigaci předmětu

1. Systematic state space search

Introduction

As part of this task, the student implements FIVE METHODS of systematic state space search and demonstrates the functionality of the implemented algorithms in solving the problem of finding the path in the maze. The programming language in which the algorithms will be implemented is chosen by the student.

Task

Solve the task of finding the path in the maze using five methods of systematic state space search:

  • Random Search
  • Depth Search (DFS)
  • Width Search (BFS)
  • Greedy Search,
  • A * algorithm with such a heuristic that it always finds the shortest path.

INPUT: Maze for testing algorithms. Mazes are available in the form of text files.

OUTPUT: Simple visualization of the operation of each of the algorithms.

Subtasks:

  1. Design a suitable coding of the problem of finding the path through the maze so that it is possible to use the methods of systematic search of the state space to solve it.
  2. Implement the 5 above methods of systematically searching the state space.
  3. Implement a maze load from a text file.
  4. Implement a simple visualization of the algorithm’s operation.

Pseudocodes:

See the slides from lectures.

Datasets (maze):

  1. test dataset
  2. dataset for evaluation

Program architecture

  1. It is possible to implement each state space search algorithm as a separate program, or it is possible to create one program and select the algorithm from the command line.
  2. To enter the parameters needed to run the program (eg to enter the name of the maze file to be used), preferably use standard I / O or pass parameters when calling the program from the command line. Do not use program source editing.

Input

Maze format:

XXXXXXXXXXXXX
X           X
X  XXXXXXX  X
X     X     X
X X X X XXX X
X X         X
XX  X XXXXX X
X   X       X
X X X XXX XXX
X           X
X XXX X   X X
X           X
XXXXXXXXXXXXX
start 1, 7
end 5, 3
  • X are impenetrable walls, gaps indicate free passage.
  • the position is given in Cartesian coordinates, with the origin of the coordinate system in the upper left corner and the positive half-axis of the y-axis oriented downwards.
  • start 1, 7 means that the start is located at coordinates [1,7].
  • The maze is always entered correctly, ie the maze is bounded by a wall and the beginning and end of the maze are not located "in the wall".

Output

The required output is a simple visualization of the operation of each algorithm. Without meeting this goal, the task will not be evaluated and it will not be possible to submit it. Implement a simple visualization, when in each iteration the activity of the algorithm in the terminal will be displayed (stepping). The gradual opening of the nodes must be visible and at the end the path found must be displayed. At the end of the algorithm, write down the number of expanded nodes and the length of the path - the number of steps (edges) from start to finish.

Example output:

XXXXXXXXXXXXX
X           X
X  XXXXXXX  X
X ###EX     X
X X#XoX XXX X
X Xooo#     X
XX#oX#XXXXX X
XSooX       X
X#X#X XXX XXX
X           X
X XXX X   X X
X           X
XXXXXXXXXXXXX
--------------
S Start
E End
# Opened node
o Path
X Wall
space Fresh node
--------------
Nodes expanded: 17
Path length: 8

Formal requirements and submission

  • Before presenting the assignment to the instructor at the exercise, upload the assignment to your repository set up for the BI-ZUM course at the faculty gitlab. The procedure for setting up a repository is described on the main page of the exercise.

Recommended literature for task 1

[1] BI-ZUM lectures (you will find pseudocodes of algorithms in them)

[2] Norvig, Russel: Artificial Intelligence: A Modern Approach, PDF

[3] pseudocodes for chapters from a given book http://aima.cs.berkeley.edu/algorithms.pdf

[4] Depth-First Search (DFS) https://brilliant.org/wiki/depth-first-search-dfs/