---
# System prepended metadata

title: 'Homework 5: Knowledge Representation and Reasoning (KRR)'

---

# Homework 5: Knowledge Representation and Reasoning (KRR)

==**Due Date: 10/7/2025 at 11:59pm**==

<!-- Update due date and Ed link -->

**Need help?** Feel free post on [Edstem](https://edstem.org/us/courses/85591) for TA assistance.

## Assignment Overview

Knowledge Representation and Reasoning (KRR) is a fundamental area of artificial intelligence that focuses on how to formally represent information about the world and use that information to make inferences. KRR systems aim to capture knowledge in a structured format that enables automated reasoning and decision-making.

In this assignment, you will explore two key areas of KRR:

1. **Probabilistic Reasoning**: You will use Bayesian networks to represent probabilistic knowledge and reason under uncertainty.

2. **Symbolic Planning**: You will use PDDL (Planning Domain Definition Language) and first-order logic to represent a sliding puzzle tile game. Then, you will use a PDDL solver to find solutions to planning problems.

## Learning Objectives

What you will know:
* Two inference methods for estimating joint probabilities in Bayesian networks, which can be used to compute the probability of events given some evidence.
* The advantages (and disadvantages) of using formal planning languages to formulate and solve planning problems.

What you will be able to do:
* Use Pandas and dataframes to manage large datasets in Python.
* Formalize planning problems into PDDL, a formal planning language.

# Bayesian Networks

Bayesian networks (also called belief networks or Bayes nets) are probabilistic graphical models that represent variables and the conditional dependencies among them. The relationships between variables are represented using a directed acyclic graph (DAG), where each variable in the model is represented by a node in the graph, and each edge represents a conditional dependency between variables. Appended to each node is a conditional probability table (CPT), which gives the conditional probability of each variable given its parents. Together these CPTs afford a compact representation of the full joint distribution over all variables in the model.

### Conditional Probabilities
For a node $X$ with parent nodes $\{V_1, V_2, \dots, V_k\}$, the CPT defines the **conditional probabilities** of $X$ given all combinations of its parents’ values.

Formally:

$$
\text{CPT}(X) = \left\{ P(X = x \mid V_1 = v_1, \dots, V_k = v_k) \ \Big| \ x \in \text{Values}(X),\ v_i \in \text{Values}(V_i) \right\}
$$

Where:
- $\text{Values}(X)$ is the set of possible values of $X$.
- $P(X = x \mid V_1 = v_1, \dots, V_k = v_k)$ is the probability that $X$ takes value $x$, given that its parents have values $v_1, \dots, v_k$.

Not all nodes in a Bayesian network have parents. For nodes without parents, the CPT simply contains the prior probabilities over all values of that variable. 

In the first part of this assignment, you will be constructing CPTs from a dataset of samples.

<!--### Joint Probabilities

### Exact Inference-->

## Data Structures

### Pandas

In this assignment, you will be working with the *Pandas* library in Python. Pandas (frequently abbreviated *pd*) is a library for working with large scale tabular datasets. As such, it provides many common data analytics tools. The base structure for storing data in Pandas is a *dataframe*.

Consider loading the following Comma Separated Values (CSV) data into pandas (which may be done with `pd.read_csv('filename.csv')`).

| Smoker, | Excersizes, | Heart Disease Risk |
|----------|----------|----------|
| Yes, | No, | High, |
| No, | Yes, | Low, |

This will construct a DataFrame with 3 columns and 2 rows, containing the CSV data and store it in the variable `df`. Pandas defaults to using the first row of a CSV as the column labels.

## Accessing Data in DataFrames

### Column Access
To access a column of data, you can use `df["Exercises"]`, which will return a Series containing the data in that column: `["No", "Yes"]`. Additionally, multiple columns can be accessed at once if a list of column names is provided.

```python
# Access a single column
exercise_data = df["Exercises"]
print(exercise_data)  # Output: ["No", "Yes"]

# Access multiple columns
health_data = df[["Smoker", "Heart Disease Risk"]]
print(health_data)    # Output: [["Yes", "No"], ["No, Yes"]]
```

### Row Access
To access an individual row in the DataFrame, you can use `df.iloc[i]` (for index-based locate):

```python
# Access the first row (index 0)
first_row = df.iloc[0]
print(first_row)
# Output: Smoker: Yes, Exercises: No, Heart Disease Risk: High

# Access the second row (index 1)  
second_row = df.iloc[1]
```

### Iterating Through Rows
If you wish to loop through the rows of a DataFrame and perform some operation, you can use the `iterrows()` method:

```python
for index, row in df.iterrows():
    print(f"Row number {index}:")
    print(f"  Smoker: {row['Smoker']}")
    print(f"  Exercises: {row['Exercises']}")
    print(f"  Heart Disease Risk: {row['Heart Disease Risk']}")
```

## Useful DataFrame Methods

There are a number of other useful functions built into DataFrames you might find useful for this assignment:

### `value_counts()`
Counts the frequency of each unique value in a column:

```python
# Count how many people smoke vs don't smoke in the dataframe provided
# value_counts returns the values in that column as well as their frequency
smoker_counts = df['Smoker'].value_counts()
print(smoker_counts)
# Sample Output: 
# Yes    200
# No     800

# Count heart disease risk levels
risk_counts = df['Heart Disease Risk'].value_counts()
```

`value_counts` can also be used with multiple columns at a time, in which case it will count the number of times each row is repeated in the dataframe.

A larger introduction to Pandas can be found [here](https://pandas.pydata.org/docs/user_guide/10min.html) and many other guides exist from other sources. **You are welcome to use any built in method within Pandas for this assignment, not just the ones listed above.**

## Heart Disease Bayesian Network

In the first part of this assignment, you will be working with the following Bayesian Network for analyzing the risk of heart disease. The network has 6 nodes with the structure shown below: 

```mermaid
graph TD;
Smoker --> BloodPressure
Exercise --> BloodPressure
Exercise --> Cholesterol
BloodPressure --> HeartDiseaseRisk 
Smoker --> HeartDiseaseRisk 
Cholesterol --> HeartDiseaseRisk
HeartDiseaseRisk --> ECGResults
```
## Conditional Probability Tables
### 1. Smoking Status (Root Node)
| Smoking Status | Probability |
|----------------|-------------|
| Smoker         | 0.20        |
| Non-smoker     | 0.80        |

### 2. Exercise Level (Root Node)
| Exercise Level | Probability |
|----------------|-------------|
| High           | 0.30        |
| Low            | 0.70        |

### 3. BloodPressure | Smoking, Exercise

| Smoking | Exercise | High | Normal |
|---------|----------|------|--------|
| No      | High     | 0.15 | 0.85   |
| No      | Low      | 0.30 | 0.70   |
| Yes     | High     | 0.25 | 0.75   |
| Yes     | Low      | 0.50 | 0.50   |


### 4. Cholesterol | Exercise

| Exercise | High Cholesterol | Normal Cholesterol |
|----------|------------------|--------------------|
| High     | 0.25             | 0.75               |
| Low      | 0.45             | 0.55               |

### 5. HeartDiseaseRisk | Smoking, BloodPressure, Cholesterol

| Smoking | BloodPressure | Cholesterol | High | Low  |
|---------|---------------|-------------|------|------|
| No      | Normal        | Normal      | 0.05 | 0.95 |
| No      | High          | Normal      | 0.10 | 0.90 |
| No      | Normal        | High        | 0.08 | 0.92 |
| No      | High          | High        | 0.15 | 0.85 |
| Yes     | Normal        | Normal      | 0.12 | 0.88 |
| Yes     | High          | Normal      | 0.25 | 0.75 |
| Yes     | Normal        | High        | 0.20 | 0.80 |
| Yes     | High          | High        | 0.40 | 0.60 |

### 6. ECGResults | HeartDiseaseRisk

| HeartDiseaseRisk | Abnormal | Normal |
|------------------|----------|--------|
| High             | 0.60     | 0.40   |
| Low              | 0.20     | 0.80   |

## Exact Inference

:::info 
**Task 1:** Exact Inference
Compute the following probabilities by hand, include your work and results in your README.md. If you prefer, you can upload a handwritten document or a PDF generated by latex as a separate file. Include the filename in your README.md.

1. A patient receives an abnormal ECG result, but is an otherwise healthy individual (exercise=high, bloodpressure=normal, smoker=no, cholesterol=normal). What is the probability they have high heart disease risk? What is the probability they have low heart disease risk?
2. What is the conditional probability that someone at high risk for heart disease is also a smoker?
3. What is the prior probability that someone is at high risk for heart disease (with no other evidence)?
:::
:::spoiler Tips
There are multiple ways to get answers for each of these questions. You will likely need to use Marginalization, the Chain Rule, and Bayes' Rule in some form to answer these questions.
:::
## Car Diagnostics Network

The mechanics in a car garage put together the following Bayesian Network structure to help them diagnose issues in cars. It models the relationship between different components in cars. The mechanics collected data on each car that came into their shop for a year, tracking the status of each component. Now they want you to help them to answer queries about the probability of certain issues. First, you must finish constructing the Bayesian Network by building CPTs for each node based on the data. Then, you will implement methods to estimate the probability of some issue with the car given other known evidence.

```mermaid
graph TD;
    %% Root nodes (no parents)
    MainFuse["Main Fuse"]
    BatteryAge["Battery Age"]
    Alternator["Alternator"]
    Distributor["Distributor"]
    StarterMotor["Starter Motor"]
    SparkPlugs["Spark Plugs"]
    FuelSystem["Fuel System"]
    AirFilter["Air Filter"]
    
    %% Intermediate nodes
    ChargingSystem["Charging System"]
    BatteryVoltage["Battery Voltage"]
    VoltageAtPlug["Voltage at Plug"]
    StarterSystem["Starter System"]
    SparkTiming["Spark Timing"]
    SparkQuality["Spark Quality"]
    AirSystem["Air System"]
    CarCranks["Car Cranks"]
    
    %% Output nodes
    Headlights["Headlights"]
    CarStarts["Car Starts"]
    
    %% Connections
    Alternator --> ChargingSystem
    ChargingSystem --> BatteryVoltage
    BatteryAge --> BatteryVoltage
    
    BatteryVoltage --> Headlights
    BatteryVoltage --> StarterSystem
    BatteryVoltage --> VoltageAtPlug
    
    MainFuse --> StarterSystem
    MainFuse --> VoltageAtPlug
    StarterMotor --> StarterSystem
    
    StarterSystem --> CarCranks
    
    Distributor --> SparkTiming
    Distributor --> VoltageAtPlug
    
    SparkPlugs --> SparkQuality
    VoltageAtPlug --> SparkQuality
    
    AirFilter --> AirSystem
    
    %% All systems feed into Car Starts
    SparkTiming --> CarStarts
    SparkQuality --> CarStarts
    FuelSystem --> CarStarts
    AirSystem --> CarStarts
    CarCranks --> CarStarts
```

# Implementing Bayes Networks

:::info
**Task 2.1:** Constructing CPTs

Implement the `build_cpt_from_data` method in `bayesian_network.py`. This method:
- Takes a node name and pandas DataFrame as input
- Counts occurrences of each outcome in the training data
- Returns a CPT object with learned conditional probabilities

**Important: CPT Dictionary Structure**

Your CPT table must use the correct dictionary format:
- **Root nodes (no parents):** `{"Yes": 0.2, "No": 0.8}` - Simple outcome to probability mapping
- **Nodes with one parent:** `{("High",): {"Yes": 0.3, "No": 0.7}}` - Parent value tuple maps to outcome probabilities
- **Nodes with multiple parents:** `{("Yes", "High"): {"High": 0.5, "Normal": 0.5}}` - Parent combination tuple maps to outcome probabilities

**Critical:** When a node has multiple parents like `["Smoking", "Exercise"]`, the tuple must be in that exact order: `("smoking_value", "exercise_value")`.
:::

:::success
Note: The conditional probabilities in the CPT are computed using relative frequencies from the dataset. This corresponds to the maximum likelihood estimate (MLE) of the conditional distribution P(X|Pa(X)). In other words, given a fixed network structure, the CPT values are chosen to maximize the likelihood of the observed data with respect to the parameters of the network.
:::
Run ``python bayesian_network.py --network heart --dataset heart_data.csv`` and ``python bayesian_network.py --network car --dataset car_data.csv`` to print out and inspect the bayesian networks and CPTs produced by your code. Your CPTs for the heart disease network, should closely match the probabilities provided above.

:::info
**Task 2.2:** Querying CPTs

Implement the `get_probability` method in the `CPT` class of `bayesian_network.py`. This method retrieves conditional probabilities from your CPT dictionary.

**Method Signature:** `get_probability(outcome, parent_values=None)`

**Usage Examples:**
- **Root node (Smoking):** `cpt.get_probability("Yes")` --> returns P(Smoking=Yes)
- **Node with parents (BloodPressure):** `cpt.get_probability("High", {"Smoking": "Yes", "Exercise": "Low"})` → returns P(BloodPressure=High | Smoking=Yes, Exercise=Low)

**Key Requirements:**
- The `parent_values` dictionary must contain ALL parent nodes as keys
- Parent values must be converted to a tuple in the correct order to match your CPT table keys
- For the BloodPressure example above, convert `{"Smoking": "Yes", "Exercise": "Low"}` to tuple `("Yes", "Low")` based on the parents list `["Smoking", "Exercise"]`
:::

:::spoiler Hint
If you have implemented your CPT table correctly as a dictionary, `get_probability` amounts to a lookup in that dictionary. Just make sure the order you construct the key (a tuple of strings) is the same order as when the table was constructed.
:::

:::info 
**Task 2.3:** Testing
In `unit_tests.py`, we have provided tests for checking the network structure and CPTs the heart disease Bayesian Network. Test your `get_probability` method to verify that it works for a node with parents and a node without parents.
:::

### Monte Carlo Sampling

Bayesian Networks are a **generative** AI model. You may be familiar with this term (or the shortening GenAI) from other classes of models, like LLMs or image generation models, like Dalle or Midjourney. What does it mean to be a generative model? Generative models represent joint probabilities of data. In Bayesian Networks, we can query our network for the probability of any node and value given some set of evidence. Large Language Models learn to estimate the probability of the next token (e.g., next word) given context (i.e., preceding tokens). Why does learning this probability distribution relate at all to **generative**? If we have learned a probability distribution, we can sample new data from that distribution to generate new examples. A sample from a Bayesian Network is a value for each node, drawn at random from the specified (conditional) probabilities.

Sampling can provide a computationally efficient means of estimating the probabilities of queries in Bayesian Networks. Rather than exact an exact algorithm to compute the conditional probability of a query, sampling generates a number of samples and estimates the probability of a query from the samples. In this assignment you will implement **rejection sampling**. Rejection sampling works by generating $n$ samples and ignoring (rejecting) any samples generated where the evidence does not match the query.

How can we actually generate a sample? Look back at the heart disease network. What variables are easy to draw new values for? Exercise and smoking are easy to generate values for because they are root nodes (i.e., they have no parents). The values of all other nodes depend on their parents. We cannot sample new values for non-root nodes until we sample the values of their parents. We have to generate samples in a specific order, starting at the roots of the network and working our way down. This order is called the *topological order* of nodes in a graph. So long as we sort our nodes into topological order, we can simply sample new values for each node using the previously sampled values. Topological sorting can be done with DFS.

:::info
**Task 3.1: Implement Rejection Sampling**

Implement the `estimate_probability` method in `bayesian_network.py`. The method takes in a query node (e.g., "Battery Age"), query value (e.g., "Old"), and (optionally) evidence (e.g., Car Starts=False), and should return the estimated probability using rejection sampling.

**Algorithm Steps:**
1. **Generate samples:** Use prior sampling to create N complete samples
2. **Filter by evidence:** Keep only samples that match all evidence constraints  (reject other samples)
3. **Count matches:** Among valid samples, count how many have query_node = query_value
4. **Calculate probability:** Return count / total_valid_samples 
:::

:::success
**Tip:** We have provided a heart disease dataset that matches the example from the previous questions. You can test your `estimate_probability` method with the answers you found previously!
:::

:::info
**Task 3.2: Querying Bayesian Networks**

Use your `estimate_probability` method to answer the following questions:

1. What is the probability a car that comes into the shop has an engine that starts?
2. What is the probability the battery voltage is strong when we know the battery is new and the charging system is working?
3. A new car has come into the shop that won't start. The headlights are dim. When the key is turned, the engine cranks. Should the mechanics investigate the fuel system, spark plugs, or alternator first? Which is most likely to be broken given the evidence provided?

Implement your queries in the `query_network.py` script and run it to get your results. Include your results in your README.md file.
:::

:::info 
**Task 3.3: A closer look at sampling**

In the previous task, you used rejection sampling to estimate probabilities. During this process, you specified some number of samples to generate that match your provided evidence and rejected other samples.

1. Edit your estimate probability function to print how many total samples were generated (i.e., number of rejected samples + number of kept samples). Which of the queries from Task 3.2, required the highest number of total samples? Why do you think that is?
2. Try the queries from 3.2 again with different numbers of samples (`estimate_probability` takes `num_samples` as an argument). Try with 10 samples, 100, 1000, and 10,000 samples. What trends do you notice as you increase the number of samples? Do any of the queries converge faster than the others?
3. Suppose you ran your `estimate_probability` for $n$ samples. How could you know if $n$ was a large enough number of samples? How could you know if you needed to run more samples? What information would you track and how would you make that decision.

Add the answers to these questions to your README.md.
:::

:::info
**Task 3.4**
If you knew the labor cost of checking the status of the outcome of each node (e.g., checking the headlights or battery voltage is easy, but testing spark plugs takes an hour of labor), how might you could use a bayesian network to determine which component a mechanic should test next? Include 2-3 sentences on how you might incorporate labor cost into your README.md.
:::


## The Super Sliding Puzzle and PDDL

In Homework 2, you worked with the swapping tile game where tiles were arranged in a grid and you swapped adjacent tiles until the goal state was reached. That game is based on the 15-tile puzzle, which has one open cell that tiles can slide into. In this assignment, you will work on an extension of this puzzle, that goes by many names (klotski, super-slider puzzle, Huarong Dao, and many more).

![Screenshot 2025-08-19 at 10.05.46 PM](https://hackmd.io/_uploads/rynFTjfYeg.png)

### Rules of the game

The game takes place on a 4x5 board of square cells. Blocks are placed on the board at various positions. Blocks can slide up, down, left, and right **only if the cells they will move into are unoccupied by other blocks**. The goal is typically to move a 2x2 block to the bottom-center of the board. This [video](https://www.youtube.com/watch?v=YGLNyHd2w10) provides insight into the structure of the problem (it discusses our version of the puzzle at 5:20).

## Writing PDDL

There are two options available for writing PDDL and running solvers for this assignment. You can use the online editor that was demonstrated in class or you can use a PDDL extension in VSCode that adds highlighting and solvers for PDDL. In both cases, you will utilize [Planning-as-a-service](https://github.com/AI-Planning/planning-as-a-service), which provides an API to interact with PDDL solvers hosted on the cloud.

### Option 1: Planning Domains Editor

[editor.planning.domains](https://editor.planning.domains) provides an online editor and access to planners. It provides an easy way to write PDDL files and run popular solvers. You can load existing files (i.e., the files provided in the stencil) by clicking on the File menu and the load files button.

To run a solver on a PDDL problem, click the solver button on the toolbar. You must always specify the correct domain file, problem file, and a solver. Different solvers work with different variations of PDDL. For example the Temporal Fast Downward Solver works with durative actions, or actions that take some amount of time to run. Some guarantee optimality, others only find satisficing plans (i.e., suboptimal plans that satisfy the goal condition).

For this assignment, we recommend using **BFWS: Best-Frist Width Search** on editor.planning.domains. It provides support for STRIPS and all of the features of PDDL you will need. Run the solver BFWS on `hello_world_problem.pddl` and the `hello_world_domain.pddl` to test your environment. However, if you are facing problems with BFWS, feel free to use **LAMA**.

### Option 2: PDDL VSCode Plugin

Another option is to work locally in VSCode.

1. Install the PDDL extension for VSCode, which will provide syntax highlighting and other useful tools for PDDL. You can install through the extension menu in VSCode or through the [online portal](https://marketplace.visualstudio.com/items?itemName=jan-dolejsi.pddl).
2. Navigate to hello_world_problem.pddl. We will be using external planners for this assignment. To run a planner, press Alt + p (or option + p on a mac) or right click anywhere on the text and look for the "PDDL: Run the planner" option. This will bring up a list of possible solvers to use. We recommend the first option, **Delfi** for this assignment in VSCode. (BFWS, the recommended solver for the online editor does not have an endpoint set up for the VSCode plugin)
3. Running a solver should produce a chart of actions (two hello world actions to be specific). You can export the plan in plain text by clicking the three horizontal bars in the top right pane and saying export to `.plan` file.

### PDDL Tips

For more information and guidance on PDDL, you can refer to the course notes, [the planning wiki](https://planning.wiki/ref/pddl/domain), or watch a [video](https://www.youtube.com/watch?v=_NOVa4i7Us8&list=PL1Q0jeuU6XppS_r2Sa9fzVanpbXKqLsYS) guide from the author of the VSCode extension.

## Klotski PDDL

The purpose of this assignment is to practice modeling problems. There are many ways to represent this problem. We have provided starter files in each of the problem and domain files you will write that specifies the layout of the grid.

:::info
Task 4.1: Complete `domain1x1.pddl`, which should work for sliding puzzle games with only 1x1 blocks.

1. Specify the necessary types. What types of objects do you need to keep track of?
2. Specify the necessary predicates. What do you need to know about each type of object?
3. Specify the actions. Each action should be sliding a block to an adjacent cell.
:::

:::info
**Optional AI Task (Not Graded)**

The goal of the PDDL portion of this assignment is for you to practice modeling. It is challenging to provide a visualization tool to visualize the Klotski game if we don't know what your actions, objects, or predicates will be a priori.

Use an LLM tool of your choice to produce a visualization tool for your klotski game.

:::spoiler Tips for coding with LLMs
1. Provide all of the necessary information: The LLM will need the context (that you are solving klotski), and the relevant files.
2. Generate a plan of action: Before asking your LLM to solve your problem, ask it to produce a plan. Make sure you understand and approve that plan before telling the LLM to actually execute the plan. This typically reduces the number of hallucinations and aligns the model with what you actually want to accomplish.
3. Be specific in your prompts: General prompts cause the LLM to make assumptions about what you want, which may or may not be correct. Be as specific as possible when prompting LLMs. If you know what you want your visualization to look like, specify it. Do you want to visualize it with ASCII on the command line? Or with a matplotlib animation? Or do you want to make a webapp? Be specific.
4. Give detailed feedback: An LLM likely will not be able to create the visualization in one shot and will produce errors or poor visualizations. **Don't just paste the error messages** into the LLM and ask it to fix it. Read the LLM code and try to understand where it went wrong, then prompt the LLM again with specific guidelines for fixing the bug you found. If you don't understand where the bug is, ask the LLM to help explain it to you based on the error message you are receiving.
:::

If you create a visualization with an LLM, remember to attach your chat transcript link to your README.md. The major LLM providers provide a way to link a single chat (i.e., you don't just have to copy your LLM output into the README as plain text).
:::

![Screenshot 2025-09-30 at 11.24.24 PM](https://hackmd.io/_uploads/BJa8M7c3xg.png)


:::info
Task 4.2: Complete `problem1x1.pddl` using the diagram above. The objective is to move the red tile from the top left corner (1,1) to the top right corner (4,5). Four purple tiles start in the middle row, but can be anywhere at the end of the puzzle.

1. Specify the objects in the problem
2. Specify the initial conditions of the problem
3. Specify the goal condition of the problem

Use a solver to solve the PDDL problem (see above for instructions based on your platform). Save the .plan file created by the solver as `1x1.plan`.
:::

![Screenshot 2025-09-29 at 1.13.59 PM](https://hackmd.io/_uploads/r1_DR4_2le.png)


:::info
Task 4.3: Complete `domain2x2.pddl`, which should work for sliding tile games with both 1x1 blocks **and** 2x2 blocks. This domain file should add new types and/or predicates and/or actions on top of what you already completed for `domain1x1.pddl`.

Complete `problem2x2.pddl` based on the diagram above. A 2x2 block begins in the top left corner and should end in the green region (the center of the bottom two rows).

Use a solver to solve the problem. Save the output as `2x2.plan`.
:::

![Screenshot 2025-09-30 at 11.11.12 PM](https://hackmd.io/_uploads/By5g2fqhel.png)


:::info
**Task 4.4 (Extra Credit):** Complete `klotski_domain.pddl`, which will work for 1x1, 2x2, 1x2, and 2x1 blocks. 

Write `klotski_problem.pddl`, which describes the problem presented in the previous diagram. This is the example presented in 2swap's Klotski [video](https://www.youtube.com/watch?v=YGLNyHd2w10) (that took his co-worker many hours to solve). The objective, like the previous problem, is to get the 2x2 block to the center of the bottom row.

Use a solver to find a plan and save the output in `klotski.plan`.
:::


:::info
**Task 4.5**: In your README.md, answer the following questions:

1. There are other ways of solving these problems, notably, we can write a search problem implementation that matches what we did in assignment 1 and 2. What are two potential advantages that PDDL provides over creating a search problem directly in python (as you did in homeworks 1 and 2). What are some potential disadvantages of using PDDL?
 
2. We don't expect anyone to have gotten their PDDL correct on their first try. Name one bug you encountered while writing your PDDL files. How did you determine it was a problem and how did you fix it?
:::

## Submission

### Download
Please click [here](https://classroom.github.com/a/C_3vUy9u) to access the assignment.

### Handin

Your handin should contain the following:
- all files, including comments describing the logic of your implementations and tests
- a README containing:
    - a summary of your tests, explaining their outcomes
    - your responses to any conceptual questions 
    - known problems in your code
    - anyone you worked with
    - any outside resources used (eg. Stack Overflow, ChatGPT)


### Gradescope

Submit your assignment via Gradescope.

To submit through GitHub, follow this sequence of commands:
1. `git add -A`
2. `git commit -m "commit message"`
3. `git push`

Now, you are ready to upload your repo to Gradescope.

:::danger 
**⚠️WARNING⚠️** Make sure you have the correct assignment repo and branch selected before submitting. 
:::

*Tip*: If you are having difficulties submitting through GitHub, you may submit by zipping up your hw folder.


### Grading

Your code for Bayesian Networks will be graded on correctness. For PDDL, because we do not specify the actions you must implement, we cannot reliably autograde your submissions and will rely more heavily on manual grading.


### Rubric

| Component | Points | Notes |
| -------- | -------- | -------- |
| Exact Inference  | 20     | Points awarded for answers and work shown in README for task 1. (5 points each)|
| CPTs      |  15    | Points awarded for proper structure of Conditional Probability Tables and |
| Approximate Inference | 25 | Points awarded for correct implementation of rejection sampling and ability to query bayesian network with evidence. |
| Klotski 1x1 |   15   | Points awarded for correctness of submitted problem and domain files, as well as plan output.|
| Klotski 2x2     | 15  | Points awarded for correctness of submitted problem and domain files, as well as plan output.|
| PDDL Conceptual Questions| 10 | Points awarded for including answers in README. |
| Klotski Extra Credit  | 10 | Points awarded for adding 1x2 and 2x1 blocks into PDDL Domain and solving the provided puzzle.|