Homework answers / question archive / Programming Assignment 2 Logic & Planning CMSC 421 Spring 2022CMSC 421 Fall 2020 Welcome to your second programming assignment

Programming Assignment 2 Logic & Planning CMSC 421 Spring 2022CMSC 421 Fall 2020 Welcome to your second programming assignment

Computer Science

Share With

---

Programming Assignment 2

Logic & Planning

CMSC 421 Spring 2022CMSC 421 Fall 2020

Welcome to your second programming assignment. In this assignment you are going to explore the relationship between logic and planning. The goal of this assignment is for you to explore propositional logic, first-order logic, logical inference, and use some of these ideas to solve a planning problem. You are encouraged to collaborate, discuss and compare results with your classmates. However, the final code and report submitted should be your own work.

Time Commitment: This assignment should take between 1 and 3 hours, maybe less if you’ve mastered FOL. Section 1 (Propositional Logic) has 3 short subproblems. Section 2 (First-order logic) has 4 short subproblems. Section 3 (The Liar Puzzle) has 6 short subproblems. Section 4 (Planning) has 2 problems, where the last problem may take some time to formulate.

General Instructions:

1. We will be using Python 3 in this assignment. Instructions on how to download and install are available here: https://www.python.org/downloads/
2. This assignment’s code and scripts are available here: https://github.com/psandovalsegura/ cmsc421-prog-assignment-2. All of the code you write will be within submission.py. For every question, you should modify the code in submission.py between

# BEGIN_YOUR_CODE and

# END_YOUR_CODE

Grading Rubric:

Your code will be evaluated on two types of test cases, basic and hidden, which you can see in grader.py. Basic tests, which are fully provided to you, do not stress your code with large inputs or tricky corner cases. Hidden tests are more complex and do stress your code. The inputs of hidden tests are provided in grader.py, but the correct outputs are not. To run the tests, you will need to have graderUtil.py in the same directory as your code and grader.py. Then, you can run all the tests by typing:

python3 grader . py

This will tell you only whether you passed the basic tests. On the hidden tests, the script will alert you if your code takes too long or crashes, but does not say whether you got the correct output. You can also run a single test (e.g., 2a) by typing python3 grader . py 2a Getting Started:

A table that describes how logical formulas are represented in code is given in Figure 1. Use it as a reference guide. To get started, launch a Python shell and try typing the commands from Figure 2 to add logical expressions into the knowledge base.

1. Propositional Logic

Write a propositional logic formula for each of the following English sentences in the given function in submission.py. For example, if the sentence is ”If it is raining, it is wet,” then you would write Implies(Atom(’Rain’), Atom(’Wet’)), which would be Rain→Wet in symbols (see examples.py).

Note: Don’t forget to return the constructed formula!

You can run the following command to test each formula: python grader.py 1a

If your formula is wrong, then the grader will provide a counterexample, which is a model that your formula and the correct formula don’t agree on. For example, if you accidentally wrote And(Atom(’Rain’), Atom(’Wet’)) for ”If it is raining, it is wet,”, then the grader would output the following:

Your formula (And(Rain,Wet)) says the following model is FALSE, but it should be TRUE:

• Rain = False
• Wet = True
• (other atoms if any) = False

In this model, it’s not raining and it is wet, which satisfies the correct formula Rain→Wet (TRUE), but does not satisfy the incorrect formula RainWet (FALSE). Use these counterexamples to guide you in the rest of the assignment.

1. 1. “If it’s summer and we’re in California, then it doesn’t rain.”
   2. “It’s wet if and only if it is raining or the sprinklers are on.”
   3. “Either it’s day or night (but not both).”
2. First-order logic

Write a first-order logic formula for each of the following English sentences in the given function in submission.py. For example, if the sentence is ”There is a light that shines,” then you would write

Exists('$x', And(Atom('Light', '$x'), Atom('Shines', '$x')))

which would be ∃x.Light(x) ∧ Shines(x) in symbols (see examples.py).

Tip: Python tuples can span multiple lines, which help with readability when you are writing logic expressions (some of them in this homework can get quite large)

1. “Every person has a mother.”
2. “At least one person has no children.”
3. Create a formula which defines Daughter(x,y) in terms of Female(x) and Child(x,y).
4. Create a formula which defines Grandmother(x,y) in terms of Female(x) and Parent(x,y).

3. The Liar Puzzle

Someone crashed the server, and accusations are flying. For this problem, we will encode the evidence in first-order logic formulas to find out who crashed the server. You’ve narrowed it down to four suspects: John, Susan, Mark, and Nicole. You have the following information:

1. John says: “It wasn’t me!”
2. Susan says: “It was Nicole!”
3. Mark says: “No, it was Susan!”
4. Nicole says: “Susan’s a liar.”
5. You know that exactly one person is telling the truth.
6. You also know exactly one person crashed the server.

Fill out the liar() function to return a list of 6 formulas, one for each of the above facts. Be sure your formulas are exactly in the order specified. You can test your code using the following commands:

python grader.py 3a-0 # Tests the statement by John python grader.py 3a-1 # Tests the statement by Susan python grader.py 3a-2 # ...

python grader.py 3a-3 python grader.py 3a-4 python grader.py 3a-5

python grader.py 3a-all # Tests the conjunction of all the formulas

To solve the puzzle and find the answer, tell the formulas to the knowledge base and ask the query CrashedServer($x), by running: python grader.py 3a-run

4. Planning

The AIMA GitHub repository (https://github.com/aimacode/aima-python) contains an implementation of the GraphPlan algorithm. You can read more about this algorithm in Section 10.3.2 of the AIMA book, but for this problem, all the relevant code pieces are already present in the assignment code.

To use the GraphPlan algorithm to solve a planning problem, you need to instantiate a PlanningProblem object which contains an initial state, goal state, and actions with preconditions and effects. These states, preconditions, and effects are described using first-order logic.

For example, consider the simple Blocks World problem in Figure 3 where there are 3 blocks A, B, and C. This is how we would represent this planning problem in code:

PlanningProblem(initial='On(A, B) & Clear(A) & OnTable(B) & OnTable(C) & Clear(C)', goals='On(B, A) & On(C, B)', actions=[Action('ToTable(x, y)', precond='On(x, y) & Clear(x)',

effect='~On(x, y) & Clear(y) & OnTable(x)'),

Action('FromTable(y, x)', precond='OnTable(y) & Clear(y) & Clear(x)', effect='~OnTable(y) & ~Clear(x) & On(y, x)')])

Note that you don’t need to declare what predicate functions you’ll use, because the framework will parse the statements for you. In other words, we could’ve replaced all the “OnTable(·)” predicates with “OnTheTable(·)”.

1. As a warm-up, add a new block called “D” under “C”. Modify the initial state accordingly. Make the goal state for this new problem be the same as in Figure 3 but with the new “D” block on top of “C”.
2. Formulate a planning problem, like part (a), for the logistics domain of Figure 4 where a robot tries to move all the containers to a specific destination. In this domain, there is one robot R1 which wants to plan actions to move all the containers C1, C2, and C3 to destination D3. The robot can move between adjacent destinations (i.e. from D1 to D3), can load a container if the robot is in the same location as the container, and can unload a container by placing the container at the robot’s location. The robot can only carry one container at a time. Figure 4 is the initial state and the goal state is where all containers are unloaded at D3. Run the GraphPlan algorithm on your planning problem and report your findings in words on Gradescope. If the plan returned by GraphPlan seems wrong, try and comment on why. This problem is not graded by the grading script, and is meant for you to explore the output of the GraphPlan algorithm.

 

Figure 1: How logical formulas are represented in the provided code. The operations And and Or only take two arguments. If we want to take a conjunction or disjunction of more than two, use AndList and OrList. For example: AndList([Atom(’A’), Atom(’B’), Atom(’C’)]) is equivalent to And(And(Atom(’A’), Atom(’B’)), Atom(’C’)).

 

Figure 2: In the output, ’*’ means the fact was explicitly added by the user, and ’-’ means that it was inferred. Here is a table that describes how logical formulas are represented in code.

 

Figure 3: A simple Blocks World example. The start state and the goal state are shown.

 

Figure 4: The initial state of the simple logistics domain where robot R1 carries container C1. Containers C2 and C3 are initially at destination D1 and D2 respectively.