We will use the Camping Problem as a domain for an experimental study of search. For this problem, one is given a grid
with trees placed at various squares of the grid. One must associate one tent with every tree (at either a horizontal or vertical neighbor,
not diagonal). No tent can be a neighbor of another tent (either horizontal, vertical or diagonal). Each row and column
has an associated number of tents that must be placed there. Below is an example of such a problem,
with "T"'s for trees and numbers at the ends of the rows and columns indicating how many tents must be placed in each.
----------------------------------------- | | T | | T | | | | T | | | 3 ----------------------------------------- | T | | | | T | | | | | | 1 ----------------------------------------- | | T | | | | | | | T | | 3 ----------------------------------------- | | | | | | | | | | T | 1 ----------------------------------------- | T | | | | | T | | | | | 2 ----------------------------------------- | | | T | | | | | T | | | 3 ----------------------------------------- | T | T | | | | | | | | | 1 ----------------------------------------- | | | | T | | T | | T | T | | 4 ----------------------------------------- | T | | | | | | | T | | | 1 ----------------------------------------- | | T | | | T | | | | | T | 4 ----------------------------------------- 4 1 4 1 3 2 1 3 1 3A solution consists of an associated tent location for each tree.
The Camping Problem has several nice properties for use in the study of constraint satisfaction algorithms.
It is a well-defined problem with clear, checkable solutions. The constraints are readily implementable,
and one can propagate assignments from partial solutions to fill or vacate other cells of the grid.
We will write programs to solve the problem, based upon a files in the CSP directory. To complete an implementation
using BacktrackSearch you must reimplement/specialize the abstract class State , creating a CampingState class.
The general algorithm counts the number of states generated and the actual number of states considered/expanded.
For each implementation, we will count the number of choices made; a choice is made when a location is selected for placing a tent
and the placement is uncertain (i.e., the placement is not required by constraints). When placing a tent
that is implied by constraints, do not count that placement as a choice.
There are input/output functions in the CampingState class (uncompiled and untested, a concept .....).
A problem is input as a file, where the first line indicates the x and y dimensions
of the problem; the next y lines each have x 0 and 1 values for each row, where a 1 indicates a tree;
the next line has y values separated by blanks, indicating how many tents can be placed in each row;
the last line has x values, indicating how many tents can be placed in each column.
Below is the input file for the problem above, as found in file Camping1.in.
10 10 0101000100 1000100000 0100000010 0000000001 1000010000 0010000100 1100000000 0001010110 1000000100 0100100001 3 1 3 1 2 3 1 4 1 4 4 1 4 1 3 2 1 3 1 3A solution to the above problem could be represented as follows, where 1 indicates a tre, as given, 2 indicates a tent
4151500100 1000100200 0150200015 4000000001 1000010402 0415020100 1100000040 2031313110 1000000104 2150150201
You will implement a solution algorithm two ways and compare the cost of finding a solution
in terms of number of choices made, as well as states generated and considered.
A description of your program and of your results is an important component of what you submit. Fully describe
your representation, showing annotated/commented code as to how you implemented the state and were able to check or propagate constraints.
Fully discuss your results as to counts of states considered and choices made for the four example
problems found in directory CSP as files "***.in.txt". Estimate the size of the search space.
2. Specific Searches (5)
Problem 4.11 on page 135 of the text.
3. CSP (10)
Solve the cryptarithmetic problem OOOH + FOOD = FIGHT by hand, using backtracking, forward checking (propagation) and
the MRV heuristic. Indicate where you are applying the various operations and heuristics.
4. Means-Ends Planning (10)
Problem 11.13 on page 414 of the text.
5. Planning and Acting in the Real World -- Urban Driving (10)
Read the article on urban driving . Discuss the sensing, planning and execution approaches
found in the entries discusses (CMU, Stanford). How does it relate to our discussion of agent types and problem solving and planning?