CSE 341, Autumn 2008, Assignment 6
CLP(R)

Due: Friday Nov 14, 10:00pm
(Assignment updated Nov 10)

20 points total (4 points each question)

You can use up to 3 late days for this assignment.

  1. Write a CLP(R) rule abs for finding the absolute value of a number. Demonstrate your rule where both arguments are constants, just one is a constant, and both are variables. In each case backtrack to find all possible solutions. For example, one of your test goals might be abs(X,10). You should get two solutions: X = 10 and X = -10.

  2. Write a rule maximum that finds the maximum element in a list of numbers. For example, maximum([4,2,6,2],N) should succeed once with N = 6. The goal maximum([],N) should fail, since there is no minimum element in the empty list. The goal maximum(L,4) should succeed as many times as you try it, binding L to various lists of which 4 is the maximum element. (These don't need to be generated in any particular order.) What does maximum([4,10,K,20],N) give? (Backtrack through all possibilities.) What about maximum([4,20,5,20],N)?

  3. Write CLP(R) rules to find paths through a maze. The maze has various destinations (which for some strange reason are named after well-known spots on the UW campus), and directed edges between them. Each edge has a cost. Here is a representation of the available edges: 

    edge(allen_basement, atrium, 5).
edge(atrium, hub, 10).
edge(hub, odegaard, 140).
edge(hub, red_square, 130).
edge(red_square, odegaard, 20).
edge(red_square, ave, 50).
edge(odegaard, ave, 45).
edge(allen_basement, ave, 20).
    The first fact means, for example, that there is a edge from the Allen Center basement to the Atrium, which costs $5 (expensive maze). These edges only go one way (to make this a directed acyclic graph) --- you can't get back from the Atrium to the basement. There is also a mysterious shortcut tunnel from the basement to the Ave, represented by the last fact.

    You can use these facts directly as part of your program -- copy them and paste them into the start of your solution. You should also write rules that define the path relation: 

    path(Start, Finish, Stops, Cost) :- ....
    This succeeds if there is a sequences of edges from Start to Finish, through the points in the list Stops (including the start and the finish), with a total cost of Cost. For example, the goal path(allen_basement, hub, S, C) should succeed, with S=[allen_basement, atrium, hub], C=15. The goal path(red_square, hub, S, C) should fail, since there isn't any path from Red Square back to the HUB in this maze.

    The goal path(allen_basement, ave, S, C) should succeed in four different ways, with costs of 20, 200, 195, and 210 and corresponding lists of stops. (It doesn't matter what order you generate these in.)

    Hint: if you have trouble with this question, solve a simplified version first, in which you omit the list of stops and the cost. Then first modify your solution to include the cost, then after that's working add the stops.

  4. The remaining questions build on the file resistors.clpr. Copy this file to your own directory on attu using this command: 
    cp ~borning/clpr/resistors.clpr .
    You shouldn't need to modify this file. You can then read in both the resistors file and your own additions (say in a file assign6.clpr) using this command in CLP(R): 
     [resistors, assign6].

    Define two rules that define how a switch operates. The rules should take 3 arguments: 2 leads, and a position. The position will be either open or closed, and your switch should define the appropriate constraints depending on the position. So the rules might look like this: 

    switch(lead(I1,V1), lead(I2,V2), open) :- .....
switch(lead(I1,V1), lead(I2,V2), closed) :- .....
    (You may want to use constants or expressions in place of some of the variables, but the two rules should have this general form.)

    Using the switch and the other rules in resistors.clpr you can define a simple_circuit rule that builds the following circuit. This rule should have two arguments: the state of the switch, and the amperes shown by the ammeter.

    To help you get started here's a definition: 

    simple_circuit(State,Amps) :-
   battery(B1,B2,10),
   ammeter(A1,A2,Amps),
   switch(S1,S2,State),
   resistor(R1,R2,100),
   electrical_ground(G),
   connect([B2,A1]), connect([A2,S1]), connect([S2,R1]),
   connect([R2,B1,G]).
    Try invoking simple_circuit with the switch open, and then closed; and also with the switch state left as a variable.

  5. Define another rule three_resistors_switches that builds the following circuit. This rule should have seven arguments: one for the amperes shown on the ammeter, three for the states of the switches S1 through S3, and three for the resistances of resistors R1 through R3.

    Use this rule to find the current when all the switches are closed and R1=10, R2=20, R3=30. Also, still with R1=10, R2=20, and R3=30, use the rule to find all settings for the switches such that the current is at most 0.8 amperes.

Extra Credit (10% max). Define a rule many_resistors_switches that is similar to the three_resistors_switches rule, but that allows N resistor/switch pairs, where N is a parameter to the rule. You need to decide how to represent the parameters for the switch settings and resistances. Using many_resistors_switches, define a network with 10 pairs, and resistances of 10 ohms, 20 ohms, 40 ohms, 80 ohms, ... 5120 ohms. Show your rule on some test cases, including finding all the settings that give a current of greater than 1 ampere.

Turnin: Turn in your CLP(R) program and a script showing it running on some well-chosen test cases. As usual, your program should be tastefully commented (i.e. put in a comment before each set of rules saying what they do).