CSci 4511 - Homework 1

Homework 1 -- due Thursday February 1

This homework will be graded out of 100 points. It will count 5% of the grade.
Submit the assignment electronically using moodle. The written part has to be uploaded as a .pdf file. This makes it easy for us to mark the homework.
For the programming part in general you need to upload the code you wrote and the output produced.

Written questions

  1. [15 points] A robot has to deliver three identical packages to locations A, B, and C in an office environment. The robot starts in location S holding the packages. The environment is a grid of squares, some of which are free (so the robot can move into them) and some of which are occupied (by walls, doors, etc.). The robot can move in the horizontal or vertical direction into neighboring squares, one square at a time, and can pick up and drop packages if they are in the same square as the robot.
    1. Specify the state space representation of the problem by specifying the states, the initial state, the goal test, the actions, and the cost of the actions. Be precise and consistent.
  2. [25 points] This question is on using the proper search algorithm for each problem. The algorithms to compare are:
    1. depth-first,
    2. breadth-first,
    3. depth-limited depth first,
    4. iterative deepening depth first,
    5. bidirectional.
    For each of those algorithms describe briefly an example of a problem for which the algorithm is well suited and one for which it is not. Be specific and precise. For example, uniform cost is appropriate to find a path in a graph, where each node represents a location and the cost of each arc is the distance between the two locations connected by the arc. Uniform cost is not useful for problems where all the actions have the same cost, and for problems that have a complete state formulation (see Section 3.2.1 for the definition).
  3. [15 points] This question is on properties of search algorithms. You need to explain the reasons for your answers, not simply write the name of one algorithm.
    1. if you want to limit the memory requirements, which algorithm(s) would you choose? why?
    2. if you want to limit the time required the find a solution, which algorithm(s) would you choose? why?
    3. if you want to find the minimum cost solution, which algorithm(s) would you choose? why?
    4. if you want to solution with the minimum number of steps, but you do not want to use a lot of memory, which algorithm(s) would you choose? why?
    5. if you want to parallelize your algorithm, which algorithm(s) would you prefer? why? [this is not in the textbook]
  4. [10 points]
    1. If you are given a problem described using a state space representation and add 10 to the cost of each action, will the optimal solution be the same as the one with the original costs? Explain.
    2. If in the previous problem instead of adding 10 to the costs of each actions you double its cost, will the optimal solution be the same as the one with the original costs? Explain.
  5. [10 points] Does a finite state space always lead to a finite search tree? What if the finite state space is a tree? Can you be more precise about what types of state spaces always lead to finite search trees? [Be short but precise. Explain your answers. You can support your answer with example or counterexamples, or use more formal arguments.]
  6. [10 points] If you do not use CLOSED (this is what the textbook calls explored set in Fig 3.7) in an algorithm that uses it, what happens? be specific on what happens in each of the algorithms that we have studied.

Programming Part

[15 points]
  1. Download and install the AIMA book code from The code is written for different programming languages. The ones we will use are lisp or python
  2. Use the code to run the vacuum cleaning agent.
  3. To show that you have the software installed and working, and you know how to use it, show the output of the program.
    For the output, if you start the program from the command line in linux you can save the output into a file (let's call it output.txt) using the command
     % script > output.txt 

    If you use windows or do not use the command line, submit a screen dump that shows the output of the vacuum cleaning agent.
    If you use Lisp there are other ways of capturing the output. See for details.
    You can upload multiple files.

Details on using the software

Copyright: © 2018 by the Regents of the University of Minnesota
Department of Computer Science and Engineering. All rights reserved.
Comments to: Maria Gini
Changes and corrections are in red.