HOMEWORK  (Planning)

Q-1: Write a program to solve the water-jugs problem. You have three jugs, measuring 12 gallons, 8 gallons, and 3 gallons, and a water faucet. You can fill the jugs up or empty them out from one to another or onto the ground_ You need to measure out exactly one gallon.

Q-2: Write a program to solve the bridge-crossing problem. Four people come to a river during the night. There is a narrow bridge, but it can only hold two people at a time. They have one torch and, because it’s night, the torch has to be used when crossing the bridge. Person A can cross the bridge in one minute, person B in two minutes, person C in five minutes, and person D in eight minutes. When two people cross the bridge together, they must move at the slower person’s pace. Find an optimal plan that requires the shortest time for the four people to cross the bridge.

Q-3: Consider three heuristic functions generated from the following relaxed problems for the 15-puzzle:
  1. A tile can move from square A to square B if A is adjacent to B.

  2. A tile can move from square A to square B if B is blank.

  3. A tile can move from square A to square B.
The function from problem (1) is the Manhattan-distance heuristic, the function from problem (2) is the Gaschnig's heuristic, and the function from problem (3) gives the number of misplaced tiles. Compare these three heuristic functions by measuring the execution time of the 15-puzzle program.

Q-4: Write a program to solve the vehicle-moving problem: n vehicles occupy squares (1, 1) through (n, 1) (i.e., the bottom row) of an n x n grid. The vehicles must be moved to the top row but in reverse order; so the vehicle i that starts in (i, 1) must end up in (n – i + 1, n). On each time step, every one of the n vehicles can move one square up, down, left, or right, or stay put; but if a vehicle stays put, one other adjacent vehicle (but not more than one) can hop over it. Two vehicles cannot occupy the same square.

Q-5 (optional): A classical planning problem can be formulated as a satisfiability problem. This planning-as-satisfiability approach finds a bounded-length sequence of states, where the first state corresponds to the initial state, the last state satisfies the goal condition, and each pair of successive states constitutes a valid action. Write a program for the vehicle-moving problem using the planning-as-satisfiability formulation.