Instructions:
If anything is ambiguous or unclear:
- Discuss possible interpretations with other students, your TA, and instructor
- Make assumptions, state them explicitly, and then use them to work out the problem
- Send e-mail to your TA first, and to your instructor if an issue is not resolved to your satisfaction.
Remember that after general discussions with others, you are required to work out the problems by yourself. All submitted work must be your own. Please refer back to the Honor code for clarifications.
Important:
- Write legibly, be sure to staple all your answer sheets together, and write your name, section number, and the honor pledge on the top of the first answer sheet.
- Start early, and avoid last minute stress!
The female solitary wasp, Sphex, lays her eggs in a cricket that she has paralyzed and brought to her burrow nest. The wasp grubs hatch and then feed on this cricket. According to [Wooldridge 1968, p. 70]1 the wasp exhibits the following interesting behavior:
The wasp’s routine is to bring the paralyzed cricket to the burrow, leave it on the threshold, go inside to see if all is well, emerge, and then drag the cricket in. If the cricket is moved a few inches away when the wasp is inside making her preliminary inspection, the wasp, on emerging from the burrow, will bring the cricket back to the threshold, but not inside, and will repeat the preparatory procedure of entering the burrow to see that everything is all right. If again the cricket is moved a few inches when the wasp is inside, once again she will move the cricket up to the threshold, and reenter the burrow for her final check … On one occasion this procedure was repeated 40 times all with the same result.
Come up with a set of features, actions, and a production system that models this behavior of the wasp.
The state representation can be represented with the form: c:<n|f|b>|b:<u|e> where:
The legal transitions then would be: (> marks the start node and * marks goal nodes)
| Origin State | Action | Destination State |
|---|---|---|
| >c:n|b:u | Examine Burrow | c:f|b:e |
| c:n|b:e | ||
| c:f|b:e | Bring Cricket Back | c:n|b:u |
| c:n|b:e | Bring Cricket Inside | *c:b|b:e |
Select the state space representation, operators/actions, goal test, and path cost for the eight queens problem: Place 8 queens on a standard chessboard, such that each row, column, and diagonal contains no more than one queen. Make sure that the formulation is precise enough to be implemented. Generate the sequence of actions that leads to the solution.
Russel and Norvig in Artificial Intelligence mention than a useful constraint on the problem is to keep in mind each queen must be limited to one of the eight rows. So a state representation could be <r1,r2,…,r8> where each 1 ≤ ri ≤ 8 is the column the piece in row i.
The goal state will need for each queen to be unique on three axes. For a given ri with value x and rj with value y such that i ≠ j:
One workable algorithm is based on incrementally building the goal state. It adds to the state a factor n which represents the current column under consideration. The start state is 1:<1,∅,∅,∅,∅,∅,∅,∅>. There are then two options for state transitions:
This algorithm is a depth-first search of the state space using backtracking rather than saving the state. An optimization if there was sufficient memory might be to save a 8x8 boolean matrix and simply mark the invalid positions on the board.
This program implements that algorithm (though it currently doesn't quite work).
You have to color a planar map using only four colors, in such a way as no two adjacent regions have the same color. Give the initial state, goal test, successor function and cost function in a precise enough specification it could be implemented.
The graph coloring can be represented as a tuple with n elements where each ci is a number 1-4. The borders are represented in a nxn adjacency matrix where if there is a 1 at element x,y it means there is a border between cx and cy.
The initial state could be to set all the colors to the same. All permutations of the tuple could then be identified and tested against the adjacency matrix as a solution. This is likely the least efficient solution possible, but it will work. There could certainly be greater efficiency found in constraining the state space further, but time is pressing.
Three missionaries and three cannibals come to a river. There is a boat on their side of the river that can take either one or two persons across the river at one time. How should they use the boat to cross the river in such a way that the cannibals never outnumber missionaries on either side of the river? Apply breadth-first search to this problem to find the shortest solution.
To help in defining the graph, two things are needed:
State Representation: shore:near count:far count where:
n for "near" or f for "far"xmyc where x is the number of missionaries and y is the number of cannibalsSo, for example, the initial state is n:3m3c:0m0c meaning the boat is on the near bank, there are 3 missionaries and 3 cannibals on the near bank, and there are 0 on the far bank.
From the problem definition, illegal states are those where, for xmyc, x < y.
Edge Representation: xmyc where x is the number of missionaries in the boat and y is the number of cannibals.
Rather than do the search by hand, I wrote a short script to do the search. The breadth-first solution had the following output:
So, the solution is:
n:3m3c:0m0c + 0m2cf:3m1c:0m2c + 0m1cn:3m2c:0m1c + 0m2cf:3m0c:0m3c + 0m1cn:3m1c:0m2c + 2m0cf:1m1c:2m2c + 1m1cn:2m2c:1m1c + 2m0cf:0m2c:3m1c + 0m1cn:0m3c:3m0c + 0m2cf:0m1c:3m2c + 0m1cn:0m2c:3m1c + 0m2cf:0m0c:3m3cIs it a good idea to check for repeated states? Draw a diagram of the state space to help you decide.
Yes, repeated states should be avoided. They will significantly increase the size of the tree since the states are reversible by simply sending the people that just came across back. Because the search is breadth first or iterative deepening depth first, the shallowest solution will always be found.
Repeat the solution for Iterative Deepening DFS, and compare the results.
Iterative deepening is implemented in the same script. From the output one can see that there were significantly more nodes visited in the deepening search. This is because the branching factor is relatively small and the solution fairly deep. The solution that is found is identical however.
Show that iterative lengthening search is optimal for general path costs
Uniform-cost simply iteratively examines the unexplored node closest to the start node. Iterative lengthening is uniform-cost search which is run multiple times with an increasing bound on the maximum cost from the start to reach before quitting.
Iterative lengthening search doesn't have advantages in the same way iterative deepening depth-first search does. Iterative lengthening will simply search the same nodes each time adding more at the end since the first closest node, second closest node, etc. is invariant. All that iterative lengthening does is require the algorithm to restart repeatedly before finding a solution.
The optimality of iterative lengthening is straightforward from the concept that a solution is found when the set of explored nodes includes an element from the set of goal nodes. By the definition, the explored nodes are the closest nodes to the start node so the first goal encountered must be at least as close as any other goal node.
Consider a uniform tree with branching factor b, solution depth d, and unit step costs. How many iterations will iterative deepening require?
With uniform costs, uniform-cost search runs through nodes in the same order as breadth-first search. So the progression would go:
All of those runs must then be added together for the d times it runs, so the final node count is:
db + (d - 1)(b2) + … + bd / 2
This is O(bd)
Consider step costs drawn from the continuous range [0,1] with a minimum positive cost ε. How many iterations are required in the worst case?
The worst cast is the limit starts at the minimum, 0, and increments by the minimum, ε, until it is d. The number of iterations required to do this is (d - 0) / ε.
Consider an implementation of iterative lengthening length search. How does the algorithm's performance compare to uniform-cost search?
As mentioned at the outset, the algorithm simply requires k uniform-cost searches where each iteration simply expands the boundary for closest nodes examined. It does not change the search ordering of the nodes. The nth closest node will always be the nth closest node regardless of the cost limit.
Prove that uniform-cost search and breadth-first search with constant step costs are optimal when used with the graph-search algorithm.
Uniform-cost search with constant step costs is identical to breadth-first search. (Since all nodes at a given depth are the same cost from the start node, so they will all have to be explored before moving to the next depth.)
The way that switching from tree-search to graph-search could make the search non-optimal would be if a node that is a part of the optimal path ended up on the closed list. (And so the optimal path that included that node would not be considered.) This is not possible because for each node n, n will only be explored if the path to its parent that is, by definition the shortest route to n possible. If there was a shorter route to n that would already have been taken and n would already be on the closed list.
Since the path to each node on the path to the goal node is a minimum and the goal is the closest goal found then the solution mush to optimum.
Show a state space with constant step costs in which graph-search using iterative deepening finds a suboptimal solution.
Consider the following state diagram (which represents a graph, it is drawn as a tree to simplify understanding the depth-first search):
The iteration of depth-first searches and the "closed" list of searched nodes will progress like this:
| Iteration | Node Search Order | Closed List |
|---|---|---|
| 1 | Start, N1, N2 | Start |
| 2 | Start, N1, N2, N2 | Start, N1 |
| 3 | Start, N1, N2, N3, N2 | Start, N1, N2 |
| 4 | Start, N1, N2, N3, *N4 | Start, N1, N2, N3 |
Because N2 goes on the closed list while searching the left-hand subtree, a shallower solution is missed in the right-hand subtree.
Suppose actions can have arbitrarily large negative costs; explain why this possibility would force and optimal algorithm to explore the entire state space.
Because you never know if an unexplored node will have a negative path to the goal that, when combined with the cost of getting to that node, will make the total cost less than any possible best cost. So, every node must be explored.
Does it help if we insist that step costs must be greater than or equal to some negative constant c? Consider both trees and graphs.
For a tree, if the number of nodes is known then the number of nodes remaining to be searched can be known. For n remaining nodes, there are n remaining transitions, if each transition had a cost of -k then the total negative cost will be -nk. If the current cost is nk greater than the best cost to a goal then further exploration can't produce a better path.
With an arbitrary graph, any set of nodes, even a single node can contain a cycle that is negative and that could be traversed however often is necessary to lower the cost below the current best.
Suppose there is a set of operators that form a loop, so that executing the set in some order results in no net change to the state. If all these operators have negative cost, what does this imply about the optimal behavior for an agent in such an environment?
The agent seeking to find a minimal cost path will simply loop forever.
One can easily imagine multiple operators with high negative cost, even in domains such as route finding. For example, some stretches of road might have such beautiful scenery as to outweigh the normal costs in terms of time and fuel. Explain, in precise terms, within the context of state-space search, why humans do not drive around scenic routes indefinitely, and explain how to define the state space and operators for route finding so that artificial agents can also avoid looping.
One possible option is to define the state space such that once a scenic route has a negative cost, but once you've taken it you end up in a new state with all the same connections as the previous state save the scenic route. It is also possible that the state space could contain other factors such as available time or available gas. The weighting on various factors could be non-linear such that when I've got lots of free time it is about equal with gas and scenery, but as it approached zero it begins to dominate the combination.
Can you think of a real domain in which step costs are such as to cause looping?
Tooth brushing. Each transition I take by eating a meal takes me a little toward the state of all my teeth falling out. There is a negative cost (where the path is total tooth decay) associated with brushing my teeth. On a daily basis this means plays out as regular brushing.
Apply a depth-limited search algorithm (depth limit l=3) to find the solution to the following 8-puzzle problem. When generating the successors for a particular state assume the operators are always applied in the following order: left, down, right, and up.
| 3 | 1 | 2 |
| 4 | 7 | 5 |
| 6 | 8 |
| 1 | 2 | |
| 3 | 4 | 5 |
| 6 | 7 | 8 |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
1D. Wooldridge, Mechanical Man: The Physical Basis of Intelligent Life. Mc-Graw Hill, New York, NY, 1968.