Fill This Form To Receive Instant Help
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. 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:
# 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.
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:
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.
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)
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:
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
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(·)”.
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.
Already member? Sign In