Assignment 1: Search, Planning, & Logic

Questions 1,2, and 3: Due January 23rd

Remaining questions: due January 30

Written exercises:

  1. R&N Exercise 1.2.  A copy of Turing's paper is available at www.abelard.org/turpap/turpap.htm .  (Your response need not be lengthy.)
  2. Our discussion of the Missionaries & Cannibals problem showed how the proper abstraction of a problem can reduce the size of the search space significantly.  Discuss (at a high level) how the task of creating a good abstraction of a problem could be cast as a state-space search problem.  To be concrete, suppose the input to the system uses the STRIPS language.
  3. Read the section in R&N on bidirectional search (pg. 79). The idea of bidirectional search is to search both forward from the initial state A and backward from the goal B, and stop when the two searches intersect: i.e., when a node expanded from one direction and a node expanded from the other both correspond to the same state s, thus generating a complete path from the inital state to the goal by merging those two paths. Typically, bidirection search is breadth first, which is guaranteed to be complete and optimal, but often quite inefficient.

    We assume that the can compute both the predecessors and successors of a node, and that all edges have cost 1.

    Suppose we try to use bidirectional search with A*. In other words, assume we have an admissible heuristic h_B which estimates the distance from any state to the goal B, and another heuristic h_A which estimates the distance from any state to the initial state A.

    The forward A* search uses f_A(n) = g_A(n) + h_B(n), where g_A(n) is the actual length of the shortest path currently found from A to n.

    The backward A* search uses f_B(n) = g_B(n) + h_A(n), where g_B(n) is the actual length of the shortest path currently found from B to n.

     Assume that both f_A and f_B are monotonic (see pg. 99).

    Is bidirectional A* complete? Why or why not?

    Show that bidirectional A* is not optimal, by giving an example where s is the state where the two searches meet, but the path made by conjoining the path from A to s and s to B is not a shortest path from A to B.

    Now, we are going to let the algorithms pool some information, in order to let them verify whether a generated path from A to B is optimal. State a simple sufficient condition for the path from A to s to B to be optimal. This condition should be something that the two algorithms can verify given the information they have at the time s is found. There is no need to prove your condition; state it precisely. Hint: consider what is going on in  Heap_A, the priority queue used by the forward search, and Heap_B, the priority queue used by the backwards search.
  4. R&N Exercise 7.11.
  5. Suppose Walksat (section 7.6) is run with no noise (p=0).  Specify a small set of satisfiable clauses that will never be solved starting from the initial state where all variables are false.

Computer Exercise

Problem

    There is a game called "Sokoban" which roughly translated from Japanese means "warehouse keeper." The first sokoban game was created in 1982 by Hiroyuki Imabayashi at the Japanese company Thinking Rabbit, Inc. The idea is that you are a warehouse keeper trying to push crates to their proper locations in a warehouse. The problem is that you cannot pull the crates or step over them. If you are not careful, some of the crates can get stuck in wrong places and/or block your way.1 This problem naturally lends itself to a grid world representation. Take the following problem in a 4x4 world where the goal is to move the crate to the other side of the "wall":

    "W" is a wall, "O" is a clear space, "S" is Sokoban, "c" is a crate destinations for the crates are underlined

    OOOO

    OWcS

    OOOO

    OOOO

    In this example, in order for the sokoban to accomplish his goal, he must move to the north side of the crate and push it down one space (2 moves and one push). Then he must move to the east side of the crate and push it west two squares (2 more moves and two pushes). Then he must move to the south side of the crate and push it up one square to completion (2 more moves and a push). By adding additional crates, the problem quickly can become non-trivial. As in the following example:

    WWOOWWW

    OOOOOcO

    OWOOWcO

    OOOOWSO

Assignment

Your assignment is to formulate the sokoban problem in STRIPS representation. Utilize the program "Blackbox" to solve the following problems. How many steps does it take to solve each problem?

  1.  

    OOWW

    OOWW

    cSOO

    OOcO

    OOWW

     

  2. (Same as 1. but with two sokobans (sokobani?))

    OOWW

    OOWW

    cSOO

    OOcS

    OOWW

     

  3.  

    OOOO

    OWSO

    OccO

    OOcO

Resources:

  1. There is an interactive version of Sokoban that ships with KDE.

  2. Http://javaboutique.internet.com/Sokoban is a java applet that you can play to get a feel for the game.

  3. Blackbox binaries and descriptions of the strips language format are located at http://www.cs.washington.edu/homes/kautz/blackbox/index.html

  4. I strongly advise you to build up to the full sokoban representation. For example first try and represent the problem of moving the sokoban in one dimension in one direction to a goal square. Then try extending the representation to include moving in two directions in one dimension. Then try moving in two dimensions, then add moving crates in one dimension, etc. etc. If you try and implement the whole thing all at once you will get very frustrated at the representation language, and won't be able to figure out several things which are bound to be going wrong all at once.

  5. Remember that there should be no negative preconditions. Make ~Wall() into Clear() for example. Also remember the hack that two parameters may not be the same object. Consider this in your problem formulation.

Turn-in

Print out the domain.pddl file that you used to solve the three problems above. Print out the problem.pddl file that corresponds to problem 3 above. Print out the sequence of moves that your representation produced. Please translate the raw output, if necessary, so that I can easily figure out what each action in your plan is.

1From the documentation for Ksokoban a game that ships with KDE