The first two weeks of the course Artificial Intelligence CS188.1x or self-learning algorithms AI

Do you think that machines with artificial intelligence today already know how to do and what not?


In the photo is a robot who can fold towels.

In distance learning course CS188.1x Artificial Intelligence from the University of California at Berkeley, Professor Dan Klein lists some tasks in the field of artificial intelligence. Some of them have already been resolved (fully or partially), and the other part has not yet. The course is dedicated to AI algorithms, on which many modern intelligent systems are based. I would like to briefly share what it begins with and tell you more about the first practical task.

The first two weeks were devoted to:

• Introduction to programming in Python;
• History of development and review of modern achievements in the field of AI ( video );
• Uninformed search method ( video ) - depth search, wide search, Dijkstra's algorithm;
• informed search method ( video ) - A *.

(For reference, links to Wikipedia: the uninformed search method — depth search, wide search , Dijkstra’s algorithm , an informed search method — A * ).
')
As a review of advances in artificial intelligence, Professor Dan Klein has compiled the following list of what AI can already do and what it does not. Every year, he notes which tasks go from the category “no” to the category “in question”, and which from the category “in question” into the category “yes”:

• Good to play table tennis - yes;
• Good to play Jeopardy (Own game) - yes;
• Driving safely on winding mountain roads - yes;
• Driving a car safely over Telegraph Avenue (street) is questionable;
• Buying groceries for a week through the Internet - yes;
• Buying groceries for a week in a regular store - no;
• Discovering and proving new mathematical theorems is questionable;
• Successfully engage in dialogue with a person for an hour - no;
• Perform surgery - in question;
• To clean the dishes and fold laundry - yes;
• Translate spoken Chinese to spoken English in real time - yes;
• Writing interesting stories is not.

The third week was a practical project. It was required to implement all the algorithms mentioned in the lectures. In particular, finding a path in a maze with different conditions in the world of Pacman.

Sources of tasks in Python ( zip-archive ) can be downloaded from the official site of the course , where there is all the material: video lectures, presentations, descriptions of tasks.

Next, I will translate the text of the first task and describe what needs to be run to verify the solution. To perform tasks on your computer, Python must be installed, for example, in the Anaconda assembly.

Task N1. Search for a given position. Depth search algorithm

Pacman lives in a world of winding corridors and tasty round points. And effective navigation in this world will be his first step to victory.



Unzip the archive. In searchAgents.py you will find a fully implemented SearchAgent class that starts a search for a path through the maze and then executes this path step by step. Path search algorithms are not implemented - this is your job.

First, make sure that the SearchAgent class works correctly:

 python pacman.py -l tinyMaze -p SearchAgent -a fn=tinyMazeSearch 

This command tells SearchAgent use tinyMazeSearch as a search algorithm, which is implemented in search.py . Pacman must successfully pass the maze.

In order to perform the first task, you need to add only one function depthFirstSearch , which is located in the search.py file and must implement a depth-first search algorithm (DFS).

Comment. The algorithms — depth search (DFS), width search (BFS), Dijkstra algorithm (UCS), and A * are very similar and differ only in some implementation details. Thus, having implemented DFS, the rest is obtained from it relatively simply.

For reference, the general pseudocode search algorithm of the lectures is as follows:



Term descriptions can be found in lectures or wikis .

Important note 1: The search function must return a list of actions that will lead the agent from the starting position to the target. Therefore, the graph node must contain not only the current state of the game, but also the information necessary to restore the path from the initial position. In addition, all these actions must be valid, i.e. do not pass through walls.

Important note 2: Make sure you use the Stack , Queue and PriorityQueue data structures implemented in util.py These implementations have special properties that are necessary for compatibility with autograder.py (see below).

To ensure that your algorithm is not infinite, when implementing the search function, avoid visiting any states that have already been considered.

Your code should quickly find a solution for:

 python pacman.py -l tinyMaze -p SearchAgent 

 python pacman.py -l mediumMaze -p SearchAgent 

 python pacman.py -l bigMaze -z .5 -p SearchAgent 

During the execution of the command, a maze will appear on the screen, which will show the locations examined by the search function. The brighter the red color, the more times this state was part of the path as a result of the search.

Tip: If you use Stack in your DFS implementation, the solution found for mediumMaze should be 130 elements long (assuming you are adding new items to the stack in the order specified by getSuccessors . If you add them in the reverse order, you will get 246). Is the solution found at least economical? If not, think about what the depth search does wrong.

When launched, pacman.py supports several input parameters. A list of all options and their values ​​can be called with the command:

 python pacman.py -h 

Or look in the commands.txt file.

Job check

The archive includes an autograder.py script that allows you to verify the implementation of all tasks on your computer with the following command:

 python autograder.py 

For more information on autograder.py see the Autograding section in the course manual .

Finally a couple of words

At first it may seem that the surrounding code is too much and difficult to understand, but it passes quickly. All code is well documented, so you will never get lost.

For those who especially want to break their heads, the most difficult tasks are №6 and №8 .

I tried to state briefly, therefore I recommend to watch lectures from the site of the course. There you will find many other practical topics and tasks.

On Habré there are some more articles about this course. Once and twice , and from the third I found out about him.

Good luck to your pacman!