Solving problems by search

Put your solution into a search_agents.py file and upload it. See deadlines in https://cw.felk.cvut.cz/brute

Implement a Breadth-First agent and Uniform-Cost agent

Implement an Iterative-deepening agent and the A* algorithm with at least one heuristics. You can implement more than one heuristic.

You algorithms will be tested on several maps checking whether they find a valid path and the optimal one. Manual evaluation will reflect readability and efficiency of your implementation.

The code essentially defines the problem, provides a necessary interface and basic visualization for easier development. The basic usage is demonstrated in the sandbox.py. You will probably need to define a Node class and some data structures for keeping/organizing the Nodes.

kuimaze package (zip-archive) contains also some maps and package documentation, which is also available on-line. The package is a bit more general it contains more methods we need at the moment.

The basic interface/communication with the problem provide the following methods:

problem = kuimaze.Maze('map.png') # create a problem (object)
state = problem.get_start_state() # get started
problem.is_goal_state(state)      # does the state belong to the goal set?

Loop over all actions that are possible for the given state.

for action in problem.get_actions(state):

Get result of an action

child_state, transition_cost = problem.result(state, action)

The basic visualisation and how to construct the path is shown in sandbox.py.

Some screenshots:

Probably a better solution: