program an agent to find a path through the maze and reach the exit.

Your program will solve the problem of finding the shortest path given an initial start state and one goal state. The maze layout will be provided as a simple text file, in which $\%$ means obstacles, $$S$$ is the starting position, and $$G$$ the goal location. See the sample mazes files uploaded with the homework for an illustration.

The agent can move in one of four directions: North, West, South, and East.

You should implement the state representation, transition model, and goal test necessary to solve the problem. Then, you should implement the following search algorithms

$($a$)$ Depth$-$first search

$($b$)$ Greedy best$-$first search

$($c$)$ A$*$ search

Your program should run using Python $3.$ Your code can only import extra modules, but only if they are part of the standard python library.

For this part $,$ you will use the Euclidean distance from the current position to the goal as the heuristic function for A$*$ search.

For each maze, your solution should include an output $,$ the solution cost, and the number of nodes expanded in your search.

Your program should run as follows:

python$3$ search.py $--$method astar maze.txt

where astar is the name of the method, which can be one of depth, greedy, or astar, and maze.txt is the input file. We will supply three mazes that you can use to test your program, but you can test other mazes.

Please describe the algorithms and data structures that you used for the implementation of all three search strategies. Answer the following questions in your solution:

$$ What is a state?

$$ What is a node?

$$ Are they the same or different in your implementations?

$$ What is the frontier?

$$ Do you maintain an explored states list?

$$ How are repeated states detected and managed?