Introduction to Artificial Intelligence

Assignment 1


Simple agent and environment simulator

In this first exercise you are asked to implement a simple environment simulator that generates instances of a search problem, runs agent programs, and evaluates their performance according to a simple performance measure. The search problem we will use is the 8-puzzle. The environment simulator will generate the problem instances in one of three modes (user-selected): randomly, by prompting the user for a problem instance, and by using the standard starting position (see below). The simulator receives a step from the agent, and the number of search expansion steps, and computes a performance score. Performance is measured by the number of steps required to reach a solution, times a constant factor F, minus the number of expansion steps used by the search algorithm.

You will also implement three different search agents:

  • One that chooses an arbitrary legal step at each turn (i.e. only 1 expansion step per turn).
  • One that performs a complete A* search.
  • One that performs a limited, "real-time" A* search (of a constant, say 10, expansion steps), and executes the seemingly best move.

    Use whichever non-trivial heuristic you prefer (e.g. Manhattan distance).

    After implementing the programs, run them (using the simulator) on the default initial state, and an additional start state of your choice. Compute the score for each agent at the terminal state minus the sum of all search steps executed by the agent. Do that for F=-1, F=-100, and F=-10000 (note that F is negative because a shorter solution is better). Include the results in your report.

    Game data and scoring

    Default initial game position is:

    +-------+
    |       |
    | 8 7 6 |
    |       |
    | 5 4 3 |
    |       |
    | 2 1   |
    |       |
    +-------+
    
    Final game position is:
    +-------+
    |       |
    | 1 2 3 |
    |       |
    | 4 5 6 |
    |       |
    | 7 8   |
    |       |
    +-------+
    

    Implementation Steps

    As at the beginning of the semester we will not have covered search as yet, start by programming the environment simulator, and the first "non-search" search agent. You will need to program at this stage the functions that compute and check legality of states and moves, for use in the simulator and agent. Also, your simulator at this stage should be able to compute agent score.

    As a detail, note that the agent keeps a list of actions (initially empty - for and is re-initialized for every problem instance), and returns only one action for each time it is called. An agent that performs a complete search keeps a list of actions in static variables and returns one action each time it is called.

    Now, implement A* search in the agent, with a heuristic of your choice, as well as the "real-time" limited A*. Note that this type of agent does not explicitly reason about the number of search steps executed - it simply tries to find the best sequence of steps, with a "hard-programmed" search strategy, limiting the number of search steps. While it is possible to do that, (it is called "meta-control of search"), you must learn to walk before you can run...

    Deliverables

    The program and code sent to the grader, Mr. Ami Berler by e-mail or otherwise as specified by the grader, a printout of the code and results. Set up a time for frontal grading checking of the delivered assignment, in which both members of each team must demonstrate at least some familiarity with their program...

    Deadline: November 20, 2001